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

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

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