[PATCH]Get territory neighbours from territory manager

[sanderd17]

Storing the territory neighbours in the territory manager would be handy for code related to decaying.

F.e., the decaying code can decide not to decay when the territory is unconnected, but borders allied territory, or is surrounded by allied territory. As diplomacy is rather complex, this isn't something that should be implemented directly in the connectivity calculation, but rather be provided as extra information for the scripted mods.

Next to that, if some building is actually decaying, it could decay towards its neighbours rather than towards gaia.

Currently, the territory map is stored as an u8 map. The first 6 bits are used to code the ownership, the 7th bit is used to mark the tile as (un)connected, and the 8th bit is used to mark the tile as (un)processed.

So to encode the neighbours, we should porbably switch to an u16 map, with 5 bits to encode the ownership (4 would be enough in fact), then 9 bits to represent the 9 possible neighbours (8 players + gaia), and the 2 status bits.

[sanderd17]

The patch adds a u16 grid that holds the neighbours per zone.

As for a big part of the game, there are no unconnected pieces, the calculation is done lazily, only when requested. And not even for the entire map (since these regions are normally small, and span only a tiny portion of the map), but only for the requested territory. After the calculation, the results are cached.

The calculation itself is a flood-fill, which fills the queried territory up to the boundaries, and saves the player ids it ran into. Following the boundaries isn't possible, since there's a chance on territory enclaves, which would cause multiple boundaries. As such, a flood fill up to the boundary queries the least amount of data.

I still have doubts about the caching though. The caching is only usefull when multiple buildings are in the same unconnected territory. The caching is also a flood-fill algorithm that sets the neighbours on every tile of that territory. So it's just as expensive as querying the neighbours for a second building on that territory. Caching only has a possitive effect on speed from the third building on the territory onwards.

For the data format, I opted for u16 values. I certainly needed 8 values for the 8 possible players, and preferably 1 for gaia and I also use 1 for the cache status.

Next to the actual work, I also optimised one of the existing flood-fills, so that it only copies the affected region (inside the buildings influence radius), while it used to copy the entire map for every building.

The changes aren't used in the simulation yet, but the decay component shows they're accessible, and ready for use.

[sanderd17]

For the new version of the patch, I allow 32 player ids. Because this would double the memory footprint of the cache, this version also doesn't have a cache anymore.

Another advantage of dropping the cache is that the scripted side can now choose to only query the neighbours listed as "connected", or to query all neighbours. Thus the function name changed from GetConnectedNeighbours to GetNeighbours, with an added flag to filter out only the connected ones.

Next to that work, I also uniformised more flood fill algorithms, so they use the same variable names and have the same way of boundary checking. This should at least make it easier to read the code.

[sanderd17]

The new version is more versatile. Next to listing who are neighbours, it also returns with how many tiles the neighbours border. As such, you can say that f.e. 70% of the border is with player 2, and 30% with gaia. This cleaned up the c++ code a bit more.

This patch also implements the actual territoryDecay changes, where the decay happens in favour of the neighbouring territories, but distributed to their border share.

[leper]

Wouldn't reduce be a better choice for this?

var numberOfEnemies = this.cp.filter((v, i) => v > 0 && cmpPlayerSource.IsEnemy(i)).length;

Missing ; on line 129 in Capturable.js. The comment for CheckTimer() could use longer lines (that's not even 80...). We don't post a message in case the regen rate changes?

That TODO should be fixed, moving them to eg a helper function or auxiliary file. FloodFill() is reusing the tile name (not an issue code-wise, but might confuse readers). Also why not just construct that new tile in-place? (Constructing this in-place in a few other places in that file too.) for (auto& it : influences) hides the type of it, which isn't an iterator but a pair. I guess introducing an InterfacePair typedef and using that explicitly might be nicer. Similar comment regarding naming things it if it isn't an iterator in the other range based for loops. for (auto& it : influenceEntities) and below: First using auto, then explicitly having that std::vector<entity_id_t>& ents just to use that once in the range based for is a bit strange.

void addRegion() for loops with <= are strange, use + 1 before that or something.

(Didn't check the flood fill logic (or rather the logic behind those few loops you added/changed), so those could still have some issues.)

[sanderd17]

• Didn't change the filter into a reduce, it resulted in longer code, and I needed 3 variables in the reduce function instead of 2 in the filter function, thus the code was less clear too.
• I did investigate all types of variables used in the loops, and tried to name them as well as their types.
• The floodfill loops are all unified, and put in a "define", with unique variable names for the tile coordinates.

Next to that, I included overall optimisations.

• I removed any looping over the entire grid. The calculation of the best player happens while the entities are added, and the pathfinder grid is only read when needed.
• For the floodfill, I used a queue instead of a stack. This causes the oldest tiles to be expanded first, resulting in inkt-stane-like floodfill, instead of a snake-like floodfill. Thus less tiles are expanded. Next to that, the deque makes sorting on heighest weight unneeded, since these tiles are already in front of the queue (with a rare exception where the floodfill has to do a bit more work).

The territory_block entity is removed, and the territory_pull entity is replaced with an immediately-capturable entity. This is because it caused clutter in the code, and only the territory_pull was used once, in a demo map (so apparently not very wanted for the map makers).

Overall, I tested the performance by loading various maps, and on maps with a lot of buildings (like demo maps), I could achieve 30% faster code for the territory calculation. On maps with few buildings, the effect of not looping over the entire grid is even more obvious, and I could see over 50% faster code.

[leper]

Missing null check for a system component (pathfinder) (we omit those in JS since they aren't fatal and we can assume them, but in C++ a missing check might cause a crash that could have been prevented easily).

Don't do defines that don't need a ; after them STMT() might be helful. Having the define be something like

FLOODFILL(init, STMT(code));

might work. Though init might not be needed if you'd actually put

TileQueue openTiles;
openTiles.emplace(i, j);

in there too.

The range-based for loops are better already, but all of them now do a copy of the value (for some that isn't an issue (entity_id_t), but for others that might be costly), so make those a reference.

[sanderd17]

Null check done and references in the for loop are implemented.

For some reason, I couldn't use the STMT() call, it complained about giving too many arguments to STMT, and undefined variables. However, it was possible to wrap it with a do..while, which is exactly the same as STMT (this makes me wonder why STMT didn't work, but at least it works now as a function call).

[sanderd17]

In 16676:

Implement methods to find the neighbour of a certain territory, and use it for territory decay. Fixes #3204