• Post Reply Bookmark Topic Watch Topic
  • New Topic
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:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Maze Building Algorithm Help

 
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.



 
Bartender
Posts: 3323
86
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
It is difficult to free fools from the chains they revere - Voltaire. tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic