next »

[lasttea999]

Hello TIGSource! I've been interested in auto-tiling (automatic placing of tiles in tile-based games) in the past, and when the issue came up over in this thread, I thought perhaps it could use a dedicated thread.

Personally I've only ever used what I would call the:

Brute force method

1) For each tiled position, check its surroundings with a bunch of if statements. Assign a corresponding value.

2) Assign each value a tile, and draw each corresponding tile at each tiled position.

It worked fine for me, but somehow I feel there are more efficient, more elegant, or smoother methods. What kinds of methods have you all been using?

[TheLastBanana]

Alright, here's the post I promised.
Instead of using lots of if statements, I came up with a way of using bitfields for this that makes life a lot easier in the long run.

Each of the eight adjacent spaces to the tile are represented as a power of two, from left to right, top to bottom, like so:

1	2	4
8		16
32	64	128

When a tile is placed, it checks the spaces around it, combining them into one value using bitwise OR. So, a tile which has another tile to its left and one below it would be represented as 01001000.

Then, the tile checks itself against a list of all possible "cases". At its most basic level, a tile case has three values: its filled tiles, its optional tiles, and the sprite index that it's associated with. Filled tiles are which surrounding spaces much contain a tile, and optional tiles are which spaces may contain a tile or not. The optional tiles make things a lot easier to manage, as you don't have to create a huge number of duplicate tiles for all possible cases. That said, it means getting a wee bit more complicated in checking whether the current tile's situation and the potential tile case are equal.

To check whether a potential case fits, I do this (assuming "filled" is the current tile's filled adjacent spaces, and "case", containing "filled" and "optional" is the tile case we're checking against):

Code:

if ((filled | case.optional) == (case.filled | case.optional)) {
    //This case is a match, so set the tile's sprite.
}

The way this works is (in case you're not familiar with bitwise operations), the "optional" spaces can be ignored, so due to the bitwise OR they're set to 1 on either side of the equality operator. For instance, let's say you have the same tile situation as before (01001000) and you have a tile case that must include a tile below it (01000000) and can optionally include a tile anywhere above it, or to its left (0001111).

Code:

01001000 | 0001111 = 0101111

and

Code:

01000000 | 0001111 = 0101111

so it's a match!

The nice part about this is that you can easily make your tiles defined from a text file once you can get a parser working. I've got a little format to define tiles like this:

Code:

(7,5) {
    ---
    + +
    ***
}

The tile's index within the sheet is given between the brackets, and then between the curly brackets is which spaces around it are filled ("+" meaning there must be a tile, "-" meaning there must not, and "*" meaning it's optional).

The main downside of this is that it can be a bit slow to sift through a list of tile cases to find matching tiles when there are a lot of tiles being placed at once. There are probably some ways to optimize this that I haven't thought of, though.

[Triplefox]

I have been making a progressively more and more complicated tile engine for Moto (and for Magnate before that), autotiling is just one part of it.

I've described some of this in other threads, but the way I make it scale is to slice up the architecture in a bunch of different ways:

Still mostly based on brute force, very little bit-trickery

Load times remain fractions of a second long but I don't use huge ginormous maps(64x64 to 256x256). Although I could probably use more optimal algorithms for some situations, I have a relatively diverse number of auto-tiling algorithms at this point - alpha blends, repeating patterns, borders baked into the image, borders added on top, power lines added on top...

A general compositing system to describe the final render

The compositor simply describes how to layer bitmaps on top of each other within a tile, using offsets and sometimes alpha masks. It emits both a bitmap and a string key.

When I go to render a tile, I do the brute force check to figure out what composite key I'm looking for. If I have the key in cache I just take that bitmap, otherwise I generate it. I've experimented with a max cache size but right now I let it grow indefinitely(much simpler implementation). After finding the composite I store the key on the tile, so I don't have to do any checks again until it changes. That's why I can get away with brute forcing the autotiler.

Tiles contain multiple values

Besides the composite key, it's helpful to have definitions for different layers. In Moto I have these layers:

