Home

Note: this wiki is for the developers...if you need support you can contact us via the Blender Market.

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