World Generation for Top-Down Survival Games

Table of Content

1. Introduction

1.1 Inspiration

For forever I’ve had a great liking for open-world games, like most people my age I’ve grown up with Grand Theft Auto games. The world’s Rockstar Games made for those games are massive yet still very beautiful. I always loved driving through the world to just explore but even back then I always imagined what it would be like to build my house in GTA San Andreas’s forest or build a tower in the middle of GTA 3’s city.

Then a little game called Minecraft was released. Minecraft must be my first introduction to a procedurally generated world. I spent hours building houses on cool cliffsides, on beaches, and in forests. I was amazed by how the world seemed different every time I played, I couldn’t understand how a game could do something like that. This game is what lit the flame that is my love for survival games.

Fast forward to this semester, where we had to do a small assignment about procedural generation. I loved doing the assignment but it wasn’t enough to satisfy my thirst for knowledge, I wanted to know how to make a world out of nothing but air. When the lecturers announced that we were allowed to choose our own research subject I knew immediately what I wanted to research, Procedural World Generation for a survival game.

1.2 Scope

The scope of this research was very difficult to imagine. I wanted to make the biggest most beautiful world imaginable due to my love for survival games. Obviously, that wasn’t going to happen… Might be because of my lack of artistic skills or just due to time constraints, but I was pretty sure I wouldn’t be able to create anything remotely good-looking. Though it is worth a shot!

The least I wanted to create was a world that is randomly generated with two biomes. Obviously, these biomes need to have some filling so they also need to have some kind of resource spawning like for example trees. But then we run into another issue, trees don’t spawn in the desert so I would need to make some sort of object pool from which each biome can take its resource spawns. It would also be cool if each biome has different enemies like mummies in the desert and golems in the mountains, but now the scope might get a little bit too big.

To sum it up, the project has to procedurally generate a world with two biomes with each their own resource spawns. This world has to be different than the other but you should be able to get the same world each time when using the same seed.

1.3 Goal

The goal of this semester is to learn about the different types of procedural generation algorithms and which one would be most suited for my games. But also to try out some more unorthodox ways of procedural generation. I want to be able to divide the world into chunks for better performance and want to learn how to have different objects spawns depending on in which biome this spawn happens.

To be able to check if I have reached my desired end result I’ve set up four goals to reach, similar to how the assignments worked at the start of this semester.

1. Easy – The player can generate a world with resource spawns in two-dimensional space.
2. Medium – The world has multiple biomes, these biomes have their own resource spawn pool.
3. Hard – The world has a smooth transition between each biome.
4. Extra – The world has monsters, these monsters have some form of pathfinding through the procedurally generated world.

To define my goal as clearly as possible, if I manage to reach the fourth goal Extra: I want to create a prototype of a procedurally generated world in two-dimensional space that has multiple biomes. Each biome has its own pool of spawnable resources and a pool of spawnable monsters that roam around the world with pathfinding. The biomes have a smooth transition between each other to avoid sudden changes in scenery.

2. Research

2.1 World Generation Algorithms

The first major point of this project was to generate a world, obviously, but how was the question? There are many different algorithms to tackle this problem but which one would be the best? The first obvious choice would be Perlin Noise. Perlin Noise is an algorithm developed by Ken Perlin way back in 1983 and formally published in 1985 in a SIGGRAPH paper called An Image Synthesizer(Perlin, 1985).

Perlin Noise is a useful tool to use while creating games or other visual products like movies. In game development, Perlin Noise can be used for all sorts of wave-like uses. For example, it works great for world generation, water, fire effects, and loads more(Understanding Perlin Noise, 2014). Perlin Noise comes in many different forms, from one-dimensional all the way up to four-dimensional, although the use of the fourth dimension does not pop up often. In our case, we would use two-dimensional Perlin Noise but three-dimensional is used often in world generation too like for example Minecraft-like generation.

