Hey All, I've been scratching my head on this problem for some time and searching to my heart's content hasn't really lead me to any valuable resources. Hoping someone out there reading this will.
I'm designing a game in which the user will be travelling around on a theoretical grid of numbers. Each square--or ahem--sector of the grid is assigned a number (1-whatever), and in order to "navigate" around the grid, each sector is 'linked' to 5-10 other sectors at random. Of course, all of this is stored in a database.
The whole first part is already complete, and works wonderfully. Now, I'm trying to devise a way for the user to search for a path to a sector that is not linked from the one he or she is currently in.
Talking to a few other developers, it's pretty much guaranteed that I need a form of the spanning-tree algorithm to do this. However, I'm pretty much lost at how to attack this with php. I've gotten a few ways to work, but they're either very slow (it's a given, I suppose...) or very sloppy. I figure there's an elegant way to do this and it's just not smacking me on the face.
Any ideas?
"Spanning Tree" algorithm
Moderator: General Moderators
Have you checked out an algorithm books? Knuth's Art of Programming Vol 3 (Searching and Sorting) would be good or CLRS's Introduction to Algorithms or, even Winton's Intro AI book, all cover different types of search and spanning algorithms.
In your application, do the links between sectors have associated distances? Is it possible to bound the total distance between two arbitrary grid cells?
In your application, do the links between sectors have associated distances? Is it possible to bound the total distance between two arbitrary grid cells?
I haven't yet; but I'm nearly to that point. I have found seveal algorithm examples on the web, but they're mostily theoretical in nature and show next to nothing in actually applying it to any programatic language. I really just need a rough draft of how something would be applied (in php) to get off and running with it.nielsene wrote:Have you checked out an algorithm books? Knuth's Art of Programming Vol 3 (Searching and Sorting) would be good or CLRS's Introduction to Algorithms or, even Winton's Intro AI book, all cover different types of search and spanning algorithms.
Not really. In a similar game, they accomplish this by creating a delta within which ever sector is guaranteed to be a certain amount of cells away from the original. The problem I found with this approach is that every generation of the game is identical as far as layout is concerned.nielsene wrote:In your application, do the links between sectors have associated distances? Is it possible to bound the total distance between two arbitrary grid cells?
The only limiter which I'm planning to use is how many levels deep the user can delve through links before he'll run out of chances to find his or her target. This too would be variable, based upon what level the player has gotten to in the game.
Hmm that means that the better search algorithms (A* or Branch and Bound) won't work in your case as they require the ability to estimate the worst case distance.
Spanning tree algorithms, however, are likely be overkill, I think. I suspect a breadth-first search, removing cycles, will likely be best with your limited-fanout random connection data. This also makes sense if you're going to impose a maximum deapth of search.
So what I would do:
1) Keep track of visited nodes in a a $vistited list
2) Keep track of possible paths in a $path list
On each loop, pick the first possible path, and check if you've reached the target. If you haven't and you haven't reached the maximum deapth, create a new set of paths, by appending each exit node that DOESN'T appear in the $visited list to current possible path. Add the new paths to the end of the possible path list.. And keep looping...
Spanning tree algorithms, however, are likely be overkill, I think. I suspect a breadth-first search, removing cycles, will likely be best with your limited-fanout random connection data. This also makes sense if you're going to impose a maximum deapth of search.
So what I would do:
1) Keep track of visited nodes in a a $vistited list
2) Keep track of possible paths in a $path list
On each loop, pick the first possible path, and check if you've reached the target. If you haven't and you haven't reached the maximum deapth, create a new set of paths, by appending each exit node that DOESN'T appear in the $visited list to current possible path. Add the new paths to the end of the possible path list.. And keep looping...