Procedural Map Generation with Godot — Part 2
For previous articles, visit https://medium.com/pumpkinbox-blog/procedural-generation-series
In the last post, we setup a basic project for procedural generation, created a random walker, and let them loose on the world. The result was not consistently satisfying though, and the key in procedural is, well, consistency.
By the end of this article, we’ll achieve the following result:
You want to be able to generate a randomized outcome every single time, and you want that randomized outcome to be constrained enough to look good, consistently. So what happened with our random walker? At some iterations, if not most iterations, the walker seemed to traverse a blob of floors over and over again due to its completely random nature. So how can we fix this? Here, we have to be creative. It can be avoided in any number of ways, and here are a few simple ones just to demonstrate how easy it is to come up with solutions to such problems:
1. Tendency to Preserve Direction
Force the random walker to walk a certain number of steps in the same direction before changing directions (5 in this case). The code simply keeps track of the previous direction, and the current number of steps. Note that the new direction could match the old direction, a feature we might not want.
An interesting variation of this, is to simply plug-in some randomness. Instead of the walker having to walk a certain number of steps, make it a random number of steps, between 1 and 5 for example. But the thing is that, if the map generated is far from what we’d like, then fine-tuning this tiny part of the algorithm will not fix the bigger problem. It is for this reason that we postpone all fine tuning till the end, until we can consistently get a grid that fits our expectations.
2. Get Some Friends
What better way to drunkenly explore a huge field of grass than to get more drunk explorers? By drunk, I’m referring to the random nature of the walker. Due to randomness, the explored areas are usually very specific, and a large portion of the grid is left undiscovered. To remedy this, we can create a list of random walkers, and progress each at every iteration.
This seems to create some more interesting paths, like one going upwards the other downward, and then they meet up at some point. So we successfully added some variety, but things are still clumped around the grid start point. Translating this into our analogy, the explored area seems to be clumped around the starting point of all the explorers, which makes sense. We’d directly think of spreading those explorers across the grid! The tiny issue with that is that we might have unconnected areas in that case (i.e. some explorers might never cross paths). This would force us to post-process the grid just to connect unconnected areas, which would take up time.
Reflecting upon the problem again, we have a group of explorers clumped around the origin, and they’re not getting very far. The maximum iterations limit is similar to their “energy”. When its depleted, they stop exploring. Now another idea pops up! What if, when one explorer got tired, another would take their place? In this case though, tired means our main loop is finished, so we don’t want that exactly, but the intuition behind this idea is that we can have explorers teleport in at random points, to one of the explorers’ positions, and start exploring from there. Imagine the explorer had a bunch of tiny explorer robots in their pockets. As they went along the path, at random points, they’d release a tiny robot into the wild, to explore some more. Now imagine that the tiny robots in turn had robots of their own, that they could release. This should create a larger explored area while also keeping the graph connected, as any robot would be starting from an already explored path.
Let’s spawn one walker to begin with, then with random chance, spawn another at some random point in time, starting at the main walker’s position and exploring from there.
At this point, let’s explore this solution, tweak some of the values, because it seems promising. It’s no longer clumping at the origin, but its exploring a little too much of the map I’d say. Let’s try to minimize that by reducing the maximum number of walkers, and reducing the new walker spawn chance.
It doesn’t seem to be getting much better, which leads us to reconsider the source of the problem. It seems that the number of iterations we’re going through is too high. We could reduce that, but even if we did, we cannot guarantee that the explorers won’t have explored too much of the map. By “too much” I mean that I don’t like the fact that the map is filled.
3. Limit Explored Tiles
All our efforts for procedural generation to end up with just a background of tiled dirt? We wouldn’t want that. To limit the number of dirt tiles generated, let’s just stop iterating when we fill a certain percentage of the grid. To do that, we have to slightly change our code to check whether the tile is already traversed, or none of the walkers have crossed this tile yet. This way, we can count how many tiles were covered, and stop when the tile count covers a certain percentage of the total number of tiles. Filling X% of our grid, we get the following results.
Now this ensures that the walkers stop early enough so as to not fill the grid with tiles rendering the generation pointless, but this doesn’t solve all our problems.
One behavior that I’m seeing and not liking is still some clumping around the origin. This is probably due to the fact that the main walker spawns there, tries to walk up or left, but is limited by the boundaries. This automatically increases the density in that region, as the walker is forced to go left or down, as its attempts at going up or left fail, messing with our equal likelihood of going in any direction. Let’s try starting in the middle instead!
I won’t write code for this one, since all I changed is this one line:
This already looks much better, although the isolated clumps are a tiny bit annoying. The open areas in other parts can be tuned in the end by modifying our parameters. For example, if we mess with the direction change chance and lower it, we have less chances of open areas forming. If we increase that chance, we’ll have more open areas, since the walker is more likely to go in different directions than keep going in a straight . You can get an intuition for the effects of those parameters by thinking about them logically, and confirming your guesses by testing.
Let’s make things a little more interesting now. For every step each explorer takes, there’s a chance we’ll take them out of the map, unless they’re the only explorer left. This way, we’ll get abrupt ends for paths that are straying too far and a little less straight paths. In code, one walker has a chance of getting pulled out of the game in every iteration. We’ll limit this to removing just one walker per iteration, so we can still converge reasonably quickly.
This looks a bit better! It’s starting to look like an actual game map, with some key open areas, some hidden isolated areas that aren’t too far away, and reasonable clumping. At this point, we can start post processing in my opinion. That means adding in the walls, adding in decoration, maybe modifying the extents of the dirt floor, adding objects, AI, etc.
One last thing I did before post processing is adding a property to the walker class, to track how long each walker has been walking in the same direction. This allowed me to limit the length and frequency of occurrence of straight paths.
In the next article, we’ll be adding in the walls, going over some basic graph algorithms while changing the placement of dirt tiles, and seeing some much more impressive visuals! Follow the publication to stay posted!