Voronoi graph pathfinding (concept exploration and sources)

[msafwan]

Voronoi graph is a set of vertex/line in between 2 point/dots. If there're many dots, then Voronoi graph will create a set of lines that never collide with any dots. This is true even for randomly positioned dots.

Visual example:


If we store list of Voronoi vertexes in a table (as coordinate), we can find a sequence of coordinates that plot a unit trajectory to target without colliding with any dots.

Lets say we use open-source/free library to produce Voronoi vertexes. We then use the vertexes as a path-space for our standard pathfinding algorithm. The advantage of the vertexes compared to regular map's path-space is: a featureless/empty area is automatically discarded, thus greatly increasing efficiency.

Simply a working Voronoi graph demo in opengl & C++ (with source)
The theories

Disclaimer: These source code and demo are only for producing Voronoi vertexes, I do not have any sources to demonstrate pathfinding concept. Although this article do hint that Red Alert 3 use such pathfinding.

[Anarchid]

My two cents:

QTPFS already pretty much does that, except that it uses a square grid.
It also discards empty space and such, and requires much less cycles to be wasted because you can binary-tree search it.



There seem to be two problems with QTPFS that prevent its massive adoption by Spring game projects:

1) Massive memory footprint. Allegedly, half of that can be relatively easily optimized away for great justice.

2) Command latency. Each time an unit is ordered to go somewhere, it seems to compute the path on-the-fly instead of using some cached approximation like in Legacy. This results in weird cases like quickly clicking move commands actually causes the unit to sit in place.

Simply adding a heuristic to act upon while path is being computed would likely do this problem completely away. Even if that heuristic is simply "go in a straight line towards goal", that would already be a massive improvement.

Both those problems are low hanging fruit that a novice could try fixing for massive kudos at low investment.

[Silentwings]

As far as I can see, the link you have given is nothing more than to a (standard) algorithm for computing Voronoi tesselations.

You should try to explain why and how you think Voronoi tesselations contributes to a good/efficient pathfinding algorithm compared to the current ones.

Your vague suggestion above - as I understood it "follow the edges of the Voronoi graph between points in some way" leads to very indirect paths between points. E.g. turning huge number of corners (and consequently travelling very slowly) when moving through a densely tiled region. Trying to mitigate this by tiling sparsely in regularly travelled regions would lead to clumping.

As I understand it (and I'm no expert here), Spring already has a mechanism using nested regular square lattices where cpu is not wasted on calculating paths through 'empty' areas - you can even see it in action by pressing alt+p.

QTPFS: ... a novice could try fixing for massive kudos at low investment.

I suspect it's not going to be that easy.

[msafwan]

QTFS .... nested regular square lattices

QTFS uses boxes while Voronoi graph use triangle. I learn from web lecture here that triangle is one of fundamental shape in nature, not boxes. So I think it should be more efficient. (why use box when there is triangle? triangle have 3 fork to search, while box have 4. Also, legacy pathfinder use triangle and is still more efficient, so could box be the culprit?)

I can't really argue more since I have never tried it before.

E.g. turning huge number of corners

Probably someone can just code them to make unit skip the edges, but I can't really say how.

Unit deviate from path is not unprecedented. Spring unit always deviate from pathfinding each time it about to collide, which doesn't seems to cause ill effect. Same can be done to make it skip long edges IMHO.

[Anarchid]

I suspect it's not going to be that easy.

I never said that dwarves with Novice C++ Programmer skills are easy to come by heheh.

triangle is one of fundamental shape in nature

Triangle is merely the minimal polygon. But you can't tree search those easily.
Especially because a triangulated voronoi graph is not a *regular* triangle grid.
Also defining any two-dimensional shape as "fundamental in nature" is lol.

[Silentwings]

Voronoi graph use triangle

Whatever "fundamental shape in nature" is supposed to mean, and whether or not it has anything to do with pathfinding, you can see in your picture that a Voronoi tesslation consists of much more than triangles. If you want a lattice of triangles you could use the dual graph of the Voronoi tesselation; http://en.wikipedia.org/wiki/Delaunay_triangulation (maybe you already meant this).

why use box when we can use triangle? triangle have 3 fork to search thru, while box have 4

I would guess the point here is regularity of the lattice structure rather than the number of side of the segments. Springs pathfinding systems use a square lattice with crosspieces - 8 eges per vertex. As said, reducing this numbers means either less direct paths or more corners (although I think you are right that it would be broadly speaking more efficient).

[Anarchid]

Also, legacy pathfinder use triangle and is still more efficient, so could box be the culprit?)

Nope.

[Silentwings]

Also, legacy pathfinder use triangle and is still more efficient, so could box be the culprit?)

I think it uses square lattices with crosspieces.

[AF]

Voronoi stuff would be very useful in the spring AIs, and I dont say that from a pathfinding point of view

[msafwan]

I agree with AF,

I hope Spring dev include the Voronoi graph sourcecode into Spring and add interface to LUA that allow you to input list of coordinate/points and output list of vertexes.

Currently I want to try it for a widget but have problem translating the C++ and complex algorithm into LUA.

[Anarchid]

I hope Spring dev include the Voronoi graph sourcecode into Spring and add interface to LUA that allow you to input list of coordinate/points and output list of vertexes.

Currently I want to try it for a widget but have problem translating the C++ and complex algorithm into LUA.

https://github.com/interstellarDAVE/iVoronoi

[zwzsg]

Last year I coded some Voronoi library in Lua too:
http://pastebin.com/TJcWdMQW

My version might not be very well coded (I remember there was stuff to optimize, and division by zero if points happen to be aligned), and not even do what you want: I just wanted to create the Voronoi of random points in a wraparound 2d area.

Interestingly, just like the link Anarchid posted, I used Löve2D for the drawing as well. (I could add the main and other source if needed).

[smoth]

Reads like you read a solution you liked and want to apply it to a problem.

[msafwan]

Anarchid, zwzsg thanks!

I want to try a widget that can help "read" the battlefield condition using different tool (cluster detection and voronoi area) and somehow process it to (probably) increase player awereness. It might not work, so having these readily available code is really helpful so I can focus more on trying stuff.