But, I'm a computer programmer, so I could make my own! With
blackjack and hookers the ability to upload custom pictures and randomly generate grids!
Most everything is straightforward there, except for the generation of the grids. How do I take a rectangle and partition it in smaller rectangles? And not only that, I want to be sure that my algorithm can produce ANY possible split within my limitations. (I'll need to add some limitations to make the grids playable. My first idea is to limit the minimum size of rectangle sides, but that will come from playtesting)
Searching for an answer to this I found the CS.SE question "Randomly partition an rectangle into N smaller rectangles". This suggests an algorithm:
- Take a rectangle
- Randomly do one of the following:
- Split the rectangle into two rectangles with a line parallel to its sides
- Split the rectangle into this pattern (with randomize sides and possibly mirrored):
- Take each one of the new rectangles and go to point 1. (Recursion)
It's something. But I had doubts if it could produce ALL possible splits. So I took a look at the games, and sure enough, the first level I clicked already had a split which cannot be produced with the above algorithm:
This also gave me inspiration to produce this split, which I think is a minimal example of another split that cannot be produced by the above algorithm:
OK, so if that doesn't work, what does? It feels to me that a problem like this (partitioning a rectangle into smaller rectangles) is something that should have been explored mathematically, but I don't know where how and what to look for.
So, my question is - is there any mathematical research which, either as its primary focus or as a side effect, has developed an algorithm for enumerating all possible splits of a rectangle into smaller rectangles?