This week's book giveaway is in the Other Languages forum.We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Maze Building Algorithm Help

William Koch
Ranch Hand
Posts: 76
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.

Tony Docherty
Bartender
Posts: 2989
59
• 1
I need help with an algorithm.

Get a pencil, some paper and draw out a small grid. Now select a start cell and work your way through the grid following the rules you've been given writing down all the decisions you make as you go.

William Koch
Ranch Hand
Posts: 76
I am stuck... for example I know that if I am in a room on the edge of the maze I do not want to open up the wall on the edge. I also need to figure out a way to make sure the wall I open will not create a loop in the maze.