How can I generate random levels like in "Square it!" game?

Question

In this game, you have a 2d field with some free squares and two colored squares which you can move but only together (they'll move only if the spot is still "free"). And you have to fill whole free space.

Here is a video that demos how the game is played.

How can I generate random game levels like in that game?

Answer 1

The following should be enough to generate a level for a clone of the game:

1. Decide - at random - the start position for the squares.
2. Repeat n times:
   1. Decide a direction - at random.
   2. For each square, if block at that direction:
      1. Has been walked in, or is out of bounds: Do nothing.
      2. Has not been walked in: Decide - at random:
         1. Mark the block as solid.
         2. Mark the block as not solid. Add it to the set of walked blocks, or mark it walked. And move the square there.

These are the things you can tweak:

• What is the distribution for the starting positions? Would it prefer the squares to start nearby or not? Do you want to use a different distribution for one square than from the other?

• What is the distribution for the directions? Would it prefer to stay in the same direction, or will it prefer to change direction every step? Addendum: Here is an idea: you could have one square to prefer to move towards the other square, while the other prefer to stay in the same direction... or other combinations of distributions.

• What is the distribution of solid vs not solid? Will the squares find obstacles too often, or will the obstacle be more sparse.

• How many iterations does it do? Will the map requires few moves or lots of moves?

Note: it is possible that the above algorithm has steps in which it does nothing. That is ok. Eventually it will run out of iterations.

Teak until you have satisfactory results. You may consider to make the distributions a function of the number of level to create a difficulty curve.

---

You can do something more exotic with the same approach. Instead of picking a direction with a given distribution, you can pick a destination, and then use path finding to decide the steps the squares take to get there. In this case, you will not pick a direction n times, but pick a destination n times, and run until you have reached all the destinations or there is no more moves posible.

Addendum: A variation is to pick a set of destinations blocks, and on each iteration you decide for which one of those you want to go. You may, for example, always pick the nearest one, or pick at random.

Note: Be aware that the algorithm may lead to a sitiation in where there are no more possible moves, but it didn't reach all the destinations. In this case I suggest to just ignore the fact that you didn't reach the destinations, you should still have a valid level.