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 : }
|
