View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Triangulation-based pathfinding library - coming soon!

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

16 replies to this topic

### #1Sneftel  Senior Moderators

Posted 13 September 2007 - 03:42 AM

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?

### #2mfawcett  Members

Posted 13 September 2007 - 07:01 AM

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]

### #30BZEN  Members

Posted 13 September 2007 - 09:38 AM

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.

### #4ToohrVyk  Members

Posted 13 September 2007 - 09:55 AM

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.

### #5Sneftel  Senior Moderators

Posted 13 September 2007 - 03:41 PM

Quote:
 as for libraries and samples :http://www.cs.cornell.edu/Info/People/chew/Delaunay.htmland 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]

### #60BZEN  Members

Posted 13 September 2007 - 10:00 PM

Quote:
 Original post by SneftelWhich 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.

### #7wodinoneeye  Members

Posted 16 September 2007 - 12:48 PM

Quote:
 Original post by SneftelI'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.

### #8Choff  Members

Posted 17 September 2007 - 08:30 AM

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

### #9Sneftel  Senior Moderators

Posted 17 September 2007 - 08:34 AM

Quote:
 Original post by Choffwhat 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.

Posted 17 September 2007 - 10:07 AM

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.

### #11Symphonic  Members

Posted 17 September 2007 - 11:36 AM

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.
Geordi
George D. Filiotis

### #12Sneftel  Senior Moderators

Posted 17 September 2007 - 11:56 AM

Quote:
 Original post by SteadtlerAbout 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).

### #13Extrarius  Members

Posted 22 September 2007 - 08:39 AM

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.

### #14Sneftel  Senior Moderators

Posted 23 September 2007 - 04:06 AM

Quote:
 Original post by ExtrariusI 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.

### #15Sneftel  Senior Moderators

Posted 01 October 2007 - 06:01 AM

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/.

### #16serg3d  Members

Posted 05 October 2007 - 11:55 PM

Quote:
 Original post by SneftelThis 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 ?

### #17jbadams  Senior Staff

Posted 07 October 2007 - 09:15 PM

Quote:
Original post by serg3d
Quote:
 Original post by SneftelThis 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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.