How to randomly generate a layout on a two-dimensional array?

Question

I have a 2D array of a given size and a list of numbered rectangles to fit into this space. Each of these rectangles has a known fixed height and width. The 2D array is guaranteed to be large enough to conveniently place all the rectangles.

I need to randomly put each of these rectangles in an array so as not to overlap and put everything. They can be placed in any orientation. Imagine that you place your ships in a battleship game, just with many different sizes of the ship and a much larger grid.

The finished array should look something like this: (0 represents empty space, a nonzero number represents the number of rectangles)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 4 4 4 0
0 1 1 0 2 2 2 2 2 0 0 0 0 0 0 0
0 0 0 0 2 2 2 2 2 0 0 0 0 0 0 0
0 0 0 0 2 2 2 2 2 0 5 5 0 0 0 0
0 3 3 3 3 3 0 0 0 0 5 5 0 0 0 0
0 3 3 3 3 3 0 7 7 7 5 5 6 6 0 0
0 0 0 0 0 0 0 7 7 7 5 5 6 6 0 0

One approach that I examined relates to each rectangle, selects random placement and orientation, tries to fit it into the matrix. If a collision is detected with a previously placed block, try again. This would probably be the easiest to implement, but it doesn’t seem very efficient and doesn’t end in an explicitly deterministic way (the rectangle at the end of the list may collide with previously generated blocks for a long time).

Is there a better way to do this that would not be so problematic for placing later rectangles?

Answer 1

The following approach:

• Find out what your minimum size is. Calculate a size that is smaller than this size, but fits several times in your field. For example: The minimum size is 7 cm / inch, the box is 120 cm / inch. Choose 120/20 = 6 cm / inch. I hope your problem is small enough because you will save all possible coordinates in a list. In this case, we have 20x20 = 400 coordinates.

• To ensure that the entire area cannot be locked, select your matrix so that the smallest dimension (x, y) is larger or smaller than the double dimension with the maximum size of your rectangle (for example, the maximum length of rect = 8, and x and y must have at least 32) , and that the entire area of ​​your matrix has at least a region that is two times larger than all the inserted elements.

• Placement selection: use a random number generator to randomly select a coordinate. Place the rectangle at the given coordinate, and also select a random orientation. Try to set the rectangle in the box, if it does not fit first, rotate it. If it still does not fit, try the following coordinate.

• If it finally fits, remove all coordinates that overlap with your rectangle from the list. This way you only select the correct coordinates for the other rectangles.

• Randomization: DON'T USE linear congruent generators (unfortunately, for your standard job for most programming languages). They have poor multidimensional characteristics. Use either protected random, hardware generators, or known good ones, for example. The whirlwind of Mersenne.

Answer 2

The IMO problem degrades to the question: "Do we have enough space to place the next rectangle and how to find this place in an efficient way?" So:

• The initial condition is that we have 1 rectangle (the original matrix) in the "list of available rectangles", basically we should only store the height and weight of the free rectangle and the upper left position on the original matrix
• Select a random rectangle to add = "toAdd", remove it from the list to add rectangles.
• Randomly select a free available rectangle that is equal to or greater than "toAdd" = "available", remove it from the "list of available rectangles", if there are no available rectangles, go to step 2
• Select a random location in the "accessible" to add the "toAdd" rectangle to it
• Cut the "available" rectangle to subtract "toAdd". A different cutting strategy may be applied here, but at the end you can get a maximum of 4 new available rectangles.
• Add new available rectangles to the list of available rectangles
• go to step 2

The algorithm is not optimal, because in an ideal world, we must combine the 2 available neighbors in step 6.

Answer 3

This problem is almost the same as generating a roguelike dungeon. There are many approaches to this with different appearances.

I would suggest the BSP tree approach here (the steps are simple): http://www.futuregadgetlab.com/proceduraldungeon/

Answer 4

You can simplify the calculation and start with some rotation limit, then you can use the kd tree. A good example is the jquery masonry plugin or the treemap jquery algorithm. The idea is to place the rectangle somewhere and separate the points x to the left and y to the right of the tree.