Index: binaries/data/mods/public/simulation/data/territorymanager.xml
===================================================================
--- binaries/data/mods/public/simulation/data/territorymanager.xml
+++ binaries/data/mods/public/simulation/data/territorymanager.xml
@@ -1,6 +1,6 @@
- 4
+ 255
0.75
0.85
Index: source/graphics/TerritoryBoundary.cpp
===================================================================
--- source/graphics/TerritoryBoundary.cpp
+++ source/graphics/TerritoryBoundary.cpp
@@ -142,7 +142,8 @@
ENSURE(!(grid.get(ci, cj) & ICmpTerritoryManager::TERRITORY_PROCESSED_MASK));
grid.set(ci, cj, grid.get(ci, cj) | ICmpTerritoryManager::TERRITORY_PROCESSED_MASK);
- if (ci < maxi && cj > 0 && (grid.get(ci+1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
+ if (ci < maxi && cj > 0 && (grid.get(ci+1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr &&
+ (grid.get(ci+1, cj) & TERRITORY_DISCR_MASK) == tileDiscr)
{
++ci;
--cj;
@@ -159,7 +160,8 @@
break;
case TILE_RIGHT:
- if (ci < maxi && cj < maxj && (grid.get(ci+1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
+ if (ci < maxi && cj < maxj && (grid.get(ci+1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr &&
+ (grid.get(ci, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
{
++ci;
++cj;
@@ -176,7 +178,8 @@
break;
case TILE_TOP:
- if (ci > 0 && cj < maxj && (grid.get(ci-1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
+ if (ci > 0 && cj < maxj && (grid.get(ci-1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr &&
+ (grid.get(ci-1, cj) & TERRITORY_DISCR_MASK) == tileDiscr)
{
--ci;
++cj;
@@ -193,7 +196,8 @@
break;
case TILE_LEFT:
- if (ci > 0 && cj > 0 && (grid.get(ci-1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
+ if (ci > 0 && cj > 0 && (grid.get(ci-1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr &&
+ (grid.get(ci, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
{
--ci;
--cj;
Index: source/graphics/TerritoryTexture.cpp
===================================================================
--- source/graphics/TerritoryTexture.cpp
+++ source/graphics/TerritoryTexture.cpp
@@ -167,7 +167,7 @@
void CTerritoryTexture::GenerateBitmap(const Grid& territories, u8* bitmap, ssize_t w, ssize_t h)
{
int alphaMax = 0xC0;
- int alphaFalloff = 0x20;
+ int alphaFalloff = 0x10;
CmpPtr cmpPlayerManager(m_Simulation, SYSTEM_ENTITY);
Index: source/simulation2/components/CCmpTerritoryManager.cpp
===================================================================
--- source/simulation2/components/CCmpTerritoryManager.cpp
+++ source/simulation2/components/CCmpTerritoryManager.cpp
@@ -312,9 +312,9 @@
// shouldn't be expanded on its own. (without continue, an infinite loop will happen)
# define FLOODFILL(i, j, code)\
do {\
- const int NUM_NEIGHBOURS = 8;\
- const int NEIGHBOURS_X[NUM_NEIGHBOURS] = {1,-1, 0, 0, 1,-1, 1,-1};\
- const int NEIGHBOURS_Z[NUM_NEIGHBOURS] = {0, 0, 1,-1, 1,-1,-1, 1};\
+ const int NUM_NEIGHBOURS = 4;\
+ const int NEIGHBOURS_X[NUM_NEIGHBOURS] = {1,-1, 0, 0};\
+ const int NEIGHBOURS_Z[NUM_NEIGHBOURS] = {0, 0, 1,-1};\
std::queue openTiles;\
openTiles.emplace(i, j);\
while (!openTiles.empty())\
@@ -417,8 +417,14 @@
// Find all territory influence entities
CComponentManager::InterfaceList influences = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_TerritoryInfluence);
- // Split influence entities into per-player lists, ignoring any with invalid properties
- std::map > influenceEntities;
+ // Store the root influences to mark territory as connected
+ std::vector rootInfluenceEntities;
+
+ // Store the best weight (remaining steps), so that larger radius buildings can expand through smaller ones with the same owner
+ Grid bestWeightGrid(tilesW, tilesH);
+
+ std::queue initialTiles;
+
for (const CComponentManager::InterfacePair& pair : influences)
{
entity_id_t ent = pair.first;
@@ -432,83 +438,102 @@
if (owner <= 0 || owner > TERRITORY_PLAYER_MASK)
continue;
- influenceEntities[owner].push_back(ent);
- }
+ CmpPtr cmpPosition(GetSimContext(), ent);
+ if (!cmpPosition || !cmpPosition->IsInWorld())
+ continue;
- // Store the overall best weight for comparison
- Grid bestWeightGrid(tilesW, tilesH);
- // store the root influences to mark territory as connected
- std::vector rootInfluenceEntities;
+ CmpPtr cmpTerritoryInfluence(GetSimContext(), ent);
+ u32 radius = cmpTerritoryInfluence->GetRadius();
+ if (radius == 0)
+ continue;
- for (const std::pair >& pair : influenceEntities)
- {
- // entityGrid stores the weight for a single entity, and is reset per entity
- Grid entityGrid(tilesW, tilesH);
- // playerGrid stores the combined weight of all entities for this player
- Grid playerGrid(tilesW, tilesH);
-
- u8 owner = (u8)pair.first;
- const std::vector& ents = pair.second;
- // With 2^16 entities, we're safe against overflows as the weight is also limited to 2^16
- ENSURE(ents.size() < 1 << 16);
- // Compute the influence map of the current entity, then add it to the player grid
- for (entity_id_t ent : ents)
+ CFixedVector2D pos = cmpPosition->GetPosition2D();
+ u16 i, j;
+ NearestTerritoryTile(pos.X, pos.Y, i, j, tilesW, tilesH);
+
+ if (cmpTerritoryInfluence->IsRoot())
+ rootInfluenceEntities.push_back(ent);
+
+ // Use sqrt(2) = 7/5, so it takes 5 steps to move orthogonally and 7 steps to move diagonally
+ u32 weight = 5 * radius / (Pathfinding::NAVCELL_SIZE * NAVCELLS_PER_TERRITORY_TILE).ToInt_RoundToNegInfinity();
+
+ if (weight > bestWeightGrid.get(i, j))
{
- CmpPtr cmpPosition(GetSimContext(), ent);
- if (!cmpPosition || !cmpPosition->IsInWorld())
- continue;
+ bestWeightGrid.set(i, j, weight);
+ m_Territories->set(i, j, owner);
+ initialTiles.emplace(i, j);
+ }
+ }
- CmpPtr cmpTerritoryInfluence(GetSimContext(), ent);
- u32 weight = cmpTerritoryInfluence->GetWeight();
- u32 radius = cmpTerritoryInfluence->GetRadius();
- if (weight == 0 || radius == 0)
- continue;
- u32 falloff = weight * (Pathfinding::NAVCELL_SIZE * NAVCELLS_PER_TERRITORY_TILE).ToInt_RoundToNegInfinity() / radius;
+ // Modified floodfill
+ do {
+ const int NUM_NEIGHBOURS = 8;
+ const int NEIGHBOURS_X[NUM_NEIGHBOURS] = {1,-1, 0, 0, 1,-1, 1,-1};
+ const int NEIGHBOURS_Z[NUM_NEIGHBOURS] = {0, 0, 1,-1, 1,-1,-1, 1};
+ const int NEIGHBOURS_D[NUM_NEIGHBOURS] = {5, 5, 5, 5, 7, 7, 7, 7};
+ const int MAX_D = 8;
- CFixedVector2D pos = cmpPosition->GetPosition2D();
- u16 i, j;
- NearestTerritoryTile(pos.X, pos.Y, i, j, tilesW, tilesH);
-
- if (cmpTerritoryInfluence->IsRoot())
- rootInfluenceEntities.push_back(ent);
-
- // Initialise the tile under the entity
- entityGrid.set(i, j, weight);
- if (weight > bestWeightGrid.get(i, j))
- {
- bestWeightGrid.set(i, j, weight);
- m_Territories->set(i, j, owner);
- }
+ std::vector> openTiles(MAX_D);
+ openTiles[0] = initialTiles;
- // Expand influences outwards
- FLOODFILL(i, j,
- u32 dg = falloff * m_CostGrid->get(nx, nz);
-
- // diagonal neighbour -> multiply with approx sqrt(2)
- if (nx != x && nz != z)
- dg = (dg * 362) / 256;
-
- // Don't expand if new cost is not better than previous value for that tile
- // (arranged to avoid underflow if entityGrid.get(x, z) < dg)
- if (entityGrid.get(x, z) <= entityGrid.get(nx, nz) + dg)
- continue;
-
- // weight of this tile = weight of predecessor - falloff from predecessor
- u32 newWeight = entityGrid.get(x, z) - dg;
- u32 totalWeight = playerGrid.get(nx, nz) - entityGrid.get(nx, nz) + newWeight;
- playerGrid.set(nx, nz, totalWeight);
- entityGrid.set(nx, nz, newWeight);
- // if this weight is better than the best thus far, set the owner
- if (totalWeight > bestWeightGrid.get(nx, nz))
+ bool loop = true; // Track if we've processed any tiles
+ while (loop)
+ {
+ loop = false;
+ for (u32 b = 0; b < MAX_D; ++b)
+ {
+ loop |= !openTiles[b].empty();
+ while (!openTiles[b].empty())
{
- bestWeightGrid.set(nx, nz, totalWeight);
- m_Territories->set(nx, nz, owner);
+ u16 x = openTiles[b].front().x;
+ u16 z = openTiles[b].front().z;
+ openTiles[b].pop();
+
+ u8 owner = m_Territories->get(x, z);
+ u32 weight = bestWeightGrid.get(x, z);
+ bool sides[4] = {false, false, false, false};
+
+ for (int n = 0; n < NUM_NEIGHBOURS; ++n)
+ {
+ u16 nx = x + NEIGHBOURS_X[n];
+ u16 nz = z + NEIGHBOURS_Z[n];
+
+ /* Check the bounds, underflow will cause the values to be big again */
+ if (nx >= tilesW || nz >= tilesH)
+ continue;
+
+ u32 steps = m_CostGrid->get(nx, nz) * NEIGHBOURS_D[n];
+
+ // Quit if we can't move here
+ if (weight <= steps)
+ continue;
+
+ // Quit if the tile belongs to someone else
+ if (owner != m_Territories->get(nx, nz) && bestWeightGrid.get(nx, nz) > 0)
+ continue;
+
+ // If we've gotten this far, we either own the tile or will own the tile
+ if (n < 4)
+ sides[n] = true;
+
+ // Quit if the new weight is worse than its current weight
+ if (weight <= bestWeightGrid.get(nx, nz) + steps)
+ continue;
+
+ // Quit at a diagonal if we own neither of the adjacent sides
+ if ((n == 4 && !sides[0] && !sides[2]) || (n == 5 && !sides[1] && !sides[3]) ||
+ (n == 6 && !sides[0] && !sides[3]) || (n == 7 && !sides[1] && !sides[2]))
+ continue;
+
+ // Set the owner and new best weight, and add the tile to the queue
+ m_Territories->set(nx, nz, owner);
+ bestWeightGrid.set(nx, nz, weight - steps);
+ openTiles[(b + NEIGHBOURS_D[n]) % MAX_D].emplace(nx, nz);
+ }
}
- );
-
- entityGrid.reset();
+ }
}
- }
+ } while (false);
// Detect territories connected to a 'root' influence (typically a civ center)
// belonging to their player, and mark them with the connected flag
Index: source/simulation2/components/ICmpTerritoryManager.h
===================================================================
--- source/simulation2/components/ICmpTerritoryManager.h
+++ source/simulation2/components/ICmpTerritoryManager.h
@@ -35,7 +35,7 @@
* resolution, and a lower resolution can make the boundary lines look prettier
* and will take less memory, so we downsample the passability data.
*/
- static const int NAVCELLS_PER_TERRITORY_TILE = 8;
+ static const int NAVCELLS_PER_TERRITORY_TILE = 4;
static const int TERRITORY_PLAYER_MASK = 0x1F;
static const int TERRITORY_CONNECTED_MASK = 0x20;
Index: source/simulation2/helpers/Render.cpp
===================================================================
--- source/simulation2/helpers/Render.cpp
+++ source/simulation2/helpers/Render.cpp
@@ -462,8 +462,11 @@
// Interpolate at regular points across the interval
for (int sample = 0; sample < segmentSamples; sample++)
- newPoints.push_back(EvaluateSpline(sample/((float) segmentSamples), a0, a1, a2, a3, offset));
-
+ {
+ CVector2D w = EvaluateSpline(sample/((float) segmentSamples), a0, a1, a2, a3, offset);
+ if (newPoints.empty() || (w - newPoints.back()).Length() > 0.25f)
+ newPoints.push_back(w);
+ }
}
if (!closed)