Building a Maze Generation (Part3)

Final Step(FOR REAL), the FINAL POLISH

So it turns out, my method of attributing each element in my “maze” list a second value in order to check how many neighbors of empty space that they have is actually quite impractical and flawed. When you see a maze, you often see a bunch of OVERLAPPING paths in the maze, as they intersect each other. That is what makes a maze truly a maze, as there are countless options on where to go. However, if you look at my results above, you can see that my paths RARELY intersect with each other. Up until now, I had no idea what was causing it. However, I found out, so here is the explanation of my genius:

Let’s call the “special” value I assign to each element in my maze variable “surcheck”. Basically, as a quick recap, my maze is a list, where each value in my maze list decides whether or not that value should be either empty space or a wall in the physical maze. I’ve assigned each of these values a surcheck next to them, although you cannot physically see it. The surcheck simply tells me how many neighbors of a given block are empty space. In my first version, before I implemented my backtracking algorithm, my code only considered a neighbor to be a block that is DIRECTLY above, below, to the left, or to the right of a given block. I tried to use this surcheck value in order to tell my code to NOT make a block an empty space, IF it has 2 or more neighbors who are empty space. This way, I can effectively avoid situations where my maze has a path that looks too “open”(ex: a visible 2x2 area of empty space is quite the eyesore to look at in any maze). I thought that this wouldn’t be an issue when it comes to letting my generated paths intersect, but turns out, it was a huge problem. However, I would only notice it after I finished my second version of my maze generation, where this time, I not only made blocks that are directly above, below, to the left, or to the right of a block a neighbor, but I labeled blocks that are directly DIAGONAL to a given block as a FRACTION of a neighbor. Basically, if a block that is to the direct left of a given block becomes empty space, then the surcheck value of that block increases by 1. However, if a block to the direct diagonal of a given block becomes empty space, then the surcheck of that block increases by 0.1. In a diagram, it would look like this:

Thinking that if I simply asked the code to check if a block could become empty space if its surcheck value was below a certain threshold would work, I ran the code several times. However, each time, I didn’t get the result I wanted, and then it hit me. This system is flawed because the amount of times the surcheck value increases is simply too much and too often. Every time I move onto the next block to carve out, EIGHT blocks have their surcheck value increased. Not only that, but FIVE of the EXACT SAME blocks have their surcheck value increased after moving TWO TIMES. In other words, this system was heavily unreliable and had no value when it came to controlling the shape of the maze. In order to truly achieve what I want, I had to think of an entirely different system, which is what I did. I thought of what I wanted differently. What is the only thing I wanted to prevent? I asked myself. The only thing I wanted to prevent is for my maze to generate a “room,” or an area with too much open space. In other words, I wanted my maze to be so that if I were to check every single 2x2 tile on the maze, I wouldn’t find a single 2x2 tile such that all 4 tiles present in that 2x2 tile are empty spaces. That was my solution. I built a completely new function that checks the adjacent 2x2 tiles of a given position in my maze to see if any of them can become a 2x2 block of empty space, and avoided any such tiles. This system is much easier to code, simpler, faster, and more compact than my previous system. What I basically did is that whenever I move onto my next block in my path, I check my surrounding 2x2 tiles. What I want to avoid is any 2x2 tile with 3 empty spaces, so that such 2x2 tiles with 3 empty spaces can never become a 2x2 tile with 4 empty spaces. Here is my code for this new idea of mine(I deleted my previous system so it looks a lot smaller now):

Now here are the results:

THERE WE GO!!! My maze has successfully generated multiple paths that overlap and intersect with each other. The vibe of my new mazes are completely different, as they seem a lot less random and jumbled up, and now seem more “maze-like.” Finally, I can truly say that my maze generation process is complete.