Difference between revisions of "Brain Maze"

From Noah.org
Jump to: navigation, search
m (Simplified Brain Maze)
 
(32 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
[[Category:Free_Software]]
 
[[Category:Free_Software]]
 
[[Category:Python]]
 
[[Category:Python]]
 +
This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze.
  
This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze. This version also generates HTML.
+
In this version I also added HTML output. When I came up with the algorithm there were fewer than 1000 web sites -- it wasn't popular yet. My original C source has this comment explaining the limit to the number of recursive iterations that could be done:
 +
<pre>
 +
/* Six is the max value that seems to work on a 640K DOS machine */
 +
</pre>
 +
Nowadays, my Apple Mac Mini with a dual core 1 GHz CPU can run the interpreted Python version in less than 400 ms when set for 6 iterations. It can do 10 iterations in under 2 minutes producing an output of 2047 columns by 2047 rows, taking 4 MB of ASCII text (XPM format). This is easily converted to PNG. You may click on the following link to view the maze: [[Media:big_maze.png]]
  
This generates a random maze with no loops. It is a [http://en.wikipedia.org/wiki/Spanning_tree_%28mathematics%29 spanning tree] -- a connected, undirected graph that uses all the vertices in a graph with no cycles.
+
This generates a random maze with no loops. It is a Lattice Graph [http://en.wikipedia.org/wiki/Spanning_tree_%28mathematics%29 spanning tree] -- ''a connected, undirected graph that uses all the vertices in a graph with no cycles''. This program will also optionally "solve" the maze. That means it will show you two points that are as far apart as possible. The corresponds to the diameter of the tree. There may be more than one path that has a length equal to the longest path length. The full path is not shown. Only the beginning and end points are shown... This is a very slow calculation.
  
You can run the brain maze algorithm by clicking here: [http://www.noah.org/cgi-bin/brainmaze.py brainmaze.py]
+
You can run the brain maze algorithm by clicking here: [http://www.noah.org/cgi-bin/brainmaze.py Generate a Brainmaze]
  
 
<table border="0" cellpadding="0" cellspacing="0">
 
<table border="0" cellpadding="0" cellspacing="0">
Line 14: Line 19:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 29: Line 34:
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ff0000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
+
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#00ff00"></td>
+
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
+
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 62: Line 67:
 
</tr>
 
</tr>
 
<tr>
 
<tr>
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 73: Line 76:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
</tr>
 
</tr>
Line 98: Line 103:
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 105: Line 109:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
Line 116: Line 121:
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 126: Line 131:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
+
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 142: Line 147:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
</tr>
 
</tr>
 
<tr>
 
<tr>
Line 150: Line 155:
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ff0000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 164: Line 169:
 
</tr>
 
</tr>
 
<tr>
 
<tr>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 170: Line 174:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 200: Line 205:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 207: Line 214:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 216: Line 221:
 
<tr>
 
<tr>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 226: Line 231:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 238: Line 242:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
Line 243: Line 248:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 +
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
</tr>
 
</tr>
Line 255: Line 260:
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#00ff00"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
Line 262: Line 267:
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
<td  width="9" height="9" bgcolor="#ffffff"></td>
+
<td  width="9" height="9" bgcolor="#000000"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
<td  width="9" height="9" bgcolor="#ffffff"></td>
 
</tr>
 
</tr>
 
</table>
 
</table>
  
Click here to download: [http://www.noah.org/downloadsvn.php?src=file:///home/svn/src/python/brainmaze.py brainmaze.py]
+
The mazes generated by this algorithm are made up of the following maze '''atoms'''. This is the number of trees in a 2x2 Grid Tree.
<include svncat src="file:///home/svn/src/python/brainmaze.py" highlight="python" />
+
 
 +
<pre>
 +
    # #    ###    ###    ###    # #    ###
 +
    # #    # #      #    #      ###    #
 +
    ###    # #    ###    ###    # #    ###
 +
</pre>
 +
 
 +
This can be simplified by removing rotated copies to these two maze atoms:
 +
 
 +
<pre>
 +
    ###    # #
 +
    # #    ###
 +
    # #    # #
 +
</pre>
 +
 
 +
Click here to download: [http://www.noah.org/engineering/src/python/brainmaze.py brainmaze.py]
 +
<include src="/home/noahspurrier/noah.org/engineering/src/python/brainmaze.py" highlight="python" />
 +
 
 +
= Simplified Brain Maze =
 +
 
 +
This removes the middle connectors to give only the following atoms:
 +
<pre>
 +
### ### # # ###
 +
  # # # # # #
 +
### # # ### ###
 +
</pre>
 +
 
 +
Connect 3 at any of the four corners.
 +
<pre>
 +
### ###
 +
  # # #
 +
##* * #
 +
 
 +
# * *##
 +
# # #
 +
### ###
 +
</pre>
 +
<pre>
 +
### ###
 +
  # # #
 +
##*-* #
 +
  | |
 +
# *-*##
 +
# # #
 +
### ###
 +
</pre>
 +
 
 +
<pre>
 +
### ### ### ###
 +
  # # #  # # #
 +
##*-* # ##*-* #
 +
  | |    | |
 +
# *-*## # *-*##
 +
# # #  # # #
 +
### ##*-*## ###
 +
      | |
 +
### ##*-*## ###
 +
  # # #  # # #
 +
##*-* # ##*-* #
 +
  | |    | |
 +
# *-*## # *-*##
 +
# # #  # # #
 +
### ### ### ###
 +
</pre>

Latest revision as of 13:47, 30 May 2017

This is a fractal algorithm I created for generating mazes. I think it's pretty neat. The original was written in C for a computer science class I was taking at UCSC. This version is in Python. The original would print spaces and hashes (#) to display the maze.

In this version I also added HTML output. When I came up with the algorithm there were fewer than 1000 web sites -- it wasn't popular yet. My original C source has this comment explaining the limit to the number of recursive iterations that could be done:

/* Six is the max value that seems to work on a 640K DOS machine */

Nowadays, my Apple Mac Mini with a dual core 1 GHz CPU can run the interpreted Python version in less than 400 ms when set for 6 iterations. It can do 10 iterations in under 2 minutes producing an output of 2047 columns by 2047 rows, taking 4 MB of ASCII text (XPM format). This is easily converted to PNG. You may click on the following link to view the maze: Media:big_maze.png

This generates a random maze with no loops. It is a Lattice Graph spanning tree -- a connected, undirected graph that uses all the vertices in a graph with no cycles. This program will also optionally "solve" the maze. That means it will show you two points that are as far apart as possible. The corresponds to the diameter of the tree. There may be more than one path that has a length equal to the longest path length. The full path is not shown. Only the beginning and end points are shown... This is a very slow calculation.

You can run the brain maze algorithm by clicking here: Generate a Brainmaze

The mazes generated by this algorithm are made up of the following maze atoms. This is the number of trees in a 2x2 Grid Tree.

    # #    ###    ###    ###    # #    ###
    # #    # #      #    #      ###     #
    ###    # #    ###    ###    # #    ###

This can be simplified by removing rotated copies to these two maze atoms:

    ###    # #
    # #    ###
    # #    # #

Click here to download: brainmaze.py <include src="/home/noahspurrier/noah.org/engineering/src/python/brainmaze.py" highlight="python" />

Simplified Brain Maze

This removes the middle connectors to give only the following atoms:

### ### # # ###
  # # # # # #
### # # ### ###

Connect 3 at any of the four corners.

### ###
  # # #
##* * #

# * *##
# # #
### ###
### ###
  # # #
##*-* #
  | |
# *-*##
# # #
### ###
### ### ### ###
  # # #   # # #
##*-* # ##*-* #
  | |     | |
# *-*## # *-*##
# # #   # # #
### ##*-*## ###
      | |
### ##*-*## ###
  # # #   # # #
##*-* # ##*-* #
  | |     | |
# *-*## # *-*##
# # #   # # #
### ### ### ###