Jump to content
  • Advertisement

Archived

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

nikha

pathfinding in 3D

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!