Bitwise Auto-tiling in Game Maker

So I was fooling around with auto-tiling objects, and went through the long process of comparing neighbors through a series of if statements.  It was a lot of freakin work, but in the end I came up with something that did the job.

autotile1

As you can kinda see, the borders around the tiles adjust themselves based on the surrounding tiles.  Because the project I’m using this for involves destructible terrain, the neighbors above, below, to the left and right are all calculated per step.  While that is all well-to-do when there are only 50 or so blocks in the room, once more and more are added, the amount of collision checking per step is atrocious,  and slows down the frame rate severely, not to mention the amount of body work with all of the ifs and thens.

Then, I happened upon a wonderful way to use binary operations to remove the spaghetti that was a series of if’s.

In the step event of an auto-tiled object, set a variable count to zero and do four place_meeting checks (one in each direction) and store the returned Booleans in a couple variables:

var count = 0;
nUp = place_meeting(x,y-1,obj_autotile);
nDown = place_meeting(x,y+1,obj_autotile);
nRight = place_meeting(x+1,y,obj_autotile);
nLeft = place_meeting(x-1,y,obj_autotile);

Now comes the cool stuff!  Take a look at the diagram below.  The pink square with “TILE” written in it represents the instance of an object calculating these collisions.  Moving from the top, clockwise around it, are numbers that double the last.

autotile2If another tile is meeting our current tile directly above it, we will add “1” to our count.  If one is meeting to the right, add “2”, if below, add “4”, and if to the left, add “8”.
Because each number is double the previous number, and the numbers can only be added once, there is only one way to have our count equal any particular number from 0 to 15.  For example, the only way to make the number 5 in this method is to add the 1 from above and the 4 from below, so we know that image number 5 has to be the tile that is drawn when only a tile above and tile below are meeting our object. Therefore, by adding these numbers based on the collisions that we declared previously, we can determine 16 unique tiles to draw by using five simple lines of code:

if(nUp) count += 1;
if(nRight) count += 2;
if(
nDown) count += 4;
if(nLeft) count += 8;
image_index = count;

The most arduous part of this process is determining exactly which tile corresponds with which count number.  Luckily, since I went through the process already, I’ve made a diagram:

spr_terrain_strip16

This diagram shows which border tile corresponds with which image_index if you use the method above.

On to the other problem, and one that I know everybody has concerning auto-tiling, optimization for real-time auto-tiles.

So with our auto-tiling set up using binary operations, that cuts back on a lot of thinking that the game has to do per frame, but it is still inefficient because it each object has to calculate four collisions each, then determine which image it should display, (assuming the room speed is 60) 60 times per second.  If you have 50 auto-tiling objects, that is 
50*4*60 =
12,000 collision checks per second.

oops.

The solution I came up with is to only update the tiles when a change has been made to the map!  Why should we need to collision check over and over again if nothing has changed?  While this isn’t the most efficient because even unaffected tiles will update themselves if a change to the map has been made elsewhere, it is a simple and more efficient solution than running a four collision checks per object per step.

In the create event of our object, initialize a variable “tile_count” or something of the like:

tile_count = 0;

Then, in our step event, before calculating the collisions, compare this variable to the number of tile-able instances that currently exists, and if tile_count is equal to that number, simply exit the code!

if (tile_count == instance_number(obj_autotile)) exit;
//then your collision stuff

So essentially, on the first step, because we initialized tile_count to be 0, tile_count will not equal the instance_number and will proceed through the code and auto-tile.
Now, after your auto-tile stuff, we also have to update our variable tile_count to equal the instance_number so that way it will not keep looping through the code.

//collisions and autotile stuff
tile_count = instance_number(obj_autotile);

This makes it so that on the next step, the part we put at the beginning of the step will flag “true” and the code will exit itself before doing collision checks and auto-tiling, because nothing has happened.

If the amount of instances changes, either more are added or some are destroyed, the remaining instances’ tile_count will no longer equal instance_number because instance_number has changed, and they will all loop through their auto-tile code once, before tile_count is set to be equal to the new instance_number!

Pretty nifty, eh?

The complete step event should look something like this:


if (tile_count == instance_number(obj_autotile)) exit;

var count = 0;
nUp = place_meeting(x,y-1,obj_autotile);
nDown = place_meeting(x,y+1,obj_autotile);
nRight = place_meeting(x+1,y,obj_autotile);
nLeft = place_meeting(x-1,y,obj_autotile);

if(nUp) count += 1;
if(nRight) count += 2;
if(nDown) count += 4;
if(nLeft) count += 8;
image_index = count;

tile_count = instance_number(obj_autotile);


-Cullen (Coyote) @cullenddwyer

1 Comment

Leave a Reply