Page MenuHomeWildfire Games

Use walking distance to calculate territories
Needs RevisionPublic

Authored by temple on Aug 28 2017, 2:51 AM.


Group Reviewers
Restricted Owners Package(Owns No Changed Paths)

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.

Test Plan

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.

Diff Detail

Lint Skipped
Unit Tests Skipped

Event Timeline

temple created this revision.Aug 28 2017, 2:51 AM
Stan added a subscriber: Stan.Aug 28 2017, 9:55 AM

Trac ticket also

Related bugs : wrong territory rendering after map resize : Territory Manager should exclude 3 territory tile border

Animation when changing borders would be nice

Maybe slightly related

No updates. I was hoping for more feedback, one way or the other.

Thanks for the research, btw.

(I wasn't going to do 2-5 in the summary until this one had been decided on. But the general idea would be that buildings don't lose their territory, but if they're disconnected from a root territory (e.g. if you lose a cc), then they're much easier to capture (haven't decided to what degree), and also you can't build in the territory. So then you won't lose your houses until the enemy actually captures them with troops, but at the same time you can't build more houses until you have another cc. So losing a cc is still devastating, but in a different way.)

I happened to take a couple of screenshots the other day. The first is a captured temple that doesn't have any territory influence since it's next to a fortress. (There's also a hole in the upper left.) And the second is a good example of crossing territories with the same temple after the fortress was destroyed.

It might be nice to have better resolution, even 4x4 instead of 8x8 tiles. Maybe I'll look into that.

temple updated this revision to Diff 3662.Sep 15 2017, 2:09 AM

We can do 4x4 tiles without changing other parts of the code, and I think it looks better and could play better. Here's the same test map:

The two Ptolemy houses are now disconnected, so we might have to fine-tune some radii. Multiples of four work well (note that the squares are half the size of the squares in earlier pictures):

On sharp corners the boundary line texture can be distorted (#919), and with smaller tiles we're more likely to see this. The problem is that when we create the boundary line from the tiles, we add in extra points but also offset them from the boundary line (so that my territory line doesn't overlap with yours). If the curve is too sharp then these offset points can extend past each other and not really follow the curve:

One solution is to remove points if they're close to each other, and that's what I did in the second picture. This looks better, but it's not perfect, so I'd like to think about it a little more.

I don't like territory extending through impassable tiles, since the logic is "walking distance". Also, it's annoying wondering why you can't build at the edge of the map or why your units can't climb a mountain. So I've changed it so that territory doesn't pass through impassable tiles. (This also helps somewhat with #919, since boundary lines won't go very far up the sides of mountains.)

Here's an example of the difference on Acropolis Bay:

There was an error with the algorithm on diagonals, which I've fixed.

mimo added a subscriber: mimo.Sep 15 2017, 7:23 PM
In D840#35413, @temple wrote:

We can do 4x4 tiles without changing other parts of the code, and I think it looks better and could play better. Here's the same test map:

You nonetheless should check that the ai behaviour is ok (when trying to position buildings, it constantly switches from the passability map to the territory one: hopefully the code should be able to deal with different sizes, but has never been tested with other values than 1x1 for passability and 8x8 for territory) and some profiling would be useful.

The change to first behaviour, notably, is a bigger gameplay change than it looks. It's quite a fundamental component of the game that you can "steal" territory right now, and this makes it redundant entirely.

Territories are already quite feature-limited, removing one more might not be a great-great idea.

Other than that, I don't really mind the change as it does look better. But to me, it's blocking as it stands now.

(I'm leaving this as "to review" so that hopefully somebody else will come along and comment)

bb added a subscriber: bb.Nov 12 2017, 3:57 PM

Some general comments:

Removing "capture by territory" is bad, players should still be able to do so.

Would it be possible to give every building his obstruction size as minimal territory? that way we don't have the "cc captured by fort" issue I guess.

Walkspeeds => please do (I actually don't mind about the "territory jumping over buildings" issue)

I guess with this patch it would be possible to loose territory by building a new building: Build a fort (or anything with big radius), then build a house (something with small radius) before the fort, then we territory of the fort would shrink in the direction of the house (since we need to walk around the house) and thus get a smaller territory. Maybe that would be fixed by allowing to walk through own (maybe allied too?) buildings

Building order matters: fine but do watch out for OOS's when buildings are build at the same moment, I guess using entity ID would be save, but then upgrading goes wrong (since ent id changes then).

Don't like the "holes" in unreachable areas there were there in the past too and hard to fix i guess, so meh


use consistent commenting


players should be able to steal territory from there allies with building on there border imo, better compare the weights, and the highest weight gets it.


shouldn't more buildings add up there weights, so more buildings have a saver territory

wraitii added a reviewer: Restricted Owners Package.Nov 15 2017, 12:20 PM

@temple I think you need to reduce the scope of this patch, it will never get committed in its current incarnation imo.

wraitii requested changes to this revision.Nov 15 2017, 1:03 PM
This revision now requires changes to proceed.Nov 15 2017, 1:03 PM
In D840#40885, @wraitii wrote:

@temple I think you need to reduce the scope of this patch, it will never get committed in its current incarnation imo.

I have seen patches change 10x as many lines and files than this one. Why is the "scope" too large in your estimation?