# Difference between revisions of "Brain Maze"

m (→Simplified Brain Maze) |
|||

(31 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. | ||

− | + | 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 | + | 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 267: | Line 272: | ||

</table> | </table> | ||

− | Click here to download: [http://www.noah.org/ | + | 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 | + | |

+ | <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 14: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.

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

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

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