This algorithm is flexible, too! If you want long corridors, then you can add a horizontal bias to the random cell picker.
This was probably the most enjoyable thing to work on for me. If you want more info on the algorithm, since my explanation will be brief, you can read on it here for the algorithm itself, and here for how it’s used to generate mazes.
Using depth-first-search to create a maze is pretty easy, actually. How it works is basically it keeps a notebook on all the cells, and every cell starts unchecked. It then begins by picking a random cell around the starting cell, and once it picks a cell, it marks it as picked. It then repeats this process. If it hits a dead end, as in all the cells around it are picked, then it will backtrack on the exact path it took to get there until it finds a cell that hasn’t been picked. This can ensure every cell has a path to it. if it backtracks all the way to the beginning, then we can reliably know that the maze is finished. In my case, there may be some cells that are totally boxed, but this is rare.
I can fix it, but basically, its a result of 3 am code. Basically, when boxes are being checked in my code, there’s a table of the 4 surrounding boxes. Whenever a box in the table is picked, it removes the box from the table and sets it to nil. This apparently doesn’t remove the entry from the table, so the #table still returns 4, so whenever i get a random entry using
table[random(1,#table)]
it may return nil and cause an error. To combat this, I have it so it picks 1,4 in the table until it gets an entry. If no entry is acquired in 20 tries, then it assumes the table is empty. Since it’s completely random, there’s a very small chance that in all 20 of those tries, it missed an entry it the table. This creates the boxes. Of course, to prevent this, you can increase the iteration to something like 100 before it assumes the table is empty. This runs poorly however, so I had it at 20.
Seems like a very similar game to my Beast project back in 2019. I used a recursive backtracking algorithm to generate a maze, and then had a number of monsters attack the player while they attempted to find a key and escape through the door.
