Changeset 9906 for ps

Timestamp:

07/24/11 13:42:35 (13 years ago)

Author:

philip

Message:

# New dynamic territories design

Location:

ps/trunk

Files:

• binaries/data/mods/public/simulation/templates/special/territory_block.xml (modified) (1 diff)
• binaries/data/mods/public/simulation/templates/special/territory_pull.xml (modified) (1 diff)
• binaries/data/mods/public/simulation/templates/template_structure_civic_civil_centre.xml (modified) (1 diff)
• binaries/data/mods/public/simulation/templates/template_structure_civic_house.xml (modified) (1 diff)
• source/simulation2/components/CCmpTerritoryInfluence.cpp (modified) (3 diffs)
• source/simulation2/components/CCmpTerritoryManager.cpp (modified) (7 diffs)
• source/simulation2/components/ICmpTerritoryInfluence.h (modified) (1 diff)
• source/simulation2/helpers/PriorityQueue.h (modified) (7 diffs)

ps/trunk/binaries/data/mods/public/simulation/templates/special/territory_block.xml

@@ -29 +29 @@
   </VisualActor>
   <TerritoryInfluence>
-    <OverrideCost>100</OverrideCost>
+    <OverrideCost>64</OverrideCost>
+    <Weight>0</Weight>
+    <Radius>0</Radius>
   </TerritoryInfluence>
 </Entity>

ps/trunk/binaries/data/mods/public/simulation/templates/special/territory_pull.xml

@@ -30 +30 @@
   <TerritoryInfluence>
     <OverrideCost>0</OverrideCost>
+    <Weight>0</Weight>
+    <Radius>0</Radius>
   </TerritoryInfluence>
 </Entity>

ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_civic_civil_centre.xml

@@ -68 +68 @@
     </Entities>
   </TrainingQueue>
+  <TerritoryInfluence>
+    <Radius>256</Radius>
+    <Weight>65536</Weight>
+  </TerritoryInfluence>
 </Entity>

ps/trunk/binaries/data/mods/public/simulation/templates/template_structure_civic_house.xml

@@ -55 +55 @@
     </Entities>
   </TrainingQueue>
+  <TerritoryInfluence>
+    <Radius>64</Radius>
+    <Weight>65536</Weight>
+  </TerritoryInfluence>
 </Entity>

ps/trunk/source/simulation2/components/CCmpTerritoryInfluence.cpp

@@ -30 +30 @@
     DEFAULT_COMPONENT_ALLOCATOR(TerritoryInfluence)
 
-    u8 m_Cost;
+    int m_Cost;
+    u32 m_Weight;
+    u32 m_Radius;
 
     static std::string GetSchema()
     {
         return
-            "<element name='OverrideCost'>"
+            "<optional>"
+                "<element name='OverrideCost'>"
+                    "<data type='nonNegativeInteger'>"
+                        "<param name='maxInclusive'>255</param>"
+                    "</data>"
+                "</element>"
+            "</optional>"
+            "<element name='Weight'>"
+                "<data type='nonNegativeInteger'/>"
+            "</element>"
+            "<element name='Radius'>"
                 "<data type='nonNegativeInteger'/>"
             "</element>";
@@ -42 +54 @@
     virtual void Init(const CParamNode& paramNode)
     {
-        m_Cost = paramNode.GetChild("OverrideCost").ToInt();
+        if (paramNode.GetChild("OverrideCost").IsOk())
+            m_Cost = paramNode.GetChild("OverrideCost").ToInt();
+        else
+            m_Cost = -1;
+
+        m_Weight = paramNode.GetChild("Weight").ToInt();
+        m_Radius = paramNode.GetChild("Radius").ToInt();
     }
 
@@ -58 +76 @@
     }
 
-    virtual u8 GetCost()
+    virtual int GetCost()
     {
         return m_Cost;
     }
 
+    virtual u32 GetWeight()
+    {
+        return m_Weight;
+    }
+
+    virtual u32 GetRadius()
+    {
+        return m_Radius;
+    }
 };
 

ps/trunk/source/simulation2/components/CCmpTerritoryManager.cpp

@@ -28 +28 @@
 #include "simulation2/components/ICmpObstruction.h"
 #include "simulation2/components/ICmpObstructionManager.h"
+#include "simulation2/components/ICmpOwnership.h"
 #include "simulation2/components/ICmpPathfinder.h"
 #include "simulation2/components/ICmpPosition.h"
