Hello everyone and welcome to my another blogpost. Or rather, an another blogpost series where I'm gonna be talking about the development of Sourcerama, stuff that I already made or plan making.
From my previous posts you know that I started working on procedural dungeon generation for my next source project, but incase you forgot - here's a latest video with it
Sooo, I was supposed to be improving this system further, right? Well yes, but actually no.
The system's code was kind of crap, it was an unoptimised mess made out of lots of spaghetti code, almost everything in a single script file with >1600 lines of code and hard to navigate around.
There was no algorithmic "model" of the layout. To determine whether there's a floor/wall somewhere, I had to rely solely on collision checks during generation, which is very very bad.
Hence I decided to actually scrap all that and start rewriting the entire system from scratch. So far here's what I got in around a week:
Say hello to my new little friend, the Layout Preview! It looks like your average ASCII Roguelike, not too far from it, because it's actually a top-down grid representation of level's layout.
The generator now creates a data with matrix and all room information that is necessary, before placing everything in game world. That way I can no longer use collision checks and overall it's much easier to edit or improve the system now. I'm making a separate script files for each individual process of generation, so that they work almost independently.
Here's how generated layouts look like right now:
Colored squares with assigned digit/letter - Rooms
Yellow hashtags are hallways
And any '+' signs are places where doorways should spawn.
The rooms' sizes are random, but this time I used my RNG in slightly different way. My default RandInt(A,B) function simply chooses random integer value between A and B, based on seed. But the problem is that each possible room size generated this way has same probability of being chosen, resulting in pretty chaotic room layouts. There has to be atleast some bit of consistency, right?
My problem is the "uniform distribution" of my random number generator. Rolling a die gives you from 1 to 6 points, and each outcome has same probability.
But if we roll 2 or 3 dice at same time, probabilities are no longer equal, because different "scores" now have different amount of corresponding outcomes. So 2 dice rolls have "Triangular probability distribution".
But even that is not enough, if we roll more than 2 dice, we get closer to what I actually need - "Normal distribution".
So in my way of generating "pseudo-normally-distributed" numbers I basically call RNG 3 times. So possible room sizes are from 1 to 10, but the majority of rooms you see in screenshot above have size of 5 or 6, and extreme values are still possible, yet rare. That's exactly what I need. Normally distributed random numbers can be quite useful in Procedural Generation.
I rewrote the algorithm for placing hallways, so that they don't get too long. And most importantly, hallways are built in a specific way so that room connections can be imagined as tree graphs now.
What do I mean by that? Well, let's imagine the screenshot above, but all rooms are resembled by circles(nodes) connected with lines(edges) which resemble hallways.
(Assume that we forget the exception when hallways intersect with each other, adding possibility of same-depth rooms to be connected, I'll find a way around that later)
As you can see, a new interesting property is added - The room Depth. It determines the amount of rooms player has to travel from the starting room(Room 0) to selected room.
Imagine that there has to be a puzzle player has to solve to progress through the dungeon. For simplicity we'll take the well-known Key/Lock puzzle.
Let's make player unable to access rooms at Depth 3 or below. The only room at such depth is Room 6, which we'll place locked doors at.
So now that we need to spawn a key, we can place it in any room that has depth value equal or below 2. But most preferably it would be to place the key in rooms 1, 3 or 6, because they're not included in paths to the locked room, which makes it necessary for the player to explore those dead end rooms and do a little bit of backtracking.
The depth parameter solves the problem of accidentally spawning keys behind the locked doors they're supposed to be used on.
In future, I want to use the level matrix for Line-of-sight checks and optimisation - Generating ONLY rooms that player can possibly see and despawn rooms which are no longer needed, therefore freeing edicts. With such optimisation I can have big layouts with probably over a hundred rooms, without exceeding the entity limit.
I also plan adding multiple floor support. Generating rooms with different Z-Height, or having multi-floor layouts connected by staircases.
Thanks for reading, see ya next time!
мило
interesting stuff