koobas.hobune.stream
Largest Rectangle of Tiles
Hello!
I'm writing a Tile based game, similar to Rimworld or Prison Architect.
I have a system for creating Zones (a set of connected tiles) for designated areas, and also for Rooms.
To put labels on the zones, I need to find the largest rectangle of tiles from the set of tiles in the Zone, to position and size the UI Gameobject with its text. The zone's tiles are always continuous but the set is possibly concave.
I have tried the brute force 'Find every rectangle - > find largest' approach, however this gets slow very quickly.
I have looked at algorithms to find the largest rectangle of a set of pixels in an image however these dont account for connectedness so wouldn't be ideal.
The image should clarify what I'm looking to calculate.
Any pointers in the right direction?
Regards Matt
So that this thread isn't left unanswered. I managed to implement the algorithm described in this youtube video https://www.youtube.com/watch?v=g8bSdXCG-lA&t=9s
The algorithm involves first implementing 'Largest rectangle in a histogram', which is the harder part (dude has a video on that too, but there are others). The main algorithm calculates a new largest rectangle for each row in the matrix of tiles that make up the zone, and works quickly enough for my purposes.
