Win a copy of Rust Web Development this week in the Other Languages forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Paul Clapham
Saloon Keepers:
• Tim Holloway
• Tim Moores
• Jesse Silverman
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Frits Walraven

# Maze Building Algorithm Help

Ranch Hand
Posts: 76
• Number of slices to send:
Optional 'thank-you' note:
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.

Bartender
Posts: 3323
86
• 1
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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.

 You showed up just in time for the waffles! And this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton