main

Note: this wiki is for the developers...if you need support you can contact us via the Blender Market. While you are free to use this product from GitHub, further development costs time and money. By purchasing the "official" version from the Blender Market, you help to support continued work on this add-on.

Maze Generator [Pro] Wiki

Tasks

• Clean custom tile storing interface - nice workflow (create tiles --> test tiles with a predefined maze --> export tiles)
• Research circular mazes further to see if that could be implemented
• Training videos

Notes

• Add bias for x or y axis (giving it a higher chance of going in a particular direction)
• Kruskal's Algorithm - DONE
• Recursive division algorithm
• Eller's algorithm - DONE
• Hunt and kill algorithm
• Binary tree algorithm - DONE
• Sidewinder algorithm
• Other shapes...see mazegenerator.net below

Important Links For Maze Algorithms

Best

• https://en.wikipedia.org/wiki/Maze_generation_algorithm
• https://github.com/theJollySin/mazelib
• http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap
• http://www.astrolog.org/labyrnth/algrithm.htm

Must Read Still

• http://weblog.jamisbuck.org/2015/1/15/better-recursive-division-algorithm.html
• https://community.unity.com/t5/General-Discussion/Pacman-Maze-Generation-Logic/td-p/2012538
• https://community.unity.com/t5/Scripting/Quick-maze-generator/m-p/1331871#M248963
• http://gamedev.stackexchange.com/questions/910/algorithm-for-generating-a-2d-maze
• http://pacman.shaunew.com/play/mapgen/

Average

• http://datagenetics.com/blog/november22015/index.html
• http://ilay.org/yann/articles/maze/index.en.html
• http://pcg.wikidot.com/pcg-algorithm:maze
• http://www.mazegenerator.net
• https://en.wikipedia.org/wiki/Spanning_tree
• https://en.wikipedia.org/wiki/Maze_generation_algorithm#Graph_theory_based_methods
• http://elfnor.com/blender-3d-maze-generator.html
• http://catlikecoding.com/unity/tutorials/maze/

Using and Maintaining toggle_in_blender.py

I created this script to quickly switch all the files that can be used in/out of Blender with slight modifications between Blender and non-Blender mode. Just add new scripts to it's files list and fire it up, then type "T" or "F" for if you are in Blender (T = True in Blender).

Growing Tree Algorithms

1. Start at a (random) cell, make it a path, and add it to a stack
2. Choose a cell in the stack
3. If there is a valid neighboring cell, pick one at random
4. Make the cell a path and add it to the stack
5. If there is no valid neighboring cell, remove the cell from the stack
6. Repeat steps 2-5 until the stack is empty

Depth-First Variation

Always choose the last (most recent) cell in the stack.

Breadth-First Variation

Always choose the first (oldest) cell in the stack.

Prim's Variation

Choose a random cell from the stack.

Binary Tree Algorithm

1. Choose 2 adjacent cardinal directions (NW, SE, NE, or SW)
2. For every cell, choose 1 of the 2 directions to make a path

Kruskal's Algorithm

TODO

Eller's Algorithm

TODO

Dube's Algorithm

1. Start in the center of the grid (or space you would like to infinitely fill)
2. Assign that cell to a unique set
3. For every set on the +x face of cells, clone it to the right
4. Fill in cells in the x + 1 column that were not filled when cloning with their own unique set
5. Repeat steps 3-4 for the -y, -x, and +y axis until an axis hits a boundary
6. If an axis hits a boundary just remove it from the list to loop through, and continue on