Kaiagan

This article is, in a way, the continuation of a previous one treating about looping maps.

Usually, when making a blocky game, we take advantage of the chunk-segmentated nature of the map to generate (almost) infinite worlds. The player can keep walking in one direction forever, they will never reach the end.

Sounds awesome, isn’t it? Well, is it really?

Are infinite maps possible?

First, we’re not really in a position here to debate about what ‘infinity’ really is (dozens of philosophers have done that for the past few centuries), but at the risk of appearing pedantic (there is no risk, really, I am pedantic 😀 ), ‘infinite procedural worlds’ are rarely truly infinite. More often than not, there is some – usually very large – limit of numerical precision in the data used to simulate these large worlds. Eventually, after holding down the forward key for several (real life) days straight, a player may actually reach the end of your map.

What happens then will depend on how your game is made. If the bottleneck is a precision issue, your player may encounter some strange generation shapes or, worse, crashes.

Do we even care?

Most computers now work with large enough data types to relegate this issue in the pile of ‘not actually an issue’: indeed, the maps can be so big that they are effectively infinite.

But I still asked myself, disregarding technicalities, if trying to have maps as big as possible even made sense…

The answer will vary per project, of course. In my opinion, procedural games with very large maps tend to overly rely on their procedural aspects. Building new worlds procedurally is awesome, but if the worlds themselves are poor, mostly empty or unintersting, making them infinite will just make them infinitely boring. And we don’t want that.

Procedural tools are just tools, and what matters is what we do with them. The procedurality of a game, or the infinity of a map, are not goals by themselves.

Is there any advantage to finite maps?

Yes. Many, many, many advantages.

First, if we already have a system allowing us to build infinite maps, we can easily just decide to limit the size of these maps. Boom. No extra work required, except maybe a condition here and there.

Everything you built in your infinite, super-mega-cool procedural generation code can work just the same with limited coordinates. But what can we do with finite maps that we can’t with infinite ones?

One obvious answer is pre-generation and aware maps. The intrinsic requirement for an infinite world is that you should be able to continuously generate new chunks of the world as you discover new places. This also means that you don’t need to (and can’t) know what will be in this chunk before you generate it.

Pre-Generation

This is quite a big limitation, when you think about it. What do you want to put in your world? Do you want to have named continents and countries? What if a continent only has a tiny bit of land generated? Is the continent aware of its full size? Is it even possible to know the full size of this continent, where it ends, which other continents are close to it? What about cities? Cities should be connected to each other with roads, right? How can you generate a road to another city if it isn’t generated yet? Where is it? Is there even another city connected to this one?

I could go on forever. All these problems can surely have very imperfect, hacky and frankly terrible solutions in infinite worlds, but they become much more approachable when dealing with finite maps.

As mentioned in previous articles, my world is subdivided in a few levels of ‘containers’: the map is made of regions, which are made of chunks (there are also cells, that come before the chunks, but it’s not too important in this matter), which contain the blocks.

Picking a ‘level’ of pre-generation

Pre-generating a map usually requires generating the whole world before being able to play. Obviously, if you want a map of a decent size, it is unreasonable to expect your game to be able to generate the full chunks, down to the block level. Not only it can take a very long time but, even when being careful, it can potentially take an absurd amount of disk space.

It’s also a bit dumb to go with this brute-force approach: the bigger your world, the less likely your players are going to be able to explore them fully, so why waste so much time trying to generate it with such degree of precision?

The actual answer will depend on your goals, obviously. In my case, I wanted to be able to make maps in which we can find:

• named continents, oceans, seas, lakes, islands, etc,
• semi-realistic erosion of terrain,
• semi-realistic rivers spawned from the heights and going to the oceans,
• artificial structures influenced by and capable of influencing the natural surroundings (cities, isolated buildings, monuments, etc),
• roads connecting some structures (cities, etc),
• bridges when roads need to cross rivers.

This list is non-exhaustive, but hopefully you can understand why having a pre-generation step is so useful for all of those things.

Above, I mentioned the region objects. I actually have 2 types of regions: the 2d regions and the 3d regions.

The 3d regions hold the 3d chunks (which eventually draw the blocks to the player) while the 2d regions hold the cells (which are abstract data holders representing a 2d location in the map).

If you take a look at the list above again, you might realise that these things can be achieve with a 2d approach: continent and oceans are binary (land = continent, water = ocean), erosion can be done on a heightmap, rivers can also be generated via heightmap, roads as well, the structures spawn location can be defined in 2d.

And this is great news for us because, as you get to work on 3d blocky worlds more, you will soon realise how much faster things are in 2d.

