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)
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!