A Maze A Day

2009-03-23 - Solution

2009-03-23T23:59:00.000-07:00

2009-03-23

2009-03-23T05:00:00.000-07:00

This is a weave maze built with a recursive back tracker alogirthm, rendered with a block pattern. I find the weave mazes to be very pretty and slightly more complicated to solve.

2009-03-22 - Solution

2009-03-22T23:59:00.000-07:00

Knowing Your Enterance And Exit

2009-03-22T20:17:00.000-07:00

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.

2009-03-22

2009-03-22T10:18:00.000-07:00

This site advertises "A Free Daily Online Maze Every Day", however I have been negligent for the last couple of days. Here is a braid maze that I constructed. It is difficult, however I am not particularly proud of it, I would like to construct one with only a single solution path:

Size: 39 x 39
Dead ends: 0
Passages: 1327
Forks: 172
Cross Roads: 20
Decisions: 212
Branches: 99
Corners: 785

Solving - Dead End Filling

2009-03-18T19:26:00.000-07:00

Here is a YouTube video of a maze solving technique called dead end filling.

Basically you find all the dead ends and fill them, working backwards down the passages that leads to the dead ends till you reach a junction. If filling the maze leads to a junction that is a dead end you fill that junction and continue backfilling. Keep doing this until all passsages lead to a dead end are filled. What is left (not filled) is the solution path

Braid Mazes - And Their Corners

2009-03-18T07:50:00.000-07:00

Braid mazes sometimes called purely multiply connected maze, refers to a maze without any dead ends. In an orthogonal mazes (a maze made up of a square cell with four sided) this means that there are no cells with three sides.

Let's consider the corners of an orthogonal maze. Each corner by default has two sides (unless one of the sides is an exit or and entrance). Which means that the other two sides can not have a wall (hedge) in a braid maze. In other words, the cell in the upper left corner of the maze (Northwest) already has two walls, one to the north and one to the west. Adding a wall on the east or the south would create a dead end.

If we have a orthogonal braid maze without any rooms (vertexes without touching walls) the corners are always passages.

In an orthogonal braid maze where is the best place to put the exit (if this is an outside to outside solution)? If you put the exit in the corners, then you will have one of two scenarios:

1) There will be two solutions paths to the exit, since the corner has to be a passage, both sides of the corner cell could be a path to the solution.

2) There will be one solution path to the corner, and one will be a branch (non-solution path). This is probably the worst scenario of the two, since the solver will never take the non-solution path when they are at the exit. Which means that the branch is wasted space. By wasted I mean, not adding to the complexity of the puzzle.

In conclusion: if you are creating a orthogonal braid maze (no dead ends) and want to have a single solution path without wasted space the exit should not be in a corner.

2009-03-16 - Solution

2009-03-16T23:59:00.000-07:00

Design Your Own Maze

2009-03-16T07:36:00.001-07:00

I think this web site is very good for explaining the fundementals of creating a maze. Their good use of graphics and explainations really help me get started.

Link: Design Your Own Maze

2009-03-16

2009-03-16T05:00:00.000-07:00

A better Island generation.

Type: Spanning Tree Algorithm / Simply-Connected Maze / Island
Size: 39 x 39
Dead ends: 451
Passages: 668
Forks: 345
Cross Roads: 55
Decisions: 455
Correct Decisions: 102
Branches: 120
Corners: 427
Solution Length: 244

2009-03-15 - Solution

2009-03-15T23:59:00.000-07:00

Dead Ends

2009-03-15T19:51:00.000-07:00

In an Orthogonal maze a dead end is a cell where three of the four walls are present. The solver can not continue when a dead end is reached, they most go back the way they came.

There are no dead ends on the solution path. The solution path consists of only: passages (cells with two opposite walls), corners (cells with two wall that touch), forks (cells with 1 wall) and crossroads (cells with no walls). If the solver runs into a dead end they know they have gone down the wrong path.

Mazes without dead ends are called braid mazes or purely multiply connected Maze. Braid mazes are harder to solve then simply-connected Maze -- because it is harder to figure out when you are lost. With simply-connected mazes you will know you have gone down the wrong path when you hit a dead end.

It is analogous to driving down a dead end street. If you reach the end of the street and you are not at your destination, you know that you have gone the wrong way.

2009-03-15

2009-03-15T05:00:00.000-07:00

Type: Spanning Tree Algorithm / Simply-Connected Maze / Island
Size: 31 x 31
Deadends: 295
Passages: 397
Branches: 233
Cross Roads: 33
Decisions: 299
Correct Decisions: 87
Corners: 243
Solution Length: 179

2009-03-14 - Solution

2009-03-14T23:59:00.000-07:00

Amazed By The Maze

2009-03-14T12:01:00.000-07:00

If you are looking for more artistic mazes try: maze-of-the-moment. Hats off to people with artistic talent.

Maze Ranking - Part I

2009-03-14T06:54:00.000-07:00

