"Spanning Tree" algorithm
Posted: Tue Jul 08, 2003 4:42 pm
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?
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?