RimWorld Technology - Region System

via @asterope@anime.website

• World tileset is segregated in to chunks.
• Flood filling / reachability analysis on tiles within the chunk. Where a region is not fully connected to itself the region becomes smaller sub-regions within the chunk.
• Each sub-region knows which chunk edges its reachable through.
• When joining two regions whoever already had the most tiles “wins.”
• Spans cover a straight horizontal or vertical line which covers tiles which you can use to walk across to another tile.
• Edge spans which have a direction, size, x and y coordinate, which are hashed. Chunks find their neighboring regions by looking at a span, hashing it, and seeing other regions which share the same hashed tile.

"Rooms" are identified by breaking a world in to chunks, doing reachability analysis within a chunk to create regions, creating edge spans to determine how one can step out of one region to an adjacent region, and then flood filling these larger regions in to “rooms” which backlink to one another.