Thanks in advance!
-=-=---
Sirmanson@yahoo.com
Pathing Theory
Author
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
Thanks in advance!
-=-=---
Sirmanson@yahoo.com
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
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
Author
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
Thanks for the help!
-=-=---
Sirmanson@yahoo.com
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