What makes Perlin Noise such a useful tool is that each point has a similar value to its neighbors. Due to this, you can make beautiful smooth height differences. See the image for an example taken from the meshes assignment earlier this semester. I won’t go into the mathematics of this algorithm but the source “Understanding Perlin Noise” from the paragraph above does a great job explaining how it works.

Now is the question, would this work for my project? No, not really… Now let me explain, while Perlin Noise is awesome and works great for procedural world generation I won’t be able to make full use of it because my project will be in two-dimensional space. Even though I am not going to use Perlin Noise for the world generation it could still have other users later down the line. For example, adding beaches to biomes that are adjacent to water biomes or adding variation to tiles in biomes by placing other tiles in certain positions.

Luckily not too much research later I found an algorithm from which I am not entirely sure what the name is nor who invented it but it looked promising. According to the website I used it’s called “Grown Biomes”(Generating Terrain in Cuberite, n.d.).

This algorithm is rather interesting, it takes a small 3×3 square where on each point you place a different biome. Now you zoom out this square and fill in the gaps. With each interaction the square doubles in size minus 1, so 3×3 becomes 5×5, which in turn becomes 9×9, etc. This will create a more complex world every time you zoom out.

This algorithm could work for our project, though you might run into issues when there are more than 9 biomes due to the 3×3 start size. This algorithm sounds very interesting and is something unorthodox, so I decided to choose the Grown Biomes algorithm for my world generation.

3. Features

3.1 Base Features

3.1.1 Procedural World Generation

As said in the research, to start using this algorithm you need to have a 3×3 square. The easiest way to do this was to use an Integer two-dimensional array. Each integer is connected to a certain biome, for example, zero is a water biome.

In this case, I’ve decided to make it so that the lowest integer is also the lowest point in the world.
Int Zero = Water Biome (e.g. The Ocean)
Int One = Sand Biome (e.g. The Beaches)
Int Two = Tree Biome (e.g. The Forest)
Int Three = Rock Biome (e.g. The Mountains)

I can add randomized biomes in the future but for testing purposes let’s keep it simple.

Now let’s add a small visualization so we can test this properly. Obviously, this is bound to change in the future but for now, let’s use 3D cubes.

First I use a simple extra protection check for if there already is a tileParent (in case I want to regenerate a world in run-time). If that is the case, destroy this GameObject. After this check, we create a new tileParent GameObject.

Now I have to loop through the 2D map array, for this, I use a two-dimensional for-loop. In every iteration of this loop, we spawn a new cube on the same location as the position in the map array. So when the loop is at X=1 and Y=2 this will spawn a cube at (1,0,2). Note that I use the Z axis instead of the Y axis for the top-down view. It grabs a cube from the tiles array with the value from the 2D map array.

Now let’s take a look at the result:

Beautiful! It almost looks just like Minecraft! But for real, this is a big step from nothing to something. But no matter how great this is, it’s still very small… Let’s fix this.

3.1.2 Array Zooming and Smoothing

So I talked about how this algorithm zooms the array out and uses math to fix the gaps, sounds easy no? Well, I’m no math expert so this really broke my brain.

First of all, I need to create a new map with the new size. As you can see we take two arguments with this function, the current smaller world and a sample size (aka how big do we want the new world). We create the new world array with a width and height of the given sample size, which is the old world size times two minus one. In the case of a 3×3 world we do 3*2-1=5, The new world has a size of 5×5.

Now we loop through the old world array and set all the tiles present in the old world array into the new world array. But very importantly, not in the same spot but in the spot times two. So the first tile will end up at the second spot and the second tile will end up at the fourth spot etc. We do it like this for one so that the algorithm works and two this way the biomes can grow instead of us generating new biomes at the far end of the world with each iteration.

So now technically we should have a bigger world, let’s take a look:

Okay yes, this works, we do have a bigger world but it’s still quite wet. This is because every value in the array that we don’t populate manually gets a default value, which is in the case of an integer zero. If you remember we bound the integer zero to a water tile so that explains the water everywhere. Now we can get into the mathematical part, filling in the gaps.

