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.

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?

My current pseudo code

blocks = array of all blocks [2x2, 2x2, 2x2, 3x3, 3x3]
iterate(0)
function iterate(i) {
    currentblock = blocks[i]
    for each possible position of currentblocks
        see if there are any more blocks to place, and if there are
            iterate(i+1)
        else
            all blocks are placed, so get the rank
            if the rank is better than thebestrank
                thebestrank = rank
                thebestposition = position
}
at this point, we proceed with thebestposition.
share|improve this question

4 Answers 4

When you iterate over each possible position of currentblocks, instead of placing it automatically, check a 'previously placed' list, and if this current combination of blocks (including the one you're considering placing) has already been tried, skip this possible position. When comparing the combinations, treat similarly sized blocks as equivalent.

When you successfully place a block, add the current combination of block positions to the 'previously placed' list before recursing.

You are basically running a depth-first search that has multiple ways of reaching equivalent goals - so you need to keep track of previous approaches to ensure that you don't duplicate them.

share|improve this answer

Instead of telling the computer program to test each different type of 2x2 block separately, tell it to only test one of those types of 2x2 block.

Addendum: In your pseudocode, all you need to do to implement this is to change your first line to:
blocks = array of all blocks [2x2, 3x3]

share|improve this answer
    
+1. To @GeorgeBailey, As in, "Not this apple, but apples in general", a type being representative of individuals of that type. –  Nick Wiggill Oct 28 '12 at 0:19

Off the top of my head to place some identically sized blocks without duplicates you'll want something like this.

  Firstly enumerate all legal positions for a 2x2 block.

  function PlaceBlock(int blockcount, int start = 0)
  {
    if (blockcount <= 0) {OutputCurrentSetup(); return;}
    for (int i=start; i < legal_position_count; i++)
    {
      if (legal_position[i].IsBlocked()) continue;
      legal_position[i].Apply();
      PlaceBlock(i + 1, blockcount - 1);
      legal_position[i].UnApply();
    }
  }
share|improve this answer
up vote 0 down vote accepted

Thanks for your quick answers. I did find a simple way to edit my code to prevent duplicated iterations. However, it seems my idea of checking every possible combination is impractical, due to the sheer magnitude of the total number of possible combinations, particularly when you have blocks averaging a size of 3x3 filling over 50% of the container which is 30x40

share|improve this answer
1  
Note that depending on what your notion of 'best' is, there are a number of optimization algorithms that may be able to help you find much better (if not perfect) solutions - basic hill-climbing algorithms being the most straightforward and simulated annealing being perhaps the most flexible 'good' algorithm for your problem. I'd encourage asking another question about 'how can I find a good solution to this problem?' with more details as to just what you're looking for in your layout... –  Steven Stadnicki Nov 7 '12 at 22:24

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.