I have a lot of ideas for territory and capture. Here's the big picture:

1. Use "walking distance" to calculate territories
2. Get rid of most capture by territory
3. Get rid of most territory decay
4. Disallow building and make capturing easier in disconnected territories
5. Let gaia buildings have territory influence

This patch tackles the first one and indirectly the second one. I'll discuss the others later.

One issue with territory, that's especially apparent in pizza games, is that there can be "holes", where one person's influence hops over buildings. This doesn't seem like desirable behavior.

It can get more extreme with the large influence of forts:

Another issue is that territories use a square grid but they can be connected diagonally, which means that territories can cross each other. This can make for weird boundary lines. In the two images on the right, the orange circle is around a red territory tile, which is connected diagonally to the rest of red's territory, so the red boundary line goes around it. If the tile had been completely separated from the rest of red's territory, then it would've had its own tiny red circle inside the orange circle.

In the next picture the blue and red territories are connected even though it looks like green is separating them. If blue and red are allies, the red territory won't blink and the red house won't decay. (Mentioned in a comment of #4681.)

The current territory tile system is a rough approximation of "true" territory, since it uses large 8m x 8m tiles and octagons rather than circles. It might be nice to implement something more accurate, but my patch here is just a tweak to the current system.

Instead of calculating the total weight of every player at a tile, I thought it would be better to start walks from every building, and stop when they reach the building radius or run into an enemy. This seems to me like a more natural sense of territory influence, and it removes the possibility of holes. In addition, connected territory should be calculated using just the four neighbors rather than also the four diagonals. This eliminates the possibility of crossing territories.

This method doesn't require territory weights, although a similar effect could be implemented as walking speeds. I'm not sure that's necessary, so for now I've ignored weights.

Currently, it's possible to capture buildings by building something with more weight next to it. For example, a barracks or fort next to a civic center can capture it. (See #4309 and #3528.) In this patch territories are grown outwards one step at a time, so every building has at least one tile of influence. This means that it's not possible to capture enemy buildings by territory anymore. (Fields don't have territory influence, so they can still be captured.)

Here's the current territory shapes for (radius, weight):

In the patch I use sqrt(2) = 7/5 rather than 392/256, which produces slightly different shapes. Here's the ones for radii below 100m:

We need to adjust some radii, but all of the old shapes except for 140m and 200m can be matched exactly with new shapes. For example, small houses had a radius of 16m, but to get the same shape of 13 territory tiles, the radius needs to be between 18-20m. In this patch I've changed a few of the smaller radii so that the buildings have the same territory shapes as in a22. I can do the rest in another patch (or just leave them as they are).

Finally, here's a map I made in a22 illustrating a lot of the problems, and the same map loaded with the patch. All of the holes go away, except for a spot on the hill where blue can't reach. The fortress isn't taking over the red cc, and the territory isn't extending to the other side of the houses because now he has to walk around them.

In the case of a tie, there's a bias towards buildings that were built earlier, that's why the blue territory is eating into the red barracks a little. In this picture, the buildings were created left to right.

Here's the similar configuration in a22, in one position and then shifted a little to the right. Obviously, you can play around with this stuff yourself. Territory tiles are 8m x 8m, so you can move buildings around a bit without changing the territories.

It might be nice to start territories where the obstructions or footprints end, but again, this patch is working within the current system.

See if you like the change.
See if everything works as expected, e.g. disconnected territories blink when they're supposed to.

I don't have much of a sense for performance optimizations. For example, the weights here are much smaller (basically just the radius), so u32 might be overkill. I changed the regular floodfill to only use four directions (to avoid diagonal connections), and I'm not sure if that's significantly slower or if it matters.