LCOV - code coverage report
Current view: top level - source/graphics - TerritoryBoundary.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 86 86 100.0 %
Date: 2023-01-19 00:18:29 Functions: 3 3 100.0 %

          Line data    Source code
       1             : /* Copyright (C) 2012 Wildfire Games.
       2             :  * This file is part of 0 A.D.
       3             :  *
       4             :  * 0 A.D. is free software: you can redistribute it and/or modify
       5             :  * it under the terms of the GNU General Public License as published by
       6             :  * the Free Software Foundation, either version 2 of the License, or
       7             :  * (at your option) any later version.
       8             :  *
       9             :  * 0 A.D. is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :  * GNU General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU General Public License
      15             :  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #include "precompiled.h"
      19             : #include "TerritoryBoundary.h"
      20             : 
      21             : #include <algorithm> // for reverse
      22             : 
      23             : #include "graphics/Terrain.h"
      24             : #include "simulation2/helpers/Grid.h"
      25             : #include "simulation2/helpers/Pathfinding.h"
      26             : #include "simulation2/components/ICmpTerritoryManager.h"
      27             : 
      28           3 : std::vector<STerritoryBoundary> CTerritoryBoundaryCalculator::ComputeBoundaries(const Grid<u8>* territory)
      29             : {
      30           3 :     std::vector<STerritoryBoundary> boundaries;
      31             : 
      32             :     // Copy the territories grid so we can mess with it
      33           6 :     Grid<u8> grid(*territory);
      34             : 
      35             :     // Some constants for the border walk
      36             :     CVector2D edgeOffsets[] = {
      37             :         CVector2D(0.5f, 0.0f),
      38             :         CVector2D(1.0f, 0.5f),
      39             :         CVector2D(0.5f, 1.0f),
      40             :         CVector2D(0.0f, 0.5f)
      41           3 :     };
      42             : 
      43             :     // syntactic sugar
      44           3 :     const u8 TILE_BOTTOM = 0;
      45           3 :     const u8 TILE_RIGHT = 1;
      46           3 :     const u8 TILE_TOP = 2;
      47           3 :     const u8 TILE_LEFT = 3;
      48             : 
      49           3 :     const int CURVE_CW = -1;
      50           3 :     const int CURVE_CCW = 1;
      51             : 
      52             :     // === Find territory boundaries ===
      53             :     //
      54             :     // The territory boundaries delineate areas of tiles that belong to the same player, and that all have the same
      55             :     // connected-to-a-root-influence-entity status (see also STerritoryBoundary for a more wordy definition). Note that the grid
      56             :     // values contain bit-packed information (i.e. not just the owning player ID), so we must be careful to only compare grid
      57             :     // values using the player ID and connected flag bits. The joint mask to select these is referred to as the discriminator mask.
      58             :     //
      59             :     // The idea is to scan the (i,j)-grid going up row by row and look for tiles that have a different territory assignment from
      60             :     // the one right underneath it (or, if it's a tile on the first row, they need only have a territory assignment). These tiles
      61             :     // are necessarily edge tiles of a territory, and hence a territory boundary must pass through their bottom edge. Therefore,
      62             :     // we start tracing the outline of the territory starting from said bottom edge, and go CCW around the territory boundary.
      63             :     // Tracing continues until the starting point is reached, at which point the boundary is complete.
      64             :     //
      65             :     // While tracing a boundary, every tile in which the boundary passes through the bottom edge are marked as 'processed', so that
      66             :     // we know not to start a new run from these tiles when scanning continues (when the boundary is complete). This information
      67             :     // is maintained in the grid values themselves by means of the 'processed' bit mask (stressing the importance of using the
      68             :     // discriminator mask to compare only player ID and connected flag).
      69             :     //
      70             :     // Thus, we can identify the following conditions for starting a trace from a tile (i,j). Let g(i,j) indicate the
      71             :     // discriminator grid value at position (i,j); then the conditions are:
      72             :     //     - g(i,j) != 0; the tile must not be neutral
      73             :     //     - j=0 or g(i,j) != g(i,j-1);  the tile directly underneath it must have a different owner and/or connected flag
      74             :     //     - the tile must not already be marked as 'processed'
      75             :     //
      76             :     // Additionally, there is one more point to be made; the algorithm initially assumes it's tracing CCW around the territory.
      77             :     // If it's tracing an inner edge, however, this will actually cause it to trace in the CW direction (because inner edges curve
      78             :     // 'backwards' compared to the outer edges when starting the trace in the same direction). This turns out to actually be
      79             :     // exactly what the renderer needs to render two territory boundaries on the same edge back-to-back (instead of overlapping
      80             :     // each other).
      81             :     //
      82             :     // In either case, we keep track of the way the outline curves while we're tracing to determine whether we're going CW or CCW.
      83             :     // If at some point we ever need to revert the winding order or external code needs to know about it explicitly, then we can
      84             :     // do this by looking at a curvature value which we define to start at 0, and which is incremented by 1 for every CCW turn and
      85             :     // decremented by 1 for every CW turn. Hence, a negative multiple of 4 means a CW winding order, and a positive one means CCW.
      86             : 
      87           3 :     const int TERRITORY_DISCR_MASK = (ICmpTerritoryManager::TERRITORY_BLINKING_MASK | ICmpTerritoryManager::TERRITORY_PLAYER_MASK);
      88             : 
      89             :     // Try to find an assigned tile
      90          19 :     for (u16 j = 0; j < grid.m_H; ++j)
      91             :     {
      92         138 :         for (u16 i = 0; i < grid.m_W; ++i)
      93             :         {
      94             :             // saved tile state; from MSB to LSB:
      95             :             // processed bit, blinking bit, player ID
      96         122 :             u8 tileState = grid.get(i, j);
      97         122 :             u8 tileDiscr = (tileState & TERRITORY_DISCR_MASK);
      98             : 
      99             :             // ignore neutral tiles (note that tiles without an owner should never have the blinking bit set)
     100         122 :             if (!tileDiscr)
     101          59 :                 continue;
     102             : 
     103          63 :             bool tileProcessed = ((tileState & ICmpTerritoryManager::TERRITORY_PROCESSED_MASK) != 0);
     104          63 :             bool tileEligible = (j == 0 || tileDiscr != (grid.get(i, j-1) & TERRITORY_DISCR_MASK));
     105             : 
     106          63 :             if (tileProcessed || !tileEligible)
     107          53 :                 continue;
     108             : 
     109             :             // Found the first tile (which must be the lowest j value of any non-zero tile);
     110             :             // start at the bottom edge of it and chase anticlockwise around the border until
     111             :             // we reach the starting point again
     112             : 
     113          10 :             int curvature = 0; // +1 for every CCW 90 degree turn, -1 for every CW 90 degree turn; must be multiple of 4 at the end
     114             : 
     115          10 :             boundaries.push_back(STerritoryBoundary());
     116          10 :             boundaries.back().owner = (tileState & ICmpTerritoryManager::TERRITORY_PLAYER_MASK);
     117          10 :             boundaries.back().blinking = (tileState & ICmpTerritoryManager::TERRITORY_BLINKING_MASK) != 0;
     118          10 :             std::vector<CVector2D>& points = boundaries.back().points;
     119             : 
     120          10 :             u8 dir = TILE_BOTTOM;
     121             : 
     122          10 :             u8 cdir = dir;
     123          10 :             u16 ci = i, cj = j;
     124             : 
     125          10 :             u16 maxi = (u16)(grid.m_W-1);
     126          10 :             u16 maxj = (u16)(grid.m_H-1);
     127             : 
     128             :             // Size of a territory tile in metres
     129          10 :             float territoryTileSize = (Pathfinding::NAVCELL_SIZE * ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE).ToFloat();
     130             : 
     131             :             while (true)
     132             :             {
     133         112 :                 points.push_back((CVector2D(ci, cj) + edgeOffsets[cdir]) * territoryTileSize);
     134             : 
     135             :                 // Given that we're on an edge on a continuous boundary and aiming anticlockwise,
     136             :                 // we can either carry on straight or turn left or turn right, so examine each
     137             :                 // of the three possible cases (depending on initial direction):
     138         112 :                 switch (cdir)
     139             :                 {
     140          30 :                 case TILE_BOTTOM:
     141             : 
     142             :                     // mark tile as processed so we don't start a new run from it after this one is complete
     143          30 :                     ENSURE(!(grid.get(ci, cj) & ICmpTerritoryManager::TERRITORY_PROCESSED_MASK));
     144          30 :                     grid.set(ci, cj, grid.get(ci, cj) | ICmpTerritoryManager::TERRITORY_PROCESSED_MASK);
     145             : 
     146          30 :                     if (ci < maxi && cj > 0 && (grid.get(ci+1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
     147             :                     {
     148           3 :                         ++ci;
     149           3 :                         --cj;
     150           3 :                         cdir = TILE_LEFT;
     151           3 :                         curvature += CURVE_CW;
     152             :                     }
     153          27 :                     else if (ci < maxi && (grid.get(ci+1, cj) & TERRITORY_DISCR_MASK) == tileDiscr)
     154          18 :                         ++ci;
     155             :                     else
     156             :                     {
     157           9 :                         cdir = TILE_RIGHT;
     158           9 :                         curvature += CURVE_CCW;
     159             :                     }
     160          30 :                     break;
     161             : 
     162          26 :                 case TILE_RIGHT:
     163          26 :                     if (ci < maxi && cj < maxj && (grid.get(ci+1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
     164             :                     {
     165           5 :                         ++ci;
     166           5 :                         ++cj;
     167           5 :                         cdir = TILE_BOTTOM;
     168           5 :                         curvature += CURVE_CW;
     169             :                     }
     170          21 :                     else if (cj < maxj && (grid.get(ci, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
     171          13 :                         ++cj;
     172             :                     else
     173             :                     {
     174           8 :                         cdir = TILE_TOP;
     175           8 :                         curvature += CURVE_CCW;
     176             :                     }
     177          26 :                     break;
     178             : 
     179          30 :                 case TILE_TOP:
     180          30 :                     if (ci > 0 && cj < maxj && (grid.get(ci-1, cj+1) & TERRITORY_DISCR_MASK) == tileDiscr)
     181             :                     {
     182           4 :                         --ci;
     183           4 :                         ++cj;
     184           4 :                         cdir = TILE_RIGHT;
     185           4 :                         curvature += CURVE_CW;
     186             :                     }
     187          26 :                     else if (ci > 0 && (grid.get(ci-1, cj) & TERRITORY_DISCR_MASK) == tileDiscr)
     188          17 :                         --ci;
     189             :                     else
     190             :                     {
     191           9 :                         cdir = TILE_LEFT;
     192           9 :                         curvature += CURVE_CCW;
     193             :                     }
     194          30 :                     break;
     195             : 
     196          26 :                 case TILE_LEFT:
     197          26 :                     if (ci > 0 && cj > 0 && (grid.get(ci-1, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
     198             :                     {
     199           5 :                         --ci;
     200           5 :                         --cj;
     201           5 :                         cdir = TILE_TOP;
     202           5 :                         curvature += CURVE_CW;
     203             :                     }
     204          21 :                     else if (cj > 0 && (grid.get(ci, cj-1) & TERRITORY_DISCR_MASK) == tileDiscr)
     205          14 :                         --cj;
     206             :                     else
     207             :                     {
     208           7 :                         cdir = TILE_BOTTOM;
     209           7 :                         curvature += CURVE_CCW;
     210             :                     }
     211          26 :                     break;
     212             :                 }
     213             : 
     214             :                 // Stop when we've reached the starting point again
     215         112 :                 if (ci == i && cj == j && cdir == dir)
     216          10 :                     break;
     217         102 :             }
     218             : 
     219          10 :             ENSURE(curvature != 0 && abs(curvature) % 4 == 0);
     220             :         }
     221             :     }
     222             : 
     223           6 :     return boundaries;
     224           3 : }

Generated by: LCOV version 1.13