"bg" (non functional elements)
"tall" (has actual gameplay data)
"anim" (animating tile - this is still pretty underdeveloped)
"ent" (entity spawn point - only really meant for the editor)

Discard tile ids in favor of referencing definition objects (a recent change)

Something I discovered in the gameplay side of Moto is that I have a lot of similar properties on different tile types: Rocks and diamonds both fall, for example. So after a while I ended up with a lot of unnecessary logic for if "this or that." Finally I decided I would just use definition objects and they can have all the different properties as booleans. I've switched everything but the animtiles over to this system with good results. One of the major ones, for rendering purposes, is that I can easily apply new compositor methods, reference multiple images, and other cool data-driven type thingies, even though it's still hard-coded, because I don't have to go from an id to some lookup table out in the blue yonder. It's harder to maintain those.

I am running into performance bottlenecks at this point, but it's mostly due to other aspects of the implementation(using the Flash scenegraph, I have multiple nodes on it for every tile displayed, some are unnecessary - in total it's a large rendering overhead). I still have room to improve that, but I'm letting it be for now.

[baconman]

Seems that's about the way it's done. About the only way to simplify that approach is by only checking the 4 adjacent tiles, and allowing enough graphical overlaying to trace edges or something.

x1x
2x4
x8x

(Frame 0-15.)

[Sam]

I've written a bit (and made pretty diagrams) about the "assign values to neighbours" technique for automatic tiling.

It's a technique that I've reused for a fair few situations, with the odd slight adaption. Just now I was making tile selection logic for an oblique-view engine using just the same technique:



I very much like TheLastBanana's method for encoding which neighbours actually matter for particular tile types.

[Intrepid59]

How I did it was a bit similar to to TheLastBanana's method, but not as sophisticated and no bitwise operations.

It starts out similar, checking each neighbor and creating a case to test, although my layout was different;

 16 1 128
  2     8
 32 4 64

 
But instead of having it solve for itself, I have it assign the tile its frame (out of 47) from a 1D array, from 0 to 255.
I had previously gone and solved all cases on paper, and then wrote the solutions to the
array. So instead of checking through every potential solution, (This is how LastBanana's method does it to my knowledge, right?)
it will just grab the solution from the array.

This is done at level generation, not runtime. I'm pretty sure just tilesolving is fast, although I can't give a specific time.
(Generating a 512x512 level takes maybe 2 seconds, including digging caves, seeding resources and then cleanup and tile solving)

Not pretty or elegant, but it works well, and that's all I need.
     

[TheLastBanana]

Yep, mine has to look through a list of all possible cases for every tile. Obviously, that makes it a bit slower, but it does allow for things like optional cases (which has saved me a lot of time) as well as some other things I added in like tiles being able to automatically add each other and having different layers of tiles.

[lasttea999]

Thanks for all the input, guys! It's definitely going to take me a while to process all of this, ha ha.

Unfortunately I'm not familiar with bitwise operations... I wonder if this would be a good opportunity to figure them out.

But instead of having it solve for itself, I have it assign the tile its frame (out of 47) from a 1D array, from 0 to 255.
I had previously gone and solved all cases on paper, and then wrote the solutions to the
array. So instead of checking through every potential solution, (This is how LastBanana's method does it to my knowledge, right?)
it will just grab the solution from the array.

I considered this method once, and decided that there were too many cases...

[Zack Bell]

I do something similar to what some of the guys were saying. I have did a very simple version in Game Maker awhile back when I was playing with perlin noise stuff.

Code:

a=0;

if(collision_right){
        a+=1;
}

if(collision_right){
        a+=2;
}

if(collision_right){
        a+=4;
}

if(collision_right){
        a+=8;
}

image_index=a;

Obviously pseudocode, but you get the point 

[_Tommo_]

I will add my method here, it's similar to what was posted above but it allows for rotated sprites 
Also, everything is pre-cached and is blazing fast!

Premise: everything only has smooth transitions with grass, which in my game is perfectly fine. Also, under some conditions corner neighboring tiles are ignored (reducing by a lot the amount of needed tiles).

Hash Building phase (done with another program):

1) I made a list of the "unrotated type tiles", using their neighbour distribution, etc: zero, one, two at opposite sides, two at a corner, three at a corner etc.
2) Each tile type was assigned a bitmask, where each "1" in it is a required equal neighbour. This assigned a number from 0 to 256 to each tile, used to index an hashmap and store the tile type and rotation (0).
Eg: a straight road has two neighbours, one north and one south, and its hash is 01000100 = 34.
Each tile hashcode is then bit-rotated-with-carry by 2, to account for rotated version of the same tiles. The resulting hashcode was used to store the original tile type in the hashmap, and an increased tile rotation (1-3).
Eg: the same road from before, but horizontal, has an hashcode of 00010001 = 136, and a rotation of 1.

