1 |
/* emacs settings information: -*- mode: c++; tab-width: 4; c-file-style: "glob2"; -*- */ |
2 |
/* |
3 |
Copyright (C) 2001-2004 Stephane Magnenat & Luc-Olivier de Charrière |
4 |
for any question or comment contact us at nct@ysagoon.com or nuage@ysagoon.com |
5 |
|
6 |
This program is free software; you can redistribute it and/or modify |
7 |
it under the terms of the GNU General Public License as published by |
8 |
the Free Software Foundation; either version 2 of the License, or |
9 |
(at your option) any later version. |
10 |
|
11 |
This program is distributed in the hope that it will be useful, |
12 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 |
GNU General Public License for more details. |
15 |
|
16 |
You should have received a copy of the GNU General Public License |
17 |
along with this program; if not, write to the Free Software |
18 |
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
19 |
*/ |
20 |
|
21 |
/** |
22 |
\file Grid.h |
23 |
\brief A parent class for 2D elevation grids (e.g. maps and buildings) |
24 |
|
25 |
This class is based as much as possible around the principles of STL containers. To access an element in a grid, do: |
26 |
Grid[x][y] to get the cell at (x, y) |
27 |
Grid[x][y][t] to the data for team t at (x, y) |
28 |
Grid[x][y][t][s] to get swim/no-swim elevation(s) for team t at (x, y) |
29 |
|
30 |
Grid[x][y] is wrap-safe. You can use Grid(x)(y) for unchecked access if you prefer. You can even mix them: Grid[x](y) and Grid(x)[y] are valid. |
31 |
Despite the pretty interface, these functions are highly optimised. They're (almost) transparent wrappers around get(x, y) and UnsafeGet(x, y), which you can use instead if you don't believe me. |
32 |
You can also use Grid[i] and Grid(i) to get a cell, where i is an inhabitant of the map (unit, building, etc.). In the long-term, I hope to deprecate the use of explicit co-ordinates |
33 |
|
34 |
Note for inheritors: the contained class can be anything, but must be accessible as foo[t][s][i], where [t] == team, [s] == elevation set (currently either CAN_SWIM or CANNOT SWIM), [i] == elevation index |
35 |
|
36 |
Grids also have a set of iterators defined, although they're more complex than normal STL iterators (for the sake of efficiency). |
37 |
The iterator classes take some getting used to, and the syntax isn't as nice as I'd like, but they are worth it: they can easily run 10 times faster than unoptimised implementations. |
38 |
Iterators take several template parameters defining the way they behave. The general form of an iterator definition is: |
39 |
|
40 |
iterator<IterationDiscipline, iterationWidth, iterationHeight, WrapDiscipline> |
41 |
Or... |
42 |
const_iterator<IterationDiscipline, iterationWidth, iterationHeight, WrapDiscipline> |
43 |
|
44 |
The parameters mean the following: |
45 |
IterationDiscipline |
46 |
This parameter controls the way the iterator moves around the grid. Valid values include: |
47 |
* HBOX - across then down - i.e. a horizontal box |
48 |
* VBOX - down then across - i.e. a vertical box |
49 |
* BOX - whichever type of box is most efficient |
50 |
|
51 |
* CW_OUTLINE - squares around the edge of the box, clocwise ("inside" squares aren't touched at all) |
52 |
* OUTLINE - whichever type of outline is most efficient (I bet you can't guess which type of outline I chose ;) |
53 |
Note: if you want a "circle" iterator, the current solution is to use a BOX iterator, and discard squares where wrapDistSquare(centre, square) >= radius*radius |
54 |
|
55 |
iteratorWidth |
56 |
The width squares the iterator covers. This is optional - if you don't know this at compile-time, you can specify it at run-time (see below) |
57 |
|
58 |
iteratorHeight |
59 |
The height squares the iterator covers. This is optional - if you don't know this at compile-time, you can specify it at run-time (see below) |
60 |
|
61 |
WrapDiscipline |
62 |
Usually, the level wrap-safety needed for an iterator is obvious from the context (i.e. everything except iterators that span the whole grid need to be wrap-safe). |
63 |
However, you might very occasionally know that you can be more lenient (or less lenient) about wrap safety then the default. Valid values for this parameter are: |
64 |
* WRAP_BOTH - The iterator checks for wraping along both the X and Y axes |
65 |
* WRAP_HORIZONTAL - The iterator checks for wraping along the X axis. |
66 |
* WRAP_VERTICAL - The iterator checks for wraping along the Y axis. |
67 |
* WRAP_NEITHER - The iterator doesn't (necessarily) check for any wraping. |
68 |
If an iterator moves past a non-wrap-safe boundary, its behaviour is undefined. It might happen to work at the minute, but is liable to break without warning in the future. |
69 |
|
70 |
Generally speaking, the compiler will create more efficient code if you give it less restrictive disciplines ("BOX" and "WRAP_NEITHER" rather than "VBOX" and "WRAP_BOTH"). |
71 |
It will also create more efficent code if you specify the iterator height and width at compile-time rather than run-time |
72 |
|
73 |
Here are some iterator examples: |
74 |
|
75 |
To iterate over the entire grid, use: |
76 |
for (typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<BOX, WRAP_NEITHER, gridWidth, gridHeight> i=m.begin(); i!=m.end(); ++i) |
77 |
{ |
78 |
foo(*i); |
79 |
} |
80 |
|
81 |
Given an inhabitant of the grid called "myGlob", iterate over the squares surrounding it with: |
82 |
for (typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<OUTLINE, WRAP_BOTH, 3, 3> i=m.begin(myGlob); i!=m.end(); ++i) |
83 |
{ |
84 |
foo(*i); |
85 |
} |
86 |
|
87 |
To iterate horizontally over a box defined at run-time, do: |
88 |
for (typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<HBOX, WRAP_BOTH> i=m.begin(x, y, width, height); i!=m.end(); ++i) |
89 |
{ |
90 |
foo(*i); |
91 |
} |
92 |
|
93 |
You can skip over many squares at once: |
94 |
for (typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<HBOX> i=m.begin(MyBuilding, MyBuilding.length()); i!=m.end(); i+=2) { |
95 |
foo(*i); |
96 |
} |
97 |
And skip columns as well as rows if you prefer: |
98 |
for (typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<HBOX> i=m.begin(MyBuilding, MyBuilding.length()); i!=m.end(); i.skip_forward(2, 2)) { |
99 |
foo(*i); |
100 |
} |
101 |
Note that this last one doesn't do what you might expect. It skips across two places, and *if* it passes the end of a row, skips to the row after next. |
102 |
So the above snippet of code will iterate over every even-numbered square in the grid, *not* in a diagonal line across the grid. |
103 |
**/ |
104 |
|
105 |
#ifndef __GRID_H |
106 |
#define __GRID_H |
107 |
|
108 |
#include <SDL_rwops.h> |
109 |
#include <Debug.h> |
110 |
#include <Iostream.h> |
111 |
|
112 |
enum elevation_name { TROUGH=0, VALLEY=1, PEAK=255 }; |
113 |
typedef Uint8 elevation_t; |
114 |
typedef Uint32 elevation_sum_t; // Can hold the sum of two elevations |
115 |
typedef Sint8 elevation_offset_t; |
116 |
const elevation_t elevation_max=PEAK; |
117 |
const elevation_t elevation_min=TROUGH; |
118 |
const unsigned int elevation_count=elevation_max-elevation_min+1; |
119 |
|
120 |
typedef Sint16 gradient_t; // difference between two elevations |
121 |
|
122 |
enum elevation_set_t { CAN_SWIM=0, CANNOT_SWIM=1 }; |
123 |
const elevation_set_t elevation_set_min=CAN_SWIM; |
124 |
const elevation_set_t elevation_set_max=CANNOT_SWIM; |
125 |
const unsigned int elevation_set_count=elevation_set_max-elevation_set_min+1; |
126 |
|
127 |
//! Positions and distances on the grid, measured in cells |
128 |
typedef int grid_xpos_t; //!< Horizontal position on the grid |
129 |
typedef int grid_xoffset_t; //!< Horizontal position on the grid |
130 |
typedef unsigned int grid_width_t; //!< Distance between two horizontal grid positions |
131 |
|
132 |
typedef int grid_ypos_t; //!< Vertical position on the grid |
133 |
typedef int grid_yoffset_t; //!< Vertical position on the grid |
134 |
typedef unsigned int grid_height_t; //!< Distance between two vertical grid positions |
135 |
|
136 |
typedef int grid_pos_t; //!< Horizontal or vertical position on the grid |
137 |
typedef unsigned int grid_length_t; //!< Distance between any two positions on the grid |
138 |
typedef int grid_offset_t; //!< The result of adding or subtracting two grid co-ordinates |
139 |
|
140 |
typedef unsigned int grid_area_t; //! An area on the grid |
141 |
|
142 |
typedef unsigned int team_ID_t; |
143 |
typedef unsigned int team_count_t; |
144 |
|
145 |
typedef Uint8 grid_direction_t; // TOP_LEFT=0, TOP=1, TOP_RIGHT=2, LEFT=3, RIGHT=4, BOTTOM_LEFT=5, BOTTOM=6, BOTTOM_RIGHT=7 |
146 |
typedef Sint8 grid_xdirection_t; // LEFT=-1, MIDDLE=0, RIGHT=1 |
147 |
typedef Sint8 grid_ydirection_t; // UP =-1, MIDDLE=0, DOWN =1 |
148 |
|
149 |
//! Positions and distances on the grid, measured in pixels |
150 |
typedef int pixel_xpos_t; |
151 |
typedef int pixel_xoffset_t; |
152 |
typedef unsigned int pixel_width_t; |
153 |
|
154 |
typedef int pixel_ypos_t; |
155 |
typedef int pixel_yoffset_t; |
156 |
typedef unsigned int pixel_height_t; |
157 |
|
158 |
typedef int pixel_pos_t; |
159 |
typedef unsigned int pixel_length_t; |
160 |
typedef int pixel_offset_t; |
161 |
|
162 |
typedef unsigned int pixel_area_t; |
163 |
|
164 |
//! Positions and distances, relative to the on-screen display, measured in pixels |
165 |
typedef pixel_xpos_t display_xpos_t; |
166 |
typedef pixel_xoffset_t display_xoffset_t; |
167 |
typedef pixel_width_t display_width_t; |
168 |
|
169 |
typedef pixel_ypos_t display_ypos_t; |
170 |
typedef pixel_yoffset_t display_yoffset_t; |
171 |
typedef pixel_height_t display_height_t; |
172 |
|
173 |
typedef pixel_pos_t display_pos_t; |
174 |
typedef pixel_length_t display_length_t; |
175 |
typedef pixel_offset_t display_offset_t; |
176 |
|
177 |
typedef pixel_area_t display_area_t; |
178 |
|
179 |
//! "normal" displays are only valid if they are greater than 0, relative displays can be less than zero. |
180 |
//! I'm not sure what the point of these two types are yet, or whether they really are distinct types. I'm just playing it safe for now. |
181 |
typedef pixel_xpos_t relative_display_xpos_t; |
182 |
typedef pixel_xoffset_t relative_display_xoffset_t; |
183 |
typedef pixel_width_t relative_display_width_t; |
184 |
|
185 |
typedef pixel_ypos_t relative_display_ypos_t; |
186 |
typedef pixel_yoffset_t relative_display_yoffset_t; |
187 |
typedef pixel_height_t relative_display_height_t; |
188 |
|
189 |
typedef pixel_pos_t relative_display_pos_t; |
190 |
typedef pixel_length_t relative_display_length_t; |
191 |
typedef pixel_offset_t relative_display_offset_t; |
192 |
|
193 |
typedef pixel_area_t relative_display_area_t; |
194 |
|
195 |
namespace GridInternal { |
196 |
class BadElevation : public Debug::KillGame { |
197 |
public: |
198 |
BadElevation(char* e) : Debug::KillGame(e) {}; |
199 |
}; |
200 |
|
201 |
class Print {}; |
202 |
class PrintPathFind : public Print {}; |
203 |
class unsafeGet; |
204 |
class BadIndex : public Debug::KillGame { |
205 |
public: |
206 |
BadIndex(char* e) : Debug::KillGame(e) {}; |
207 |
}; |
208 |
class IO; |
209 |
|
210 |
/** |
211 |
\brief helper class for use with grid updates |
212 |
|
213 |
Since only one grid can be getting updated at a time, and since the amount of memory required for an update is quite large, |
214 |
we pre-allocate a single buffer to be used by all grids of a given area |
215 |
**/ |
216 |
template<grid_area_t area> |
217 |
class GridParent |
218 |
{ |
219 |
protected: |
220 |
static void* TempElevations; |
221 |
static unsigned int references; |
222 |
|
223 |
GridParent() { if (!references++) TempElevations = new void*[area]; }; |
224 |
~GridParent() { if (!--references) delete[](static_cast<void**>(TempElevations)); }; |
225 |
}; |
226 |
|
227 |
template<grid_area_t area> |
228 |
void* GridParent<area>::TempElevations; |
229 |
template<grid_area_t area> |
230 |
unsigned int GridParent<area>::references=0; |
231 |
|
232 |
}; |
233 |
|
234 |
#include "Team.h" |
235 |
//! An inhabitant of the globulation world. Anything that exists on the grid (unit, building, etc.) should derive from this |
236 |
class Inhabitant |
237 |
{ |
238 |
grid_xpos_t posX_v; |
239 |
grid_ypos_t posY_v; |
240 |
Team* owning_team_v; |
241 |
|
242 |
template<class T> |
243 |
class InhabitantReader |
244 |
{ |
245 |
Inhabitant& i; |
246 |
const Game& g; |
247 |
const T name; |
248 |
public: |
249 |
InhabitantReader(Inhabitant& ii, const Game& gg, const T nn) : i(ii), g(gg), name(nn) {}; |
250 |
template<class Ch, class Tr> friend std::basic_istream<Ch, Tr>& operator<<(std::basic_istream<Ch, Tr>& in, const InhabitantReader& r) |
251 |
{ |
252 |
team_ID_t teamNumber; |
253 |
return in |
254 |
>> enterSection(r.name) |
255 |
>> title("posX") >> r.i.posX_v |
256 |
>> title("posY") >> r.i.posY_v |
257 |
>> title("team") >> teamNumber |
258 |
>> leaveSection(); |
259 |
r.i.owning_team_v = r.g.getTeam(r.i.teamNumber); |
260 |
} |
261 |
}; |
262 |
|
263 |
template<class T> |
264 |
class InhabitantWriter |
265 |
{ |
266 |
const Inhabitant& i; |
267 |
const T name; |
268 |
public: |
269 |
InhabitantWriter(const Inhabitant& ii, const T nn) : i(ii), name(nn) {}; |
270 |
template<class Ch, class Tr> friend std::basic_ostream<Ch, Tr>& operator>>(std::basic_istream<Ch, Tr>& out, const InhabitantWriter& r) |
271 |
{ |
272 |
return out |
273 |
<< enterSection(r.i.name) |
274 |
<< title("posX") << r.i.posX_v |
275 |
<< title("posY") << r.i.posY_v |
276 |
<< title("team") << r.i.teamNumber() |
277 |
<< leaveSection(); |
278 |
} |
279 |
}; |
280 |
|
281 |
protected: |
282 |
const grid_xpos_t posX(const grid_xpos_t x) { return posX_v = x; } |
283 |
const grid_ypos_t posY(const grid_ypos_t y) { return posY_v = y; } |
284 |
Team *const team(Team *const t) { return owning_team_v = t; }; |
285 |
Inhabitant(const grid_xpos_t x, const grid_ypos_t y, Team *const t) : posX_v(x), posY_v(y), owning_team_v(t) {}; |
286 |
|
287 |
public: |
288 |
const grid_xpos_t posX() const { return posX_v; } |
289 |
const grid_ypos_t posY() const { return posY_v; } |
290 |
|
291 |
const Team *const team() const { return owning_team_v; }; |
292 |
const team_ID_t teamNumber() const { return owning_team_v->teamNumber; }; |
293 |
|
294 |
template<class T> |
295 |
InhabitantReader<T> operator()(Game& g, T name = "Inhabitant") { return InhabitantReader<T>(*this, g, name); }; |
296 |
template<class T> |
297 |
InhabitantWriter<T> operator()(T name) const { return InhabitantWriter<T>(*this, name); }; |
298 |
InhabitantWriter<const char* > operator()() const { return InhabitantWriter<const char* >(*this, "Inhabitant"); }; |
299 |
}; |
300 |
|
301 |
template<class Ch, class Tr> |
302 |
std::basic_ostream<Ch, Tr>& operator<<(std::basic_ostream<Ch, Tr>& out, const Inhabitant& i) { return out << i(); } |
303 |
|
304 |
// Iterator disciplines |
305 |
class HBOX {}; |
306 |
class VBOX {}; |
307 |
typedef HBOX BOX; |
308 |
|
309 |
class CW_OUTLINE {}; |
310 |
typedef CW_OUTLINE OUTLINE; |
311 |
|
312 |
class WRAP_BOTH {}; |
313 |
class WRAP_HORIZONTAL {}; |
314 |
class WRAP_VERTICAL {}; |
315 |
class WRAP_NEITHER {}; |
316 |
class WRAP_DEFAULT {}; |
317 |
|
318 |
template<class Contained, grid_width_t gridWidth, grid_height_t gridHeight> class Grid; |
319 |
#include "GridIterators.tcc" |
320 |
|
321 |
template<class Contained, grid_width_t gridWidth, grid_height_t gridHeight> class Grid : public GridInternal::GridParent<gridWidth * gridHeight> |
322 |
{ |
323 |
using GridInternal::GridParent<gridWidth * gridHeight>::TempElevations; |
324 |
public: |
325 |
static const grid_area_t gridArea = gridWidth * gridHeight; |
326 |
Grid() : GridInternal::GridParent<gridArea>(), Tail(static_cast<Contained**>(TempElevations)) {}; |
327 |
private: |
328 |
Contained data[gridArea]; |
329 |
Contained** Tail; |
330 |
|
331 |
//! Exposing these to the public would make the interface dependant on storage format |
332 |
static const grid_pos_t coordinatesToIndex(const grid_xpos_t x, const grid_ypos_t y) { return y * gridHeight + x; } |
333 |
static const grid_offset_t areaToLength(const grid_xoffset_t x, const grid_yoffset_t y) { return y * gridHeight + x; } |
334 |
Contained *const unsafeGet(const grid_pos_t p) |
335 |
{ |
336 |
debugOut(GridInternal::unsafeGet) << "Grid< " << gridWidth << ", " << gridHeight << ">.unsafeGet(" << p << ") returning " << data+p << std::endl; |
337 |
Assert(p < static_cast<grid_pos_t>(gridArea), GridInternal::BadIndex("the program tried to access a grid position outside the grid")); |
338 |
return data + p; |
339 |
} |
340 |
Contained *const get(const grid_pos_t p) { return unsafeGet((p<0)?(p%gridArea)+gridArea:p%gridArea); } |
341 |
//! A helper class to make operator[] work correctly |
342 |
struct Row { |
343 |
Grid *const g_v; |
344 |
const grid_xpos_t x_v; |
345 |
|
346 |
Row(Grid *const g, const grid_xpos_t x) : g_v(g), x_v(x) {} |
347 |
Contained& operator[](const grid_ypos_t y) const { return *g_v->unsafeGet(x_v, y%gridWidth); } |
348 |
Contained& operator()(const grid_ypos_t y) const { return *g_v->unsafeGet(x_v, y); } |
349 |
}; |
350 |
|
351 |
protected: |
352 |
void registerPeak(Contained* C) { *Tail++ = C; } |
353 |
void updateElevation(const team_ID_t t, const elevation_set_t s, const elevation_index_t index); |
354 |
|
355 |
// Generic template function to find a gradient - path_find_function_name_t is a hackish workaround for not allowing strings in template parameters |
356 |
template<const elevation_sum_t (*optionElevation)(Contained *const, const team_ID_t, const elevation_set_t), void (*Success)(), void (*Failure)(), char* (*pathFindName)()> |
357 |
const bool pathFind(const grid_xpos_t x, const grid_ypos_t y, const team_ID_t team, const elevation_set_t s, grid_xpos_t& directionX, grid_ypos_t& directionY) const; |
358 |
|
359 |
public: |
360 |
//! Access an individual cell - wrap unsafe/safe versions |
361 |
Contained *const unsafeGet(const grid_xpos_t x, const grid_ypos_t y) { return unsafeGet(coordinatesToIndex(x, y)); } |
362 |
Contained *const get (const grid_xpos_t x, const grid_ypos_t y) { return unsafeGet(x%gridWidth, y%gridHeight); } |
363 |
Contained *const unsafeGet(const Inhabitant& I) const { return unsafeGet(I.posX(), I.posY()); } |
364 |
Contained *const get (const Inhabitant& I) const { return get (I.posX(), I.posY()); } |
365 |
|
366 |
Row operator[](const grid_xpos_t x) { return Row(this, x%gridWidth); } |
367 |
Row operator()(const grid_xpos_t x) { return Row(this, x); } |
368 |
Contained& operator[](const Inhabitant& I) { return get(I); } |
369 |
Contained& operator()(const Inhabitant& I) { return unsafeGet(I); } |
370 |
|
371 |
//! Conversion functions |
372 |
static const pixel_xpos_t gridToPixelX(const grid_xpos_t x ) { return x * 32; } |
373 |
static const pixel_ypos_t gridToPixelY(const grid_ypos_t y ) { return y * 32; } |
374 |
static const pixel_width_t gridToPixelW(const grid_width_t w ) { return w * 32; } |
375 |
static const pixel_height_t gridToPixelH(const grid_height_t h) { return h * 32; } |
376 |
|
377 |
static const grid_xpos_t pixelToGridX(const pixel_xpos_t x ) { return x / 32; } |
378 |
static const grid_ypos_t pixelToGridY(const pixel_ypos_t y ) { return y / 32; } |
379 |
static const grid_width_t pixelToGridW(const pixel_width_t w ) { return w / 32; } |
380 |
static const grid_height_t pixelToGridH(const pixel_height_t h) { return h / 32; } |
381 |
|
382 |
//! Convert a grid position to a display position |
383 |
static const display_xpos_t gridToDisplayX(const grid_xpos_t x, const grid_width_t viewportX) { return (gridToPixelX(x) - gridToPixelW(viewportX) + gridToPixelW(gridWidth)) % gridToPixelW(gridWidth); } |
384 |
static const display_xpos_t gridToDisplayY(const grid_xpos_t y, const grid_width_t viewportY) { return (gridToPixelY(y) - gridToPixelH(viewportY) + gridToPixelH(gridWidth)) % gridToPixelH(gridWidth); } |
385 |
|
386 |
//! Convert a pixel position (relative to the grid) to a display position (relative to the on-screen display) |
387 |
static const display_xpos_t pixelToDisplayX(const pixel_xpos_t x, const pixel_width_t viewportX) { return (x - viewportX + gridToPixelW(gridWidth)) % gridToPixelW(gridWidth); } |
388 |
static const display_xpos_t pixelToDisplayY(const pixel_xpos_t y, const pixel_width_t viewportY) { return (y - viewportY + gridToPixelH(gridWidth)) % gridToPixelH(gridWidth); } |
389 |
|
390 |
//! Value nearest to 0 that is a valid pixel position for X relative to the on-screen display |
391 |
//! These used to be known as mapCaseToDisplayable |
392 |
static const relative_display_xoffset_t gridToRelativeDisplayX(const grid_xpos_t x, const grid_width_t viewportX) { gridToPixelX(x-viewportX + gridWidth*((x-viewportX)%(gridWidth/2+1))); }; |
393 |
static const relative_display_yoffset_t gridToRelativeDisplayY(const grid_ypos_t y, const grid_width_t viewportY) { gridToPixelY(y-viewportY + gridWidth*((y-viewportY)%(gridWidth/2+1))); }; |
394 |
|
395 |
//! Next few functions are not well understood |
396 |
static const grid_xpos_t toXposAligned (const pixel_xpos_t x, const grid_xpos_t viewportX) { return ((x>>5) +viewportX) % gridWidth; } |
397 |
static const grid_ypos_t toYposAligned (const pixel_ypos_t y, const grid_ypos_t viewportY) { return ((y>>5) +viewportY) % gridHeight; } |
398 |
static const grid_xpos_t toXposUnaligned(const pixel_xpos_t x, const grid_xpos_t viewportX) { return (((x+16)>>5) +viewportX) % gridWidth; } |
399 |
static const grid_ypos_t toYposUnaligned(const pixel_ypos_t y, const grid_ypos_t viewportY) { return (((y+16)>>5)+viewportY) % gridHeight; } |
400 |
|
401 |
static const grid_xpos_t toBuildingXpos(const pixel_xpos_t x, const pixel_width_t W, const grid_xpos_t viewportX) { return (((x + (W&1)?0:16) >> 5) + viewportX) % gridWidth; } |
402 |
static const grid_ypos_t toBuildingYpos(const pixel_ypos_t y, const pixel_height_t H, const grid_ypos_t viewportY) { return (((y + (H&1)?0:16) >> 5) + viewportY) % gridHeight; } |
403 |
|
404 |
//! Used to be buildingPosToCursor |
405 |
static const grid_xpos_t toCursorXpos(const pixel_xpos_t x, const pixel_xpos_t W, const grid_xpos_t viewportX) { return gridToRelativeDisplayX(pixelToGridX(x), viewportX) + W*16; } |
406 |
static const grid_ypos_t toCursorYpos(const pixel_ypos_t y, const pixel_ypos_t H, const grid_ypos_t viewportY) { return gridToRelativeDisplayY(pixelToGridY(y), viewportY) + H*16; } |
407 |
//! End poorly understood functions |
408 |
|
409 |
//! Number of cells you'll have to walk (including obstacles) to reach the nearest peak, or PEAK if there are no nearby peaks |
410 |
static const grid_length_t elevationToDistance(const elevation_t e) { return e>1?PEAK-e:PEAK; } |
411 |
//! Translate an elevation_t to TROUGH, VALLEY or PEAK. |
412 |
static const elevation_name elevationToName(const elevation_t e) { return e & 0x81; } |
413 |
//! Square of the distance between (x1, y1) and (x2, y2) - not wrap-safe |
414 |
const int distSquare(const int x1, const int y1, const int x2, const int y2) |
415 |
{ return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1); } |
416 |
//! The square of the distance between (x1, y1) and (x2, y2) - wrap-safe but not rooted. |
417 |
static const grid_length_t wrapDistSquare(grid_xpos_t x1, grid_ypos_t y1, const grid_xpos_t x2, const grid_ypos_t y2) |
418 |
{ |
419 |
return |
420 |
((x1 = abs(x1-x2) % gridWidth )>(gridWidth /2)?(x1 = gridWidth - x1) * x1 : x1*x1) |
421 |
+ |
422 |
((y1 = abs(y1-y2) % gridHeight)>(gridHeight/2)?(y1 = gridHeight - y1) * y1 : y1*y1); |
423 |
} |
424 |
static const grid_length_t wrapDistSquare(const Inhabitant& i, const Inhabitant& j) |
425 |
{ return wrapDistSquare(i.posX(), i.posY(), j.posX(), j.posY()); } |
426 |
//! The max distance on x or y axis, between (x1, y1) and (x2, y2) - wrap-safe. |
427 |
static const grid_length_t wrapDistMax(grid_xpos_t x1, grid_ypos_t y1, const grid_xpos_t x2, const grid_ypos_t y2) |
428 |
{ |
429 |
return |
430 |
((x1 = abs(x1-x2) % gridWidth )>(gridWidth /2)?x1 = abs(gridWidth - x1) : x1) |
431 |
> |
432 |
((y1 = abs(y1-y2) % gridHeight)>(gridHeight/2)?y1 = abs(gridHeight - y1) : y1) |
433 |
?x1:y1; |
434 |
} |
435 |
static const grid_length_t wrapDistMax(const Inhabitant& i, const Inhabitant& j) |
436 |
{ return wrapDistMax(i.posX(), i.posY(), j.posX(), j.posY()); } |
437 |
|
438 |
// Does the specified point fall within a particular area - wrap-safe. |
439 |
static const bool pointFallsWithinArea(const grid_xpos_t pointX, const grid_ypos_t pointY, grid_xpos_t areaX, grid_ypos_t areaY, const grid_xoffset_t areaW=1, const grid_yoffset_t areaH=1) |
440 |
{ |
441 |
if ((areaX%=gridWidth )<0) areaX += gridWidth; |
442 |
if ((areaY%=gridHeight)<0) areaY += gridHeight; |
443 |
return (pointX-areaX+(areaX<pointX)?gridWidth:0 <= areaW) && |
444 |
(pointY-areaY+(areaY<pointY)?gridHeight:0 <= areaH); |
445 |
} |
446 |
static const bool pointFallsWithinArea(const Inhabitant& P, const grid_xpos_t areaX, const grid_ypos_t areaY, const grid_xoffset_t areaW=1, const grid_yoffset_t areaH=1) |
447 |
{ PointFallsWithinArea(P.posX(), P.posY(), areaX, areaY, areaW, areaH); } |
448 |
|
449 |
//! Functions useful for iterators |
450 |
private: |
451 |
//! Offsets from a given position, used by various iterator classes |
452 |
static const grid_length_t left(const grid_pos_t pos) { return pos%gridWidth?-1:gridWidth-1; } |
453 |
static const grid_length_t right(const grid_pos_t pos) { return pos%gridWidth==gridWidth-1?1-gridWidth:1; } |
454 |
static const grid_length_t top(const grid_pos_t pos) { return pos<static_cast<grid_pos_t>(gridWidth)?gridArea-gridWidth:-gridWidth; } |
455 |
static const grid_length_t bottom(const grid_pos_t pos) { return pos/gridWidth==gridHeight-1?gridWidth-gridArea:gridWidth; } |
456 |
|
457 |
const grid_pos_t offsetT (const grid_pos_t pos) const { return pos + top(pos); } |
458 |
const grid_pos_t offsetB (const grid_pos_t pos) const { return pos + bottom(pos); } |
459 |
const grid_pos_t offsetL (const grid_pos_t pos) const { return pos + left(pos); } |
460 |
const grid_pos_t offsetR (const grid_pos_t pos) const { return pos + right(pos); } |
461 |
const grid_pos_t offsetTL(const grid_pos_t pos) const { return pos + left(pos) + top(pos); } |
462 |
const grid_pos_t offsetTR(const grid_pos_t pos) const { return pos + right(pos) + top(pos); } |
463 |
const grid_pos_t offsetBL(const grid_pos_t pos) const { return pos + left(pos) + bottom(pos); } |
464 |
const grid_pos_t offsetBR(const grid_pos_t pos) const { return pos + right(pos) + bottom(pos); } |
465 |
const grid_pos_t offset (const grid_pos_t pos, const grid_xoffset_t offsetX, const grid_yoffset_t offsetY) const |
466 |
{ return (pos + offsetX)%gridWidth + ((pos/gridWidth + offsetY)%gridHeight)*gridWidth; } // The extra complexity is to ensure the function is wrap-safe |
467 |
public: |
468 |
const grid_pos_t offsetT (const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet(x , (y+gridHeight-1)%gridHeight); } |
469 |
const grid_pos_t offsetB (const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet(x , (y+1 )%gridHeight); } |
470 |
const grid_pos_t offsetL (const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+gridWidth-1)%gridWidth, y ); } |
471 |
const grid_pos_t offsetR (const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+1 )%gridWidth, y ); } |
472 |
const grid_pos_t offsetTL(const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+gridWidth-1)%gridWidth, (y+gridHeight-1)%gridHeight); } |
473 |
const grid_pos_t offsetTR(const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+1 )%gridWidth, (y+gridHeight-1)%gridHeight); } |
474 |
const grid_pos_t offsetBL(const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+gridWidth-1)%gridWidth, (y+1 )%gridHeight); } |
475 |
const grid_pos_t offsetBR(const grid_xpos_t x, grid_ypos_t y) const { return unsafeGet((x+1 )%gridWidth, (y+1 )%gridHeight); } |
476 |
const grid_pos_t offset (const grid_xpos_t x, grid_ypos_t y, const grid_xoffset_t offsetX, const grid_yoffset_t offsetY) const { return get(x+offsetX, y+offsetY); } |
477 |
|
478 |
Contained *const offsetT (const Contained *const pos) { return unsafeGet(offsetT (pos - data)); } |
479 |
Contained *const offsetB (const Contained *const pos) { return unsafeGet(offsetB (pos - data)); } |
480 |
Contained *const offsetL (const Contained *const pos) { return unsafeGet(offsetL (pos - data)); } |
481 |
Contained *const offsetR (const Contained *const pos) { return unsafeGet(offsetR (pos - data)); } |
482 |
Contained *const offsetTL(const Contained *const pos) { return unsafeGet(offsetTL(pos - data)); } |
483 |
Contained *const offsetTR(const Contained *const pos) { return unsafeGet(offsetTR(pos - data)); } |
484 |
Contained *const offsetBL(const Contained *const pos) { return unsafeGet(offsetBL(pos - data)); } |
485 |
Contained *const offsetBR(const Contained *const pos) { return unsafeGet(offsetBR(pos - data)); } |
486 |
Contained *const offset(Contained *const pos, const grid_xoffset_t offsetX, const grid_yoffset_t offsetY) { return unsafeGet(offset(pos - data, offsetX, offsetY)); } |
487 |
|
488 |
const grid_xpos_t posX(const Contained *const pos) { return (pos - data) % gridWidth; } |
489 |
const grid_ypos_t posY(const Contained *const pos) { return (pos - data) / gridWidth; } |
490 |
|
491 |
const grid_offset_t position_DoNotUse(const Contained *const pos) const { return pos - data; } //!< Don't use this - it's an ugly workaround for problems with templates and friendship |
492 |
const grid_offset_t position_DoNotUse(const grid_xpos_t x, const grid_ypos_t y) const { return coordinatesToIndex(x, y); } //!< Don't use this - it's an ugly workaround for problems with templates and friendship |
493 |
|
494 |
public: |
495 |
//! Normal iterator class |
496 |
template<class iteration_discipline, grid_width_t iteratorWidth=0, grid_width_t iteratorHeight=0, class wrap_discipline=WRAP_DEFAULT> |
497 |
struct iterator : public GridInternal::Iterator<Contained, gridWidth, gridHeight, iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline> |
498 |
{ |
499 |
iterator(const grid_xpos_t x1, const grid_ypos_t y1, const grid_xoffset_t W, const grid_yoffset_t H, Grid *const g) |
500 |
: GridInternal::Iterator<Contained, gridWidth, gridHeight, iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>::Iterator(x1, y1, W, H, g) {} |
501 |
}; |
502 |
|
503 |
//! Const iterator - just a simple wrapper around its non-const equivalent |
504 |
template<class iteration_discipline, grid_width_t iteratorWidth=0, grid_width_t iteratorHeight=0, class wrap_discipline=WRAP_DEFAULT> |
505 |
class const_iterator : public GridInternal::Iterator<Contained, gridWidth, gridHeight, iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline> |
506 |
{ |
507 |
typedef const_iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline> base; |
508 |
typedef GridInternal::Iterator<Contained, gridWidth, gridHeight, iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline> parent; |
509 |
public: |
510 |
const_iterator(const const_iterator& b) : parent(b) {} |
511 |
const_iterator(const grid_xpos_t x1, const grid_ypos_t y1, const grid_xoffset_t W, const grid_yoffset_t H, Grid *const g) |
512 |
: parent(x1, y1, W, H, g) {} |
513 |
base& operator++() { parent::operator++(); return *this; } |
514 |
base& operator--() { parent::operator--(); return *this; } |
515 |
base operator++(int) { base temp = *this; operator++(); return temp; }; |
516 |
base operator--(int) { base temp = *this; operator--(); return temp; }; |
517 |
const parent& operator+=(const grid_xoffset_t offset) { return parent::operator+=(offset); } |
518 |
const parent& operator-=(const grid_xoffset_t offset) { return parent::operator-=(offset); } |
519 |
const parent& skip_forward(const grid_xoffset_t x1, const grid_yoffset_t y1) { return parent::skip_forward(x1, y1); } |
520 |
const parent& skip_backward(const grid_xoffset_t x1, const grid_yoffset_t y1) { return parent::skip_backward(x1, y1); } |
521 |
const bool operator==(const GridInternal::IteratorEnd& e) { return parent::operator==(e); } |
522 |
const bool operator!=(const GridInternal::IteratorEnd& e) { return parent::operator!=(e); } |
523 |
const Contained& operator*() { return parent::operator*(); } |
524 |
const Contained *const operator->() { return parent::operator->(); } |
525 |
const Contained *const offset(const grid_xoffset_t x, const grid_yoffset_t y) { return parent::offset(x, y); } |
526 |
const Contained *const offsetT () { return parent::offsetT (); } |
527 |
const Contained *const offsetL () { return parent::offsetL (); } |
528 |
const Contained *const offsetB () { return parent::offsetB (); } |
529 |
const Contained *const offsetR () { return parent::offsetR (); } |
530 |
const Contained *const offsetTL() { return parent::offsetTL(); } |
531 |
const Contained *const offsetTR() { return parent::offsetTR(); } |
532 |
const Contained *const offsetBL() { return parent::offsetBL(); } |
533 |
const Contained *const offsetBR() { return parent::offsetBR(); } |
534 |
}; |
535 |
private: |
536 |
struct BeginStruct |
537 |
{ |
538 |
typedef Grid<Contained, gridWidth, gridHeight> grid; |
539 |
|
540 |
const grid_xpos_t x; |
541 |
const grid_ypos_t y; |
542 |
const grid_width_t w; |
543 |
const grid_height_t h; |
544 |
grid *const G; |
545 |
BeginStruct(const grid_xpos_t x1, const grid_ypos_t y1, const grid_xoffset_t w1, const grid_yoffset_t h1, grid *const g) : x(x1), y(y1), w(w1), h(h1), G(g) {}; |
546 |
BeginStruct(const grid_xpos_t x1, const grid_ypos_t y1, const grid_xoffset_t w1, const grid_yoffset_t h1, grid const*const g) : x(x1), y(y1), w(w1), h(h1), G(const_cast<grid *const>(g)) {}; |
547 |
|
548 |
operator iterator<BOX, 0, 0, WRAP_DEFAULT>() |
549 |
{ return iterator<BOX, 0, 0, WRAP_DEFAULT>(x, y, w, h, G); } |
550 |
|
551 |
template<class iteration_discipline, class wrap_discipline, grid_width_t iteratorWidth, grid_width_t iteratorHeight> |
552 |
operator iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>() |
553 |
{ return iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>(x, y, w, h, G); } |
554 |
|
555 |
template<class iteration_discipline, class wrap_discipline, grid_width_t iteratorWidth, grid_width_t iteratorHeight> |
556 |
operator const_iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>() const |
557 |
{ return const_iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>(x, y, w, h, G); } |
558 |
}; |
559 |
public: |
560 |
BeginStruct begin() { return BeginStruct(0, 0, gridWidth, gridHeight, this); } |
561 |
const BeginStruct begin() const { return BeginStruct(0, 0, gridWidth, gridHeight, this); } |
562 |
BeginStruct begin(const grid_xpos_t x, const grid_ypos_t y) { return BeginStruct(x, y, gridWidth, gridHeight, this); } |
563 |
BeginStruct begin(const grid_xpos_t x, const grid_ypos_t y, const grid_xoffset_t W, const grid_yoffset_t H) { return BeginStruct(x, y, W, H, this); } |
564 |
BeginStruct begin(const Inhabitant& I, const grid_length_t L=1) { return gridIteratorBegin(I.posX()-1, I.posY()-1, L+2, L+2, this); } |
565 |
template<class iteration_discipline, grid_width_t iteratorWidth, grid_width_t iteratorHeight, class wrap_discipline> |
566 |
BeginStruct begin(const iterator<iteration_discipline, iteratorWidth, iteratorHeight, wrap_discipline>& I) { return gridIteratorBegin(I.posX(), I.posY(), I.width()-I.posX(), I.height()-I.posX(), this); } |
567 |
static const GridInternal::IteratorEnd end() { return GridInternal::IteratorEnd(); } |
568 |
}; |
569 |
|
570 |
template<class Ch, class Tr, class Contained, grid_width_t gridWidth, grid_height_t gridHeight> |
571 |
std::basic_ostream<Ch, Tr>& operator<<(std::basic_ostream<Ch, Tr>& out, const Grid<Contained, gridWidth, gridHeight>& g) |
572 |
{ |
573 |
out << enterSection("Grid") |
574 |
<< title("Grid"); |
575 |
typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<BOX, gridWidth, gridHeight> i=g.begin(); |
576 |
while (i!=g.end()) |
577 |
{ |
578 |
debugOut(GridInternal::IO) << "operator<<(Grid< " << gridWidth << ", " << gridHeight << "> printing (" << i.posX() << ", " << i.posY() << ") == " << *i << std::endl; |
579 |
out << (i.posX()%gridWidth?' ':'\n') |
580 |
<< *i; ++i; |
581 |
}; |
582 |
out << leaveSection(); |
583 |
return out; |
584 |
} |
585 |
|
586 |
template<class Ch, class Contained, grid_width_t gridWidth, grid_height_t gridHeight> |
587 |
std::basic_ostream<Ch, Binary<Ch> >& operator<<(std::basic_ostream<Ch, Binary<Ch> >& out, const Grid<Contained, gridWidth, gridHeight>& g) |
588 |
{ |
589 |
out << enterSection("Grid") |
590 |
<< title("Grid"); |
591 |
typename Grid<Contained, gridWidth, gridHeight>::template const_iterator<BOX, gridWidth, gridHeight> i=g.begin(); |
592 |
while (i!=g.end()) |
593 |
{ |
594 |
debugOut(GridInternal::IO) << "operator<<(Grid< " << gridWidth << ", " << gridHeight << "> printing (" << i.posX() << ", " << i.posY() << ") == " << *i << std::endl; |
595 |
out << (i.posX()%gridWidth?' ':'\n') |
596 |
<< *i; ++i; |
597 |
}; |
598 |
out << leaveSection(); |
599 |
return out; |
600 |
}; |
601 |
|
602 |
template<class Ch, class Tr, class Contained, grid_width_t gridWidth, grid_height_t gridHeight> |
603 |
std::basic_istream<Ch, Tr>& operator>>(std::basic_istream<Ch, Tr>& in, Grid<Contained, gridWidth, gridHeight>& g) |
604 |
{ |
605 |
in >> enterSection("Grid") |
606 |
>> title("Grid"); |
607 |
for (typename Grid<Contained, gridWidth, gridHeight>::template iterator<HBOX, gridWidth, gridHeight> i=g.begin(); i!=g.end(); ++i) |
608 |
{ |
609 |
in >> (*i); in.ignore(1); |
610 |
debugOut(GridInternal::IO) << "operator>>(Grid< " << gridWidth << ", " << gridHeight << "> getting (" << i.posX() << ", " << i.posY() << ") = " << *i << std::endl; |
611 |
}; |
612 |
in >> leaveSection(); |
613 |
return in; |
614 |
} |
615 |
|
616 |
template<class Ch, class Contained, grid_width_t gridWidth, grid_height_t gridHeight> |
617 |
std::basic_istream<Ch, Binary<Ch> >& operator>>(std::basic_istream<Ch, Binary<Ch> >& in, Grid<Contained, gridWidth, gridHeight>& g) |
618 |
{ |
619 |
in >> enterSection("Grid") |
620 |
>> title("Grid"); |
621 |
for (typename Grid<Contained, gridWidth, gridHeight>::template iterator<HBOX, gridWidth, gridHeight> i=g.begin(); i!=g.end(); ++i) |
622 |
{ |
623 |
in.ignore(1); in >> (*i); |
624 |
debugOut(GridInternal::IO) << "operator>>(Grid< " << gridWidth << ", " << gridHeight << "> getting (" << i.posX() << ", " << i.posY() << ") = " << *i << std::endl; |
625 |
}; |
626 |
in >> leaveSection(); |
627 |
return in; |
628 |
} |
629 |
|
630 |
// Grid to handle a single elevation |
631 |
namespace GridInternal { |
632 |
class ElevationAssignment {}; |
633 |
struct Elevation { |
634 |
elevation_t e; |
635 |
Elevation() : e() {}; |
636 |
operator elevation_t() const { return e; }; |
637 |
const elevation_t operator=(const elevation_t ee) |
638 |
{ debugOut(ElevationAssignment) << "Elevation(" << this << ").operatior=(" << ee << ")" << std::endl; return e=ee; }; |
639 |
Elevation& operator* () { return *this; } |
640 |
Elevation& operator[](const int) { return *this; } |
641 |
|
642 |
template<class Ch, class Tr> friend std::basic_ostream<Ch, Tr>& operator<<(std::basic_ostream<Ch, Tr>& out, const Elevation& e) { out.width(3); return out << static_cast<unsigned int>(e.e); }; |
643 |
template<class Ch, class Tr> friend std::basic_istream<Ch, Tr>& operator>>(std::basic_istream<Ch, Tr>& in, Elevation& e) |
644 |
{ |
645 |
unsigned int i; |
646 |
in >> i; |
647 |
e.e = static_cast<elevation_t>(i); |
648 |
return in; |
649 |
}; |
650 |
|
651 |
template<class Ch> friend std::basic_ostream<Ch, Binary<Ch> >& operator<<(std::basic_ostream<Ch, Binary<Ch> >& out, const Elevation& e) { return out << e.e; }; |
652 |
template<class Ch> friend std::basic_istream<Ch, Binary<Ch> >& operator>>(std::basic_istream<Ch, Binary<Ch> >& in, Elevation& e) { return in >> e.e; }; |
653 |
}; |
654 |
}; |
655 |
|
656 |
template<grid_width_t elevationWidth, grid_height_t elevationHeight> class ElevationGrid : public Grid<GridInternal::Elevation, elevationWidth, elevationHeight> |
657 |
{ |
658 |
typedef Grid<GridInternal::Elevation, elevationWidth, elevationHeight> parent; |
659 |
static const elevation_sum_t optionElevation(GridInternal::Elevation *const f, const team_ID_t, const elevation_set_t) { return *f; }; |
660 |
static void Nothing() {}; |
661 |
static char* pathFindName() { return "Elevation"; } |
662 |
public: |
663 |
bool pathFind(const grid_xpos_t x, const grid_ypos_t y, grid_xpos_t& directionX, grid_ypos_t& directionY) const |
664 |
{ return parent::template pathFind<optionElevation, Nothing, Nothing, pathFindName>(x, y, 0, CANNOT_SWIM, directionX, directionY); } |
665 |
void registerPeak(GridInternal::Elevation* C) { parent::registerPeak(C); } |
666 |
void updateElevation() { parent::updateElevation(static_cast<team_ID_t>(0), CANNOT_SWIM, static_cast<elevation_index_t>(0)); }; |
667 |
}; |
668 |
|
669 |
#include "Grid.tcc" |
670 |
|
671 |
#endif // __GRID_H |