@@ -168 +169 @@
      * or 1+c if the influence have cost c (assumed between 0 and 254).
      */
-    void RasteriseInfluences(Grid<u8>& grid);
+    void RasteriseInfluences(CComponentManager::InterfaceList& infls, Grid<u8>& grid);
 };
 
@@ -175 +176 @@
 
 /*
-
-We compute territory influences with a kind of best-first search:
- 1) Initialise an 'open' list with tiles that contain settlements (annotated with
-    territory ID) with initial cost 0
- 2) Pick the lowest cost tile from 'item'
- 3) For each neighbour which has not already been assigned to a territory,
-    assign it to this territory and compute its new cost (effectively the
-    distance from the associated settlement) and add to 'open'
- 4) Go to 2 until 'open' is empty
-
+We compute the territory influence of an entity with a kind of best-first search,
+storing an 'open' list of tiles that have not yet been processed,
+then taking the highest-weight tile (closest to origin) and updating the weight
+of extending to each neighbour (based on radius-determining 'falloff' value,
+adjusted by terrain movement cost), and repeating until all tiles are processed.
 */
 
-typedef PriorityQueueHeap<std::pair<u16, u16>, u32> OpenQueue;
-
-static void ProcessNeighbour(u8 pid, u16 i, u16 j, u32 pg, bool diagonal,
-        Grid<u8>& grid, OpenQueue& queue, const Grid<u8>& influenceGrid)
-{
-    // Ignore tiles that are already claimed
-    u8 id = grid.get(i, j);
-    if (id)
+typedef PriorityQueueHeap<std::pair<u16, u16>, u32, std::greater<u32> > OpenQueue;
+
+static void ProcessNeighbour(u32 falloff, u16 i, u16 j, u32 pg, bool diagonal,
+        Grid<u32>& grid, OpenQueue& queue, const Grid<u8>& costGrid)
+{
+    u32 dg = falloff * costGrid.get(i, j);
+    if (diagonal)
+        dg = (dg * 362) / 256;
+
+    // Stop if new cost g=pg-dg is not better than previous value for that tile
+    // (arranged to avoid underflow if pg < dg)
+    if (pg <= grid.get(i, j) + dg)
         return;
 
-    // Base cost for moving onto this tile
-    u32 dg = diagonal ? 362 : 256;
-
-    // Adjust cost based on this tile's influences
-    dg *= influenceGrid.get(i, j);
-
-    u32 g = pg + dg; // cost to this tile = cost to predecessor + delta from predecessor
-
-    grid.set(i, j, pid);
+    u32 g = pg - dg; // cost to this tile = cost to predecessor - falloff from predecessor
+
+    grid.set(i, j, g);
     OpenQueue::Item tile = { std::make_pair(i, j), g };
     queue.push(tile);
 }
 
-void CCmpTerritoryManager::CalculateTerritories()
-{
-    PROFILE("CalculateTerritories");
-
-    if (m_Territories)
-        return;
-
-    CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
-    uint32_t tilesW = cmpTerrain->GetVerticesPerSide() - 1;
-    uint32_t tilesH = cmpTerrain->GetVerticesPerSide() - 1;
-
-    Grid<u8> influenceGrid(tilesW, tilesH);
-
-    RasteriseInfluences(influenceGrid);
-
-    SAFE_DELETE(m_Territories);
-    m_Territories = new Grid<u8>(tilesW, tilesH);
-
-    CmpPtr<ICmpPathfinder> cmpPathfinder(GetSimContext(), SYSTEM_ENTITY);
-    ICmpPathfinder::pass_class_t passClass = cmpPathfinder->GetPassabilityClass("default");
-    const Grid<u16>& passGrid = cmpPathfinder->GetPassabilityGrid();
-
-    // Adjust influenceGrid so it contains terrain-passability-dependent costs,
-    // unless overridden by existing values in influenceGrid
-    for (u32 j = 0; j < tilesH; ++j)
-    {
-        for (u32 i = 0; i < tilesW; ++i)
-        {
-            u8 cost;
-            u8 inflCost = influenceGrid.get(i, j);
-            if (inflCost)
-            {
-                cost = inflCost-1; // undo RasteriseInfluences's offset
-            }
-            else
-            {
-                if (passGrid.get(i, j) & passClass)
-                    cost = 100;
-                else
-                    cost = 1;
-            }
-            influenceGrid.set(i, j, cost);
-        }
-    }
-
-    OpenQueue openTiles;
-
-    // Initialise open list with all settlements
-
-    CComponentManager::InterfaceList settlements = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_Settlement);
-    u8 id = 1;
-    for (CComponentManager::InterfaceList::iterator it = settlements.begin(); it != settlements.end(); ++it)
-    {
-        entity_id_t settlement = it->first;
-        CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), settlement);
-        if (cmpPosition.null() || !cmpPosition->IsInWorld())
-            continue;
-
-        // TODO: maybe we need to ignore settlements with owner -1,
-        // since they're probably destroyed
-
-        CFixedVector2D pos = cmpPosition->GetPosition2D();
-        int i = clamp((pos.X / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesW-1);
-        int j = clamp((pos.Y / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesH-1);
-
-        // Must avoid duplicates in the priority queue; ignore the settlement
-        // if there's already one on that tile
-        if (!m_Territories->get(i, j))
-        {
-            m_Territories->set(i, j, id);
-            OpenQueue::Item tile = { std::make_pair((u16)i, (i16)j), 0 };
-            openTiles.push(tile);
-        }
-
-        id += 1;
-    }
+static void FloodFill(Grid<u32>& grid, Grid<u8>& costGrid, OpenQueue& openTiles, u32 falloff)
+{
+    u32 tilesW = grid.m_W;
+    u32 tilesH = grid.m_H;
 
     while (!openTiles.empty())
     {
         OpenQueue::Item tile = openTiles.pop();
-
-        // Get current tile's territory ID
-        u8 tid = m_Territories->get(tile.id.first, tile.id.second);
 
         // Process neighbours (if they're not off the edge of the map)
@@ -298 +217 @@
         u16 z = tile.id.second;
         if (x > 0)
-            ProcessNeighbour(tid, x-1, z, tile.rank, false, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x-1, z, tile.rank, false, grid, openTiles, costGrid);
         if (x < tilesW-1)
-            ProcessNeighbour(tid, x+1, z, tile.rank, false, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x+1, z, tile.rank, false, grid, openTiles, costGrid);
         if (z > 0)
-            ProcessNeighbour(tid, x, z-1, tile.rank, false, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x, z-1, tile.rank, false, grid, openTiles, costGrid);
         if (z < tilesH-1)
-            ProcessNeighbour(tid, x, z+1, tile.rank, false, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x, z+1, tile.rank, false, grid, openTiles, costGrid);
         if (x > 0 && z > 0)
-            ProcessNeighbour(tid, x-1, z-1, tile.rank, true, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x-1, z-1, tile.rank, true, grid, openTiles, costGrid);
         if (x > 0 && z < tilesH-1)
-            ProcessNeighbour(tid, x-1, z+1, tile.rank, true, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x-1, z+1, tile.rank, true, grid, openTiles, costGrid);
         if (x < tilesW-1 && z > 0)
-            ProcessNeighbour(tid, x+1, z-1, tile.rank, true, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x+1, z-1, tile.rank, true, grid, openTiles, costGrid);
         if (x < tilesW-1 && z < tilesH-1)
-            ProcessNeighbour(tid, x+1, z+1, tile.rank, true, *m_Territories, openTiles, influenceGrid);
+            ProcessNeighbour(falloff, x+1, z+1, tile.rank, true, grid, openTiles, costGrid);
+    }
+}
+
+void CCmpTerritoryManager::CalculateTerritories()
+{
+    PROFILE("CalculateTerritories");
+
+    if (m_Territories)
+        return;
+
+    CmpPtr<ICmpTerrain> cmpTerrain(GetSimContext(), SYSTEM_ENTITY);
+    uint32_t tilesW = cmpTerrain->GetVerticesPerSide() - 1;
+    uint32_t tilesH = cmpTerrain->GetVerticesPerSide() - 1;
+
+    SAFE_DELETE(m_Territories);
+    m_Territories = new Grid<u8>(tilesW, tilesH);
+
+    // Compute terrain-passability-dependent costs per tile
+    Grid<u8> influenceGrid(tilesW, tilesH);
+
+    CmpPtr<ICmpPathfinder> cmpPathfinder(GetSimContext(), SYSTEM_ENTITY);
+    ICmpPathfinder::pass_class_t passClass = cmpPathfinder->GetPassabilityClass("default");
+    const Grid<u16>& passGrid = cmpPathfinder->GetPassabilityGrid();
+    for (u32 j = 0; j < tilesH; ++j)
+    {
+        for (u32 i = 0; i < tilesW; ++i)
+        {
+            u8 cost;
+            if (passGrid.get(i, j) & passClass)
+                cost = 4; // TODO: should come from some XML file
+            else
+                cost = 1;
+            influenceGrid.set(i, j, cost);
+        }
+    }
+
+    // Find all territory influence entities
+    CComponentManager::InterfaceList influences = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_TerritoryInfluence);
+
+    // Allow influence entities to override the terrain costs
+    RasteriseInfluences(influences, influenceGrid);
+
+    // Split influence entities into per-player lists, ignoring any with invalid properties
+    std::map<player_id_t, std::vector<entity_id_t> > influenceEntities;
+    for (CComponentManager::InterfaceList::iterator it = influences.begin(); it != influences.end(); ++it)
+    {
+        // Ignore any with no weight or radius (to avoid divide-by-zero later)
+        ICmpTerritoryInfluence* cmpTerritoryInfluence = static_cast<ICmpTerritoryInfluence*>(it->second);
+        if (cmpTerritoryInfluence->GetWeight() == 0 || cmpTerritoryInfluence->GetRadius() == 0)
+            continue;
+
+        CmpPtr<ICmpOwnership> cmpOwnership(GetSimContext(), it->first);
+        if (cmpOwnership.null())
+            continue;
+
+        // Ignore Gaia and unassigned
+        player_id_t owner = cmpOwnership->GetOwner();
+        if (owner <= 0)
+            continue;
+
+        // Ignore if invalid position
+        CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), it->first);
+        if (cmpPosition.null() || !cmpPosition->IsInWorld())
+            continue;
+
+        influenceEntities[owner].push_back(it->first);
+    }
+
+    // For each player, store the sum of influences on each tile
+    std::vector<std::pair<player_id_t, Grid<u32> > > playerGrids;
+    // TODO: this is a large waste of memory; we don't really need to store
+    // all the intermediate grids
+
+    for (std::map<player_id_t, std::vector<entity_id_t> >::iterator it = influenceEntities.begin(); it != influenceEntities.end(); ++it)
+    {
+        Grid<u32> playerGrid(tilesW, tilesH);
+
+        std::vector<entity_id_t>& ents = it->second;
+        for (std::vector<entity_id_t>::iterator eit = ents.begin(); eit != ents.end(); ++eit)
+        {
+            // Compute the influence map of the current entity, then add it to the player grid
+
+            Grid<u32> entityGrid(tilesW, tilesH);
+
+            CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), *eit);
+            CFixedVector2D pos = cmpPosition->GetPosition2D();
+            int i = clamp((pos.X / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesW-1);
+            int j = clamp((pos.Y / (int)CELL_SIZE).ToInt_RoundToNegInfinity(), 0, (int)tilesH-1);
+
+            CmpPtr<ICmpTerritoryInfluence> cmpTerritoryInfluence(GetSimContext(), *eit);
+            u32 weight = cmpTerritoryInfluence->GetWeight();
+            u32 radius = cmpTerritoryInfluence->GetRadius() / CELL_SIZE;
+            u32 falloff = weight / radius; // earlier check for GetRadius() == 0 prevents divide-by-zero
+
+            // TODO: we should have some maximum value on weight, to avoid overflow
+            // when doing all the sums
+
+            // Initialise the tile under the entity
+            entityGrid.set(i, j, weight);
+            OpenQueue openTiles;
+            OpenQueue::Item tile = { std::make_pair((u16)i, (i16)j), weight };
+            openTiles.push(tile);
+
+            // Expand influences outwards
+            FloodFill(entityGrid, influenceGrid, openTiles, falloff);
+
+            // TODO: we should do a sparse grid and only add the non-zero regions, for performance
+            for (u16 j = 0; j < entityGrid.m_H; ++j)
+                for (u16 i = 0; i < entityGrid.m_W; ++i)
+                    playerGrid.set(i, j, playerGrid.get(i, j) + entityGrid.get(i, j));
+        }
+
+        playerGrids.push_back(std::make_pair(it->first, playerGrid));
+    }
+
+    // Set m_Territories to the player ID with the highest influence for each tile
+    for (u16 j = 0; j < tilesH; ++j)
+    {
+        for (u16 i = 0; i < tilesW; ++i)
+        {
+            u32 bestWeight = 0;
+            for (size_t k = 0; k < playerGrids.size(); ++k)
+            {
+                u32 w = playerGrids[k].second.get(i, j);
+                if (w > bestWeight)
+                {
+                    player_id_t id = playerGrids[k].first;
+                    m_Territories->set(i, j, (u8)id);
+                    bestWeight = w;
+                }
+            }
+        }
     }
 }
