Maze Game
This is an interactive maze program which I wrote in C99 using SDL2. You are the red square trying to get to the gold square. This isn't meant to be a polished game; it's more of an interactive demonstration of maze generation algorithms rather than something polished and meant for entertainment.
Controls:
- W/Up Arrow - Move up
- S/Down Arrow - Move up
- A/Left Arrow - Move up
- D/Right Arrow - Move up
- C - Toggle cell distance visualization
- P - Toggle path to goal
- B - Braid the maze (aka. remove deadends). Cannot be undone!
- 1 - Generate maze with BSearch algorithm
- 2 - Generate maze with Sidewinder algorithm
- 3 - Generate maze with Aldous Broder algorithm
- 4 - Generate maze with Hunt and Kill algorithm (I didn't pick the name)
- 5 - Generate maze with Recursive Backtracker algorithm
- 6 - Generate maze with a simplified Prim's algorithm (evenly weighted)
- 7 - Generate maze with a Prim's algorithm
- 8 - Generate maze with Ellers algorithm
- 9 - Generate maze with Recursive division (it does do room generation)
About
A lot of the algorithms are zero allocation. The grid itself lives on the stack instead of being allocated, and it's memory is reused anytime there is a change (which is why I can't reverse removing deadends - I'm only storing one grid and I remove the deadends from the grid). The grid has bit flags for which direction has a wall.
I'm using Breadth-First Search for solving the maze. I store the weights in the grid itself, and then I reuse those stored distances for the cell distance visualization. For the path, I just have an additional bit flag (I only needed 4 bits for the walls, so I had at least an extra 4 bits). I also added a bit flag for the start and end because I could.
There are a few maze generation algorithms which do make a memory call. I could remove the call by forcing my grid to be a fixed size (since it doesn't change), and then all my memory could be on the stack. I didn't really want to do that though, so I went with having a few memory allocations instead. I do limit how many allocations I do, so it's generally only one or two allocations.
As for why I chose C, well I just wanted to. I'd normally use C++ for WASM/SDL programming, but this time I wanted to try using C. It was different to not have so many data structures available (such as sets, stacks, vectors, etc), but it didn't change things too much. When I needed a stack, I just allocated a chunk of memory the size of the maximum elements I could ever push on it, and then I had a pointer keep track of where the top of the stack was. For queues it was similar, I just had two pointers. For sets I just used an array and searched through it (usually I didn't have enough elements where a hash set or tree would noticeably beat out the CPU prefetching optimizations, so this worked pretty well. In the end, I think my code was often more performant because I had far fewer allocations and less overhead in my data structures (a few years ago I had implemented these same algorithms in C++ using the fancy data structures, and some of them were noticeably slower than my C code).
The only thing I really missed was a decent random number generator library, so instead I wrote one based off of TinyMT with some tweaks. It was good enough, and it's nice since it uses very little memory and doesn't require any heap allocations.
I used Emscripten to compile my C code into WASM. I also used their generated JavaScript for hooking it up to the DOM, so the amount of JavaScript I needed to write was minimal (I just needed to add code to hide the loading text and select the canvas).