3) then I do something even uglier and trickier to ignore all the neighbours combinations where a corner neighbour is not adjacent to two side neighbours, eg: this

Code:

o o *
o * *
o * *

Is hashed the same as this

Code:

o o o
o * *
o * *

And then both the rotation and tile type hash are printed to screen in a C array form.

Then, at runtime, I use this exceedingly magical code, that computes the hash code for the current tile and tells it its tile version and rotation:

Code:

static const char tileHash[] = {
			0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 3, 3, 1, 1, 6, 6, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 3, 3, 1, 1, 
		 6, 6, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 8, 8, 1, 1, 2, 2, 1, 1, 2, 2, 6, 6, 7, 7, 6, 
		 6, 9, 9, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 3, 3, 1, 1, 6, 6, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 3, 3, 
		 1, 1, 6, 6, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 8, 8, 1, 1, 2, 2, 1, 1, 2, 2, 6, 6, 7, 
		 7, 6, 6, 9, 9, 1, 1, 3, 6, 1, 1, 3, 6, 2, 2, 4, 8, 2, 2, 7, 9, 1, 1, 3, 6, 1, 1, 3, 6, 2, 2, 
		 4, 8, 2, 2, 7, 9, 3, 3, 4, 7, 3, 3, 4, 7, 4, 4, 5, 10, 4, 4, 10, 11, 3, 3, 4, 7, 3, 3, 4, 7, 
		 8, 8, 10, 12, 8, 8, 11, 13, 1, 1, 3, 6, 1, 1, 3, 6, 2, 2, 4, 8, 2, 2, 7, 9, 1, 1, 3, 6, 1, 1, 
		 3, 6, 2, 2, 4, 8, 2, 2, 7, 9, 6, 6, 8, 9, 6, 6, 8, 9, 7, 7, 10, 11, 7, 7, 12, 13, 6, 6, 8, 9, 
		 6, 6, 8, 9, 9, 9, 11, 13, 9, 9, 13, 14
		};
		
		static const char rotationHash[] = {
			3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 
			3, 3, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 1, 1, 
			0, 0, 1, 1, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 
			3, 3, 3, 3, 3, 3, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 2, 2, 0, 0, 2, 2, 
			0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 0, 0, 3, 3, 0, 0, 1, 1, 2, 2, 1, 1, 
			2, 2, 3, 3, 0, 0, 3, 3, 0, 0, 1, 1, 3, 3, 1, 1, 3, 3, 2, 2, 3, 3, 2, 2, 0, 3, 1, 1, 3, 3, 
			1, 1, 3, 3, 2, 2, 1, 2, 2, 2, 0, 0, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 0, 0, 3, 3, 0, 0, 1, 1, 
			2, 2, 1, 1, 2, 2, 3, 3, 0, 0, 3, 3, 0, 0, 1, 1, 3, 3, 1, 1, 3, 3, 2, 2, 2, 2, 2, 2, 3, 3, 
			1, 1, 3, 3, 1, 1, 3, 3, 2, 2, 1, 2, 2, 2, 1, 3
		};
		
		//build current hash
		unsigned char hash = 0;
	
		hash = (hash << 1) | (board->getTileOrBorder(x-1, y)==tile);
		hash = (hash << 1) | (board->getTileOrBorder(x-1, y-1)==tile);	
		hash = (hash << 1) | (board->getTileOrBorder(x, y-1)==tile);
		hash = (hash << 1) | (board->getTileOrBorder(x+1, y-1)==tile );
		hash = (hash << 1) | (board->getTileOrBorder(x+1, y)==tile);
		hash = (hash << 1) | (board->getTileOrBorder(x+1, y+1)==tile);
		hash = (hash << 1) | (board->getTileOrBorder(x, y+1)==tile);
		hash = (hash << 1) | (board->getTileOrBorder(x-1, y+1)==tile);
			
		slot = tileHash[ hash ];
		rotation = rotationHash[ hash ];