Having to pre-generate things in 3d, with 3d regions, could very quickly become a bottleneck. I have some plans regarding this (underground rivers, seas, caves, etc) but they will never be as important or predominant as the 2d aspects mentioned above.

So, for my project, I can get away with only pre-generating the 2d regions… and that’s it! For a target average maps of 4800 x 4800 chunks (reminder: chunks are 62 x 62 blocks in my game, in X and Y), with 2d regions of 120 x 120 chunks, this is a total of 1600 2d regions. This is nothing.

It’s so fast to pre-generate, that I even allowed myself to be a bit lazy and to leave a lot of stuff sub-optimised: the pre-generation cost is only paid the first time the map is loaded. So far I have implemented a lot of the above list (but not entirely), and the pre-generation for the whole map takes under 2 seconds.

Now, let’s go over a few examples of what I’m pre-generating!

Oceans & Continents

While it’s easy enough to detect whether any block is above or under an arbitrary ‘water level’ value (you don’t need pre-generation to infer that), what you can’t do with endless maps is identifying oceans and continents as whole entities.

A continent in yellow, with various oceans (green, grey). This is a very big scale with some preview meshes for the regions. In this view, we’re basically a plane high in the sky, looking down. The red areas are ‘coastlines’ (more on that later).

If you read the previous article, you know a few things about how I’m generating the biomes already. The region holds ‘region sets’, which are collections of points sharing the same biome. Based on the ‘domain’ of this biome (underwater or above water), I ‘floodill’ oceans and continents using connected region sets (it’s not really a floodfill, I’m using an algorithm like Union Find). This is much faster than having to connect region points one by one or, worse, block by block (as stated earlier: we don’t want to have to waste ressources generating blocks).

From there, you can do a lot of stuff to enrich your world. As an example, I can now detect whether an ‘ocean’ is completely enclosed by land. If so, I convert it to a ‘sea’ (and, if the total area of this ‘sea’ is too small, let’s make it a ‘lake’). All this data is saved as ‘macro entities’. Macro entities know about the region sets they contain, and can be treated as separate objects in the code, with their own methods and variables.

Something I could do with my oceans now, because I know everything about them (as I pre-generated all their macro content), is building some procedural currents and streams that make sense:

You can decide to change the composition of the water (salinity levels, is it actually water? why not make a petrol ocean? or an ocean made of honey? You can even mix these different compositions, for example using the streams and current mentioned above). Go crazy!

So, thanks to pre-generation, you just converted a boring flat piece of water into an actual ocean that has some semblence of realism (even if realism isn’t the end-goal of my project).

Furthermore, you can also set things up (as I did) so macro entities know about the neighbouring macro entities they should care about. For example, my oceans know about which continents they are touching (and vice-versa).

Continent Partitions

Continents are very similar to oceans in how they are detected. However, I intend to use different kinds of information with them, compared to oceans.

In our real world, continents are not necessarily separated by a piece of water. They may be connected by a piece of land (usually quite small compared to their total area).

This is what I’ve done: after the ‘true’ continents have been detected, I perform a ‘shrinking’ step. By virtually shrinking the region sets used to detect continents, I naturally create gaps between pieces of lands only connected by a few sets. I can then perform a new ‘detection’ of connected sets (my continent partitions) before growing them back to the initial size.

As you can see, most continents (areas enclosed in red) have multiple ‘partitions’ (colors). These partitions can be displayed as ‘continents’ in-game, or they can be of a different kind.

For example the light orange and light yellow partitions on the center left were originally a single continent. Now they’ve been separated into 2. And, by the way, I also take this opportunity to save the few regions sets linking these 2 partitions into an ‘isthmus’ macro entity, just in case 😉 . Who knows, maybe in the future some civilisation on my map will want to find a way to link two oceans, like humans did for the Panama Canal… It will be useful then, to know where the optimal crossing is!

As a side-note regarding these 2 partitions, notice the elongated grey-brown water entity in-between them. This has also been detected as being either a ‘sea’, a ‘gulf’ or a ‘bay’, depending on the size. But I digress…

Another example is the pink partition at the bottom tip of the big continent in the middle. This isn’t a ‘continent’ but a ‘peninsula’ entity. It’s only usefulness in-game is probably going to be being called ‘peninsula’ in maps that the player can look at. Not critical, but a nice touch…

Another example is all the flashy green entities you see in these pictures. They are too small to be continents, so they became simple ‘islands’. They know which continent they are logically ‘attached’ to, if any (some islands may be isolated in a big ocean).

Islands are also often generated in packs (in the screenshot above, you can notice many green areas). I’ve dedicated an extra step to detect ‘archipelago’ entities. Again, not critical but nice to have…

Don’t forget to make it loop!

