ALT
Text
City generator: districts with fewer warts
I’ve been working with this city (seed: 18172790131223986568) and it has really been bothering me. The river looks good and the districts are mostly okay, except for this guy:
This is what I like to call a “wart”. A refresher on the district algorithm:
- Choose a few random polygons inside of the voronoi space of the city
- For every district, absorb all of its neighboring polygons that are not already part of another district
- Repeat until there are no neighbors left to select
Here’s a visualization of the algorithm:
etc.
However, it does not bias against neighbors who share short borders, which is what causes these warts.
I played around with some ideas but ended up landing on a really simple solution: rather than taking all neighbors, I sort the neighbors by shared border length (descending) and take only the first half of that list. This does two things: it helps us choose the biggest borders first, and also leaves behind smaller borders for other districts to eat up. The results have been really consistent, which I’m happy with.
This worked really well - here’s that same map, with the new algorithm in place. The borders shift a little bit, but they’re more contiguous and don’t have weird bits that stick out:
Also, I’ve gone back and tagged all of the posts for this project as “#city generator” so if you want to read through the rest of them, you can do so here: https://intercal.xyz/tagged/city%20generator
And I’ve been posting them on my “real blog” if you want to read it that way instead: https://blog.intercal.top/tag/city-generator.html