Fitting geometrical 2d shapes into a rectangle like in the android game Six! (or Tetris)?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Footurist

This is what it looks like. Basically I want to have an algorithm, that generates that kind of blocks out of physics bodies. I really don’t know how to approach this, anyone got an idea?

Not sure about Godot 3.0 but there was a Tetris demo in Godot 2.1 . You could get some ideas about how to do what you want to do out of that.

SingingApple | 2018-03-02 16:24

Thanks for the advice, but the problem is I need the reverse process. I need to start with all the shapes being snapped into a perfect rectangle.

Footurist | 2018-03-02 17:27

:bust_in_silhouette: Reply From: KoBeWi

Instead of fitting whole shapes onto the board, make a “filling” algorithm that will create shapes at the end. For example, if you want to fill square with 4-block shapes, it could look like this:

  1. create an array
  2. look for free spot on board (either random or picked somehow)
  3. add Vector2 of this position to your array
  4. check all spots next to that block to see if they are free
  5. choose random free neighboring spot
  6. add this position to your array
  7. if you have less than 4 elements in array, repeat from step 4
    Now that you have the vector array, you need a table of possible shapes. Look up the table and select proper shape to place it, so that its blocks fit the vectors in array. You might want to translate the vectors first, so their top-left is at (0, 0), because your look-up table might be that way too.

Just repeat these steps until your board is filled. And if it fails because there’s a hole impossible to fit with proper shape, you can either remove last X shapes and try again or start over.

Not sure if it will work perfectly, but if I were to do this, I’d first try this way.