That document just explains the theory, u don't actually do a c_trace to determine a path between two points. I've talked about that before in this thread.

In detail, I've used a method explained in this site and looks a bit like this:



What you do is, simulate the NPC actually walking along the path, using c_traces with use_box of course. If there's an obstacle, you try again a bit higher to simulate the NPC's ability to climb, and if there's a gap below, more c_traces are used to drop the virtual 'npc' on the ground. The NPC's actual forward movement in pixels is used as well as it's MinMoveZ value(climb ability), to give accurate results.



Of course, a less accurate simulated walk is made in runtime checks for links. Runtime checks include:

Npc-->Target Point (check for direct link, to avoid engaging pathfinding)
Npc-->Closest Waypoint(find nearest point to pathfind from)
Target Point-->Closest Waypoint(same here)
String pulling:Npc-->2nd Waypoint(Try to eliminate 1st waypoint)
String pulling:2nd to last-->Target Point(Try to eliminate last waypoint)

Every other Waypoint in the path is pre-checked and pre-optimized(no string pulling) using Dijkstra on a pre-compiled automatically generated graph.


For these 5 functions, an optimized and more lose version of the simulated walk costs about 1000 microseconds on my machine (2.4ghz, 512mb, ati radeon 7500 mobility). So all 5 of them for each Pathfind take 5000 microseconds plus 10000ms to do Dijkstra in a huge level with about 250 waypoints(the bigger the search space the slower the algorithm). 15000ms is a pretty good speed and moves 30 NPCs simutaneously with no problems in my machine..

Here's a String Pulling example



The Npc has already made it to the Target Spot. The original path generated is illustrated with the thick red line(Red Waypoint-->Blue Waypoint-->Target Point).

Before attempting to move on path, it tried to do some StringPulling and remove the blue waypoint altogether. So a check for the link between the Red Waypoint and the Target Point was attempted. You can see the simulated walk drawn in the blue lines, making step by step and dropping to the ground every step. At some point it fell down the bridge, kept going on the ground below and collided with the gray box(if you observe you see an additional blue line a little higher also colliding to the gray box which is an extra raised attempt to check if the obstacle is climbable(it wasn't, it's a really tall gray box). So the String Pulling is discarded and the original path was taken(or the Npc would fall off the bridge)

I hope I made some sense...

The Wikipedia link you sent me was about NavMeshes and is a whole different thing. NavMeshes are by far superior to my approach(Points of Visibility). I made a go on NavMeshes some time ago, in co-operation with Dr. Scott Goodwin from CIDER, for an implementation on GameStudio, but it proved very hard. (Support for terrains and model-only levels would be overwhelmingly hard). Maybe some time in the future, I could give it another go. If you or anyone else is interested in helping in this, send me a PM, it would be a nice experience.


Btw, the contribution is ready. I'll get some sleep and then write some documentation and upload it when I wake up.

Cheers,
Aris