Index: source/simulation2/components/CCmpTerritoryManager.cpp =================================================================== --- source/simulation2/components/CCmpTerritoryManager.cpp +++ source/simulation2/components/CCmpTerritoryManager.cpp @@ -41,6 +41,7 @@ #include "simulation2/helpers/Grid.h" #include "simulation2/helpers/Render.h" +#include #include class CCmpTerritoryManager; @@ -324,36 +325,51 @@ u16 x, z; }; -// Floodfill templates that expand neighbours from a certain source onwards -// (posX, posZ) are the coordinates of the currently expanded tile -// (nx, nz) are the coordinates of the current neighbour handled -// The user of this floodfill should use "continue" on every neighbour that -// 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};\ - std::queue openTiles;\ - openTiles.emplace(i, j);\ - while (!openTiles.empty())\ - {\ - u16 posX = openTiles.front().x;\ - u16 posZ = openTiles.front().z;\ - openTiles.pop();\ - for (int n = 0; n < NUM_NEIGHBOURS; ++n)\ - {\ - u16 nx = posX + NEIGHBOURS_X[n];\ - u16 nz = posZ + NEIGHBOURS_Z[n];\ - /* Check the bounds, underflow will cause the values to be big again */\ - if (nx >= tilesW || nz >= tilesH)\ - continue;\ - code\ - openTiles.emplace(nx, nz);\ - }\ - }\ - }\ - while (false) +/** + * Floodfill templates that expands tiles from a certain origin onwards. + * + * @param origin Where to start the floodfill. In the first iteration it is + * passed as the second argument to the @see predicate and the floodfill + * only continues when the invocation returns @c true. + * @param bound Tiles outside the bound are never exteded. The @see predicate + * isn't called with thous tiles as second argument. + * @param predicate It is called with the currently extended tile as the first + * argument and a neighbour as the second argument. The invocation shall + * return whether to extend the neighbour (without returning @c false, an + * infinite loop will occur). In the first iteration the @see predicate is + * invoked with a @c std::nullptr as the first argument and @see origin as + * the second argument. + */ +template +void Floodfill(const Tile& origin, const Tile& bound, Predicate predicate) +{ + constexpr std::array, 8> neighbours{{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, + {-1, -1}, {1, -1}, {-1, 1}}}; + std::queue openTiles; + + const auto emplaceIfRequested = [predicate = std::move(predicate), &openTiles]( + const auto& currentTile, const Tile& neighbourTile) + { + if (predicate(currentTile, neighbourTile)) + openTiles.emplace(neighbourTile); + }; + + emplaceIfRequested(std::nullopt, origin); + while (!openTiles.empty()) + { + const Tile currentTile{openTiles.front()}; + openTiles.pop(); + for (const std::array& neighbour : neighbours) + { + const Tile neighbourTile{static_cast(currentTile.x + std::get<0>(neighbour)), + static_cast(currentTile.z + std::get<1>(neighbour))}; + + // Check the bounds, underflow will cause the values to be big again. + if (neighbourTile.x < bound.x && neighbourTile.z < bound.z) + emplaceIfRequested(currentTile, neighbourTile); + } + } +} /** * Compute the tile indexes on the grid nearest to a given point @@ -491,40 +507,54 @@ 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); - } - // Expand influences outwards - FLOODFILL(i, j, - u32 dg = falloff * m_CostGrid->get(nx, nz); - - // diagonal neighbour -> multiply with approx sqrt(2) - if (nx != posX && nz != posZ) - 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(posX, posZ) <= entityGrid.get(nx, nz) + dg) - continue; - - // weight of this tile = weight of predecessor - falloff from predecessor - u32 newWeight = entityGrid.get(posX, posZ) - 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)) + Floodfill({i, j}, {tilesW, tilesH}, [&](const auto& current, const Tile& neighbour) { - bestWeightGrid.set(nx, nz, totalWeight); - m_Territories->set(nx, nz, owner); - } - ); - + constexpr bool neighbourIsOrigin{ + std::is_same_v}; + + const u32 dg{[&] + { + const u32 dg{falloff * m_CostGrid->get(neighbour.x, neighbour.z)}; + // diagonal neighbour -> multiply with approx sqrt(2) + if constexpr (!neighbourIsOrigin) + { + if (neighbour.x != current.x && neighbour.z != current.z) + return (dg * 362) / 256; + } + return dg; + }()}; + + // 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 constexpr (!neighbourIsOrigin) + if (entityGrid.get(current.x, current.z) <= + entityGrid.get(neighbour.x, neighbour.z) + dg) + { + return false; + } + + // weight of this tile = weight of predecessor - falloff from predecessor + const u32 newWeight{[&] + { + if constexpr (!neighbourIsOrigin) + return entityGrid.get(current.x, current.z) - dg; + return weight; + }()}; + const u32 totalWeight{newWeight + (neighbourIsOrigin ? 0 : + playerGrid.get(neighbour.x, neighbour.z) - + entityGrid.get(neighbour.x, neighbour.z))}; + + playerGrid.set(neighbour.x, neighbour.z, totalWeight); + entityGrid.set(neighbour.x, neighbour.z, newWeight); + // if this weight is better than the best thus far, set the owner + if (totalWeight > bestWeightGrid.get(neighbour.x, neighbour.z)) + { + bestWeightGrid.set(neighbour.x, neighbour.z, totalWeight); + m_Territories->set(neighbour.x, neighbour.z, owner); + } + return true; + }); entityGrid.reset(); } } @@ -543,22 +573,16 @@ u8 owner = (u8)cmpOwnership->GetOwner(); - if (m_Territories->get(i, j) != owner) - continue; - - m_Territories->set(i, j, owner | TERRITORY_CONNECTED_MASK); - - if (m_CostGrid->get(i, j) < m_ImpassableCost) - ++m_TerritoryCellCounts[owner]; - - FLOODFILL(i, j, - // Don't expand non-owner tiles, or tiles that already have a connected mask - if (m_Territories->get(nx, nz) != owner) - continue; - m_Territories->set(nx, nz, owner | TERRITORY_CONNECTED_MASK); - if (m_CostGrid->get(nx, nz) < m_ImpassableCost) - ++m_TerritoryCellCounts[owner]; - ); + Floodfill({i, j}, {tilesW, tilesH}, [&](const auto&, const Tile& neighbour) + { + // Don't expand non-owner tiles, or tiles that already have a connected mask + if (m_Territories->get(neighbour.x, neighbour.z) != owner) + return false; + m_Territories->set(neighbour.x, neighbour.z, owner | TERRITORY_CONNECTED_MASK); + if (m_CostGrid->get(neighbour.x, neighbour.z) < m_ImpassableCost) + ++m_TerritoryCellCounts[owner]; + return true; + }); } // Then recomputes the blinking tiles @@ -750,21 +774,22 @@ // use a flood-fill algorithm that fills up to the borders and remembers the owners Grid markerGrid(tilesW, tilesH); - markerGrid.set(i, j, true); - FLOODFILL(i, j, - if (markerGrid.get(nx, nz)) - continue; - // mark the tile as visited in any case - markerGrid.set(nx, nz, true); - int owner = m_Territories->get(nx, nz) & TERRITORY_PLAYER_MASK; - if (owner != thisOwner) + Floodfill({i, j}, {tilesW, tilesH}, [&](const auto&, const Tile& neighbour) { - if (owner == 0 || !filterConnected || (m_Territories->get(nx, nz) & TERRITORY_CONNECTED_MASK) != 0) - ret[owner]++; // add player to the neighbour list when requested - continue; // don't expand non-owner tiles further - } - ); + if (markerGrid.get(neighbour.x, neighbour.z)) + return false; + // mark the tile as visited in any case + markerGrid.set(neighbour.x, neighbour.z, true); + int owner = m_Territories->get(neighbour.x, neighbour.z) & TERRITORY_PLAYER_MASK; + if (owner != thisOwner) + { + if (owner == 0 || !filterConnected || (m_Territories->get(neighbour.x, neighbour.z) & TERRITORY_CONNECTED_MASK) != 0) + ret[owner]++; // add player to the neighbour list when requested + return false; // don't expand non-owner tiles further + } + return true; + }); return ret; } @@ -794,25 +819,20 @@ player_id_t thisOwner = m_Territories->get(i, j) & TERRITORY_PLAYER_MASK; - u8 bitmask = m_Territories->get(i, j); - u8 blinking = bitmask & TERRITORY_BLINKING_MASK; - if (enable && !blinking) - m_Territories->set(i, j, bitmask | TERRITORY_BLINKING_MASK); - else if (!enable && blinking) - m_Territories->set(i, j, bitmask & ~TERRITORY_BLINKING_MASK); - - FLOODFILL(i, j, - bitmask = m_Territories->get(nx, nz); - if ((bitmask & TERRITORY_PLAYER_MASK) != thisOwner) - continue; - blinking = bitmask & TERRITORY_BLINKING_MASK; - if (enable && !blinking) - m_Territories->set(nx, nz, bitmask | TERRITORY_BLINKING_MASK); - else if (!enable && blinking) - m_Territories->set(nx, nz, bitmask & ~TERRITORY_BLINKING_MASK); - else - continue; - ); + Floodfill({i, j}, {tilesW, tilesH}, [&](const auto&, const Tile& neighbour) + { + const u8 bitmask{m_Territories->get(neighbour.x, neighbour.z)}; + if ((bitmask & TERRITORY_PLAYER_MASK) != thisOwner) + return false; + const bool blinking{(bitmask & TERRITORY_BLINKING_MASK) != 0}; + if (enable != blinking) + { + m_Territories->set(neighbour.x, neighbour.z, enable ? + bitmask | TERRITORY_BLINKING_MASK : bitmask & ~TERRITORY_BLINKING_MASK); + return true; + } + return false; + }); ++m_DirtyBlinkingID; m_BoundaryLinesDirty = true; }