API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 28th, 2014
74
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Diff 11.46 KB | None | 0 0
raw download clone embed print report
  1. Index: source/simulation2/components/CCmpTerritoryManager.cpp
  2. ===================================================================
  3. --- source/simulation2/components/CCmpTerritoryManager.cpp  (revision 14692)
  4. +++ source/simulation2/components/CCmpTerritoryManager.cpp  (working copy)
  5. @@ -59,6 +59,8 @@
  6.     virtual void ProcessTile(ssize_t i, ssize_t j);
  7.  };
  8.  
  9. +static const int FALLOFF = 256;
  10. +
  11.  class CCmpTerritoryManager : public ICmpTerritoryManager
  12.  {
  13.  public:
  14. @@ -84,6 +86,7 @@
  15.     float m_BorderThickness;
  16.     float m_BorderSeparation;
  17.  
  18. +
  19.     // Player ID in bits 0-5 (TERRITORY_PLAYER_MASK);
  20.     // connected flag in bit 6 (TERRITORY_CONNECTED_MASK);
  21.     // processed flag in bit 7 (TERRITORY_PROCESSED_MASK)
  22. @@ -279,26 +282,52 @@
  23.  
  24.  typedef PriorityQueueHeap<std::pair<u16, u16>, u32, std::greater<u32> > OpenQueue;
  25.  
  26. -static void ProcessNeighbour(u32 falloff, u16 i, u16 j, u32 pg, bool diagonal,
  27. -       Grid<u32>& grid, OpenQueue& queue, const Grid<u8>& costGrid)
  28. +/**
  29. + * Compute the tile indexes on the grid nearest to a given point
  30. + */
  31. +static void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
  32.  {
  33. -   u32 dg = falloff * costGrid.get(i, j);
  34. +   i = (u16)clamp((x / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, w-1);
  35. +   j = (u16)clamp((z / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, h-1);
  36. +}
  37. +
  38. +/**
  39. + * Returns the position of the center of the given tile
  40. + */
  41. +static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
  42. +{
  43. +   x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2);
  44. +   z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2);
  45. +}
  46. +
  47. +static void ProcessNeighbour(u16 i, u16 j, u32 pg, bool diagonal,
  48. +       Grid<u32>& grid, OpenQueue& queue, const Grid<u8>& costGrid, Grid<u32>& territoryExtenderGrid)
  49. +{
  50. +   u32 dg = FALLOFF * costGrid.get(i, j);
  51.     if (diagonal)
  52.         dg = (dg * 362) / 256;
  53.  
  54. +   u32 g;
  55.     // Stop if new cost g=pg-dg is not better than previous value for that tile
  56.     // (arranged to avoid underflow if pg < dg)
  57.     if (pg <= grid.get(i, j) + dg)
  58. -       return;
  59. +   {
  60. +       if (!territoryExtenderGrid.get(i, j))
  61. +           return;
  62. +       // the tile was set by another entity. Add it to the queue anyway, but with the current weight
  63. +       g = territoryExtenderGrid.get(i, j);
  64. +   }
  65. +   else
  66. +   {
  67. +       g = pg - dg; // cost to this tile = cost to predecessor - falloff from predecessor
  68. +   }
  69.  
  70. -   u32 g = pg - dg; // cost to this tile = cost to predecessor - falloff from predecessor
  71. -
  72.     grid.set(i, j, g);
  73.     OpenQueue::Item tile = { std::make_pair(i, j), g };
  74.     queue.push(tile);
  75.  }
  76.  
  77. -static void FloodFill(Grid<u32>& grid, Grid<u8>& costGrid, OpenQueue& openTiles, u32 falloff)
  78. +static void FloodFill(Grid<u32>& grid, Grid<u8>& costGrid, OpenQueue& openTiles, Grid<u32>& territoryExtenderGrid)
  79.  {
  80.     u16 tilesW = grid.m_W;
  81.     u16 tilesH = grid.m_H;
  82. @@ -311,21 +340,21 @@
  83.         u16 x = tile.id.first;
  84.         u16 z = tile.id.second;
  85.         if (x > 0)
  86. -           ProcessNeighbour(falloff, (u16)(x-1), z, tile.rank, false, grid, openTiles, costGrid);
  87. +           ProcessNeighbour((u16)(x-1), z, tile.rank, false, grid, openTiles, costGrid, territoryExtenderGrid);
  88.         if (x < tilesW-1)
  89. -           ProcessNeighbour(falloff, (u16)(x+1), z, tile.rank, false, grid, openTiles, costGrid);
  90. +           ProcessNeighbour((u16)(x+1), z, tile.rank, false, grid, openTiles, costGrid, territoryExtenderGrid);
  91.         if (z > 0)
  92. -           ProcessNeighbour(falloff, x, (u16)(z-1), tile.rank, false, grid, openTiles, costGrid);
  93. +           ProcessNeighbour(x, (u16)(z-1), tile.rank, false, grid, openTiles, costGrid, territoryExtenderGrid);
  94.         if (z < tilesH-1)
  95. -           ProcessNeighbour(falloff, x, (u16)(z+1), tile.rank, false, grid, openTiles, costGrid);
  96. +           ProcessNeighbour(x, (u16)(z+1), tile.rank, false, grid, openTiles, costGrid, territoryExtenderGrid);
  97.         if (x > 0 && z > 0)
  98. -           ProcessNeighbour(falloff, (u16)(x-1), (u16)(z-1), tile.rank, true, grid, openTiles, costGrid);
  99. +           ProcessNeighbour((u16)(x-1), (u16)(z-1), tile.rank, true, grid, openTiles, costGrid, territoryExtenderGrid);
  100.         if (x > 0 && z < tilesH-1)
  101. -           ProcessNeighbour(falloff, (u16)(x-1), (u16)(z+1), tile.rank, true, grid, openTiles, costGrid);
  102. +           ProcessNeighbour((u16)(x-1), (u16)(z+1), tile.rank, true, grid, openTiles, costGrid, territoryExtenderGrid);
  103.         if (x < tilesW-1 && z > 0)
  104. -           ProcessNeighbour(falloff, (u16)(x+1), (u16)(z-1), tile.rank, true, grid, openTiles, costGrid);
  105. +           ProcessNeighbour((u16)(x+1), (u16)(z-1), tile.rank, true, grid, openTiles, costGrid, territoryExtenderGrid);
  106.         if (x < tilesW-1 && z < tilesH-1)
  107. -           ProcessNeighbour(falloff, (u16)(x+1), (u16)(z+1), tile.rank, true, grid, openTiles, costGrid);
  108. +           ProcessNeighbour((u16)(x+1), (u16)(z+1), tile.rank, true, grid, openTiles, costGrid, territoryExtenderGrid);
  109.     }
  110.  }
  111.  
  112. @@ -380,7 +409,6 @@
  113.  
  114.     // Split influence entities into per-player lists, ignoring any with invalid properties
  115.     std::map<player_id_t, std::vector<entity_id_t> > influenceEntities;
  116. -   std::vector<entity_id_t> rootInfluenceEntities;
  117.     for (CComponentManager::InterfaceList::iterator it = influences.begin(); it != influences.end(); ++it)
  118.     {
  119.         // Ignore any with no weight or radius (to avoid divide-by-zero later)
  120. @@ -401,25 +429,20 @@
  121.         if (owner > TERRITORY_PLAYER_MASK)
  122.             continue;
  123.  
  124. -       // Ignore if invalid position
  125. +       // check valid position
  126.         CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), it->first);
  127. -       if (!cmpPosition || !cmpPosition->IsInWorld())
  128. -           continue;
  129. -
  130. -       influenceEntities[owner].push_back(it->first);
  131. -
  132. -       if (cmpTerritoryInfluence->IsRoot())
  133. -           rootInfluenceEntities.push_back(it->first);
  134. +       if (cmpPosition && cmpPosition->IsInWorld())
  135. +           influenceEntities[owner].push_back(it->first);
  136.     }
  137.  
  138.     // For each player, store the sum of influences on each tile
  139.     std::vector<std::pair<player_id_t, Grid<u32> > > playerGrids;
  140. -   // TODO: this is a large waste of memory; we don't really need to store
  141. -   // all the intermediate grids
  142.  
  143.     for (std::map<player_id_t, std::vector<entity_id_t> >::iterator it = influenceEntities.begin(); it != influenceEntities.end(); ++it)
  144.     {
  145.         Grid<u32> playerGrid(tilesW, tilesH);
  146. +       Grid<u32> territoryExtenderGrid(tilesW, tilesH);
  147. +       OpenQueue openTiles;
  148.  
  149.         std::vector<entity_id_t>& ents = it->second;
  150.         for (std::vector<entity_id_t>::iterator eit = ents.begin(); eit != ents.end(); ++eit)
  151. @@ -426,33 +449,32 @@
  152.         {
  153.             // Compute the influence map of the current entity, then add it to the player grid
  154.  
  155. -           Grid<u32> entityGrid(tilesW, tilesH);
  156. -
  157.             CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), *eit);
  158.             CFixedVector2D pos = cmpPosition->GetPosition2D();
  159. -           u16 i = (u16)clamp((pos.X / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNegInfinity(), 0, tilesW-1);
  160. -           u16 j = (u16)clamp((pos.Y / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNegInfinity(), 0, tilesH-1);
  161. +           u16 i, j;
  162. +           NearestTile(pos.X, pos.Y, i, j, tilesW, tilesH);
  163.  
  164.             CmpPtr<ICmpTerritoryInfluence> cmpTerritoryInfluence(GetSimContext(), *eit);
  165. -           u32 weight = cmpTerritoryInfluence->GetWeight();
  166. -           u32 radius = cmpTerritoryInfluence->GetRadius() / TERRAIN_TILE_SIZE;
  167. -           u32 falloff = weight / radius; // earlier check for GetRadius() == 0 prevents divide-by-zero
  168. +           u32 radius = cmpTerritoryInfluence->GetRadius() * FALLOFF / TERRAIN_TILE_SIZE;
  169.  
  170. -           // TODO: we should have some maximum value on weight, to avoid overflow
  171. +           // TODO: we should have some maximum value on radius, to avoid overflow
  172.             // when doing all the sums
  173.  
  174.             // Initialise the tile under the entity
  175. -           entityGrid.set(i, j, weight);
  176. -           OpenQueue openTiles;
  177. -           OpenQueue::Item tile = { std::make_pair((u16)i, (i16)j), weight };
  178. -           openTiles.push(tile);
  179. -
  180. -           // Expand influences outwards
  181. -           FloodFill(entityGrid, influenceGrid, openTiles, falloff);
  182. -
  183. -           // TODO: we should do a sparse grid and only add the non-zero regions, for performance
  184. -           playerGrid.add(entityGrid);
  185. +           if (cmpTerritoryInfluence->IsRoot())
  186. +           {
  187. +               playerGrid.set(i, j, radius);
  188. +               OpenQueue::Item tile = { std::make_pair((u16)i, (i16)j), radius };
  189. +               openTiles.push(tile);
  190. +           }
  191. +           else
  192. +           {
  193. +               // if it's only a territory extender, store it in a separate grid
  194. +               // and don't visit the tiles by default
  195. +               territoryExtenderGrid.set(i, j, radius);
  196. +           }
  197.         }
  198. +       FloodFill(playerGrid, influenceGrid, openTiles, territoryExtenderGrid);
  199.  
  200.         playerGrids.push_back(std::make_pair(it->first, playerGrid));
  201.     }
  202. @@ -469,90 +491,15 @@
  203.                 if (w > bestWeight)
  204.                 {
  205.                     player_id_t id = playerGrids[k].first;
  206. -                   m_Territories->set(i, j, (u8)id);
  207. +                   m_Territories->set(i, j, (u8)id | TERRITORY_CONNECTED_MASK);
  208.                     bestWeight = w;
  209.                 }
  210.             }
  211.         }
  212.     }
  213. -
  214. -   // Detect territories connected to a 'root' influence (typically a civ center)
  215. -   // belonging to their player, and mark them with the connected flag
  216. -   for (std::vector<entity_id_t>::iterator it = rootInfluenceEntities.begin(); it != rootInfluenceEntities.end(); ++it)
  217. -   {
  218. -       // (These components must be valid else the entities wouldn't be added to this list)
  219. -       CmpPtr<ICmpOwnership> cmpOwnership(GetSimContext(), *it);
  220. -       CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), *it);
  221. -
  222. -       CFixedVector2D pos = cmpPosition->GetPosition2D();
  223. -       u16 i = (u16)clamp((pos.X / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNegInfinity(), 0, tilesW-1);
  224. -       u16 j = (u16)clamp((pos.Y / (int)TERRAIN_TILE_SIZE).ToInt_RoundToNegInfinity(), 0, tilesH-1);
  225. -
  226. -       u8 owner = (u8)cmpOwnership->GetOwner();
  227. -
  228. -       if (m_Territories->get(i, j) != owner)
  229. -           continue;
  230. -
  231. -       // TODO: would be nice to refactor some of the many flood fill
  232. -       // algorithms in this component
  233. -
  234. -       Grid<u8>& grid = *m_Territories;
  235. -
  236. -       u16 maxi = (u16)(grid.m_W-1);
  237. -       u16 maxj = (u16)(grid.m_H-1);
  238. -
  239. -       std::vector<std::pair<u16, u16> > tileStack;
  240. -
  241. -#define MARK_AND_PUSH(i, j) STMT(grid.set(i, j, owner | TERRITORY_CONNECTED_MASK); tileStack.push_back(std::make_pair(i, j)); )
  242. -
  243. -       MARK_AND_PUSH(i, j);
  244. -       while (!tileStack.empty())
  245. -       {
  246. -           int ti = tileStack.back().first;
  247. -           int tj = tileStack.back().second;
  248. -           tileStack.pop_back();
  249. -
  250. -           if (ti > 0 && grid.get(ti-1, tj) == owner)
  251. -               MARK_AND_PUSH(ti-1, tj);
  252. -           if (ti < maxi && grid.get(ti+1, tj) == owner)
  253. -               MARK_AND_PUSH(ti+1, tj);
  254. -           if (tj > 0 && grid.get(ti, tj-1) == owner)
  255. -               MARK_AND_PUSH(ti, tj-1);
  256. -           if (tj < maxj && grid.get(ti, tj+1) == owner)
  257. -               MARK_AND_PUSH(ti, tj+1);
  258. -
  259. -           if (ti > 0 && tj > 0 && grid.get(ti-1, tj-1) == owner)
  260. -               MARK_AND_PUSH(ti-1, tj-1);
  261. -           if (ti > 0 && tj < maxj && grid.get(ti-1, tj+1) == owner)
  262. -               MARK_AND_PUSH(ti-1, tj+1);
  263. -           if (ti < maxi && tj > 0 && grid.get(ti+1, tj-1) == owner)
  264. -               MARK_AND_PUSH(ti+1, tj-1);
  265. -           if (ti < maxi && tj < maxj && grid.get(ti+1, tj+1) == owner)
  266. -               MARK_AND_PUSH(ti+1, tj+1);
  267. -       }
  268. -
  269. -#undef MARK_AND_PUSH
  270. -   }
  271.  }
  272.  
  273. -/**
  274. - * Compute the tile indexes on the grid nearest to a given point
  275. - */
  276. -static void NearestTile(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
  277. -{
  278. -   i = (u16)clamp((x / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, w-1);
  279. -   j = (u16)clamp((z / (int)TERRAIN_TILE_SIZE).ToInt_RoundToZero(), 0, h-1);
  280. -}
  281.  
  282. -/**
  283. - * Returns the position of the center of the given tile
  284. - */
  285. -static void TileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
  286. -{
  287. -   x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2);
  288. -   z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE/2);
  289. -}
  290. -
  291.  // TODO: would be nice not to duplicate those two functions from CCmpObstructionManager.cpp
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!