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" we will add 1, to our code, if second cell - add 2, third cell - add 4 and fourth cell - add 8.

Basically, we have next algorithm:

For i from 0 to height -2

For j from 0 to width - 2 do:

1. If cell[i][j] == 1 then additionalGrid[i][j] += 1

2. If cell[i][j + 1] == 1 then additionalGrid[i][j] += 2

3. If cell[i + 1][j + 1] == 1 then additionalGrid[i][j] += 4

4. If cell[i + 1][j] == 1 then additionalGrid[i][j] += 8

Now we can align every of 16 possible values to some correct tiles and instantiate them according to additionalGrid. Enjoy the result!

Results and perspectives

There are several consequences of this implementation of marching squares:

1. Your map's size will be less by 1 both on width and height (you can fix it by additional recalculating for last row and column)
2. You need to draw more sprites for walls
3. You can easily implement destructible walls by recalculating all walls' codes near with destroyed wall
4. It makes your map prettier

So, I hope this article was useful for you. Cya later!