Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
16 replies to this topic

#1 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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?

Sponsor:

#2 mfawcett   Members   -  Reputation: 372

Like
0Likes
Like

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]

#3 0BZEN   Crossbones+   -  Reputation: 2013

Like
0Likes
Like

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.

#4 ToohrVyk   Members   -  Reputation: 1591

Like
0Likes
Like

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.


#5 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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:
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]

#6 0BZEN   Crossbones+   -  Reputation: 2013

Like
0Likes
Like

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.


#7 wodinoneeye   Members   -  Reputation: 738

Like
0Likes
Like

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.





#8 Choff   Members   -  Reputation: 122

Like
0Likes
Like

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

#9 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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.

#10 Steadtler   Members   -  Reputation: 220

Like
0Likes
Like

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.

#11 Symphonic   Members   -  Reputation: 313

Like
0Likes
Like

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

#12 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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

#13 Extrarius   Members   -  Reputation: 1412

Like
0Likes
Like

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.

#14 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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.

#15 Sneftel   Senior Moderators   -  Reputation: 1776

Like
0Likes
Like

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

#16 serg3d   Members   -  Reputation: 100

Like
0Likes
Like

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 ?

#17 jbadams   Senior Staff   -  Reputation: 17912

Like
0Likes
Like

Posted 07 October 2007 - 09:15 PM

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.




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.



PARTNERS