One of my goals is to be able to generate 500 mazes and find the hardest one. In order to do this I need to be able to "tell" the computer how to determine which maze is the hardest. I am attempting to do this by ranking the mazes based on statistics and analysis that I can program.

In the beginning I was inclined to think that the maze with the longest solution should be the maze with the highest rank. Since the user would have "solve" more. This is not the case. I have generated a pseduo pictorial example to demostrate the flaw in this thinking:

Type: Experimental / Longest Maze
Size: 19 x 19
Deadends: 0
Passages: 359
Forks: 0
Cross Roads: 0
Decisions: 0
Correct Decisions: 0
Branches: 0
Corners: 36
Solution Length: 360

Notice that this is the longest maze I can generate in this space. I hard-coded it to appear this way, however enough iterations of the recursive back tracker algorithm would generate this eventually.

The maze isn't particually tough. In fact generations of mazes with long solution paths tend to have very little "non-solution" paths which means there isn't oppurtunity to get lost -- just like the maze above. In fact the hardest mazes give the user many oppurtunities to get lost.

2009-03-14

2009-03-14T05:00:00.000-07:00

Type: Spanning Tree Algorithm / Simply-Connected Maze / Island
Size: 31 x 31
Deadends: 285
Passages: 431
Branches: 201
Cross Roads: 41
Decisions: 283
Correct Decisions: 109
Corners: 270
Solution Length: 202

2009-03-13 - Solution

2009-03-13T23:59:00.000-07:00

Think Labyrinth

2009-03-13T19:57:00.001-07:00

From the very beginning I have been pouring over the writings of Walter D. Pullen of Think Labyrinth. Especially the Algorithms page. I haven't downloaded his code yet -- however his descriptions have been very informative, in fact it is probably the biggest repository of algorithms I have found on the Internet.

Recursive Division Part II

2009-03-13T19:46:00.000-07:00

Based on Walter Pullen's comment on my recursice division alogorithm I read his simplified approach at Think Labyrinth and implemented a second recursive division solution.

The algorithm works like this: using an orthogonal mazes, divide the area either vertically or horizontally at a random position. Then place a door in a random location in the division just created. The division will create two subsections of the original area. Repeat the process on the subsections if they are bigger then a single cell in height or width. If the subsection is wider then taller, divide vertically. If the subsection is taller then wider, divide horizontally, otherwise for a square subsection make a random choice between horizontal or vertical.

Here is an animated gif I created of this algorithm running:

Orthogonal Mazes

2009-03-13T07:39:00.000-07:00

Orthogonal mazes consists of square cells with four walls (hedges) in a square or rectangular maze. Each of the wall may be removed to create different exits from the cell. In a simply connected (perfect maze) where all the cells are reachable by definition each cells can have zero through three hedges, however no cell can have four hedges.

This leads to four basic constructions of the cells:

Dead End - a cell with three hedges (4 orientations)
Passage - a cell with two hedges (6 orientations). Passages can be divided into two types, straight corridor (2 orientations) and corners (4 orientations).
Fork - a cell with one hedge (4 orientations). Each fork presents a decision to the solver.
Cross Roads - a cell with no hedges. Each fork presents a decision to the solver, with two choices. (1 orientation)

{6230289B-5BEE-409e-932A-2F01FA407A92}

2009-03-13

2009-03-13T05:00:00.000-07:00

This is a new algorithm that creates a island maze, using the recurisve tracker algorithm. Find your way from the outside enterance to center (island).

Type: Recursive Back Tracker / Simply Connected Maze / Island
Size: 31 x 31
Deadends: 95
Passages: 770
Branches: 92
Cross Roads: 2
Decisions: 96
Correct Decisions: 30
Corners: 473
Solution Length: 352

Statistics

2009-03-12T21:30:00.000-07:00

Different algorithms produce different ratios of the statistics and different generations of the same algorithms produce mazes with varying statistics. I hope to be able to use the statistics for the maze to rank each mazes difficulty. Ranking would allow me to generate 500 mazes and choose the most difficult one from the 500.

Correct Decisions

2009-03-12T21:19:00.000-07:00

When posting a maze I also am posting statistics with the maze. Correct decisions refers to the number of correct choice the solver must make to reach the exit. To few correct decisions there is not enough opportunity to leave the path. Too many (on a simply connected maze) and all the branches are very short.

Short branches mean that the solver doesn't stray very long before encountering a dead-end.

Branches refer to any path that branches from the solution path and doesn't lead to the solution. It doesn't refer to forks in the branches (sub branches of the branch).

Correct decisions do not equal branches. Here is why: Anytime a solver reaches a fork there is one correct decision (the solution path) and one wrong decision (the branch). Every time the solver reaches a crossroad (a cell without any hedges) there is one correction decision (the solution path) and two wrong decisions (two branches).

MazeBlog - Myles

2009-03-12T12:23:00.000-07:00

I was reading Myles maze blog here: http://mazeblog.com/ and was very interested in his thoughts on how to draw mazes . Good ideas obivously gained from usability studies.