Maze generation is a pretty common problem in CS, and there are plenty of ways to go about implementing generation algorithms.

This particular implementation uses Kruskal's Algorithm with disjointed sets. The code is built out in C and should be relatively fast and memory safe.

A maze can be represented as a graph in which each cell is a node and the path from one cell to another corresponds to an edge in the graph. Thus, a wall in a maze is simply the lack of an edge connecting two nodes.

Kruskal's algorithm traditionally creates a [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree#:~:text=A%20minimum%20spanning%20tree%20(MST,minimum%20possible%20total%20edge%20weight.) out of a connected graph. This specific implementation of Kruskal's algorithm for maze generation doesn't use an explicit graph but instead simply keeps track of whether random cells are in distinct sets.

Basically, the program first intializes a basic structure for the maze (simply a grid of cells and walls in between) and stores the list of walls and a disjoint set of the cells in memory.

A random wall is picked and if the two cells that the wall divides are members of separate sets, than the wall is removed and the two corresponding sets are unioned.

The implementation of the disjoint set uses parent pointer trees and is overall pretty cool. I would recommend taking a look at the wikipedia page and the code here.

Intially, I thought I would visualize the completed using ascii art or special unicode characters, but nothing really ended up looking that good. I contemplated making an actual hands-on rendering system for it with OpenGL or another rendering library, but I thought it would be uneccessary work and distract away from the point of this project.

This implementation is essentially entirely theoretical and there is no solving algorithm or even start/end points. You could make a really easy BFS solving algorithm, but the way in which I intend to solve this problem (on my portfolio site) will relatively be unique.

Mostly, this project would be the skeleton for the maze that I'm creating in Three.js and Svelte for my portfolio site. More on this in the future.

I am also going to implement this same logic in Haskell because I desperately want to learn Haskell and I think this is a good starting point.

Feel free to use!