I'm planning on implementing the TRA* algorithm for continuous (i.e. not necessarily grid-based) pathfinding in 2D space, as described in this paper. As usual, I'll be releasing it for free. I'd like to release it under a fully unencumbered license, but I have yet to find a good, robust C or C++ library for performing Delaunay triangulations which is compatible with that goal. The best one I've found is Triangle, but that doesn't permit commercial use. So, two questions. 1. Does anyone know of a good, robust, actually free (no (L)GPL) library for Delaunay triangulations? 2. Would a triangulation-based pathfinding library, capable of solving paths in less than a hundredth of the time of grid-based algorithms, be useful to anyone, and if so what features would be essential?

1. Can't help, sorry

2. Absolutely. Some things that would be interesting to me are:

Can the triangle graph be built incrementally as the search progresses? I deal with pathfinding over huge areas in small increments (e.g. across the Atlantic Ocean, underwater, ~1 nautical mile based grid cell) and I can't create the graph ahead of time due to memory constraints.

Could this possibly be extended to 3D? Regular A* approaches can, and I've toyed with a homemade approach very similar to the one the paper describes that works in 3D. 2D pathfinding is nice, but ultimately, for me, full 3D capabilities are required.

The customization points that I think you should offer are:
- Cost to travel to next node
- Heuristic to goal
- "Map cost" at location

As an example, imagine a pathfinding algorithm to be used for jets. There is a cost for climbing and diving (1.5 times more expensive to climb than to stay level in terms of fuel, and 1.2 times more to dive), so there needs to be a customization point in calculating cost to travel to next node.

Custom heuristic for Manhattan distance vs euclidean, vs geodesic, etc...

Custom map cost function. Normally it's a lookup into a cost table, but sometimes they need to be calculated on the fly. Using the jet example, certain areas would cost more if they fell within a radar range and the cost would be calculated using the distance to the radar, the terrain being flown over, and the angle of the aircraft in relation to the radar site.

[Edited by - mfawcett on September 13, 2007 1:01:53 PM]

Delaunay triangulation is fairly dynamic. There are algorithms to add nodes to the graph and update the graph. It would probably require a bit more than just trianglulation.

I knew a guy who did research on large scale crowds to populate a virtual city. He used a similar system. Delaunay triangulation was used for the agents iirc, and he used a hierarchical convex map of polygons for the A* algorythm (organise the triangles into convex pieces), on top of the trianglulation. There was some nice properties with it, but I can't recall exactly what they were.

as for libraries and samples :

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

and more straight from the wiki.

CGAL works under multiple licenses: you can use it under LGPL or QPL for free, and you can also use it commercially with a separate license.

Quote: as for libraries and samples :

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

and more straight from the wiki.

Which wiki are you talking about?

Quote: CGAL works under multiple licenses: you can use it under LGPL or QPL for free, and you can also use it commercially with a separate license..

Thanks... I'd seen CGAL, but as I said, I don't want an encumbered license.

[Edited by - Sneftel on September 14, 2007 12:41:04 AM]

Quote: Original post by Sneftel
Which wiki are you talking about?

First google entry. :)

http://en.wikipedia.org/wiki/Delaunay_triangulation

Qhull apparently does some work with delaunay (and Voronoi diagrams obvisouly). Might be a bit too specific.

Quote: Original post by Sneftel
I'm planning on implementing the TRA* algorithm for continuous (i.e. not necessarily grid-based) pathfinding in 2D space, as described in this paper. As usual, I'll be releasing it for free. I'd like to release it under a fully unencumbered license, but I have yet to find a good, robust C or C++ library for performing Delaunay triangulations which is compatible with that goal. The best one I've found is Triangle, but that doesn't permit commercial use.

So, two questions.

1. Does anyone know of a good, robust, actually free (no (L)GPL) library for Delaunay triangulations?

2. Would a triangulation-based pathfinding library, capable of solving paths in less than a hundredth of the time of grid-based algorithms, be useful to anyone, and if so what features would be essential?

The speed up would be from node network simplification and thus would depend on whether the triangulation network would be significantly shrunk from its grid competitor. The grid with its regular adjacentcy pattern and fixed coordinate system also offers some ability for optimization that the triangulation cant have.

You would need to see how many small triangles are generated for the typical terrain map (which might have numerous internal obstacles -- consider a classic maze pattern for how many there can be). That would have to be compared against
the grid for a particular granularity required for the game situation.

what about 3d space... you think this could be modified for 3d pathfinding?

I'm building a space sim and I am looking for a more robust pathfinding method...

Keep in mind I know nothing of Triangulation-based pathfinding so please excuse me if my questions seem dense

Quote: Original post by Choff
what about 3d space... you think this could be modified for 3d pathfinding?

Very, very unlikely. 3D pathfinding is an entirely different problem, and these techniques would not be directly applicable without an explosion in complexity.

About your second question, what would be the advantage or TRA* over A* with a simplified polygonal navmesh?

The cited paper seems to compare it with grid-based techniques, which is a bit silly in my opinion.