Into the caverns we go!

Greetings, adventurer!

Today, we’re going to create some caverns. Correction, we’ll make the computer create these caverns for us. that’s right it’s randomly generated dungeons.

I want to make it very clear that there are many ways to do this. You can for instance use TinyKeepDev method. There is also this fantastic presentation by Zach Aikman of 17-BIT, which I highly recommend.

We went for a fairly simple implementation. The first thing we did was to create a 2d int array map which hold either 1 or 0. 1 means wall, 0 means floor. We then fill it, using a fill percent variable which dictates the amount of wall percentage to fill in the array. Something to note is that we want a special if statement to cover the borders, such that the cavern has borders. Moving on, we now  have a 2d array map[x,y] with 0’s and 1’s.

What do we do with it? We then run it through a modified version of Conway’s game of life in order to smooth the map a couple of times and we only need to draw the map. We now have a map with potentially many different spaces. In this context we define a space as an area of floor tiles.We need the largest such space and to do that we run a depth first search where each tile is a vertex. Now all we need is spawning “stuff” (monsters, treasure chests, etc…) and we’re done.

Now into some detail and code.

Let’s start with the creation of the map.

createMap

Now, you might think that this randomiser is an overkill, but well… Why not? Anyway, the principle is simple.

for each pair of coodinates x,y :

if map[x,y] is a border -> make it a wall n make it a wall

else -> if it’s below the fillPercent variable, make it a wall, else make it a floor.

Earlier I mentioned The Game of Life, here it is.

smooth and getAdj

Now that we have a map, we need to determine the largest space. It’s a very standard implementation of DFS (Depth First Search) using recursion. You can use stack as well. However we also need to loop through the graph.

runthrough

I love traversing a grid like graph, it’s just so cozy and intuitive.

DFS

All we need now is to draw the map.

drawmap

The position is x*0.32, y*0.32 because we’re using 32 bit sprites.

That’s all for today, hope you found this educational and and enjoyable. I actually over complicated things a bit, however I did so because I wanted a set of features like storing the most southern tile in the largest space in a cavern as a spawning point for the player, much of this could be done in far simpler manners if your game doesn’t need the same features as ours.

Best Regards

p219 Development Team

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s