Logic that can traverse all possible layouts, but not checking every combination of identical pieces?

Posted by George Bailey on Game Development See other posts from Game Development or by George Bailey
Published on 2012-10-27T21:41:02Z Indexed on 2012/10/27 23:22 UTC
Read the original article Hit count: 315

Filed under:
|
|
|

Suppose we have a grid of arbitrary size, which is filled by blocks of various widths and heights. There are many 2x2 blocks (meaning they take a total of 4 cells in the grid) and many 3x3 blocks, as well as some 5x4, 4x5, 2x3, etc.

I was hoping I could set up a program that would look at all possible layouts, and rank them, and find the best one. Simply it would look at all possible positions of these blocks, and see what setup is the best rank. (the rank based on how many of these can be connected by a roadway system of 1x1 road blocks, and how many squares can be left empty after this is done. - wanting to fit the most blocks as possible with the least roads.)

My question, is how should I traverse all the possibilities? I could take all the blocks and try them one at a time, but since all 2x2 blocks are equal, and there are a couple dozen of them, there is no point in trying every combination there, as in the following

AA BBB
AA BBB
 CCBBB
 CCEEE
DD EEE
DD EEE

is exactly the same as

CC EEE
CC EEE
 AAEEE
 AABBB
DD BBB
DD BBB

You notice that there are 2 3x3 blocks and 3 2x2 blocks in my two examples. Based on the model I have now, the computer would try both of these combinations, as well as many others. The problem is that it is going to try every single possible variation of my couple dozen 2x2 blocks. And that is sorely inefficient.

Is there a reasonable way to take out this duplicated work, somehow getting the computer program to treat all 2x2 blocks as equal/identical, instead of one requiring rearranging/swapping of these identical blocks?

Can this be done?

© Game Development or respective owner

Related posts about ai

Related posts about grid