# Algorithm for fitting geometrical 2d shapes like in the android game Six! (or Tetris)?

In the game Six!, there's a perfectly rectangular tower of geometrical 2d shapes, that you destroy on tap to reach the ground with your player. The easy way would be to design the levels by hand. However, I wondered how to do this with an algorithm, so that you save a lot of time? Any idea?

I use the Godot Engine 3.0, fyi.

• The thing is, I don't really now how to approach this. I tried putting each object on the first object's position initially and then translating it as long as it's still colliding. However, this is very time consuming and not very elegant. – footurist Mar 2 '18 at 13:40
• Hint: you're not building a tower, you're cutting a cake. The full shape is already there, and you just need to decompose it into pieces. – DMGregory Mar 2 '18 at 13:44
• Yes, I already thought about that, but still struggling to find a way. I have to say, that I have very little knowledge of math (will probably change that in the future). – footurist Mar 2 '18 at 13:51
• I think you broght me on the right track! I may define a base unit, that all forms use, like the square in tetris, so that when no combination fits in anymore, the square will still fit in. I could use pixels, but that would probably be overkill for this app. However, how to practically make the individual shapes perfectly snap into each other I still don't know. – footurist Mar 2 '18 at 14:17

EDIT: Here's another solution that would be simpler but not as random. You could make a set of many large n by n uniform squares that you fill in with predefined shapes, then use the squares with different rotations to form the tower. This is a much simpler approach, but it requires you to make enough combinations to feel random, and there will be seems that aren't crossed by any shape. Unless you offset the squares every layer, or use a different shape that can fill in a tower.

You could place the pieces by dropping random shapes randomly across the top like in Tetris until no more shapes can be dropped, then rotate the tower and let the shapes fall back into place, then continue to drop shapes from that direction. Repeat the process until you can no longer drop shapes and fill in the remaining holes with small shapes.

If you need all shapes to fit a certain profile, then you could also remove shapes around blockages that aren't fully filled in and restart the algorithm, but it might take a long time to find a configuration that works.

Here's an algorithm for dropping shapes.

0 background

1 piece 1

2 piece 2

0 0 1 1 1 0 0
0 0 0 1 2 0 0
0 0 0 0 2 0 0
0 0 0 0 2 0 0


Form a matrix that defines each piece by the grid of square locations taken up by that piece.

Start by assuming all pieces are falling.

In each iteration loop through every piece to determine which pieces are definitively anchored, and stop iterating when the previous iteration finds no new anchored pieces.

To determine whether a piece is anchored, loop through every component of the piece. If any of the following conditions are true, then the piece can be considered anchored.

1. A component is in the bottom row.
2. The space below a component is from another component that is determined to be anchored.

Once you have determined which pieces are falling you can update the matrix and the scene by dropping all the components of those pieces by 1 and restart the algorithm until you have a situation where all pieces are anchored.

• Thanks for what actually seems to be a solid solution! In the meantime I interestingly came up with something similar to this: I drop the first piece at the bottom left corner, then I put the next piece always at the position of the last piece and determine, whether it's intersecting or not with an Area2D. If it is, then I'll move it on unit to the right(predefined square like in your solution) and so on... I repeat this process for every row... this way the unit will always fit at the end if space is left. If I fail with this, I'll go with yours! Thanks a lot! – footurist Mar 3 '18 at 7:03