So, I’ve been busy trying to work out algorithms for generating interesting city layouts. I spent a good long time chasing down alleys that turned out to not work too well: I’d decided that I wanted something a bit more elaborate than the straightforward grid layout I’d been using (and that TwentySided also seemed to use), but making things look interesting and realistic, but not also horrifyingly complex to code turned out to be more difficult than I thought. I also caught myself in the classic case of refusing to throw away code I’d already written and piling more bad code on top of bad code.

One approach I initially tried was to start with an empty city, and then plant lots on it, starting with large lots clustered around the centre, and then gradually filling in the gaps with decreasing size lots. Each lot would be bordered by roads on each of the four sides, and then I’d add random roads afterwards to divide up any remaining space. However, this often ended up with a load of roads running right next to each other – and also, I wanted the ability to have variable width roads, and this approach didn’t really lend itself to that. So, after far too long, I gave up and threw it away, and came up with the approach that I’m working with now.

Instead of starting with an empty space and adding lots, I decided to do exactly the opposite – start with a space filled by a single large lot, and then carve it up: so, the initial lot gets carved into two, and then each of those gets carved into two, and so on. Each split creates a road – the initial road width is wide, but as the lots get smaller, so do the roads – thus areas with a large number of small lots will tend to have small roads, whereas areas with larger buildings will tend to have bigger roads.

I also added a number of heuristics to make it look more “city”-like: when splitting a lot, the split point is random, and may be horizontal or vertical – if the lot is taller than it is wide, the split is more likely to be horizontal than vertical, and vice-versa. This ensures that buildings are mainly roughly square – long, thing buildings are rare in real life. Also, not every lot is split: in order to create a more built-up CBD, for each lot, the probability of a split taking place is increased the further away from the center of the city the lot is, but in order to make sure the lots aren’t too big, the probability of a split is also increased as the size of a lot increases.

The result can be seen below as an animation – the road colours correspond to different “classes” of road, that may end up being rendered differently at some point.

The next job is to actually plant some buildings in the lots – there’s still some work to do here, because a lot of my code tends to work best with base sizes that are roughly square, and I’ve still got a fair few lots being generated that are of a size ratio 2:1 or more – but anyway. You can check out the latest revision – 44 – from the bzr repository.