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)