Building a Maze Generation (Part2)

Step 3, polishing the main path

Now that I have the basic generation down, I need to make it more like a maze. So, for this, I’ll construct a special mechanism during the generation of the path. Basically, what I’m going to do is make my maze, which is a list, into a list of lists.

When I first made this generation, my list which generates the maze was just a bunch of 1’s and 0’s, 1’s representing a wall and 0’s representing empty space. Instead, I’ll make each element in my list into a list with two separate values so that it looks something like this: maze = [[1,0], [1,0], [1,0]...]. The first value, or the “1” of each element, determines whether or not a given tile in my game is a wall, similarly to how I did so before adding this new feature. However, the special thing about this mechanism is that each tile holds a special, new value, which is the “0” in this case [1,0]. What this allows me to do is that, every time I carve out a tile to forge my path, I can tell the code to “add one to the second value of the element to each neighboring tile”, which looks something like this:

By attributing this new “checked” value to each element in my “maze” list, I can control which tiles can be “carved out” into the path by using logical statements that evaluate the “checked” value. That's enough explanation for now, so here are the results of my code:

[In my function pathgen(), I tell my code to first generate my maze as a list fill of “[1,0]”’s. Let us call these “[1,0]”s as a “mini list”. Essentially, I’ve made a list full of our mini lists. The first element of my mini list, which is “1”, represents if a corresponding area on the screen to my “maze” list should be a solid block or empty space. If the first element of my mini list is “1”, then that means there is a solid block. If it is a “0”, then it is an empty space. From there I determined where my player would start off in the map, as seen in “start = GRID_COLS+2”, and then I proceeded to create a new list called “Borders.” I did this in order to prevent my code from being able to make the edges of my maze into empty spaces. Essentially, I’m just creating a list full of all the values of the edges of my screen so that my code knows not to accidentally make them into empty spaces. Think of it as making the edges into super duper strong blocks that can never be broken, unlike the other blocks inside of my maze.

From there, I determined the “end” of my path in my maze, kind of like determining where the goal is for the maze.

Unfortunately, I couldn’t figure out how to utilize it, so just ignore that piece of code. Then I set the “start” of the maze into an empty space so that I can spawn into an empty space when I run my game, and I did so through the line: “maze[start-1][0] = 0. Notice how there are two pairs of brackets when I am referring to a specific element in my “maze” list. There are two pairs because the first pair, “[start-1]” is referring to the specific element in my “maze” list, and the second pair, “[0]” is referring to the first element of my specific element in my list. Remember that each element of my “maze” list is also a list, so I have to use two brackets in order to specify what specific part of my element I chose I want to change. From here, I started my path-carving algorithm.

By using “C= random.choice(“LRUD”)”, I am using the “random” module provided by python to randomly select a direction of Left, Right, Up, or Down. Upon randomly choosing a direction to go in, my code now runs into several “if” statements in order to check which direction was chosen. If the chosen direction is Up, then my “if” statements run the code for “if C = “U”. This process happens with any direction L, R, U, or D. Notice how in each “If” statement, there are a lot of things being checked. What I’m essentially telling my code for each “if” statement is that it should check, not only the direction, but also if the block in the chosen direction(left, right, up, or down) is a valid block to be able to go to and carve out. Firstly, I checked if the block in the chosen direction is a border of my entire maze. If it is, then the code doesn’t carve into the wall. If it isn’t, then the code realizes that its OK to go in the chosen direction for now.

However, there is still another parameter for the “if” statement to check to be able to go in that direction. Now this is the complicated part; the code checks if the block in the chosen direction has its second value below two. Remember how each block is a mini list? What my code is checking here is the second value of a given block, as each block is quite literally a physical representation of the mini list. In other words, a given mini list is the equivalent of its block. The reason why I check the second value is explained above, but I’ll explain again anyways. Essentially, the second value is how many times a certain block has been “checked.”  Another way to think about it is that the second value is how many times a certain block has had its neighbor been carved out. Every time a neighbor of a block is carved out, its second value increases by one. By telling the code to check if a block has a second value(in its mini list) below two, I’m basically telling the code to check if a block has less than two neighbors carved out. This way, I can prevent a carved out path looking like a block of empty space rather than the long, directional path it’s supposed to be. Moving on from the parameters inside the “if” statements, if we take a look inside the “if” statements, I’ve basically told the code to simply do the following:

• Upon checking all parameters and making sure that the block of the chosen direction is viable to be “carved” out as the next block in a path, it will do the following:

• It will make the new chosen block into empty space, “carving” it out.

• It will increase the second value of all neighbors(that are directly above, below, to the right, and to the left, not diagonally) by one in their mini list.

  
  

All of this code is within a “for loop”, where it runs a total of 200 times, as it says “for i in range(200)”. Finally, upon running this algorithm 200 times, the path generation process is finished, and the “maze” list is used to generate the yellow blocks and empty spaces we see in the screen below.]

These results are MUCH better than I had anticipated after running the code several times. It is still quite buggy, but that's an issue I intend to fix after adding the final mechanic to complete the maze generation.

Finally, after getting down how to generate a singular path in a maze, I am able to generate the entire maze.

Final Step(not really), backtracking algorithm

Finally, after getting down how to generate a singular path in a maze, I am able to generate the entire maze. With a stroke of genius, I managed to think of an easy way to generate a full fledged method to generate a maze without needing relatively much code. Basically, I told my code to keep generating one path until it no longer is able to be continued, and from there, I choose a block that I’ve already visited to return back to in order to start a new branch from there. In simpler terms, my code acts like a tree; If it cannot grow a specific branch any longer, it just starts growing branches on the side of the original branch! Although I felt like I'd discovered something new, turns out, I didn’t. This algorithm that I’ve “discovered” is actually called the “Backtracking Algorithm,” commonly used in almost all types of maze generation due to its simplicity and novel solution. However, my code doesn’t seem to coincide with that definition of backtracking algorithm, as it is quite bulky. However, all that matters is that it works, and that it looks great. Upon applying and coding this new algorithm I found, my results speak for themselves:

[Don't worry about this new version because I completely scrapped it for a way better and more efficient process because I had a sudden enlightenment recently.]

Although the results aren’t perfect, I am still quite proud of the fruits of my efforts. It seems as though my creative juices ran out, and I think I’ll leave it at this. And with that, my maze generation is complete. JUST KIDDING AHAHAAHAHAH you fools you really think I’d be satisfied with these results? The maze looks like an absolute mess and does not give off the typical “maze” vibes you see, as my maze consists of several diagonals and very thin walls and all those issues. I’ve always been frustrated about this issue and up until recently, I had no idea what was causing it. However, an idea on what the issue was and how to fix it struck me like lightning, and I’ll explain it in the next part.