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.

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

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.

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.

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

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 ?

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.