Home|Projects|About

Maze Generator, C++, 9.3.2021

This was such a fun project. In my programming 2 class, we were tasked with creating an algorithm which could, theoretically, generate a maze. Having been working on Rogue Adjacent 4, I had just finished implementing A* pathfinding, so it was on my mind. I was thinking, if you can solve a maze with pathfinding, maybe you can make one too!
Ends up, you can!

Here's some sample outputs. A lot of these don't really look like mazes but I realized if you tweak the numbers a little you can get some pretty impressive looking organic shapes too. If you couldn't tell, this is all being rendered in a console window.
The algorithm I originally described was actually shockingly close to how it ended up working, too!

-1: Create a field of positions with a random weight
-2: Use a pathfinding algorithm to go from a point to the exit which favours going to positions with low weight (so it isnt a straight line)
-3: Outline the path with walls, decrease the weight of any positions in the path, then double the weight of positions with walls (or something like that)
-4: Pick a random point which isn't a wall or already part of the path.
-5: Path from that point to the exit, still favouring low weighted paths.
-6: Overwrite any walls which were pathed over, outline the path with walls again (ignoring spaces which were already outlined)
-7: Repeat from point 4 until the entire grid is filled with walls or paths.

One quite obvious issue is that all the points are trying to path towards the exit, so all the paths somewhat converge towards it. Not a very good maze!
I did eventually change this by having it pick a random point, then having it path from that point to another point already on the maze. It worked much better.

Now, the privy among you may notice that this.... still isn't a very good maze. Though, the even more privy among you may realize that the assignment was to design an algorithm, not create a program. It was very awkward submitting a .cpp file when all I was supposed to submit was a txt file that contained my theoretical algorithm written in psuedocode. I did include the answers to the questions as a comment above the code, so if they didn't want to compile it they could just pretend the code at the bottom wasnt there.
Honestly, thinking that I showed that code to my professor is horrifying. It is some spaghetti. "Lets just throw something together" in its purest form.
I did eventually make a "screen saver" based on this idea. Like I said before, it is HORRIFICALLY written, so using it as a screen saver would be a terrible idea, though if you want to see more sample outputs, you can download it here.