Hi, we are developing a 3D "game" of sorts that relies heavily on pathfinding (i.e. finding the shortest route between point A and point B on the surface of our terrain geometry). In 2D this is an easy problem, but the 3D terrain in question is extremely varied and intricate. One approach I found by reading posted messages on the web is to create a list of spheres over the entire terrain and link them in a logical order (i.e. to get to specific coordinate in sphere Z from coordinates in sphere X, proceed through spheres X->Y->Z then move to specified coordinates in Z.) While efficient (or so they say), the set up is a hassle (thousands of spheres, drawn and linked by hand). Another approach was to break down everything into a standard 2D array, but the arrays would be so large as to be completely unmanageable. Anyway, my question is: Has anyone tried to do accurate 3D pathfinding? Could you send some ideas my way please? Guy Volckaert, Ing. email: guy_volckaert@simtran.ca or guyvolck@altavista.com

quote: Original post by IceWizard

Hi, we are developing a 3D "game" of sorts that relies heavily
on pathfinding (i.e. finding the shortest route between point A and point B on the surface of our terrain geometry). In 2D this is an easy problem, but the 3D terrain in question is extremely varied and intricate.

One approach I found by reading posted messages on the web is to create a list of spheres over the entire terrain and link them in a logical order (i.e. to get to specific coordinate in sphere Z from coordinates in sphere X, proceed through spheres X->Y->Z then move to specified coordinates in Z.) While efficient (or so they say), the set up is a hassle (thousands of spheres, drawn and linked by hand).

Another approach was to break down everything into a standard 2D array, but the arrays would be so large as to be completely unmanageable.

Anyway, my question is: Has anyone tried to do accurate 3D pathfinding?

Could you send some ideas my way please?

Guy Volckaert, Ing.
email: guy_volckaert@simtran.ca
or guyvolck@altavista.com

Laying down a node mesh over the 3D terrain, and then using an Astar derivitive algorithm to find a path through the mesh, has been a popular choice for 3D pathfinding. The granularity of the node mesh can vary as needed by the terrain specifics, without effecting the performance of the Astar. Also, as the terrain deforms (if applicable) the node mesh can be updated without too much hassle.

I''ve also used Craig Reynold''s Steering Behaviors to enable an NPC to navigate a crowded 3D world. It looks like pretty natural movement (like his flocking), but does not always find the shortest path.

Good Luck,

Eric

When you say "Laying down a node mesh over the 3D terrain,...", do you mean laying a 2D map over the terrain or a Quad-Tree.

I''ve already experimented the Astar algo and it seem to work well for small terrains. My test shows approx 0.08ms (milliseconds) per cell iteration on a Pentium II 266Mhz. For example to move from one corner of my 20x20 map to the other take approx 20*0.08ms = 1.6ms. It''s not too bad for small terrains, but I need something that will support at least 1000x1000 (maybe even 5000x5000).

I was also thinking about using a list of objects that defines the obstructions and using a collision detection algo (but it gave me a headache after a while).

Thanks for help,

Best regards,




Guy

quote: Original post by IceWizard

When you say "Laying down a node mesh over the 3D terrain,...", do you mean laying a 2D map over the terrain or a Quad-Tree.

It does not have to be 2D. In my usage (in a FPS game), the node mesh was 3D and it worked out quiet nicely.

quote:
I''ve already experimented the Astar algo and it seem to work well for small terrains. My test shows approx 0.08ms (milliseconds) per cell iteration on a Pentium II 266Mhz. For example to move from one corner of my 20x20 map to the other take approx 20*0.08ms = 1.6ms. It''s not too bad for small terrains, but I need something that will support at least 1000x1000 (maybe even 5000x5000).

H''mm, that sounds a bit slow for a 20x20 map. I was using maps that were 1024x1024 in 2D in another game (an RTS) and getting 40 step paths found in 2-3 ms with pretty dirty terrain (ie, lots of variance and obstacles). You may want to make sure your Astar is really optimized. There are some ideas for exactly that, in the Game Programming Gems book mentioned in another thread.

quote:
I was also thinking about using a list of objects that defines the obstructions and using a collision detection algo (but it gave me a headache after a while).

Of course I don''t really know how you planned to implement this, but from what I can think of, this does not really help in path finding, just collision avoidance. In the Steering Behavior reference I mentioned previously, one does maintain a list of the obstacles and has the NPC "steer" around them (ie. avoids). This tends to produce natural-looking behavior, but the NPC does not always end up on the shortest path (due to the avoidance effect).

Good Luck,

Eric