Archived

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

Pathing Theory

This topic is 5650 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

I am working on a game and am trying to come up with a good way to setup a decent pathing table for it. Map Info ---- Very simple. 5000 points randomly placed on a 10,000 x 10,000 grid. Each point can have from 1 to 4 connections to other nearby points. I''ve looked at a number of solutions that use a pre-created pathing table, but this solution (a 250,000,000 record table that stores the shortest path from each point http://www.gamedev.net/reference/programming/features/fastpathfinding/) is not feasable. It seems to me that calculating path for each move would be taxing on the server in this situation. I haven''t actually started implementing this, I''m just trying to solicit some ideas from the pros! Thanks in advance! -=-=--- Sirmanson@yahoo.com

Share this post


Link to post
Share on other sites
Sounds like you''re looking to find a path through a maze!

I don''t think that you want to consider a pathing table as suggested in the article unless the start and goal nodes are fixed at compile time... in which case you haven''t got a problem nor a need to store a table.

Assuming that you want to compute paths online (during gameplay) then you need to consider a fast and efficient pathfinding algorithm. Many people favour A* in such situations due to its optimally efficient form of tree search, however, since you have a search tree with a potential depth of 5000 nodes and a worst case branching factor of 4, then any form of tree search is going to be costly.

An alternative would be to use the Distance Transform algorithm. It requires a connectivity map (a data structure indicating which nodes are connected to which other nodes) and then is fairly easy to implement. I posted some psuedo-code for this algorithm recently in this thread.

Good luck with whatever you choose,

Timkin

Share this post


Link to post
Share on other sites
Actually I already have a connections table that stores a from and to sector for each of the connections, along with the length of the connection (used for cost). I just read your previous post and it looks like that may do it. I''ll fiddle with it
Thanks for the help!

-=-=---
Sirmanson@yahoo.com

Share this post


Link to post
Share on other sites