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. Choose a cell from C, and carve a passage to any unvisited neighbor of that cell, adding that neighbor to C as well.Let C be a list of cells, initially empty.Another trivial change, and you can generate mazes with attributes of both. Configured another, it works almost exactly like Prim’s algorithm. Configured one way, it mimics the behavior of the Recursive Backtracking algorithm. My new favorite is the Growing Tree algorithm. Remember way back in the first article of this series, where I said that Recursive Backtracking was my favorite for generating mazes? Well, I changed my mind.
0 kommentar(er)
