Does anyone know a good way to partition the space for pathfiding in a 3D-environment? We are developing a 3D action/simulator game, much like LucasArts'' Rogue Squadron, where ships fly close to the ground. Now we have come to the problem of pathfinding. We''re planning to use A* for the search but don''t know a good way to represent the world graph as it is in 3D. Any comments or suggestions appreciated. /Niklas and Henrik

There''s a way to calculate weights for BSP nodes; I don''t know what it is, but it could be useful.

Another idea might be this: If you only have to pathfind over terrain (a uniform grid?), then weight each cell according to the difference between the altitude of the highest of the four surrounding verteces and that of the lowest.

i''ve done that for a project for the university, my method was not the BEST, but it worked pretty nice and maybe it can be usefull to you.
The idea is that you have a group of "navpoints" this is points beyond all the level, and they are visible through each other; i mean, from any navpoint you can see at least one navpoint, so you make a net of navpoints. the other thing is that you must see from ANY part of the level at least one navpoint. so, if you want to go from any place to another, you look for the closest navpoint from where you are, and the closest navpoint for the place you want to go, there you "enter the navpoint net" and resolve it with any shortest-path algorithm (a*, dijkstra, floyd, whatever) and when you reach your last navpoint you can go directly to that point, it worked nice, even faster than the engine''s pathfinding algorithm (using a* and bsp mix). you can download the code from http://www.fly3d.com.br/download/firefly.exe. the other thing is DON''T USE STL for representing the list of navpoints, i don''t know why (i think because of the size of the structure) but it slow it a lot. Greets and i hope i was useful.

Thanks a lot for your replies!

The navpoint method seems nice, it''s like the "get on the freeway" analogy. Our worlds are VERY large though, so automatic creation of the navpoints is almost a necessity.

How has this solved in your project?

Another question (with newbie warning): In what way can BSP be used in pathfinding?

All I know about BSP is that it''s used in scene-traversal algoritms.

/nikha

we made the navpoints by ourselves, we didn''t make any program to "make navpoints" i think that would be a very hard task and at least for our demostration it wasn''t worth the effort.

for the bsp question, you may have the level divided in portals and use a* on them, ask on the fly3d engine''s page because they use something like that for their engine.