Overworld Overview - Part 2
In the previous post in this series we saw how terrain is generated and how the procgen system decides each area in the world will be connected, which controls the progression of the player through the game. In this post I explain how the contents of those distinct areas are filled. As mentioned earlier, while Binding of Isaac and Spelunky use hand-designed templates to generate this content, Lenna’s Inception takes a different approach.
Spatially-aware room content generation
This part of the procgen system is aware of the spatial relationships between objects. By formalizing (making strict machine-readable rules) the constraints each kind of tile places on its neighbors, the system can choose where to place randomized objects without breaking the game. As an example rule, a cracked rock requires floor next to it so that a bomb can be placed there. If it was placed next to some water, the bomb would sink and not blow up the rock. The system understands this could prevent the player from progressing and will not by default put water next to cracked rocks.
Characterizing tile properties
The spatial-awareness library has a list of rules like this for many kinds of tiles. The important part is that the rules all involve properties of local tiles - ones near the tile in question - so that checking the validity of a new tile is really quick. The locality of these properties means the system is limited to mechanics such as bombs and jumping that affect nearby tiles, and can’t do hookshots for instance, which transport the player a long distance. (Actually I have some ideas about how to do that using graphs, but it’s more work than I wanted to do for this project. Contact me if you’re thinking of doing this.)
The properties of tiles we care about for the mechanics in Lenna’s Inception are:
- Whether an item (and which) allows the player to pass this tile. For example - no items allow the player past ordinary walls; and bombs allow the player to pass a cracked wall.
- Whether a tile provides floor to stand on or to drop an item on after it has been dealt with. For example - a cracked wall becomes a floor tile after it is blown up, while water tiles do not let you use items on them even if you can swim.
- Whether the tile requires an adjacent floor tile in order to deal with. For example - to cut a bush you must be able to stand when you're next to it, so ordinary floor is OK, and so is a cracked rock (since after you destroy the rock it becomes floor). But putting a hole next to the bush is likely to mean the player will lose health due to not being able to cross the hole fast enough while using the sword.
- Whether the tile requires a second adjacent floor tile for the player to land on "on the other side." This is mostly for the hole tile. The player can only jump a certain distance, so the system cannot place a long row of holes and expect the player to jump them all in one go.
At this point, the positions of walls and doorways, and the shape of the room have already been settled.
Here, the purple area is a masked-off part of the map, not part of the room we’re generating. The gray tiles are walls (whether they’re tree, rock or cliff is irrelevant), and the white tiles are all just generic floor right now.
There are three exits from this area - through the top of the screen, through the left side, and through the door in the center at the bottom.
Besides the positioning of doorways into adjacent rooms, the room generator has an extra requirement imposed on it from the lock and key generator. There are no corridors between rooms, so the locks that were chosen earlier have to be placed inside the room.
We can automatically put the locks right by the door. That’s relatively simple to code, if not very interesting to look at and play:
These colored tiles are the tiles for the locks that the lock and key generator assigned to this room’s exits. From top to bottom, we have:
- Blue - water, for which the corresponding key is the Fish Leather Shorts (these allow the player to swim).
- Brown - cracked rocks, which the player can destroy by placing bombs on the floor next to them.
- Green - bushes, which the player can cut with a steel sword.
It might not be a very interesting room, but we do know that the player has to use the sword to get through from the bottom, the bombs to get through the left etc., which is what the lock and key generator wanted.
One way to make it more interesting is to repeatedly modify the contents of this room in a way that doesn’t change the items the player has to use. In Lenna’s Inception, I do this in a way that is a bit like simulating bubbles growing into the room. Programmers might recognize this simulation as being a cellular automaton:
You’ll notice here that the brown and blue bubbles stopped expanding into each other early and left a gap, whereas brown and green finished up touching. Each step in the expansion checks that its modification wouldn’t violate the properties of the nearby tiles.
In the case of:
- Water vs cracked rock: putting these next to each other would violate the rule that the cracked rock has adjacent floor for the player to drop a bomb onto.
- Water vs bush: the same applies here. There needs to be floor next to the bush so the player can stand on it and swing their sword.
- Bush vs cracked rock: both of these require floor next to them, but after dealing with one of them (bombing or cutting it down), it becomes floor and the player can deal with the next one.
Preventing open spaces from being bisected
Even after all this, we can still end up with a situation where one of the bubbles has bisected (cut into two) the space in the room.
Here, a bubble for the water lock on the left hand side of the screen has expanded all the way over to the right hand side. This prevents the player from passing through the screen in the North/South directions until they have the fish leather shorts, which wasn’t intended by the lock and key generator.
It’s possible to solve this problem the smart way by looking for graph partitions, but another solution that works just as well (and can be written in just a dozen lines of code) is to check if neighboring walls of the tile you’re editing are all touching.
Along the top row of examples here, placing another blocking tile - whether wall, water, bush or cracked rock - cannot split the open space in two, because it’s either (a) already at a dead end; or (b) surrounded by open space.
The bottom row shows example cases where adding a blocking tile to the center could end up dividing the open space due to there being non-contiguous blocking neighbor tiles. Placing a blocking tile in the center of these doesn’t guarantee to divide the open space (there could be another way around the obstacles). But not placing a tile there does guarantee that we won’t divide the open space.
The difference between the top and bottom rows is that: along the top row, all the neighboring wall tiles are touching, while on the bottom row there are non-touching neighboring walls.
This works as a way to avoid bisecting rooms as long as you’re adding the blocking tiles one-by-one.
Note that if we know the player will gather the keys in a particular order, we can allow some bubbles to overlap. If the player collects the sword, and then the bombs, and finally the fish leather shorts, the following room is legal, and more interesting to play:
If we do this however, we do have to run a search algorithm such as A* afterwards to make sure it hasn’t violated any of the rules, and potentially throw the room away and start again.
The empty spaces inside bubbles can be filled with special landmarks, such as buildings and dungeon entrances.
Alternatively, they can be filled with another randomization algorithm…
Seeding and spreading
Seeding is adding randomly-chosen objects to an area in a small amount, in a random position. A few parameters can be used to make it look more interesting: placing them near walls makes them look more natural; the choice of tile can be influence by the biome; and the amount of seeding can be varied depending on how chaotic we want the area to look.
Area before seeding:
On the left, the area has been seeded with chaos=20 as a parameter. On the right, it has been seeded with chaos=100:
The randomly chosen objects are placed into the area in rows and columns of three, because that seemed to give a subjectively more attractive appearance.
These seeded tiles can be spread out over a larger area into a random shape. This is really straightforward: we pick an obstacle tile and copy it to a random adjacent floor tile if it is safe to do so.
The same rooms as above with chaos=20 and chaos=100, but this time spread out:
Not much has changed on the right because to add much more to the area would start closing off paths. To know when it is safe to place a new blocking tile, it uses the same “open space bisection detection” checks as before.
And that’s it! More or less. You now know how the hard parts of overworld procgen work in Lenna’s Inception. There are some details I’ve skipped over - such as how to make sure there’s enough space in a room for all the locks; how to make sure that moving between screens doesn’t leave the player standing on a wall; etc. But those are just coding tasks - there’s nothing particularly smart about how I solved them.
I hope you found this interesting, and if you have related procgen projects, I hope that you found it useful as well! As I mentioned in the previous post, I’ve released the source of a Java implementation of the lock and key generator. If you’re not a fan of Java, @allinlabs has ported to Haxe, which is perfect for jam entries. (He’s even provided a neat online demo of it.) And of course, time permitting, I’m happy to answer any specific queries you have about any of this - [twitter] [email].
You can support the development of Lenna’s Inception (and my procedural generation projects) by purchasing it here or here:
Not all of these links are directly related to the procgen in Lenna’s Inception, but if you found this series on procedural content generation interesting, you will also like these:
- Previous posts on procgen in Lenna's Inception
- The Binding of Isaac gameplay explained
- Spelunky Generator Lessons
- 300 Mechanics #004 - Environment Tree
- 300 Mechanics #054 - PCG World
- Procedural generation in Dwarfcorp
- The Saturday Paper - A World Just For You
- Learning From The Masters: Level Design In The Legend Of Zelda
blog comments powered by Disqus