When I create a perfect maze (also called a simply-connected maze), I render the whole maze with one of the algorithms I have implemented then I find the entrance and exit with the longest solution path. The way I do this is to move the entrance and exit around the outside of the maze at different locations and "solve" the maze, checking the solution length. When I find the location of the entrance and exit that create the longest solution path I am done creating the maze.
However, finding the entrance and exit to the maze after creating it will not work when creating a braid maze (also called a purely multiply connected maze). With a braid maze there are no dead-ends, which means that all cells in an orthogonal braid maze have at 0, 1, or 2 hedges. The entrance counts as a missing hedge, which means when generating the maze I need to take into consideration the entrance, since that missing hedge on the outside allows the algorithm to add another hedge to that entrance cell. The same with the exit.
Which leaves me with the question, where is the best place to put the entrance and exit in a orthogonal braid maze.
Sunday, March 22, 2009
Subscribe to:
Post Comments (Atom)
Posts
You don't need to take into account the entrance/exit location while making a braid Maze. You can if you want to, since it might allow you to add one more hedge that wouldn't be possible if the entrance weren't there. However removing a hedge to reposition an entrance won't ever make the Maze non-braid, since it only decreases the hedge count. In other words, first create a braid Maze with zero entrances. Then you can apply your perfect Maze entrance positioning algorithm and choose whatever entrance/exit locations result in the longest solution path. :)
ReplyDeleteThis is a counter intuitive to the comment you posted about the braid corners here. If the alogirthm doesn't know where the enterance is at, you might end up with wasted space if the enterance or exit ends up in a corner.
ReplyDeleteIndeed, wanting to avoid wasted space (earlier comment) and wanting to reposition the entrance and exit (this comment) are different issues. However you can have the best of both worlds, if you only consider those entrance locations that allow you to then add a new hedge that wasn't possible before. Such locations tend to be corner cells (not necessarily corners of the Maze) that are next to a junction on the boundary wall. Adding the hedge turns your corner cell into a long passage going straight out the entrance (as mentioned in earlier comment) and the junction into a corner (so it's still a braid Maze). :)
ReplyDelete