Voronoi graph - traversing from vertex to vertex

Question

I'm working on a Unity Project in C#

I've built a 3D Voronoi Diagram using the csDelaunay library from PouletFrit and using the X and Y values from a 2D diagram to instead setup some Vector3's with something like (x,0,y)

Example:

My current task is to build a river, as a List of Vector3's

I've so far been able to figure out most of the library code, and build/retrieve lists of:

• The north-most Vertices, South-most, East and West
• All Edges, and for each their left vertex (green) and right end vertex (red)
• All Sites / Seeds

To start the river I've picked one vertex at random from the North-most list and then pick a suitable opposing vertex on the south list.

I've been at this for many hours now, getting nowhere really, but I think my main problem is I can't focus. So I'm going to avoid splines, meshes, etc. for now and keep this simple, I just want to get a list of points the river will go through.

as advised by 'Arcane Engineer' on a previous question (too broad), I'll just use the Voronoi cell boundaries for this, but I need to find the shortest or best path between my north river point and my south point.

I've been assuming that either Dijkstra's Algorithm or A* are the best way to do this but I'm really struggling now, and A* seems to be more built for open space and determining the route around obstacles, rather than shortest path through fixed nodes ?

as Dijkstra's would need a graph data structure (among other things), would I be correct in saying that The Voronoi class in the library I'm using is already a type of graph data structure ? or would I need to augment it a bit to perform Dijksta's algorithm

My background is mainly in Java, and I hope I have a decent understanding of all the OOP principles I need here, and I have some data structure knowledge, at least at a high level. but if possible i'd like to use pre-written stuff. I found a Priority Queue class from Microsoft that may help me in implementing Dijkstra's ?

I tried working on a "simpler" recursive algorithm that checks from the first point (north-most), what edges are connected, and then what direction vector they are going in and compares the angles for each edge vs the target direction, and the smallest angle wins. I haven't got it working yet. But I also get the feeling this is NOT the best way to do this.

Any advice you could give is much appreciated!

Answer 1

A* also requires a graph. It can be applied to discretized open spaces, but that just means imposing some sort of graph over the open space.

For example, imagine a grid over your open space. You are allowed to move along the lines of the grid. The intersections are the nodes. each line has a default cost of 1. Now, wherever there's an impassable obstacle on the map, remove those nodes & their associated lines. Next, if you some areas that can be moved through with greater difficulty (slow terrain, etc), increase the cost of the lines that cross those accordingly.

That's the basics of how A* (or most any other path finding algorithm) deals with open space. there's still a lot of details for real world use. Huge graphs need hierarchies in order to be performant. Graph based robot path planning may need a different discretization method.

There's an example of applying A* to a graph on wikipedia.

As a general rule, I try avoid heavily recursive code. Recursive problem solving is fine & anything that can be done with recursion can be done with a stack instead. I find iterative easier to debug & reason about. It's also tends to have fewer performance penalties.

Unless you're actual intended data set is order of magnitude bigger, or you need to repeatedly resolve the problem in near-real time, either A* or Dijkstra's will work for this problem. If you're feeling overwhelmed, I suggest Dijkstra's - while it tends to be slower, it's simpler. Also, once you have it working, it's easier to leverage what you know to write up an A* replacement.

A priority queue helps the performance of Dijkstra's. Since most languages have one built in somewhere, start with that. They're likely to be more robust, have fewer bugs & perform better than anything you cook up. Presumably, you want to develop a game first & foremost, not abstract high performance data structures. If you game needs performance improvements, find the problems when the arise by profiling.

That being said, you might want to brush up on your data structures, especially graphs. I've yet to find a premade graph class that isn't overly complex in an attempt to be super generic or overly adapted to someone else's problem.

Answer 2

In the end, my particular requirements meant that moving towards a custom algorithm based on angles gave me more control over river directions and potential meanders in the end. As wondra explained above, I don't actually need the absolute optimal path, just something that looks like a river. So I went with the recursive approach as the amount of stack space required will be reasonably low, and I will profile this later for performance if required.