Mathematically I don’t fully understand this but what this does is it checks if the current tile is an “empty” tile that needs to be filled. If it is, the coinflip function returns one randomly chosen argument back. So in the first case, we give the function four tiles from which we get one back and set the new world tile on (x,y) location to this tile.

Now with this implemented, we should have a world that feels less like Atlantis and more like an actual island. Let’s take a look:

Exactly what we wanted! It should even work if we do it multiple times.

As you can see it works perfectly, the only problem is that it still looks so blocky… But luckily for us, there is an algorithm to smoothen things down.

First, we have to loop through every tile yet again, and for each tile, we get its neighbors. As you can see in the comment section above the code, we assign each neighbor by first checking if they are still in the bounds of the array. If this is the case, we set the integer to that tile, otherwise, we set it to zero to avoid out-of-bounds exception errors.

Now that we have set the neighbors we can do our calculations. If the tiles above and below the player are the same, as well as the ones to the left and right, then pick one of these two tiles to become randomly. Otherwise, if just one of these is the same, change the current tile to that tile. Else if none of the tiles is the same as their opposite, the tile stays the same.

Now let’s take a look at the results.

After a few iterations of smoothing and the map already looks a lot less blocky!

3.1.3 Biome Generation & Resource Spawning

There are many ways to make biome generation and resource spawning but the easiest way I found was by using the unity tilemap and a custom script Tiledata that keeps track of all data a tile should have. Switching to a tilemap also increases the performance over using three-dimensional cubes because it has much less to render.

Switching to Tiles is much easier than I expected at first. At first, we create a new instance of the tilemap and, if one is found, we destroy the previous one. After this, we simply loop through the generated map(two-dimensional int array) and set the tiles in the tilemap equal to the generated map.

Now that we switched to a Tilemap we can start making the TileData script(Shack Man, 2020). The TileData class is rather simple, it just keeps track of everything a tile must know.

The TileBase variable keeps track of all tiles that should be considered in this biome, so every different tile of water. For now, it’s just one tile because we only have one sprite for each biome.

The BiomeType variable keeps track of which biome this is, this is an enum with four values(Water, Forest, Desert, and mountain).

The boolean canSpawnResources is pretty straightforward, it keeps track of this certain biome can spawn resources. For now, all of them can except the water biome.

The last two variables(resources and resourceDensity) are also very self-explanatory. the resources array is an array of which resource objects can spawn in this biome and the density float keeps track of how dense the resource spawn is in this biome.

As you can see, above the class I added a line “[CreateAssetMenu]”. This line makes it so that you can right-click to create a new instance of this class in Unity. After creating four of these classes, one for each biome, and filling them in with the correct information we can start assigning the TIleData to the TIles. Assigning the TileData to the tiles is as simple as looping through all TileData instances and adding them to the dictionary DataFromTiles with the corresponding tile as key.

Now to spawn the resources.

First, we create a new object, this is to keep all resources in one place and not flood the Unity hierarchy with objects. We have to loop through each tile and get data from each tile and check with the resource density if it can spawn resources. If either due to canSpawnResources being false or due to the resourceDensity with a random number is false the loop will continue to the next tile.

If it did get through both those checks it instantiates a random resource on that tile with a slight offset to make it seem more natural. Then we disable the object, this is for later while making render distance.

Now let’s take a look at the result!

It works like a charm, thanks to the youtube channel Shack Man and his video!

3.2 Extra Features

3.2.1 Chunking

Obviously, rendering every tile and resource constantly will drain your computer’s performance really quickly. To combat this we will implement chunking and render distance. Let’s start with chunking first!

I had to do some thinking first, what do I want a chunk to keep track of? Obviously, it got to know which tiles are in the chunk. It would be beneficial too if the chunk knows which resources are in it and probably would be useful if it knows which chunks are its neighbors. Let’s make a new class with these three variables.

Now we need to create the chunk instances. Each chunk has a size of 16×16 tiles. Of course, it is possible that the world gets generated in a size not divisible through 16, therefor when creating a new array we round up to the nearest number divisible through 16. Then we fill the array with chunks. After this, we loop through all tiles and add them to the correct chunk.

