Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am working on a tiled map editor, and I need to choose tiles automatically, based on the adjacent tiles. For example, when placing a road tile, next to another road tile, the two need to be oriented so that they form a continuous road. If there are other roads around them, we may need to use corner or intersection tiles.

Can anyone recommend some algorithms for doing this? The game uses an 8-directional square tiled map.

share|improve this question
    
Can't you just examine all the surrounding 8 tiles whenever the user puts down a new tile, and the orient the new tile accordingly? Of course you'll need to store some extra info on each tile such as orientation and type. –  XiaoChuan Yu May 23 '12 at 22:18
    
I am examining all surrounding tiles, but I didn't know how to handle all the tile combinations. For example, you have seven possible tiles to choose from (horizontal, vertical, four corners, and a cross). I thought of using complicated switch statements, but that felt wrong. –  alekop May 23 '12 at 23:02
add comment

2 Answers 2

up vote 14 down vote accepted

Maybe this is how it's typically done. You have your list of different tiles that represent a road tiles in all their possible orientations. Left to right, all four corners, top to bottom, whatever. Now you'll index all those tiles with a byte each. 8 bits, one for each direction. This could be in a hashmap or by file name... however you want to do this.

So you have this:

enter image description here

The byte code for the above tile is 00000000. Then your tile that goes from left to right (or right to left) is like this:

enter image description here

The byte code for that tile is 10001000, or 136. As another example, lets look at a three way intersection:

enter image description here

The byte code for that tile is 10101000.

You probably see where I'm going. You set bit positions in the byte representing connections. This is far better than trying to do some big if/else chain that I've seen before. When you're looking to place a tile, examine the tiles around it and create a byte along the way. Set 1's for tiles that have roads (or whatever you're looking to connect) and 0's for tiles that don't. When you're done, you'll have the byte code for the exact tile you need.

Note that when creating the assets you can reuse a lot of them by simply rotating and assigning the correct byte code to it.

EDIT: Updated images to be less crappy. Yes those are better than before.

share|improve this answer
    
Very nice! Simple and efficient. The only thing that I don't understand is how you're getting those bitmasks. For example how are you getting a bitmask of 17 from the numbers 3 and 7? –  alekop May 23 '12 at 22:41
    
Never mind, I see what you're doing. You're setting bits 3 and 7, but you're counting from the left, instead of the right. –  alekop May 23 '12 at 22:46
    
Oh wow, how embarrassing. Got my Endianness all mixed up. That was an accident I'll fix that! –  Byte56 May 23 '12 at 22:48
    
Great, now my comment doesn't make sense! :p Just kidding, thanks for your answer. That's exactly what I was looking for. –  alekop May 23 '12 at 22:54
    
still this algorithm needs to be optimized, since most of those tiles are just rotation of each other! with your current approach, you need 256 tiles (or 16 if you don't count corners) to store all that data, while most games don't use more than 4 types of tiles. –  Ali.S Oct 22 '12 at 1:18
show 2 more comments

I would recommend you take a look at this handy page for more information, as it goes into great detail about pretty much every aspect of what you're doing, as well as a few potential optimizations: http://www.angryfishstudios.com/2011/04/adventures-in-bitmasking/

The tldr is that you query each adjacent cell and store the combination in a bitfield/byte, then pass it through a map that converts a number from 0~255 into a value from 0~47, which corresponds to a unique image.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.