Sign up ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm building a small rts and in my code I have given my buildings a pattern, much like you would pieces in tetris. In other words I want to place irregular shaped buildings on a map without buildings overlapping.

Currently I'm bruteforce checking each cell with the cells in a map, but is there an easier/nicer way to check a tile map for a matching pattern?

The map could be 100 x 100 and my structure that i am placing could be as follows:




share|improve this question
What data structure are you storing your map in? –  Anko Mar 13 '13 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. –  Cameron Fredman Mar 13 '13 at 17:47
Sort of like this?… –  Byte56 Mar 13 '13 at 17:55
@CameronFredman As I understand, he wants to place irregular shaped buildings on a map without said buildings overlapping. Or something. –  petervaz Mar 13 '13 at 18:02
@CameronFredman Exactly, apologies for not being clear enough! I will update the question. –  Superflat Mar 14 '13 at 6:20

1 Answer 1

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.

share|improve this answer
I see the value of the quadtree structure but my question is a bit more low level. I will edit my post. –  Superflat Mar 13 '13 at 14:02

Your Answer


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.