Then the slot is used to index a texture atlas, and the rotation is used to rotate texture UVs (it is rendered with polygons on a terrain).

Ifs: 0
Number of unique tiles needed for a single terrain type: a mere 14
Awesome: 10
How much I recommend to try this at home: 0

 

[Cheezmeister]

Oh, yeah? Well my method needs even fewer unique tiles...ready?

One!

The idea is that you use oversized art that overlaps with itself. E.g. for a 16 pixel logical tile size, your grass tile might be 20 pixels wide with 2 pixels of overgrowth on each side. Then you just render the tiles with the proper offset so that they're centered around the tile and overlap each other properly.

I discussed this solution ages ago for a project that never got off the ground. I'm sure if I'd gone ahead and tried to implement it, I'd have discovered plenty of unpleasant restrictions, and it's not as elegant from a code standpoint, nor is it particularly tilesheet friendly (you'd either have to store the oversized images separately or take the padding pixels into account when cutting up your sheet)...also it's not as friendly for clean edges (grass works because it's scruffy and all looks the same, but if you have a sleek metal wall or a Tron neon tube, you can't just tile it).

But hey, one tile, right?

[lasttea999]

Cheezmeister brings up an interesting point: how a particular tileset is supposed to be placed. It's interesting to me that auto-tiling methods can get simpler or more complicated depending on the complexity of the tileset. The next question is: is there a general method??

[baconman]

Cheezmeister brings up an interesting point: how a particular tileset is supposed to be placed. It's interesting to me that auto-tiling methods can get simpler or more complicated depending on the complexity of the tileset. The next question is: is there a general method??

I think the general methods ARE those. 0-15 = 8-bit era, 0-255 = 16-bit era; although the rotation/flipping thing mentioned above adds a LOT to the equation - factoring in horizontal/vertical mirroring takes it down to a much more managable 64 factors, which is sort of a neat, indirect answer I was looking for in this thread.

I'm just not exactly sure how to implement the flip-factors in that layout however, because the checking nodes doesn't work the same way. (IE: it possibly does two top-collision checks, two side-collision checks, etc.) I'm debating between 3 methods of checking/reacting there by offsetting level chunks. I think "64" is the framecount we're all looking for here - varied enough to stand out, but not some insane level of grunt work that 255 would be.

[_Tommo_]

The idea is that you use oversized art that overlaps with itself. E.g. for a 16 pixel logical tile size, your grass tile might be 20 pixels wide with 2 pixels of overgrowth on each side. Then you just render the tiles with the proper offset so that they're centered around the tile and overlap each other properly.

I'm using OpenGL so I thought about using this solution, but it was impossible - iDevices are really fillrate limited and having most of the screen filled by overlapping transparent polygons was really not an option 
I'm sure this is ok on desktops, but for large levels this could be really heavy!

Also, in a 1024x1024 texture you can fit 256 64x64 tiles or 1024 32x32 tiles, so economizing on space isn't really useful. And having one single tile could be a bit artistically unwieldy?

[w01fram]

I implemented this method:

http://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M

I am now toying with the idea to make it a bit more granular and check out something like this:

http://www.gamedev.net/page/resources/_/technical/game-programming/tilemap-based-game-techniques-handling-terrai-r934

Has anyone tried out the second method or something similar ? I'm wondering if there are some pros/cons to either way.