Inspired by @jamis
I really want to learn about maze generator for a long time. This week, I found a really good resouce by Jamis Buck. In his blog, I was surprised that maze generator could be formulated as generating Minimum Spanning Tree (MST) from a graph.
Here I implemented 4 basic maze generator: Kruskal Method, Eller Method, Prim Method, and Wilson Method.
Kruskal Method: it is the simplest one. The main idea is to randomly select a pair of adjacent tiles. Check whether they are connected, if not, conntect them. Repeat the process until all tiles are conntected.
Eller Method: it runs like a printer. It runs from left to right and from top to bottom. At each step, it randomly removed the border with some conditions to make sure that all cells are connected.
Prim Method: it is my favorite. It is like BFS. It randomly picks one cell as an initial point then it tranverses from that point to the rest of the map.
Wilson Method: Similar to Prim but, this time, it is DFS. To generate a path, it will randomly tranverses until it reaches a target. Becase it randomly moves from one tile to another, it might take really long time to reach the first target.