Started by Sep 13 2007 03:42 AM

,
16 replies to this topic

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?

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]

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]

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.

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.

Posted 13 September 2007 - 03:41 PM

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:Thanks... I'd seen CGAL, but as I said, I don't want an encumbered license.

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

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

Posted 13 September 2007 - 10:00 PM

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.

Posted 16 September 2007 - 12:48 PM

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.

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

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

Posted 17 September 2007 - 08:34 AM

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.

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.

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

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.

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.

Posted 17 September 2007 - 11:56 AM

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

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.

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.

Posted 23 September 2007 - 04:06 AM

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.

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

Posted 05 October 2007 - 11:55 PM

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 ?

Posted 07 October 2007 - 09:15 PM

Quote: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.

Original post by serg3dQuote:How about adding VC6 project file ?

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