# Building placement in tilemaps (pattern matching)

I'm building a small RTS and in my code I've given my buildings a pattern, much like you would pieces in tetris, i.e. I want to place irregularly-shaped buildings on a map without overlaps.

The map could be 100x100 and my structure that I'm placing could be as follows:

OXO
XXX
XXX


I'm currently bruteforce-checking each building cell individually against cells in a map.

Is there an easier/nicer way to check a tile map for a matching pattern?

• What data structure are you storing your map in?
– Anko
Mar 13, 2013 at 14:21
• Other people seem to understand what you're asking, but I'm still very confused, and I think it would be helpful in getting responses if you clarified a little. Mar 13, 2013 at 17:47
• Sort of like this? gamedev.stackexchange.com/questions/21586/… Mar 13, 2013 at 17:55
• @CameronFredman As I understand, he wants to place irregular shaped buildings on a map without said buildings overlapping. Or something. Mar 13, 2013 at 18:02
• @CameronFredman Exactly, apologies for not being clear enough! I will update the question. Mar 14, 2013 at 6:20

One simple and really fast way to do pattern matching is to use bitsets.

Let's say your map is 8x8 tiles: each bit represents either occupied (1) / non-occupied (0), e.g.

00000110 //least significant bits (0-7)
00000110
01111110
01101110
01100110
01100000
01100000
00000000 //most significant bits (56-63)


This fits into a single 64-bit integer (in most languages these days "long" or "unsigned long int").

Now you want to see if you can place a hut in the middle of the map:

00000000
00000000
00000000
00011000
00011000
00000000
00000000
00000000


To see if you can build here:

uint64_t map = ...; //top    arrangement of bits, above
uint64_t hut = ...; //bottom arrangement of bits, above
//...to convert these bitfields into uint64_t values, we use notation 0b00001... etc. up to 64 bits.
uint64_t canBuild = !(map | hut); //logical NOT and logical OR
if (canBuild) {...} //go wild!


...which to our minds means, "if there's nothing in the way at any of the locations that the proposed hut will occupy, you can build there". In this example the result of map | hut would be:

00000000
00000000
00000000
00001000
00000000
00000000
00000000
00000000


...so one of the tiles is blocked - you can't build there (logical NOT turns non-zero to zero / false).

You mentioned a 100x100 map. In this case we use a 13x13 array of 64-bit ints as above to represent the bigger map (making 104x104 tiles). The only slightly complex part of this is trying to compare against an area that borders on 4 64-bit sets, to see if you can place a building there. In this case you'll have to make 4 bitwise checks against all these neighbouring regions.

In order to write individual bits in (x,y) format as the patterns above, you'll need to do a little bit of googling of bitwise logic. Once you have it working, just wrap it in a function like:

void writeBitAt(uint8_t x, uint8_t y, bool value)
{
//...left as an exercise for the reader...
}


Are bitsets faster? Much. Comparing 64 tiles of your map to another 64 tiles in one or two CPU cycles is many times faster than comparing a sequence of tiles via conditionals within a loop, which could easily cost hundreds of cycles when you consider the impact of conditionals on the pipeline.

P.S. If your language / platform only provides 32-bit integers, you can still make this work, it's just a little less intuitive, e.g. a 16x4 map could be as follows, the layout is entirely up to you:

0000011000000000
0000011000000110 //...end of first 32 bits
0000000000000110
0000000001100000 //...end of second 32 bits


Okay, so I'm not 100% on what your trying to achieve but I think I got the gist, here's a few ideas to get you going:

• First off you could easily cut down a lot of your algorithms calculations by adding each cell populated by a building, into a closed cell list. Then run the same calculations but on that list only.

• Another approach could be to use a Quadtree data structure, again this is greatly cut down the calculations, this may work better in the sense you could grab a chunk of your map cells containing the building and run your pattern matching algorithm just like you were doing for the whole map.

• I see the value of the quadtree structure but my question is a bit more low level. I will edit my post. Mar 13, 2013 at 14:02