Pyrogenesis  trunk
Grid.h
Go to the documentation of this file.
1 /* Copyright (C) 2017 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 #ifndef INCLUDED_GRID
19 #define INCLUDED_GRID
20 
21 #include <cstring>
22 
23 #ifdef NDEBUG
24 #define GRID_BOUNDS_DEBUG 0
25 #else
26 #define GRID_BOUNDS_DEBUG 1
27 #endif
28 
29 /**
30  * Basic 2D array, intended for storing tile data, plus support for lazy updates
31  * by ICmpObstructionManager.
32  * @c T must be a POD type that can be initialised with 0s.
33  */
34 template<typename T>
35 class Grid
36 {
37 public:
38  Grid() : m_W(0), m_H(0), m_Data(NULL), m_DirtyID(0)
39  {
40  }
41 
42  Grid(u16 w, u16 h) : m_W(w), m_H(h), m_Data(NULL), m_DirtyID(0)
43  {
44  if (m_W || m_H)
45  m_Data = new T[m_W * m_H];
46  reset();
47  }
48 
49  Grid(const Grid& g)
50  {
51  m_Data = NULL;
52  *this = g;
53  }
54 
55  Grid& operator=(const Grid& g)
56  {
57  if (this == &g)
58  return *this;
59 
60  m_DirtyID = g.m_DirtyID;
61  if (m_W == g.m_W && m_H == g.m_H)
62  {
63  memcpy(m_Data, g.m_Data, m_W*m_H*sizeof(T));
64  return *this;
65  }
66 
67  m_W = g.m_W;
68  m_H = g.m_H;
69  delete[] m_Data;
70  if (g.m_Data)
71  {
72  m_Data = new T[m_W * m_H];
73  memcpy(m_Data, g.m_Data, m_W*m_H*sizeof(T));
74  }
75  else
76  m_Data = NULL;
77  return *this;
78  }
79 
80  void swap(Grid& g)
81  {
84  std::swap(m_H, g.m_H);
85  std::swap(m_W, g.m_W);
86  }
87 
89  {
90  delete[] m_Data;
91  }
92 
93  void reset()
94  {
95  if (m_Data)
96  memset(m_Data, 0, m_W*m_H*sizeof(T));
97  }
98 
99  // Add two grids of the same size
100  void add(const Grid& g)
101  {
102 #if GRID_BOUNDS_DEBUG
103  ENSURE(g.m_W == m_W && g.m_H == m_H);
104 #endif
105  for (int i=0; i < m_H*m_W; ++i)
106  m_Data[i] += g.m_Data[i];
107  }
108 
109  void set(int i, int j, const T& value)
110  {
111 #if GRID_BOUNDS_DEBUG
112  ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H);
113 #endif
114  m_Data[j*m_W + i] = value;
115  }
116 
117  T& get(int i, int j) const
118  {
119 #if GRID_BOUNDS_DEBUG
120  ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H);
121 #endif
122  return m_Data[j*m_W + i];
123  }
124 
127 
128  size_t m_DirtyID; // if this is < the id maintained by ICmpObstructionManager then it needs to be updated
129 };
130 
131 /**
132  * Similar to Grid, except optimised for sparse usage (the grid is subdivided into
133  * buckets whose contents are only initialised on demand, to save on memset cost).
134  */
135 template<typename T>
137 {
139 
140  enum { BucketBits = 4, BucketSize = 1 << BucketBits };
141 
142  T* GetBucket(int i, int j)
143  {
144  size_t b = (j >> BucketBits) * m_BW + (i >> BucketBits);
145  if (!m_Data[b])
146  {
147  m_Data[b] = new T[BucketSize*BucketSize];
148  memset(m_Data[b], 0, BucketSize*BucketSize*sizeof(T));
149  }
150  return m_Data[b];
151  }
152 
153 public:
154  SparseGrid(u16 w, u16 h) : m_W(w), m_H(h), m_DirtyID(0)
155  {
156  ENSURE(m_W && m_H);
157 
158  m_BW = (u16)((m_W + BucketSize-1) >> BucketBits);
159  m_BH = (u16)((m_H + BucketSize-1) >> BucketBits);
160 
161  m_Data = new T*[m_BW*m_BH];
162  memset(m_Data, 0, m_BW*m_BH*sizeof(T*));
163  }
164 
166  {
167  reset();
168  delete[] m_Data;
169  }
170 
171  void reset()
172  {
173  for (size_t i = 0; i < (size_t)(m_BW*m_BH); ++i)
174  delete[] m_Data[i];
175 
176  memset(m_Data, 0, m_BW*m_BH*sizeof(T*));
177  }
178 
179  void set(int i, int j, const T& value)
180  {
181 #if GRID_BOUNDS_DEBUG
182  ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H);
183 #endif
184  GetBucket(i, j)[(j % BucketSize)*BucketSize + (i % BucketSize)] = value;
185  }
186 
187  T& get(int i, int j)
188  {
189 #if GRID_BOUNDS_DEBUG
190  ENSURE(0 <= i && i < m_W && 0 <= j && j < m_H);
191 #endif
192  return GetBucket(i, j)[(j % BucketSize)*BucketSize + (i % BucketSize)];
193  }
194 
196  u16 m_BW, m_BH;
198 
199  size_t m_DirtyID; // if this is < the id maintained by ICmpObstructionManager then it needs to be updated
200 };
201 
202 /**
203  * Structure holding grid dirtiness informations, for clever updates
204  *
205  * Note: globallyDirty should be used to know which parts of the grid have been changed after an update,
206  * whereas globalRecompute should be used during the update itself, to avoid unnecessary recomputations.
207  */
209 {
210  bool dirty;
214 
216  {
217  std::swap(dirty, b.dirty);
218  std::swap(globallyDirty, b.globallyDirty);
219  std::swap(globalRecompute, b.globalRecompute);
220  dirtinessGrid.swap(b.dirtinessGrid);
221  }
222 
223  /**
224  * Mark everything as clean
225  */
226  void Clean()
227  {
228  dirty = false;
229  globallyDirty = false;
230  globalRecompute = false;
231  dirtinessGrid.reset();
232  }
233 };
234 
235 #endif // INCLUDED_GRID
void swap(Grid &g)
Definition: Grid.h:80
#define NONCOPYABLE(className)
Indicates that a class is noncopyable (usually due to const or reference members, or because the clas...
Definition: code_annotation.h:217
Grid & operator=(const Grid &g)
Definition: Grid.h:55
Similar to Grid, except optimised for sparse usage (the grid is subdivided into buckets whose content...
Definition: Grid.h:136
bool dirty
Definition: Grid.h:210
Grid()
Definition: Grid.h:38
uint16_t u16
Definition: types.h:38
u16 m_H
Definition: Grid.h:125
static void swap(UniqueRange &p1, UniqueRange &p2)
Definition: unique_range.h:198
Grid(u16 w, u16 h)
Definition: Grid.h:42
Structure holding grid dirtiness informations, for clever updates.
Definition: Grid.h:208
Basic 2D array, intended for storing tile data, plus support for lazy updates by ICmpObstructionManag...
Definition: ICmpPathfinder.h:34
bool globallyDirty
Definition: Grid.h:211
size_t m_DirtyID
Definition: Grid.h:128
void reset()
Definition: Grid.h:171
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:287
SparseGrid(u16 w, u16 h)
Definition: Grid.h:154
bool globalRecompute
Definition: Grid.h:212
void reset()
Definition: Grid.h:93
~Grid()
Definition: Grid.h:88
~SparseGrid()
Definition: Grid.h:165
#define T(string_literal)
Definition: secure_crt.cpp:76
void add(const Grid &g)
Definition: Grid.h:100
u16 m_W
Definition: Grid.h:195
Grid< u8 > dirtinessGrid
Definition: Grid.h:213
T * m_Data
Definition: Grid.h:126
T ** m_Data
Definition: Grid.h:197
void Clean()
Mark everything as clean.
Definition: Grid.h:226
u16 m_W
Definition: Grid.h:125
size_t m_DirtyID
Definition: Grid.h:199
void swap(GridUpdateInformation &b)
Definition: Grid.h:215
Grid(const Grid &g)
Definition: Grid.h:49
u16 m_BW
Definition: Grid.h:196
T * GetBucket(int i, int j)
Definition: Grid.h:142