Monday, March 23, 2009
2009-03-23
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.
Sunday, March 22, 2009
Knowing Your Enterance And Exit
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.
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
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
Size: 39 x 39
Dead ends: 0
Passages: 1327
Forks: 172
Cross Roads: 20
Decisions: 212
Branches: 99
Corners: 785
Wednesday, March 18, 2009
Solving - Dead End Filling
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
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
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.
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.
Monday, March 16, 2009
Design Your Own Maze
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
Link: Design Your Own Maze
2009-03-16
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
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
Sunday, March 15, 2009
Dead Ends
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.
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
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
Saturday, March 14, 2009
Amazed By The Maze
If you are looking for more artistic mazes try: maze-of-the-moment. Hats off to people with artistic talent.
Maze Ranking - Part I
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.
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
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
Friday, March 13, 2009
Think Labyrinth
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
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:
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
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}
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
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
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
Thursday, March 12, 2009
Statistics
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
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).
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
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.
Tuesday, March 10, 2009
2009-03-10
There is something about a really long recursive division maze that gets your eyes "lost" in traversing the corridors. Click on the maze to get a bigger version.
Type: Recursive Division Algorithm / Simply-Connected Maze
Size: 19 x 51
Deadends: 188
Passages: 601
Branches: 168
Cross Roads: 10
Decisions: 188
Correct Decisions: 65
Corners: 112
Solution Length: 235
Type: Recursive Division Algorithm / Simply-Connected Maze
Size: 19 x 51
Deadends: 188
Passages: 601
Branches: 168
Cross Roads: 10
Decisions: 188
Correct Decisions: 65
Corners: 112
Solution Length: 235
Monday, March 9, 2009
Recursive Division
"Another simple algorithm for rectangular mazes, recursive division, works as follows. Begin with a rectangular space with no walls. Call this a chamber. Build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. Continuing in this manner recursively, until every chamber has a width of one cell in either of the two directions, one can easily generate interesting mazes that avoid the ease of solution of binary tree mazes." - Wikipedia
http://en.wikipedia.org/wiki/Maze_generation_algorithm
I took the quote from Wikipedia, however I generated the animated gif to share the process. I have developed animation for all the algorithms and solvers I am working on, it helps me think about the problems.
http://en.wikipedia.org/wiki/Maze_generation_algorithm
I took the quote from Wikipedia, however I generated the animated gif to share the process. I have developed animation for all the algorithms and solvers I am working on, it helps me think about the problems.
Sunday, March 8, 2009
Removing Dead Ends
In a simple connected maze (also called a perfect maze) there is one solution path and every cell on the maze can be reached. Every path besides the solution ends in a dead end. In other words the way you can tell you are not headed to the solution is that you come to a dead end. Which means you need to backtrack to the next branch and choose another path.
To make a multiply connected maze (also called a braid maze) you need to remove the dead ends. I wrote a dead end remover that works like this:
1) Find the solution path.
2) From the solution path find all the branches off the solution, and mark all the cells with the branch number that they are on. This can be seen below as the number in the cell. The number is the branch number.
3) Iterate over the whole grid (yellow cursor) looking for dead ends.
4) If a dead end is encountered then remove the opposite wall as the entrance to the dead end cell.
5) If the remove of that wall leads two branches to be connected seal one of the entrances to the solution path and merge both branches.
6) Do not remove walls that remove the dead end, but open the branch to the solution path.
This algorithm leads to several things:
1) There is still only one solution path.
2) There is only one way to enter a branch from the solution path.
3) It is harder to figure out that you are down the wrong path, since you are less likely to encounter a dead-end.
However, the algorithm fails in a number of ways:
1) The solution path has lots of passages and few branches making it visual stand out from the maze.
2) The branches appear like Swiss cheese and are not hard to get lost in.
Saturday, March 7, 2009
2009-03-07
This maze is created with a new algorithm that walks the maze. It is high on passages, and low on dead-ends. Which means that the solution length is very long. Hopefully modifications to this algorithm will lead to a braided maze.
Type: MazeLibrary.Algorithm.Walker
Size: 29 x 29
Deadends: 88
Passages: 665
Branches: 82
Cross Roads: 4
Decisions: 90
Correct Decisions: 31
Corners: 398
Solution Length: 355
Type: MazeLibrary.Algorithm.Walker
Size: 29 x 29
Deadends: 88
Passages: 665
Branches: 82
Cross Roads: 4
Decisions: 90
Correct Decisions: 31
Corners: 398
Solution Length: 355
Friday, March 6, 2009
2009-03-06
Using a recursive division algorithm, which leads to interesting, but not challenging mazes.
Type: Recursive Division Algorithm / Simply-Connected Maze
Size: 31 x 41
Deadends: 278
Passages: 736
Branches: 232
Cross Roads: 23
Decisions: 278
Correct Decisions: 267
Corners: 207
Solution Length: 239
Type: Recursive Division Algorithm / Simply-Connected Maze
Size: 31 x 41
Deadends: 278
Passages: 736
Branches: 232
Cross Roads: 23
Decisions: 278
Correct Decisions: 267
Corners: 207
Solution Length: 239
Thursday, March 5, 2009
2009-03-05
This is the last of the block render, tommorrow I will have a line rendering.
Size: 27 x 27
Deadends: 213
Passages: 325
Branches: 165
Cross Roads: 24
Decisions: 213
Correct Decisions: 145
Corners: 208
Solution Length: 151
Size: 27 x 27
Deadends: 213
Passages: 325
Branches: 165
Cross Roads: 24
Decisions: 213
Correct Decisions: 145
Corners: 208
Solution Length: 151
Wednesday, March 4, 2009
2009-03-04
I had a slight error in caculating the correct decisions required to solve the maze. I have solved this issue and ranked this one as tough out of 200. You will find this one is more difficult then yesterdays.
Size: 27 x 27
Dead ends: 226
Passages: 302
Branches: 172
Cross Roads: 27
Decisions: 226
Correct Decisions: 119
Corners: 196
Solution Length: 132
Please comment with the time it took you to solve it and your age.
Size: 27 x 27
Dead ends: 226
Passages: 302
Branches: 172
Cross Roads: 27
Decisions: 226
Correct Decisions: 119
Corners: 196
Solution Length: 132
Please comment with the time it took you to solve it and your age.
Tuesday, March 3, 2009
2009-03-03
Yesterday's maze was much larger at 40x40 then today's maze (29x29). I am attempting to generate a harder maze in less space. It is easy to generate this type of maze, however it is more challenging given 500 mazes to pick the hardest one with a computer.
In order to solve this maze you need to make 212 correct decisions, by limiting the number of choices, I theorize that the wrong paths will be longer. This is because all cells are either choices, dead ends, or passages. Longer paths (more passages) make it more difficult to discover you are down the wrong path.
In comparison yesterday you had to make 1.19 choices per length. Today's solution requires that you only have 1.01 choices per length. Which should make it harder.
Size: 29 x 29
Dead ends: 243
Passages: 384
Branches: 187
Cross Roads: 27
Decisions: 455
Correct Decisions: 212
Corners: 244
Solution Length: 215
Please comment with the time it took you and your age.
In order to solve this maze you need to make 212 correct decisions, by limiting the number of choices, I theorize that the wrong paths will be longer. This is because all cells are either choices, dead ends, or passages. Longer paths (more passages) make it more difficult to discover you are down the wrong path.
In comparison yesterday you had to make 1.19 choices per length. Today's solution requires that you only have 1.01 choices per length. Which should make it harder.
Size: 29 x 29
Dead ends: 243
Passages: 384
Branches: 187
Cross Roads: 27
Decisions: 455
Correct Decisions: 212
Corners: 244
Solution Length: 215
Please comment with the time it took you and your age.
Monday, March 2, 2009
2009-03-02
This is the best of 500, computational time: 2 hours.
Statistics:
Size: 40x40
DeadEnds: 479
Passages: 706
Branches: 353
Cross Roads: 62
Decisions: 892
Corners: 447
Solution Length: 347
Please comment with the time it took you to complete the maze and your age.
Sunday, March 1, 2009
2009-03-01
Size: 20 x 20
Deadends: 117
Passages: 183
Branches: 85
Cross Roads: 15
Decisions: 215
Corners: 123
Solution Length: 138
Please comment on the amount of time it takes you to solve the maze and your age.
Subscribe to:
Posts (Atom)
Posts
