Personally, I love the flexibility of this algorithm. Try it out and see what new cell selection methods you discover! Conclusion Some possible implementations of the choose_index method might be: 1 2 3 4 5 6ĭef choose_index(ceil) return ceil -1 if choose_newest? return 0 if choose_oldest? return rand(ceil) if choose_random? # or implement your own! end Grid |= dir grid |= OPPOSITE cells << index = nil breakĪnd that’s really all there is to it. When a valid, unvisited neighbor is located, we carve a passage between the current cell and that neighbor, add the neighbor to the list, set index to nil (to indicate that an unvisited neighbor was found), and then break out of the innermost loop. X, y = rand(width), rand(height) cells = 0 & ny >= 0 & nx < width & ny < height & grid = 0 #.
It starts by selecting a random cell and adding it to the list: 1 2
Maze generator algorithm c# code#
In fact, in my own implementation, the most complex part came from code that I added that lets you specify the cell-selection method when the script is executed! Implementation-wise, this is one of the simplest algorithms (another reason to love it!). Choose a few different ones and compare how they behave. Instead, you can play with the following demo, which has presets for several different cell-selection methods. I’ve already told you it would behave like Prim’s algorithm in this case, but can you see why? I hope so, because I’m not going to draw any more diagrams tonight. Take a moment and think about how the algorithm would change if, instead of choosing the newest cell each time, we chose one at random. At that point, the list of cells will be empty, and the algorithm will terminate. And it will continue to choose identically to the backtracker, clear up until every cell has been visited and it has to “backtrack” all the way back to the original cell. It wasn’t intentionally backtracking it just happened that the algorithm’s choice of cell was the same one that the backtracking algorithm would have chosen. This time, that’s #8, and sure enough, there is an unvisited adjacent cell that we can move to: Then the algorithm goes around again, grabbing the newest cell from the list. Alas, there isn’t one! So cell #9 is voted off the island removed from the list: Here we are now, six iterations further along, and we’ve hit a dead-end at cell #9.Īt this point, the algorithm would select the newest cell (#9), and then try to find an unvisited neighbor cell.
Let’s fast forward a bit and see what the behavior is. But how does the algorithm behave when the passage cannot be extended any further? See the pattern? By always choosing the cell most recently added to the list, each subsequent step simply extends the passage one more step, effectively doing a random walk. Let’s do it again, once more choosing the newest cell from the list: Next step: we choose the newest cell from the list, randomly select one of its unvisited neighbors, carve a path to it, and add the neighbor to the list: Also, cells in red are in the list of “live” cells they’ll go white once they’ve been removed from the list. We mark the cell as “in” I’m also going to assign the cell a number, visually, to help keep track of the relative age of each cell. The algorithm begins by adding an arbitrary cell to the list. I’ll demonstrate the “choose newest” cell selection method, which will hopefully be enlightening enough that you can imagine on your own how the “choose random” method might proceed. It’s remarkably fun to experiment with other ways to choose cells from C. If you always choose a cell at random, you get Prim’s. If you always choose the newest cell (the one most recently added), you’ll get the recursive backtracker. But the fun lies in how you choose the cells from C, in step #2.
If there are no unvisited neighbors, remove the cell from C.
0 kommentar(er)
