It's not a secret anymore!
The moose likes Java in General and the fly likes Maze Building Algorithm Help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of OCA Java SE 8 Programmer I Study Guide this week in the OCAJP 8 forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Maze Building Algorithm Help" Watch "Maze Building Algorithm Help" New topic

Maze Building Algorithm Help

William Koch
Ranch Hand

Joined: Sep 26, 2012
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.

Thanks for all your help.

Tony Docherty

Joined: Aug 07, 2007
Posts: 2737
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

Joined: Sep 26, 2012
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.
I agree. Here's the link:
subject: Maze Building Algorithm Help
It's not a secret anymore!