Tagged as: cavegen

Unity Development: Procedural Cave Generation

Procedural generation has become a popular aspect of video games recently, with random number generation deciding things such as level design, powerup spawning and placement, and even more advanced systems like the AI Director in the Left 4 Dead series dynamically altering play based on random number generation and player performance.

In Left 4 Dead, when players do particularly well, the game will up the number of zombies that could potentially spawn to accommodate.

In this tutorial series, one of the community members from the Unity scene goes into detail about how to build a procedurally generated cave system, based off of a 2D Array which is used as a map. At the end of the tutorial series, there is no fully functional game, per se, but you will be able to navigate your generated map with a little red cube and collide with it properly, as some time is spent explaining how to make a collision mesh based off of the random generation results.

A look at the final product

A look at the final product

The generation starts off rather simple: It takes a 2D Array of a given size and populates it with either 1s or 0s depending on an input string (the seed). The tutorial goes into some depth about how to randomize the seed, albeit with one major mistake: It uses the Unity method “Time.time()” to determine the seed, which refers to in-game time. Thus, at game start the time will always be 0, hence the map generated will always end up being the same. To use the system time (a much better solution), the seed would need to look at System.DateTime.Now.ToString() instead. After a map is generated, we apply an algorithm to the map to smooth it out: For each tile in the map, fill it if there are a certain number of filled tiles around it, otherwise unfill it. The idea behind this algorithm is to see where patterns in the random generation lie, what tiles are all filed near each other, and use that to shape out the map.

A randomly generated map

A randomly generated map

After the map is generated and smoothed, then we need to clean up the grid so it looks cohesive instead of a few thousand squares combined together. To do this, the author uses the Marching Squares algorithm and applies it to the grid.

A map with Marching Squares

A map with Marching Squares

After Marching Squares comes the mesh to actually start making the grid into something usable for our finished product. This mostly extends the map along the Y-axis, to create walls where our edges are. After this we get to start editing the map some more – detecting regions in order to flesh out our “rooms” a little better, by removing any black or white spaces less than a certain customizable size. Next comes connecting these rooms. The author breaks this into two parts – part one just ensuring that rooms are connected, and then part two ensuring that all rooms are connected by using one single “parent” room and checking that each room is connected to it somehow – either directly or via another room.

All rooms are connected via passageways - the green line indicates where a passageway was made

All rooms are connected via passageways – the green line indicates where a passageway was made

And finally, the last part is spent making sure our collision mesh works by giving us a little player object and moving it about the grid. I have noticed two problems with this resultant product so far – the first being minor; since the player object is a cube and not all collisions are straight-on parallel, the cube starts spinning around rather fast once it collides into a wall. The second is rather major, though:

cave5

Yep, the map generator is completely independent of the player object, meaning that it can spawn inside walls, rather than caves. Because of the way the collision mesh works, however, it will still obey the walls present in the generated mesh, so in effect the map is inverted for our little cube friend here. The tutorial does not acknowledge how to fix this, though I suspect it wouldn’t be too hard to relate the cube’s position to a point on the map to check if the cube is somewhere “safe”.

And thus, we have a procedurally generated cave using nothing but scripts and a few materials. The trickiest part of this was actually generating the mesh – very time consuming and not a lot of immediate payout. However, in the end, this was still a good exercise in learning how to generate something using merely the time.