Debian Codegraph @

engine/unit/unit_cache.cpp

raw
1 // ____ _ __
2 // / __ )____ _____ | | / /___ ___________
3 // / __ / __ \/ ___/ | | /| / / __ `/ ___/ ___/
4 // / /_/ / /_/ (__ ) | |/ |/ / /_/ / / (__ )
5 // /_____/\____/____/ |__/|__/\__,_/_/ /____/
6 //
7 // A futuristic real-time strategy game.
8 // This file is part of Bos Wars.
9 //
10 /**@name unit_cache.cpp - The unit cache. */
11 //
12 // Cache to find units faster from position.
13 // Sort of trivial implementation, since most queries are on a single tile.
14 // Unit is just inserted in a double linked list for every tile it's on.
15 //
16 // (c) Copyright 2004-2007 by Crestez Leonard and Jimmy Salmon
17 //
18 // This program is free software; you can redistribute it and/or modify
19 // it under the terms of the GNU General Public License as published by
20 // the Free Software Foundation; only version 2 of the License.
21 //
22 // This program is distributed in the hope that it will be useful,
23 // but WITHOUT ANY WARRANTY; without even the implied warranty of
24 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 // GNU General Public License for more details.
26 //
27 // You should have received a copy of the GNU General Public License
28 // along with this program; if not, write to the Free Software
29 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
30 // 02111-1307, USA.
31 //
32
33 //@{
34
35 /*----------------------------------------------------------------------------
36 -- Includes
37 ----------------------------------------------------------------------------*/
38
39 #include <string.h>
40
41 #include "stratagus.h"
42 #include "unit_cache.h"
43 #include "unit.h"
44 #include "unittype.h"
45
46
47 CUnitCache UnitCache;
48
49
50 /**
51 ** Initialize unit-cache.
52 **
53 ** @param mapWidth Map width
54 ** @param mapHeight Map height
55 */
56 void CUnitCache::Init(int mapWidth, int mapHeight)
57 {
58 width = mapWidth;
59 height = mapHeight;
60
61 cache.clear();
62 cache.resize(width);
63 for (int i = 0; i < width; ++i) {
64 cache[i].resize(height);
65 }
66 }
67
68 /**
69 ** Insert new unit into cache.
70 **
71 ** @param unit Unit pointer to place in cache.
72 */
73 void CUnitCache::Insert(CUnit *unit)
74 {
75 Assert(!unit->Removed);
76
77 for (int i = 0; i < unit->Type->TileWidth; ++i) {
78 for (int j = 0; j < unit->Type->TileHeight; ++j) {
79 cache[unit->X + i][unit->Y + j].push_back(unit);
80 }
81 }
82 }
83
84 /**
85 ** Remove unit from cache.
86 **
87 ** @param unit Unit pointer to remove from cache.
88 */
89 void CUnitCache::Remove(CUnit *unit)
90 {
91 Assert(!unit->Removed);
92
93 for (int i = 0; i < unit->Type->TileWidth; ++i) {
94 for (int j = 0; j < unit->Type->TileHeight; ++j) {
95 for (std::vector<CUnit *>::iterator k = cache[unit->X + i][unit->Y + j].begin();
96 k != cache[unit->X + i][unit->Y + j].end(); ++k) {
97 if (*k == unit) {
98 cache[unit->X + i][unit->Y + j].erase(k);
99 break;
100 }
101 }
102 }
103 }
104 }
105
106 /**
107 ** Select units in rectangle range.
108 **
109 ** @param x1 Left column of selection rectangle
110 ** @param y1 Top row of selection rectangle
111 ** @param x2 Right column of selection rectangle
112 ** @param y2 Bottom row of selection rectangle
113 ** @param table All units in the selection rectangle
114 ** @param tablesize Size of table array
115 **
116 ** @return Returns the number of units found
117 */
118 int CUnitCache::Select(int x1, int y1, int x2, int y2, CUnit **table, int tablesize)
119 {
120 int i;
121 int j;
122 int n;
123 CUnit *unit;
124 bool unitAdded[UnitMax];
125
126 // Optimize small searches.
127 if (x1 >= x2 - 1 && y1 >= y2 - 1) {
128 return UnitCache.Select(x1, y1, table, tablesize);
129 }
130
131 //
132 // Reduce to map limits.
133 //
134 x1 = std::max(x1, 0);
135 y1 = std::max(y1, 0);
136 x2 = std::min(x2, width - 1);
137 y2 = std::min(y2, height - 1);
138
139 memset(unitAdded, 0, sizeof(unitAdded));
140 n = 0;
141
142 for (i = x1; i <= x2 && n < tablesize; ++i) {
143 for (j = y1; j <= y2 && n < tablesize; ++j) {
144 for (size_t k = 0, end = cache[i][j].size(); k < end && n < tablesize; ++k) {
145 //
146 // To avoid getting a unit in multiple times we use a cache lock.
147 // It should only be used in here, unless you somehow want the unit
148 // to be out of cache.
149 //
150 unit = cache[i][j][k];
151 if (!unitAdded[unit->Slot] && !unit->Type->Revealer) {
152 Assert(!unit->Removed);
153 unitAdded[unit->Slot] = true;
154 table[n++] = unit;
155 }
156 }
157 }
158 }
159
160 return n;
161 }
162
163 /**
164 ** Select units on map tile.
165 **
166 ** @param x Map X tile position
167 ** @param y Map Y tile position
168 ** @param table All units in the selection rectangle
169 ** @param tablesize Size of table array
170 **
171 ** @return Returns the number of units found
172 */
173 int CUnitCache::Select(int x, int y, CUnit **table, int tablesize)
174 {
175 //
176 // Unlike in UnitCacheSelect, there's no way a unit can show up twice,
177 // so there is no need for Cache Locks.
178 //
179 int n = 0;
180 std::vector<CUnit *>::iterator i, end;
181
182 for (i = cache[x][y].begin(), end = cache[x][y].end(); i != end && n < tablesize; ++i) {
183 Assert(!(*i)->Removed);
184 table[n++] = *i;
185 }
186
187 return n;
188 }
189