Experience of implementing Cave Generator using cellular automaton

There are many algorithms of generating level maps. I wanna tell you about generating cave levels via cellular automaton

Getting started

So what actually is a cellular automaton? Simplified, cellular automaton is a grid of cells, each with one of different finite states. Cell's states are switching according to some set of rules. We will have "Wall" and "Empty" states. Initial states of cells would be chosen randomly. When generating caves usually use rules of these kind:
  1. "Wall" becomes "Empty" if there are less than X "Walls"
  2. "Empty" becomes "Wall" if there are more than Y "Walls"
X and Y characterize work of our generator. Some pairs of (X, Y) will lead to fast filling out of our map, some will lead to fast emptying. Moreover, on some (X, Y) we will have Game of Life.

Implementation

But we are here not to stare at entertaining cell's state switching forever. We can't let our map to be too full or too empty. So we need to limit our cellular automaton lifetime. I.e. we need to launch our cellular automaton only for T rounds.
Now we can characterize our automaton by three variables (X, Y, T). You can play with it (and with starting initialization) to find interesting results, but I use X = 4, Y = 4, T = 5 in Galactic Looter.

That's all? So easy?

Actually, no. The problem is that generated cave is usually disconnected. So we need to find all disconnected caves (rooms) (I use Floodfill algorithm) and connect them into one big cave. The simplest solution is to make all possible connections between rooms. But there is such problem: 
As you see on the screen connection between Cave 1 and Cave 3 goes through Cave 2. We can deal with by two ways:

  1. Start from one of the caves, add the closest one, than add the closest one to our already connected caves from the remaining and so on. It's called Prim's algorithm. 
  2. You can find all possible connections between rooms, find the shortest one between two caves, that are not yet connected directly or through other caves, make it, and than do it again, until there will be one big connected cave. It's called Kruskal's algorithm. 

So we have connected cave. Is it all? My answer is no, because this cave is a little bit boring: it doesn't have any cycles! Walking in this cave you will never go to place, where you've already been. We can easily fix this by doing more connections on each step of Kruskal's or Prim's algorithms, e.g. 5. So, on each step we have a chance to connect already connected cave and make a cycle.
Making all these steps I have caves, like this one (some tunnels are blocked by destructible walls):

Conclusion

I hope, this article was helpful for you. If you first time hear about some algorithms, you can find more on next sources:
Also, I recommend you to read the book of Th.Cormen "Introduction to algorithms".
Bye!

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

So, it's the first post about game.

Изображение
At first, I should say, that I'm not just started development. I work on it since summer 2019. But I had a laaaarge breaks, coz I'm student and I'm lazy. So what do I have now?  Map generator! I use cellular automaton cave generator with simple rule: cell type (floor or wall) is chosen according to it's neighbours. It works for 5 rounds and then connects caves into one big cave. You can read more about it in this article . Enemies! Yet just one type of simplest enemies: they are randomly spawn on their spawnpoints (that are instantiated in map-generating time), fly towards you and shoot, when you are too close. I use BFS algorithm to find path from enemy to player and let them go, when player in detection range. On this screen you can see enemies (red-black ships), player ship (drawn by my friend), enemies path (red lines) and their current direction of movement (green lines) Editor! A little bit chunky, but actually it works and I can load level...
Далее...

Marching squares in 2d tile-based game

Изображение
Marching squares - is an algorithm that can generate contour for scalar field (only two-dimensional, for three-dimensional you can look at marching cubes , it has the same idea). It's usually used in computer graphic. Why do we need it? So, let's assume you've generated map as grid of "walls" (we will call it as 1) and empty cells (0). If you'll start placing square tiles at this positions, you will get something like this It could be acceptable for some kinds of RPGs or even strategies, but when you have smooth and fluent gameplay you will stumble on corners of your squares. So you need to make your map smoother. And that's where you need marching squares. Look at the difference: That's how my game looks now: Implementation So, as I said previously, we have a grid of zeros and ones. We can encode every four neighbour cells with four bits, each of them will contain value of corresponding cell. So, if first cell contains "1...
Далее...