Remember back when we create resource spawns it had a line at the end which I said is for chunking. This line adds the resource to the chunk. The function it calls does the same as the AddTile function, it adds an object(in this case a resource) to the end of the array. But because you can’t just add an object at the end of an array we need to duplicate and create a new array which is one object bigger than the previous array.

Getting the neighbors is as easy as can be. I create a List of chunks and loop through each chunk and check if there is a neighbor, to begin with. If so then add it to the list. At the end, we convert the list to an array and return that array.

3.2.2 Render Distance

Now that each chunk knows who their neighbor is adding render distance will be a cakewalk. First, we gotta figure out which chunk the player is in. The GetChunks function returns the two-dimensional array in which the chunks are saved. With a simple check if the current chunk is not the same as the new current chunk we set the previous chunk to the current chunk and the current chunk to the new current chunk.

Now that we know in which chunk the player is we can start messing with the rendering. One thing I found out here is that the TileMap already has its own render system where it only renders tiles that are on screen. This is great because this saves us a lot of work. We still have to manually render the resources though. We turn off all the resources in the previous chunk and its neighbors and enable the resources in the current chunk and its neighbors.

Render distance is done through nested functions. I keep recalling the RenderResources function as long as there are neighbors and the render distance is not zero. Each time I call this function I give the render distance minus one.

After all this work we obviously have to check whether this works or this was all for nothing.

It works perfectly, even when we move it only renders the tiles it needs to render.

3.2.3 World Loading

A big downside so far is that the initial start-up takes a bit of time… To combat this I want to save the world and the seed so that it doesn’t have to generate the world each time we start the game. One spoiler, this did not increase boot time by much…

First of all, we need to create a class that keeps track of everything that has to be saved. As I said before, we want to save the seed and the generated world. The seed is a simple integer and the generated world is a two-dimensional integer array. In the constructor, we set the seed and worldMap to the values we got when making a new SaveFile instance.

Saving and loading a file is pretty straightforward and doesn’t require a lot of explanation. We have to set a location on our PC to save the file to(note that if any of the folders is not present the save/load will crash). To avoid accidental changes to the saved file which would make it corrupt we encrypt and decrypt the file on save and load respectively. When we load the save file we need to make sure the game reads it as a SaveFile(our previously created class) to avoid corruption. This is why when we define the saved variable we tell it to deserialize as a SaveFile class by adding (SaveFile) in front of the deserialize function.

Now before generating a world we check the save file if the seed is equal to the current seed, if so then load the map. otherwise, generate a new one.

4. Conclusion

My goal was to research procedural survival world generation with which I am very satisfied. I have learned a lot and even improved in some areas.
If we go back and take a look at the goals I set at the beginning of the research:

1. Easy – The player can generate a world with resource spawns in two-dimensional space.
2. Medium – The world has multiple biomes, these biomes have their own resource spawn pool.
3. Hard – The world has a smooth transition between each biome.
4. Extra – The world has monsters, these monsters have some form of pathfinding through the procedurally generated world.

I can say with 100% certainty that I at least managed to get the Easy and Medium goals. The world gets generated and there is a resource spawn pool that is different for each biome. Even though I did not manage to get either Hard or Extra I did do a lot of extra other features that are not in any of these goals for example render distance and world loading.

I will definitely continue developing this project and create a game with gameplay and add the features I did not manage to add during the research period. There is also a lot of improving to do, for example, I loop through each tile many times during generation. I need to find a way to only loop through these tiles only once, this will improve performance dramatically. Also, the way I render chunks now is very inefficient. First I de-render all tiles and then I render the new tiles while tiles that are neighbors of both the previous and current tile could just stay how they are right now.

But in the end, I am very happy with what I have done and could not have wished it any different.

Thank you for reading my research. 🙂

5. Sources

Leave a Reply

Your email address will not be published. Required fields are marked *