Debian Codegraph @

engine/ai/ai_building.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 ai_building.cpp - AI building functions. */
11 //
12 // (c) Copyright 2001-2009 by Lutz Sammer
13 //
14 // This program is free software; you can redistribute it and/or modify
15 // it under the terms of the GNU General Public License as published by
16 // the Free Software Foundation; only version 2 of the License.
17 //
18 // This program is distributed in the hope that it will be useful,
19 // but WITHOUT ANY WARRANTY; without even the implied warranty of
20 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 // GNU General Public License for more details.
22 //
23 // You should have received a copy of the GNU General Public License
24 // along with this program; if not, write to the Free Software
25 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
26 // 02111-1307, USA.
27 //
28
29 //@{
30
31 /*----------------------------------------------------------------------------
32 -- Includes
33 ----------------------------------------------------------------------------*/
34
35 #include <stdio.h>
36 #include <stdlib.h>
37
38 #include "stratagus.h"
39 #include "unit.h"
40 #include "unittype.h"
41 #include "map.h"
42 #include "pathfinder.h"
43 #include "ai_local.h"
44 #include "player.h"
45
46 /*----------------------------------------------------------------------------
47 -- Types
48 ----------------------------------------------------------------------------*/
49
50 enum
51 {
52 AiBuildingPlaceTried = 0x01, // tried to place a building there
53 AiBuildingPlaceBlock = 0x02, // worker cannot walk there
54 AiBuildingPlaceWalked = 0x04, // worker can walk there
55 AiBuildingPlaceEdge = 0x62 // = 98, which InitMatrix uses
56 };
57
58 /*----------------------------------------------------------------------------
59 -- Functions
60 ----------------------------------------------------------------------------*/
61
62 /**
63 ** Check if the surroundings are free. Depending on the value of flag, it will check:
64 ** 0: the building will not block any way
65 ** 1: all surrounding is free
66 **
67 ** @param worker Worker to build.
68 ** @param type Type of building.
69 ** @param x X map tile position for the building.
70 ** @param y Y map tile position for the building.
71 ** @param backupok Location can be used as a backup
72 **
73 ** @return True if the surrounding is free, false otherwise.
74 **
75 ** @note Can be faster written.
76 */
77 static int AiCheckSurrounding(const CUnit *worker, const CUnitType *type, int x, int y, bool &backupok)
78 {
79 static int dirs[5][2] = {{1,0},{0,1},{-1,0},{0,-1},{0,0}};
80 int surrounding[1024]; // Max circumference for building
81 int surroundingnb;
82 int x0, y0, x1, y1;
83 int i;
84 int lastval;
85 int dir;
86 int obstacle;
87
88 x0 = x - 1;
89 y0 = y - 1;
90 x1 = x0 + type->TileWidth + 1;
91 y1 = y0 + type->TileWidth + 1;
92
93
94 x = x0;
95 y = y0;
96 dir = -1;
97 surroundingnb = 0;
98 while (dir < 4)
99 {
100 if (x >= 0 && x < Map.Info.MapWidth &&
101 y >= 0 && y < Map.Info.MapHeight &&
102 (Map.Field(x, y)->Flags & (MapFieldUnpassable | MapFieldBuilding)) == 0)
103 {
104 surrounding[surroundingnb++] = 1;
105 }
106 else
107 {
108 surrounding[surroundingnb++] = 0;
109 }
110
111 if ((x == x0 || x == x1) && (y == y0 || y == y1))
112 {
113 dir++;
114 }
115
116 x += dirs[dir][0];
117 y += dirs[dir][1];
118 }
119
120 lastval = surrounding[surroundingnb - 1];
121 obstacle = 0;
122 for (i = 0 ; i < surroundingnb; ++i)
123 {
124 if (lastval && !surrounding[i])
125 {
126 ++obstacle;
127 }
128 lastval = surrounding[i];
129 }
130
131 if (obstacle == 0)
132 {
133 obstacle = !surrounding[0];
134 }
135
136 if (!type->ShoreBuilding)
137 {
138 backupok = obstacle < 5;
139 }
140 else
141 {
142 // Shore building have at least 2 obstacles : sea->ground & ground->sea
143 backupok = obstacle < 3;
144 }
145 return obstacle == 0;
146 }
147
148 /**
149 ** Try to place a building in each position within a rectangle,
150 ** except positions that have already been tried in earlier calls.
151 **
152 ** @param worker Worker to build building.
153 ** @param type Type of building.
154 ** @param matrix Origin in a 2d array that shows which positions
155 ** have already been tried.
156 ** @param minx Smallest X position to try building
157 ** @param miny Smallest Y position to try building
158 ** @param maxx Greatest X position to try building
159 ** @param maxy Greatest Y position to try building
160 ** @param chosenx Pointer for good X position returned.
161 ** @param choseny Pointer for good Y position returned.
162 ** @param backupx Pointer for worse X position returned.
163 ** @param backupx Pointer for worse Y position returned.
164 **
165 ** @return True if good position found, false if not found.
166 **
167 ** This function ignores TileWidth and TileHeight of the building,
168 ** so the caller should adjust maxx and maxy accordingly.
169 */
170 static inline bool AiTryBuildingPlacesRect(const CUnit *worker, const CUnitType* type,
171 unsigned char *matrix, int mwidth,
172 int minx, int miny, int maxx, int maxy,
173 int *chosenx, int *choseny,
174 int *backupx, int *backupy)
175 {
176 for (int y = miny; y <= maxy; y++)
177 {
178 for (int x = minx; x <= maxx; x++)
179 {
180 unsigned char *ptr = matrix + x + y * mwidth;
181 if (!(*ptr & AiBuildingPlaceTried))
182 {
183 CUnit *ontop = CanBuildUnitType(worker, type, x, y, 1);
184 if (ontop)
185 {
186 bool backupok;
187 if ((ontop != (CUnit *)1 && ontop != worker) ||
188 AiCheckSurrounding(worker, type, x, y, backupok))
189 {
190 *chosenx = x;
191 *choseny = y;
192 return true;
193 }
194 else if (backupok && *backupx == -1)
195 {
196 *backupx = x;
197 *backupy = y;
198 }
199 }
200
201 *ptr |= AiBuildingPlaceTried;
202 } // if not tried
203 } // for x
204 } // for y
205
206 return false;
207 }
208
209 /**
210 ** Find free building place. (flood fill version)
211 **
212 ** @param worker Worker to build building.
213 ** @param type Type of building.
214 ** @param ox Original X position to try building
215 ** @param oy Original Y position to try building
216 ** @param dx Pointer for X position returned.
217 ** @param dy Pointer for Y position returned.
218 **
219 ** @return True if place found, false if no found.
220 */
221 static int AiFindBuildingPlace2(const CUnit *worker, const CUnitType *type,
222 int ox, int oy, int *dx, int *dy)
223 {
224 static const int xoffset[] = { 0, -1, +1, 0, -1, +1, -1, +1 };
225 static const int yoffset[] = { -1, 0, 0, +1, -1, -1, +1, +1 };
226 struct p {
227 unsigned short X;
228 unsigned short Y;
229 } *points;
230 int size;
231 int x;
232 int y;
233 int rx;
234 int ry;
235 int mask;
236 int wp;
237 int rp;
238 int ep;
239 int i;
240 int w;
241 unsigned char *m;
242 unsigned char *matrix;
243 int backupx = -1;
244 int backupy = -1;
245 bool backupok;
246 CUnit *ontop;
247 int minoffx;
248 int minoffy;
249 int maxoffx;
250 int maxoffy;
251
252 size = Map.Info.MapWidth * Map.Info.MapHeight / 4;
253 points = new p[size];
254
255 x = ox;
256 y = oy;
257 //
258 // Look if we can build at current place.
259 //
260 if ((ontop = CanBuildUnitType(worker, type, x, y, 1)))
261 {
262 if ((ontop != (CUnit *)1 && ontop != worker) ||
263 AiCheckSurrounding(worker, type, x, y, backupok))
264 {
265 *dx = x;
266 *dy = y;
267 delete[] points;
268 return 1;
269 }
270 else if (backupok)
271 {
272 backupx = x;
273 backupy = y;
274 }
275 }
276 //
277 // Make movement matrix.
278 //
279 matrix = CreateMatrix();
280 w = Map.Info.MapWidth + 2;
281
282 mask = worker->Type->MovementMask;
283 // Ignore all possible mobile units.
284 mask &= ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit);
285
286 points[0].X = x;
287 points[0].Y = y;
288 // also use the bottom right
289 if ((type->TileWidth > 1 || type->TileHeight > 1) &&
290 x + type->TileWidth - 1 < Map.Info.MapWidth &&
291 y + type->TileHeight - 1 < Map.Info.MapHeight)
292 {
293 points[1].X = x + type->TileWidth - 1;
294 points[1].Y = y + type->TileHeight - 1;
295 ep = wp = 2; // start with two points
296 }
297 else
298 {
299 ep = wp = 1; // start with one point
300 }
301 matrix += w + w + 2;
302 rp = 0;
303 matrix[x + y * w] = 1; // mark start point
304
305 if (mask & ~type->MovementMask || !type->BuildingRules.empty())
306 {
307 // The worker cannot move to some types of tiles where
308 // the building can be built. For example, the worker
309 // can only walk on land and the building needs to be
310 // built in water.
311 //
312 // Or, the building type has some BuildingRules.
313 // Some of them might be BuildRestrictionOnTop,
314 // which implies there already is a building that
315 // would block the worker.
316 minoffx = -type->TileWidth;
317 minoffy = -type->TileHeight;
318 maxoffx = 1;
319 maxoffy = 1;
320 }
321 else
322 {
323 minoffx = 0;
324 minoffy = 0;
325 maxoffx = 0;
326 maxoffy = 0;
327 }
328
329 //
330 // Pop a point from stack, push all neighbours which could be entered.
331 //
332 for (;;)
333 {
334 while (rp != ep)
335 {
336 rx = points[rp].X;
337 ry = points[rp].Y;
338 for (i = 0; i < 8; ++i)
339 {
340 // mark all neighbors
341 x = rx + xoffset[i];
342 y = ry + yoffset[i];
343 m = matrix + x + y * w;
344 if (*m & (AiBuildingPlaceWalked | AiBuildingPlaceBlock))
345 {
346 // already checked
347 continue;
348 }
349
350 if (!CanMoveToMask(x, y, mask))
351 {
352 // unreachable
353 *m |= AiBuildingPlaceBlock;
354 continue;
355 }
356
357 //
358 // Look if we can build here and no enemies nearby.
359 //
360 if (!AiEnemyUnitsInDistance(worker->Player, NULL, x, y, 8)
361 && AiTryBuildingPlacesRect(
362 worker, type,
363 matrix, w,
364 std::max(x + minoffx, 0),
365 std::max(y + minoffy, 0),
366 std::min(x + maxoffx, Map.Info.MapWidth - type->TileWidth),
367 std::min(y + maxoffy, Map.Info.MapHeight - type->TileHeight),
368 dx, dy,
369 &backupx, &backupy))
370 {
371 delete[] points;
372 return 1;
373 }
374
375 *m |= AiBuildingPlaceWalked;
376 points[wp].X = x; // push the point
377 points[wp].Y = y;
378 if (++wp >= size)
379 {
380 // round about
381 wp = 0;
382 }
383 } // for i
384
385 if (++rp >= size)
386 {
387 // round about
388 rp = 0;
389 }
390 }
391
392 //
393 // Continue with next frame.
394 //
395 if (rp == wp)
396 {
397 // unreachable, no more points available
398 break;
399 }
400 ep = wp;
401 }
402
403 delete[] points;
404
405 if (backupx != -1)
406 {
407 *dx = backupx;
408 *dy = backupy;
409 return 1;
410 }
411 return 0;
412 }
413
414 /**
415 ** Find free building place.
416 **
417 ** @param worker Worker to build building.
418 ** @param type Type of building.
419 ** @param dx Pointer for X position returned.
420 ** @param dy Pointer for Y position returned.
421 **
422 ** @return True if place found, false if no found.
423 **
424 ** @todo Better and faster way to find building place of oil
425 ** platforms Special routines for special buildings.
426 */
427 int AiFindBuildingPlace(const CUnit *worker, const CUnitType *type, int *dx, int *dy)
428 {
429 DebugPrint("Want to build a %s(%s)\n" _C_ type->Ident.c_str() _C_ type->Name.c_str());
430
431 return AiFindBuildingPlace2(worker, type, worker->X, worker->Y, dx, dy);
432 }
433
434 //@}