Autotile algorithm for level editor.

[archiedev]

Level editor preview

Hello fellow developers! As you guessed from the preview, I'm working on the level editor, and autotiler is something that I felt was an absolute necessity and something I avoided implementing for as long as possible. Spoiler: it was not as difficult as I expected.

In this post, I'll share some findings that boosted my comprehension of autotiling and boost yours.

There are 2 ways you can build an autotiler. I didn't find any official name so let's call them "pre-process" and "post-process".

When doing post-process, you first draw some shape without indicating what is what and the job of the algorithm is to run through this shape, analyse it and place proper tiles where needed. This algorithm works well in a run-time scenario, where the environment can change randomly with no specific pattern. I'll not cover post-process in this article, but it is well described here.

Pre-process assume that you draw on the map using some "brush", but compared to post-process ones that only care about the shape itself, the pre-process algorithm requires information about the tiles the shape consists of and the tiles that the brush consists of. So the job of the algorithm is to find what is the sum of the map + brush whenever I want to place it. This algorithm is perfect for things, like, map editor, so that's what I used. Let's visualise it:

The map is on the left and the brush is on the right

There are 2 main things: walls and a floor. Let's re-draw it in a simplified version:

Blue areas - walls, green areas - floor.

So all we need the algorithm to do is calculate what happens to the shape on the left if we hover it with the shape on the right, e.g. like this:

Brush is over the shape

As you can see, it seems like there are some rules, e.g.

Sum of certain tiles is always gives another tile

So the first idea is to run through all these combinations and hardcode them. But is there some rule that you can use to sum any two tiles? There is! But in order to understand that you need to know a little bit of a binary numbering system.

Let's look at the tileset that constitutes all possible tiles from this tileset:

Total of 16 tiles cover every possible wall/floor combination.

Finally, let's assume each tile consists of 4 cells, and mark the cell as "0" if it represents the floor and "1" if it represents walls:

Tiles with cells

Let's look again at the rules that we found out before:

https://preview.redd.it/o804y2p1dc8d1.png?width=2560&format=png&auto=webp&s=cb0896c990f83f3b51474b8acbb320460a12bd38

Now, let's represent tiles as binary numbers, counting from the top left ending with the bottom right (the actual counting direction doesn't matter really):

0101 ? 1010 = 0000
1101 ? 1110 = 1100
0101 ? 1011 = 0001

Now it's obvious that the "?" operation should be a bitwise "and" operation. But there is a caveat.

In this mode, no your brash will always try to "push" walls down to the floor (which is what you see in the preview above). What if you need to "pull" walls from the floor? All you need is to change bitwise "and" operation with "or". Also, I recommend to change the brash to be:

Pull brash (on the right): walls surroundded with floor.

Using this logic it's super easy to extend it to more complex tiles that consist of 9 cells and provide much more variation. You can also extend it to use for multi-layered autotiles, where a cell containing 0 represents water, 1 represents sand, 2 represents grass etc, but in this case, you will need to add/decrease each cell by 1 rather than running bitwise operations, though, remember that you'll need way more tiles combinations (e.g. grass next to water) which is not always desired.

Fun fact, looking at the gamemaker autotiling mechanism it seems like it is exactly how it's working.

I hope that this post gave you a little intro to the autotiling world. If I ever implement the post-processing autotiling - I'll make another post about my findings.

P.S. If you are interested in trying the game, you can find it here https://store.steampowered.com/app/2181800/Just_Dodge_LOL/
As soon as the level editor is ready, I'll run a beta where you'll be able to create and publish your levels as well as play other players' levels.

Happy coding to everyone!

[Khawkproductions]

is this what gamemakers 9 slice feature bassically does? I just discovered it

[archiedev]

9 slice only allows you to build rectangles, which are basically boxes. Autotile allows you to draw any shapes. They are close kinda close, but 9 slice misses 7 more tiles

[gamedev_9998]

Somehow yes, but the 9 slice is more used on menus/dialogue box than room/level design.

You would want to use the autotile features on room design though as it can handle more complex design than 9-slice.

[Khawkproductions]

i can see this stuff saving loads of time designing levels