Sign in to follow this  
Sneftel

Triangulation-based pathfinding library - coming soon!

Recommended Posts

Sneftel    1788
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?

Share this post


Link to post
Share on other sites
mfawcett    373
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]

Share this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
Sneftel    1788
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]

Share this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
wodinoneeye    1689
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.



Share this post


Link to post
Share on other sites
Choff    122
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

Share this post


Link to post
Share on other sites
Sneftel    1788
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.

Share this post


Link to post
Share on other sites
Steadtler    220
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.

Share this post


Link to post
Share on other sites
Symphonic    313
Sneftel, I might implement Delaunay for you, please PM me and we'll discuss your requirements, I'm familiar with TRIANGLE and I'm confident I can reproduce his performance, though he does some smart stuff with floating point dirt that I don't know how to do.

Also, see this thread as it discusses the problem you're solving and there are some important problems with EXACT path-finding over any triangulation which are illumined.

As you might guess from my participation in that thread, I would like to take part in this project, and I will happily comply with your licensing ideals.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Steadtler
About your second question, what would be the advantage or TRA* over A* with a simplified polygonal navmesh?

The technique is similar to nav-meshes in a lot of ways. Nav-meshes don't scale particularly well, though, and in certain cases can produce some very bad-looking paths (even with string-pulling).

Share this post


Link to post
Share on other sites
Extrarius    1412
I only skimmed the paper, and it looks fairly straightforward, but how well can it handle non-euclidian geometry?

For example, instead of having a static world of triangles, what if there were 'rooms' with 'doors' that would be linked in globally-impossible ways. For example, 3 square rooms with doors only in the middle of the walls could form a triangle, or doors on the opposite side of a room can be linked so that going in one means coming out the other. Basically, each door can be between any 2 parts of any 2 rooms to form a graph that doesn't have a simple 3d layout.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Extrarius
I only skimmed the paper, and it looks fairly straightforward, but how well can it handle non-euclidian geometry?

For example, instead of having a static world of triangles, what if there were 'rooms' with 'doors' that would be linked in globally-impossible ways. For example, 3 square rooms with doors only in the middle of the walls could form a triangle, or doors on the opposite side of a room can be linked so that going in one means coming out the other. Basically, each door can be between any 2 parts of any 2 rooms to form a graph that doesn't have a simple 3d layout.

The only difference would be that a euclidean 2-norm heuristic might not be admissible. Basically, no different from standard navmesh or grid approaches. As long as you had a linear mapping from positions on the in-door to positions on the out-door, the rest would be simple.

Share this post


Link to post
Share on other sites
Sneftel    1788
This is coming along fairly well. If anyone's interested, you can check out a compileable version with SVN from http://twang.svn.sourceforge.net/svnroot/twang/tags/0.1/.

Share this post


Link to post
Share on other sites
serg3d    100
Quote:
Original post by Sneftel
This is coming along fairly well. If anyone's interested, you can check out a compileable version with SVN from http://twang.svn.sourceforge.net/svnroot/twang/tags/0.1/.


How about adding VC6 project file ?

Share this post


Link to post
Share on other sites
jbadams    25676
Quote:
Original post by serg3d
Quote:
Original post by Sneftel
This is coming along fairly well. If anyone's interested, you can check out a compileable version with SVN from http://twang.svn.sourceforge.net/svnroot/twang/tags/0.1/.
How about adding VC6 project file ?
Why would he want to support an IDE that's so ridiculously out of date when people can get an updated version for free? VC6 is old, buggy and no longer supported, it'd be much more productive for you to update than for Sneftel to try to support it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this