I am thinking of making a try on creating an efficient implementation of 3D pathfinding for games. I mean full general 3D and velocity dependent constrained turn radius. I am fully aware that it is a difficult problem. A* is at best a trivial part of a solution. Do you know of any implementations/partial implementations? Do you have an idea on how to solve it? Do you have a godd reason why I should give it up immediately? All thoughts appreciated!

There are two types of 3D pathfinding problems (IMHO): those that can be reduced to 2D and those that cannot. An example of the former variety is moving through a multistory building, or around a level with elevated areas. Some careful design of the pathfinding implementation can reduce such problems to 2D.

True 3D pathfinding is computationally very expensive, particularly in environments with continuous location variables (like air/space/marine environments). However, many of the 2D pathfinding algorithms can be directly extrapolated to 3D; the only drawback, that the search cost suffers and exponential increase.

If you want an example of an implementation of 3D pathfinding to an airborne environment, check out:

Williams, M. and Jones, D., "A Rapid Method for Planning Path in Three Dimensions for a Small Aerial Robot", Robotica, 19, 2001. pp125-135.

I''ve previously implemented A* in 3 dimensions for an aerial domain via discretisation of the action space, however I wouldn''t recommend it... even on current processors search takes an unreasonably long time if you need fast online planning.

It''s a tough problem and there really aren''t many ways to make it easier, other than constraints on the domain or the action space.

Good luck,

Timkin

Thank you for the reference! The way they build their neighbour lists in an octtree was interesting. I am interested in all such publications but haven''t found much.

I am talking about true 3D. Maybe it still is too tough, maybe not. There are many more opportunities to cheat in a game than there is for a real world robot. The key is likely to be an efficient representation of configuration space.

quote:

---

Original post by Decay
The key is likely to be an efficient representation of configuration space.

---

Hehehe... that''s always the key!

Relic recently released the Homeworld (1) source code.

it may not be the best place to learn the concept, but it should provide a decent view of an acutal implementation of pathfinding in a true 3D world. (albeit a fairly sparse one).
it can be downloaded from the relic developers network


http://www.relic.com/rdn/
(free registration required).

Good tip! Thank you!