This is in response to: https://gist.github.com/derek-knox/2aee55a146276b0514581f36b36b3f54
Here's some thoughts:
As long as even distribution is a soft goal and not a hard constraint, and you've got that specific set of small box sizes, it seems pretty tractable. It would be harder if your box sizes were weird and large like 4x19, etc. But with 1x1 in there, you can always find some solution that fills the region even if it ends up using more 1x1 boxes than you want.
There are probably a number of algorithms that would work. With those specific box sizes, I might try:
-
Keep a running count of the number of boxes of each size.
-
Fill the whole region with 1x1 boxes.
-
Until the box counts are uniformly distributed or some maximum number of attempts is made:
- Pick the box size that is least represented.
- Pick a random point. Try to collapse it with neighboring boxes to produce a box with the desired size. So, if you're trying to make a 2x1 box and you landed on a 1x1 box, see if the box to the left or right is 1x1 and, if so, merge them.
This probably won't give you a very close uniform distribution, but it's simple and might be good enough for something like a game.
Here's another:
-
Keep a running count of the number of boxes of each size.
-
As long as there are open cells that don't contain a box.
- Choose the least represented box size that is still selectable.
- Iterate over every location in the container where the box could be placed.
- If you find a place where it doesn't overlap any existing boxes, add that location to a list.
- If the list is empty, then mark that box size as no longer selectable.
- Otherwise, place the box at a randomly chosen location from that list.
This will probably end up biased towards smaller boxes because they'll stay selectable longer. You could tweak that by preferring larger boxes earlier on.
I think you can extend the second algorith to handle this. When checking to see if a location is valid, just add padding to box when checking for overlap.
I think it handles this too. When choosing the "least represented box size", just adjust the desired weights accordingly.
I hope that helps!