Maze Generation
Randomly generating a maze, used to spawn new micromouse environments.
If you are familiar with Kruskal's Algorithm in creating a minimum spanning tree then this maze generation algorithm is a recap of Kruskal's Algorithm in a special use-case. Otherwise, if you are not familiar the following document does not assume so. Enjoy.
To define our maze, let any arbitrary pair of cells have a path to each other. For now, let us define that the arbitrary pair of cells only have one unique path to each other (graph with no cycles: acyclic).
The maze can be represented by a graph where each node is a cell in the maze and an undirected edge between adjacent nodes represent an open path.
By the maze definition, every cell in the maze can be visited by running depth-first search (DFS) on any starting cell. In other words, you can start at any cell in the maze and be guaranteed that you can walk to every other cell in the maze without having to jump over walls. In graph theory, a fully connected acyclic graph is a tree.
The problem that started off as creating a random maze is now boiled down to creating a random tree from a set of nodes. The approach we did on creating a random tree is known as Kruskal's algorithm. The pseudocode is as follows:
Example: G and G with no edges respectively
Author: Jose Jimenez-Olivas Date: January 9, 2020