1 /* Copyright (C) 2012 Wildfire Games.
2 * This file is part of 0 A.D.
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.
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.
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/>.
18 #include "precompiled.h"
19 #include "TerritoryBoundary.h"
21 #include <algorithm> // for reverse
23 #include "graphics/Terrain.h"
24 #include "simulation2/helpers/Grid.h"
25 #include "simulation2/helpers/Pathfinding.h"
26 #include "simulation2/components/ICmpTerritoryManager.h"
28 std::vector
<STerritoryBoundary
> CTerritoryBoundaryCalculator::ComputeBoundaries(const Grid
<u8
>* territory
)
30 std::vector
<STerritoryBoundary
> boundaries
;
32 // Copy the territories grid so we can mess with it
33 Grid
<u8
> grid(*territory
);
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
),
44 const u8 TILE_BOTTOM
= 0;
45 const u8 TILE_RIGHT
= 1;
46 const u8 TILE_TOP
= 2;
47 const u8 TILE_LEFT
= 3;
49 const int CURVE_CW
= -1;
50 const int CURVE_CCW
= 1;
52 // === Find territory boundaries ===
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.
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.
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).
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'
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
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.
87 const int TERRITORY_DISCR_MASK
= (ICmpTerritoryManager::TERRITORY_BLINKING_MASK
| ICmpTerritoryManager::TERRITORY_PLAYER_MASK
);
89 // Try to find an assigned tile
90 for (u16 j
= 0; j
< grid
.m_H
; ++j
)
92 for (u16 i
= 0; i
< grid
.m_W
; ++i
)
94 // saved tile state; from MSB to LSB:
95 // processed bit, blinking bit, player ID
96 u8 tileState
= grid
.get(i
, j
);
97 u8 tileDiscr
= (tileState
& TERRITORY_DISCR_MASK
);
99 // ignore neutral tiles (note that tiles without an owner should never have the blinking bit set)
103 bool tileProcessed
= ((tileState
& ICmpTerritoryManager::TERRITORY_PROCESSED_MASK
) != 0);
104 bool tileEligible
= (j
== 0 || tileDiscr
!= (grid
.get(i
, j
-1) & TERRITORY_DISCR_MASK
));
106 if (tileProcessed
|| !tileEligible
)
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
113 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
115 boundaries
.push_back(STerritoryBoundary());
116 boundaries
.back().owner
= (tileState
& ICmpTerritoryManager::TERRITORY_PLAYER_MASK
);
117 boundaries
.back().blinking
= (tileState
& ICmpTerritoryManager::TERRITORY_BLINKING_MASK
) != 0;
118 std::vector
<CVector2D
>& points
= boundaries
.back().points
;
120 u8 dir
= TILE_BOTTOM
;
125 u16 maxi
= (u16
)(grid
.m_W
-1);
126 u16 maxj
= (u16
)(grid
.m_H
-1);
128 // Size of a territory tile in metres
129 float territoryTileSize
= (Pathfinding::NAVCELL_SIZE
* ICmpTerritoryManager::NAVCELLS_PER_TERRITORY_TILE
).ToFloat();
133 points
.push_back((CVector2D(ci
, cj
) + edgeOffsets
[cdir
]) * territoryTileSize
);
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):
142 // mark tile as processed so we don't start a new run from it after this one is complete
143 ENSURE(!(grid
.get(ci
, cj
) & ICmpTerritoryManager::TERRITORY_PROCESSED_MASK
));
144 grid
.set(ci
, cj
, grid
.get(ci
, cj
) | ICmpTerritoryManager::TERRITORY_PROCESSED_MASK
);
146 if (ci
< maxi
&& cj
> 0 && (grid
.get(ci
+1, cj
-1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
151 curvature
+= CURVE_CW
;
153 else if (ci
< maxi
&& (grid
.get(ci
+1, cj
) & TERRITORY_DISCR_MASK
) == tileDiscr
)
158 curvature
+= CURVE_CCW
;
163 if (ci
< maxi
&& cj
< maxj
&& (grid
.get(ci
+1, cj
+1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
168 curvature
+= CURVE_CW
;
170 else if (cj
< maxj
&& (grid
.get(ci
, cj
+1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
175 curvature
+= CURVE_CCW
;
180 if (ci
> 0 && cj
< maxj
&& (grid
.get(ci
-1, cj
+1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
185 curvature
+= CURVE_CW
;
187 else if (ci
> 0 && (grid
.get(ci
-1, cj
) & TERRITORY_DISCR_MASK
) == tileDiscr
)
192 curvature
+= CURVE_CCW
;
197 if (ci
> 0 && cj
> 0 && (grid
.get(ci
-1, cj
-1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
202 curvature
+= CURVE_CW
;
204 else if (cj
> 0 && (grid
.get(ci
, cj
-1) & TERRITORY_DISCR_MASK
) == tileDiscr
)
209 curvature
+= CURVE_CCW
;
214 // Stop when we've reached the starting point again
215 if (ci
== i
&& cj
== j
&& cdir
== dir
)
219 ENSURE(curvature
!= 0 && abs(curvature
) % 4 == 0);