If, like me, you are generating looping maps (the player can seamlessly return back to the beginning of the map when reaching the end), you should make sure your code and noises for pre-generation take it into account.

It’s exactly the same approach as for the chunk generation. This is also why I’m happy to have made a generic looping method for any kind of noise data (float). This was discussed in this video from this article.

Not sure how clear it is in the above gif (or if it is even playing for you), but we can see the map is looping correctly. For example the purple continent at the top right loops back as expected when the player moves to the left.

Coastlines

Another type of entities I’m pre-generating are coastlines. These are simply region sets (on land, not on water) where a transition between continent and ocean exists.

In all previous pictures, they are represented in red. They can be useful to force the biomes to be of type ‘beach’. Usually, with infinite maps (so, without the possibility of pre-generating), generating coastlines, beaches and shores is a matter of blind guesses and very rigid approaches.

Another use-case for coastlines would be to use them to define the direction crashing waves should be coming from. In the above image, green lines represent this rough direction. Yes, you could have waves come crashing to your beaches, in a semi-realistic fashion!

Note: macro entities (oceans, continents, lakes, islands, coastlines, etc) are independant from each other. You can have as many entities sharing the same region set, you’re not limited to one. For example, coastline entities use regions sets that are also contained in the main ‘continent’ entity.

The impact a macro entity has (or does not have) on the map is up to you.

Something that I’ve done with coastlines (and actually also with oceans, seas and lakes) is that they are increasing the moisture around them. This will have a direct incidence on the actual biomes generated around these locations (reminder: I’m using elevation, temperature and moisture to define the biomes). Have you ever played a procedurally generated game and encountered the dryest desert in existence just next to a snow-covered toundra? This is easily avoidable with pre-generation.

Rivers

Another big atrocity (in my opinion) commited by classic endless maps is the river situation.

They are usually generated in non-sensical places, in-between biomes or where the procedural noises were kind enough to give you a serpent-like shape, but this serpent-like shape really doesn’t go anywhere.

Again, realism is not a more noble goal than any other kind of goals for procedural generation, so I’m not saying we should only strive for ultra-realistic approaches. In fact, pseudo-random generation is an opportunity to build worlds that we can’t see in real life.

However, I feel like river generation being what it is in most procedural game is a matter of ‘good enough’ rather than a well defined process with a high degree of control.

As a very brief summary, real rivers are usually sourced from heights (mountains) and run down to the seas / oceans. Using our pre-generated approach, it’s easy to spawn ‘starting points’ in high elevation areas (on land) and use some kind of pathfinding to make them reach the coastline.

The above is a terrible example 😀 .

I haven’t had time to implement it yet, so I’ve just made a proof of concept with random start and end points for rivers. But hopefully you understand the benefit of pre-generating here. You could even make branching rivers, or secondary rivers spawned along the main rivers, etc.

The river being its own entity, it is of course aware of which region sets it is crossing, but also in which direction the water flows. We can even detect whether there is a ‘wall’ preventing the river from flowing (if the player ever decide to build a dam).

As for all other water entities, rivers also increase the moisture levels locally, so you will tend to see biomes with more lush vegetation around them.

Finite doesn’t mean small

As a ‘last word’ regarding this whole finite vs infinite maps debate, restricting yourself to finite maps doesn’t mean your maps have to be tiny. You can go big, as long as all the processes mentioned earlier are reasonably fast. It will be big enough, and it will almost certainly look better than a wild, purely procedural, unaware map.

So far, without making any effort to optimise my code, a 4800×4800 chunks map pre-generates everything in 2 seconds. 2 seconds that you will only ever pay once. The main difficulty remains in taking advantage of this pre-generation, in your code.

After the pre-generation is done, all entities are saved into a single file (a few kilobytes…) and can be loaded next time you open the same map. You don’t even need to save all the regions you pre-generated, the only thing that matters are the macro entities.

Finally, if you are still worried about not having infinite maps, or if for some reasons your pre-generation takes ages on bigger maps, there are other ways of achieving ‘infinity’.

You could develop a game where, while the maps themselves are finite, you can at any point ‘jump’ to other completely different maps. An inifinity of interesting finite maps.

Conclusion

I think I have been annoying enough throughout this article, constantly hammering how cool pre-generation is. But I will say it again: pre-generation is awesome!!!

This is just the baby-steps I’ve taken. Now that the pre-generation and macro entity systems are in place, I can implement a lot of features. Road generation is going to be very similar to the river generation, erosion is going to affect the elevation of the whole map, etc.

But for now I need a break from this pre-generation stuff! Like me, you may have been tired of seeing these grey blocks in the chunks meshes (although, today we showed some pretty colors!). Everything is in place to finally tackle block-level generation and bring some materials and visuals to these poor blocks!