This week I began work on the random generation. This is going to be a more technical devlog update, so I'll try to balance necessary accuracy and brevity. Please understand that I'm going to be simplifying some of the details of certain concepts and keep things pretty high-level and general, since if you're reading this, you could be anywhere from a seasoned programmer to someone who knows Java as a drink first and a programming language never. If a topic here interests you and you want to learn more about it, I encourage you to look up "[Topic] GeeksForGeeks" to read up on it!

Cool? Cool.

So, working on random room generation required me to revisit some old code for this project--as in, dating back to when I first started working on this project in October 2021! I had some really awkward naming conventions for referring to room dimension--I would refer to the x dimensions as "width" and the z dimensions as "length," even though the x dimension would almost always be larger, and it got really confusing, even with the comments I wrote telling me which was which. So I had to just call the width and length parameters xDimension and zDimension. Today I'll mainly be talking about the way I represented this problem.

The Grid

To generate rooms, I needed to make use of a 2D array of booleans (values that can be true or false). The grid would correspond to the dimensions of the world, where a grid coordinate (row, col) was the location of (the world location top left corner + (col, 0.5, -row)), where (col, 0, -row) is an xyz vector. This meant my grid had dimensions of zDimension * xDimension. If an entry is true, that means that there is a wall at that position; if it's false, it means there is no wall, and the space is "open."

There were a number of functions that I had to define to allow for room generation to be possible, and for enemies not to spawn into walls. The main ones I want to highlight:

• Position Conversion Functions: The functions GridToVector3 and Vector3ToGrid convert between grid position and Vector3 positions, and would prove very useful. I use the grid to tell me if a space is open, and if it is, I use a function to convert that grid space to a Vector3, instead of writing out the same conversion code every time.
• Adjacent/Surrounding Wall Checking: I use AdjacentWallCount to check how many walls are adjacent a grid space. This helps prevent me from accidentally creating boxes with certain wall generations--areas that can't be accessed from all four borders. SurroundingWallCount extends the check to diagonal boxes
• OpenGridPositions: This gives me a list of integer pairs that correspond to grid spaces that are false.
• Space Reachability Check: There's a lot to say about this one. It's very important that any open (i.e., non-wall) space is reachable so that when I try to spawn an enemy, the player can reach them. Additionally, when I set an entrance, I need to make sure it's not walled off.

Space Reachability

In order to check what spaces are reachable (a shorthand for "I can reach the entrance from this space"), my initial plan was to use a Breadth-First Search (BFS) algorithm to check if you could reach all four borders from every open space using adjacent movement. BFS works like this: imagine you have points on a map that have roads between them. The amount of roads you have to travel to get from location A to B is the distance between A and B. Let's say I want to find a route from New York City to Pittsburgh:

• Start by adding NYC to a queue and a seen list.
  
• Repeat until the queue is empty:
  • Remove and store the oldest location X currently in the queue.
  • If I removed Pittsburgh from the queue, then I'd return "true."
  • Otherwise, for every location Y that is one road away from X (and NOT in the seen list), add Y to the queue and seen list.
• If the queue is empty, then it means that there's no path on my map from NYC to Pittsburgh, even if both are on the map.

Now imagine instead of real world locations, it's spaces on a grid, and a "road" existing between two spaces means the spaces are adjacent. Instead of checking if I removed Pittsburgh from the queue, I'd check if the space I removed was at one of the four borders of the grid, and let any adjacent space know that it can also reach that edge of the grid. Being able to reach any of the four corners from a space meant that it wasn't isolated from the rest of the room, which meant I could reach the entrance of the room (this assumes that the borders themselves aren't completed blocked off by walls).

However, doing the cost analysis proved that this would be... inefficient, to say the least. If I have n spaces on my grid, then checking if a single space is reachable would have a time complexity of O(n) ("linear time"), meaning it would take around cn steps for some constant c to complete. Doing this for all n spaces would then give me a time complexity of O(n^2) ("polynomial time"), meaning it would take around cn^2 steps for some constant c to complete. While algorithm efficiency doesn't normally bottleneck performance in games to the same extent that physics and rendering do (at least to my current understanding), and polynomial time is perfectly respectable in the world of CS, I figured I'd optimize now and save myself the headache of optimizing later. I knew I could do better.

While thinking of how to optimize this algorithm, I came to an incorrect conclusion that to check if a single space is reachable, I'd have to attempt to check every open space anyway, since at every iteration of the loop, I would test if all four directions had the goal I was looking for by adding them to the queue. This led me to the correct conclusion that, assuming my BFS explored every space it could, not stopping until the queue was empty (meaning at any space, it's making every move possible):

• If every open space on the grid was reachable from anywhere, then my seen list would have every open space (I'll mark this statement with (=>))
• If my seen list had every open space, then every open space was reachable from somewhere (I'll mark this statement with (<=))

These are two mathematically distinct statements, but together are enough to tell me that, to determine if every space is reachable, I just need to perform a BFS search starting at some arbitrary space, expanding spaces until the queue is empty; if the seen list contains every open space, then every space is reachable; otherwise, there's some space that's not reachable.

For my CS friends, here's a proof of correctness, involving representing my seen list as a tree where a parent-child relationship between two nodes indicates two adjacent spaces:

"

CORRECTNESS: All open spaces are reachable from anywhere <=> all open spaces are on the BFS tree
(=>): If an open space is not on the tree, that means it could not be reached from my chosen start, so not all open spaces are reachable from anywhere (contrapositive)
(<=): For any two spaces on the tree, you can travel from one space to another through the parent-child edges. Since the parent-child edges indicate adjacent spaces, all open spaces being on the tree means you can reach any space from anywhere by traveling along the parent-child edges.

"

With this, I found a linear time algorithm for checking if all spaces are reachable.

Conclusion

Just describing the Space Reachability already went way longer than anticipated, and the room generation is not completely done yet, so I'll go more into it the actual design of it next week when it's fully complete.