18/03/26
If you couldn't tell by the jump in post time periods, this one is big. Maybe even the biggest. It needs lots of care and attention. So much that I can't even do it all in one go.
World Generation:
I already established procedural generation in a cave like system that I wanted to mess around with, and see if it would come up with a cool map for the players to travel around. A map of slightly tight corridors and big open caverns. This is why I made the region system. To connect these areas seamlessly into one massive cave system. My question is now though, how do I make caves.
Personally, I haven't really touched procedural level generation like this. Every game I've made is a big user of RNG, but not to this scale. How do you even make geometry with code? Then to also make it purposeful? It seems like a tough challenge.
The geometry part was not the element I was worrying about to be honest. My instinct was to go to tilemaps and tilesets for something like this. It may be grid like in the end, but something like this probably should be. My concern with using these, is that they are functions designed for beginners to use the engine to build their small games. This isn't a problem, but they aren't built for the kind of scale that my regions occupy.
No, I'd need something more raw. Something much more dynamic and fast to read from. My next thought would be to go to buffers, but that seems excessive. It would be necessary if the whole map is used at once, but considering I only need it all loaded at once, it's not worth my time and energy.
No, what I need is Data Structures. Raw data saved in array-like systems, but without all of the safety and convenience features packed in to make it slower. More specifically, I can use a DS Grid (Data structure grid) to save my data in.
Basic, not too costly on memory, and really fast to read and write to. Considering that these maps will be holding data in the hundreds-of-millions, even something like this will take some time to write to, but it shouldn't be that bad. I can always come back around and revert to my original idea of straight buffers.
That's the easy part though. There's still the monumental task of actually figuring out the shapes and implementation of these caverns to do. And honestly, I have no idea how I'm going to do it.
I looked around for a while on games that I'd previously talked about with these. That being Minecraft and Deep Rock Galactic. I still came out with no idea on how to do this. I then just searched "cave generation" on bing, and found a niche little itch page that seemed be a cave generator similar to what I had imagined.
It literally was exactly what I was looking for. A basic modular system of generating cave systems with big rooms, passageways, and having the ability to alter the generator with tags. This small generator project by watabou just proved that it was possible to make something like this. I knew it already was, but seeing it in action made it much more believable.
This generator was intended to make map images for people's RPG games like Dungeons & Dragons (another linkback). It's really well made. Makes a really fast small map of a cave system with tons of customization and additions that make each one separate itself from the other.
Seeing this was inspiring, but not the most helpful to me right now. I already knew what I wanted to make, just not how to make it. And this doesn't help me figure out any methods to go about it.
However, this project has a little rabbit hole I went down. And it saved me.
BorisTheBrave.com is another indie developer website that actually went inside the project and explained how the entire thing worked. I knew of neither of these people before this post, and now both of them are hard-carrying me through this process. Well, the theory at least. I actually need to figure out the code myself.
The cave generator does indeed use a grid as it's template, but then makes the mesh with post-processing. But does it make the shape? Well with Seed growth. (Seed growth being the name used here, as far as I can see, this isn't a well documented topic and doesn't have an official name.)
It's basically a system of taking a point on the grid, and expanding it in all directions randomly until you have a nice round-ish shape. Now, I have seen this technique before for generation of biomes in some games, but didn't really consider it's application here. I guess it was my fault because it seems like an obvious out in hindsight.
What interests me here is that nothing seemed that complicated here. I was imagining that these algorithms have some massively complicated technique to them, but that isn't necessarily the case. It's impressive and tight, but not out of my depth to recreate myself.
I did consider borrowing a bunch of the formulas, but that feels like stealing. I don't really want the exact methodology used here anyway, due to how it's supposed to look for it's smaller grid size. Remember, I'm going bigger. So whatever I make here, needs to be well optimized and well implemented into my code. It would make more sense to make it all myself anyway then.
The following process was about 4 days of trial and error of getting a system that fit the games needs, and is as efficient as possible. It wasn't made in this order, nor did it go as smoothly as this post makes out. It was quite annoying in places.
The highlighted areas are the cave openings themselves, whilst the darkened areas are inaccessible wall tiles. The FPS Counter here shows 13 frames, but that's simply because I'm rendering 16x HD to show you all of the regions at once. That will be fixed when it comes to display and mapping, but in game I get about 8000fps with everything loaded in engine without compiling to YYC (The faster one) and on college hardware (Which is medium-good in processing power). I think actual performance isn't really an issue here. I'll talk about it's shortcomings a little later.
The code for this adds up to a tad over 700 lines. I won't go over every single one, but I will go over the process and the issues I found here.
This is the first important function after creating the data structure. I simply add a bunch of randomly placed starting points for our big rooms, comprised of a big number that is unique integer taken from the x and y position of that tile. I then push it into an array to be used later.
I do this so that I can find every place that needs expanding, rather than setting tiles up with unique data. This way, I can easily skip the tiles that have nothing on them, saving more processing power and speeding the generation up. I did try the other way, but it was very slow. It took 28s on average per region. That isn't good. This method does it in about 4s on average per region. A heavy hit, but necessary. Luckily the only big hit this system does. (Again though the specifications of the build will make it slower than it will be when compiled for launch).
I use a unique integer instead of expanding the array because I actually found it to be quicker. When testing the Oil Rig idea with it's data manipulation system, I found that nested arrays are also very slow. So, manufacturing a unique id instead of using two separate ones is much easier on the processor.
This was simply a happy accident that I found this out, I would never have realised that nested arrays are as bad as they are. The speed decrease on that server went from 30000fps to 600fps once I switched from regular to nested arrays, and went through them like I do here.
I also edited the region spawner that I made last time to give the approximate locations of the exits to the region, and put them as special case hubs. There is a reason for this that I'll tackle later.
I then use a repeating script to grab each of these placements, and randomly spread them like the the post mentioned about seed growth. This is the most unoptimized part of this entire system, but I'm not going to worry about it too much right now since it only hits once every time you load a big level. That won't be often, likely after every half and hour or so. Therefore, a single heavy performance hit for about 10-20 seconds (depending on player hardware and accounting for later loading) isn't that bad.
I decay the spawners and eventually remove them from the list until nothing remains. I makes a really nice randomly expanding circle room. When combined with others, it makes really nice hubs and play areas.
I then quickly clean up the decay and make sure the data grid is only filled with binary data, not other random numbers that aren't wanted. Very small part of this system.
We can't just leave it there, because this isn't a cave system. This is a bunch of tightly packed islands of different sizes. If the islands don't connect to each other, (and they definitely won't by themselves), then the player won't be able to reach the other exit. Caves typically have small passageways in between their hubs, and that is what connects them together. Let's do that then.
This is where I go a little off script from the original website that I found, since the paths are calculated way differently from how I did it. The map in that generator is so small with everything packed so tightly, that it'll just find two touching regions on the other sides of a single tile and remove the rubble between. I can't do that, because the world is so big that that rubble might be 100 tiles in between. And I can't just calculate that by the usual method because that would bring the game up to a 10 minute long wait. And I can't control how well that system works.
What I do instead, is use MP grids which can be converted to and from DS grids really easily to figure out which original rooms I made are touching. MP grids are basically just more limited DS grids that can be used for pathfinding. So, I did that, and made an array filled with all of the isolated islands.
The next system is really complicated and I don't want to go over it too much. But basically, I then find two islands that are the closest together, find the individual points between the two that are the closest together, and then make a path line and put that into a new array. I then append the two islands together in that array and call it just one island. Because I already have the path calculated, I can assure that both will be touching by the end.
I repeat this until only one island remains in that array. Now, the paths gathered from appending them should make every single part of the map connect together.
I calculate a bunch of new points to use my seed growth mechanism on using the new paths as guides. I then just run it through that growth to make the paths.
I calculate a bunch of new points to use my seed growth mechanism on using the new paths as guides. I then just run it through that growth to make the paths.
That is the bulk of calculations for making the caves done. The actual area is carved out but still not looking the best. Now it's time to polish the area up a little.
This next part is very experimental. To get rid of the artifacting in a lot of areas, I decided to smooth out the cave walls and areas using surfaces and buffers. I basically draw the whole grid out with some extra smoothing on the grid. Making some areas much more rounded and fixed than without, and then turn that surface into a buffer to extract that data and turn it back into the grid.
It's a very minimal addition, but greatly improves the general shape of the environment. It really does feel like a natural cave now.
The last issue to discuss is about player boundaries.
The player should never be able to simply walk off of the map. All edges of the map should be covered to insure that players do not leave the designated areas.
I wrote this script here to create a natural boundary that applies to the grid after everything else has been generated. This system basically just creates random numbers from each edge tile to set as empty. Very simple, very quick. What's been forgotten about this however, is the fact that the players DO need to leave the map. They need to leave in-between the gaps designated by the region markers to go between the regions.
"I also edited the region spawner that I made last time to give the approximate locations of the exits to the region, and put them as special case hubs. There is a reason for this that I'll tackle later." - Earlier in the post.
This is where that comes in, I run some code to basically ignore the areas around the exits when creating boundaries. This does exactly what it should do, and makes the whole system clamp to the middle areas of the region, minus the exits between them.
Overall, this system is now done. The whole map now generates and renders properly with very little issues with performance and data management. I'm very happy to report that this system is ticked off my list for now, but not over entirely. To make the unique regions that I wanted to do, I will need to tweak the region spawning code to make some more unique circumstances. But, for now, it's all done!
I then quickly just added some collision scripts to our moving objects so that they actually react with this environment, and it works.
That's all I want to do for now, as there are some other topics to focus on right now.