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.
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. Also, note by our definition the graph has no cycles because an "arbitrary pair of cells only have one unique path to each other".
By the maze definition, every cell in the maze can be visited by running a 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, this 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
- Start off with a forest of nodes
- Make each node be its own set
- Pick a random edge: (u, v)
- If u and v are not in the same set, legitimize the edge and union disjoint sets.
- Repeat the last two steps...
...
Done.
The problem with the approach above for a micromouse simulation is that there exists only one unique path from start cell to goal cell due to the tree structure of the maze. In this current environment, the micromouse is not tested to find the most optimal path in the maze.
To mitigate this issue, complexity is added to the maze by introducing cycles. This can be done by simply adding an arbitrary amount of complementary edges that are not present in the maze. Now in this new environment, the micromouse will be tested in a realistic emulation where a set of solutions exists and the micromouse will then have to find the shortest solution path.