posted 11 years ago
I need help with an algorithm. Essentially there will be a grid of x by y dimensions and the algorithm needs to work for any side. A maze is described like this:
Our mazes will be rectangular grids like the one above. Each square of the grid is called a room. A room begins with walls on all four sides, but some walls can be opened to allow passage from room to room.
Mazes like these have two fundamental properties. First, the rooms are all connected. This means that you can get from any room to any other room. Put another way, no areas of the maze are completely blocked off from each other. (Whether the entire maze is completely blocked off from the outside world, as it is in the picture above, doesn't matter.)
The second fundamental property of mazes is that there are no loops. A loop occurs when you can start in some room and follow a path that eventually comes back to the same room without passing through any intermediate room twice. (We only consider paths containing two or more intermediate rooms, so starting in one room, taking one step into a neighboring room, and then immediately jumping back into the first room doesn't count as a loop.)
Together, these two properties ensure that, between any two rooms, there exists one and only one path that does not double back on itself.
By the time my method is run, the maze will already be initialized with a new maze object that begins with no open walls. Because every room is blocked off from every other room, the initial maze is not yet legal by the definitions above. Your method must gradually open walls throughout the maze until all rooms are connected, but without creating any loops along the way.
More specifically,
There is a room, called the start room, at coordinates maze.getStartX() and maze.getStartY().
A room is considered an insider if it is reachable from the start room. Otherwise, it is considered a wannabe. At the beginning, when all walls are present, the start room itself is the only insider. (Note that these categories of insider and wannabe are conceptual—they are useful for understanding the algorithm, but do not necessarily exist in your code.)
At each step of the algorithm, you will open a wall between an insider and a wannabe, converting that wannabe into an insider. (How to choose which wall? For now, think of that choice as completely arbitrary, as long as it is between an insider and a wannabe, as opposed to between two insiders or two wannabes or an exterior wall.)
The algorithm ends when all rooms are insiders.
Thanks for all your help.