#### Archived

This topic is now archived and is closed to further replies.

# pathfinding in 3D

This topic is 6226 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
you might wanna check out my path editor (java app)

http://www.geocities.com/bpj1138/path_editor_2_1_2001.zip

--bart

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633702
• Total Posts
3013450
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!