@@ -337 +388 @@
 
 
-void CCmpTerritoryManager::RasteriseInfluences(Grid<u8>& grid)
-{
-    CComponentManager::InterfaceList infls = GetSimContext().GetComponentManager().GetEntitiesWithInterface(IID_TerritoryInfluence);
+void CCmpTerritoryManager::RasteriseInfluences(CComponentManager::InterfaceList& infls, Grid<u8>& grid)
+{
     for (CComponentManager::InterfaceList::iterator it = infls.begin(); it != infls.end(); ++it)
     {
         ICmpTerritoryInfluence* cmpTerritoryInfluence = static_cast<ICmpTerritoryInfluence*>(it->second);
+
+        int cost = cmpTerritoryInfluence->GetCost();
+        if (cost == -1)
+            continue;
 
         CmpPtr<ICmpObstruction> cmpObstruction(GetSimContext(), it->first);
@@ -351 +405 @@
         if (!cmpObstruction->GetObstructionSquare(square))
             continue;
-
-        u8 cost = cmpTerritoryInfluence->GetCost();
 
         CFixedVector2D halfSize(square.hw, square.hh);
@@ -367 +419 @@
                 TileCenter(i, j, x, z);
                 if (Geometry::PointIsInSquare(CFixedVector2D(x - square.x, z - square.z), square.u, square.v, halfSize))
-                    grid.set(i, j, cost+1);
+                    grid.set(i, j, cost);
             }
         }

ps/trunk/source/simulation2/components/ICmpTerritoryInfluence.h

@@ -24 +24 @@
 {
 public:
-    virtual u8 GetCost() = 0;
+    /**
+     * Returns either -1 to indicate no special terrain cost, or a value
+     * in [0, 255] to indicate overriding the normal cost of the terrain
+     * under the entity's obstruction.
+     */
+    virtual int GetCost() = 0;
+
+    virtual u32 GetWeight() = 0;
+
+    virtual u32 GetRadius() = 0;
 
     DECLARE_INTERFACE_TYPE(TerritoryInfluence)

ps/trunk/source/simulation2/helpers/PriorityQueue.h

@@ -30 +30 @@
 #endif
 
-template <typename Item>
+template <typename Item, typename CMP>
 struct QueueItemPriority
 {
     bool operator()(const Item& a, const Item& b)
     {
-        if (a.rank > b.rank) // higher costs are lower priority
+        if (CMP()(b.rank, a.rank)) // higher costs are lower priority
             return true;
-        if (a.rank < b.rank)
+        if (CMP()(a.rank, b.rank))
             return false;
         // Need to tie-break to get a consistent ordering
@@ -58 +58 @@
  * so we shouldn't use it unless we reimplement the heap functions more efficiently.
  */
-template <typename ID, typename R>
+template <typename ID, typename R, typename CMP = std::less<R> >
 class PriorityQueueHeap
 {
@@ -71 +71 @@
     {
         m_Heap.push_back(item);
-        push_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item>());
+        push_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item, CMP>());
     }
 
@@ -94 +94 @@
 #endif
                 m_Heap[n].rank = newrank;
-                push_heap(m_Heap.begin(), m_Heap.begin()+n+1, QueueItemPriority<Item>());
+                push_heap(m_Heap.begin(), m_Heap.begin()+n+1, QueueItemPriority<Item, CMP>());
                 return;
             }
@@ -106 +106 @@
 #endif
         Item r = m_Heap.front();
-        pop_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item>());
+        pop_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item, CMP>());
         m_Heap.pop_back();
         return r;
@@ -131 +131 @@
  * much simpler and less susceptible to MSVC's painfully slow debug STL.
  */
-template <typename ID, typename R>
+template <typename ID, typename R, typename CMP = std::less<R> >
 class PriorityQueueList
 {
@@ -172 +172 @@
         for (ssize_t i = (ssize_t)bestidx-1; i >= 0; --i)
         {
-            if (QueueItemPriority<Item>()(best, m_List[i]))
+            if (QueueItemPriority<Item, CMP>()(best, m_List[i]))
             {
                 bestidx = i;