Fill a non rectangular grid with rectangles

I'm developing a city builder with a zoning system similar to Cities: Skylines. What I would need is an algorithm that would find all the way to fill this grid (in red) but with some constraints: In this case, one way to fill it would be to have a building on the left (size 4x3) and one building one the right (size 3x4). But to have some variety, I don't want to always minimize the number of buildings, so in this case I would like also to allow 2 buildings of 2x3 on the left + 1 building of 3x4 on the right. Someone pointed me toward the Dancing Links algorithm to solve this.

• I am guessing that one requirement is that all the rectangular partitions must touch the side that goes to the street. Am I right? It really makes things much simpler. I am also guessing that you intent for this to be (pseudo)random, instead of optimizing for something. Commented Feb 17, 2020 at 18:30
• Yes, you guessed right. All the rectangular partitions must touch the side that goes to the street. I want this to be random but with some constraints. I want to allow this : i.imgur.com/c2f313q.jpg and this : i.imgur.com/EQLcGAl.png Commented Feb 17, 2020 at 19:23

Given the requirement that all rectangular partitions must touch the side that goes to the street, the problem is just partitioning over one axis.

The shape we have is a set of rows of variable length. Since we want rectangle partitions, and these partitions must touch the street side, we are forced to partition at any place where the length of the rows change. If we did not partition there, then we would have partitions that are not rectangular.

That should convert your jagged area into a list of rectangular areas.

From there you can work recursively.

For each rectangular area, decide if it is worth partitioning※₁, decide by a (pseudo)random if you want to partition it, and where※₂. If you did not partition it, that's it. If you did, then you do the same for the partitions.

※₁: It could be that you would rather not partition rectangles of less than a given length, or of less of a given area. It could even be based on the type of zone.

※₂: Again, you may want to avoid placing the partition in such place that one of the part is too narrow or too small. Thus, the range of possible positions would avoid a margin. For example, if the minimum width is 2, and you have a rectangle of 5, you would only consider partitioning it at position 2 and 3. Because 1 and 4 are too close to the edge, and 0 and 5 are no partition at all.

Possible places where you may partition, assuming minimum width of 2, depicted in blue

You do not have to work recursively. This can also be done linearly... you start at one side, decide the minimum and maximum width for an area that starts there and pick by (pseudo)random. You would consider the width of the area that is left when picking the range. This should also make it easier to introduce a maximum width, plus it should work better for long rectangular areas.

• Thanks a lot. I'm not there yet, but now things are much clearer in my head. I think I see what I have to do :) Commented Feb 19, 2020 at 3:39