Debian Codegraph @

engine/pathfinder/pathfinder.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 pathfinder.cpp - The path finder routines. */
11 //
12 // I use breadth-first.
13 //
14 // (c) Copyright 1998-2007 by Lutz Sammer, Russell Smith
15 //
16 // This program is free software; you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation; only version 2 of the License.
19 //
20 // This program is distributed in the hope that it will be useful,
21 // but WITHOUT ANY WARRANTY; without even the implied warranty of
22 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 // GNU General Public License for more details.
24 //
25 // You should have received a copy of the GNU General Public License
26 // along with this program; if not, write to the Free Software
27 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
28 // 02111-1307, USA.
29 //
30
31 //@{
32
33 /*----------------------------------------------------------------------------
34 -- Includes
35 ----------------------------------------------------------------------------*/
36
37 #include "stratagus.h"
38 #include "map.h"
39 #include "unittype.h"
40 #include "unit.h"
41 #include "pathfinder.h"
42
43 /*----------------------------------------------------------------------------
44 -- Variables
45 ----------------------------------------------------------------------------*/
46
47 /**
48 ** The matrix is used to generated the paths.
49 **
50 ** 0: Nothing must check if usable.
51 ** 1-8: Field on the path 1->2->3->4->5...
52 ** 88: Marks the possible goal fields.
53 ** 98: Marks map border, for faster limits checks.
54 */
55 static unsigned char Matrix[(MaxMapWidth + 2) * (MaxMapHeight + 3) + 2]; /// Path matrix
56
57 static int STDCALL CostMoveTo(int x, int y, void *data);
58
59 /*----------------------------------------------------------------------------
60 -- Functions
61 ----------------------------------------------------------------------------*/
62
63 /**
64 ** Init the pathfinder
65 */
66 void InitPathfinder()
67 {
68 InitAStar(Map.Info.MapWidth, Map.Info.MapHeight, CostMoveTo);
69 }
70
71 /**
72 ** Free the pathfinder
73 */
74 void FreePathfinder()
75 {
76 FreeAStar();
77 }
78
79 /**
80 ** Initialize a matrix
81 **
82 ** @note Double border for ships/flyers.
83 **
84 ** 98 98 98 98 98
85 ** 98 98 98 98 98
86 ** 98 98
87 ** 98 98
88 ** 98 98 98 98 98
89 */
90 static void InitMatrix(unsigned char *matrix)
91 {
92 unsigned i;
93 unsigned w;
94 unsigned h;
95 unsigned e;
96
97 w = Map.Info.MapWidth + 2;
98 h = Map.Info.MapHeight;
99
100 i = w + w + 1;
101 memset(matrix, 98, i); // +1 for ships!
102 memset(matrix + i, 0, w * h); // initialize matrix
103
104 for (e = i + w * h; i < e;) { // mark left and right border
105 matrix[i] = 98;
106 i += w;
107 matrix[i - 1] = 98;
108 }
109 memset(matrix + i, 98, w + 1); // +1 for ships!
110 }
111
112 /**
113 ** Create empty movement matrix.
114 */
115 unsigned char *CreateMatrix(void)
116 {
117 InitMatrix(Matrix);
118 return Matrix;
119 }
120
121 /**
122 ** Allocate a new matrix and initialize
123 */
124 unsigned char *MakeMatrix(void)
125 {
126 unsigned char *matrix;
127
128 matrix = new unsigned char[(Map.Info.MapWidth + 2) * (Map.Info.MapHeight + 3) + 2];
129 InitMatrix(matrix);
130
131 return matrix;
132 }
133
134 /*----------------------------------------------------------------------------
135 -- PATH-FINDER USE
136 ----------------------------------------------------------------------------*/
137
138 /**
139 ** Can the unit 'src' reach the place x,y.
140 **
141 ** @param src Unit for the path.
142 ** @param x Map X tile position.
143 ** @param y Map Y tile position.
144 ** @param w Width of Goal
145 ** @param h Height of Goal
146 ** @param minrange min range to the tile
147 ** @param range Range to the tile.
148 **
149 ** @pre The unit's field flags must have been marked
150 ** on the map; see MarkUnitFieldFlags.
151 **
152 ** @return Distance to place.
153 */
154 int PlaceReachable(const CUnit *src, int x, int y, int w, int h, int minrange, int range)
155 {
156 // Please do not use UnmarkUnitFieldFlags and MarkUnitFieldFlags
157 // around PlaceReachable calls.
158 Assert((Map.Field(src->X, src->Y)->Flags & src->Type->FieldFlags) != 0);
159
160 UnmarkUnitFieldFlags(src);
161 int i = AStarFindPath(src->X, src->Y, x, y, w, h,
162 src->Type->TileWidth, src->Type->TileHeight, minrange, range, NULL, 0, (void *)src);
163 MarkUnitFieldFlags(src);
164
165 switch (i) {
166 case PF_FAILED:
167 case PF_UNREACHABLE:
168 case PF_REACHED:
169 i = 0;
170 break;
171 case PF_WAIT:
172 Assert(0);
173 i = 0;
174 break;
175 case PF_MOVE:
176 break;
177 default:
178 break;
179 }
180
181 return i;
182 }
183
184 /**
185 ** Can the unit 'src' reach the unit 'dst'.
186 **
187 ** @param src Unit for the path.
188 ** @param dst Unit to be reached.
189 ** @param range Range to unit.
190 **
191 ** @pre The unit's field flags must have been marked
192 ** on the map; see MarkUnitFieldFlags.
193 **
194 ** @return Distance to place.
195 */
196 int UnitReachable(const CUnit *src, const CUnit *dst, int range)
197 {
198 int depth;
199
200 // Please do not use UnmarkUnitFieldFlags and MarkUnitFieldFlags
201 // around UnitReachable calls.
202 Assert((Map.Field(src->X, src->Y)->Flags & src->Type->FieldFlags) != 0);
203
204 //
205 // Find a path to the goal.
206 //
207 depth = PlaceReachable(src, dst->X, dst->Y, dst->Type->TileWidth, dst->Type->TileHeight, 0, range);
208 if (depth <= 0) {
209 return 0;
210 }
211
212 return depth;
213 }
214
215 /**
216 ** Compute the cost of crossing tile (dx,dy)
217 **
218 ** @param data The CUnit * that wants to cross the tile. This is
219 ** passed in as void * so that the low-level A* code
220 ** need not know about CUnit.
221 ** @param x X tile where to move.
222 ** @param y Y tile where to move.
223 **
224 ** @pre The unit's field flags must have been unmarked
225 ** on the map; see UnmarkUnitFieldFlags.
226 **
227 ** @return -1 -> impossible to cross.
228 ** 0 -> no induced cost, except move
229 ** >0 -> costly tile
230 */
231 static int STDCALL CostMoveTo(int x, int y, void *data)
232 {
233 int i;
234 int j;
235 int flag;
236 int cost = 0;
237 CUnit *goal;
238 const CUnit *unit = (const CUnit *)data;
239 int mask = unit->Type->MovementMask;
240
241 cost = 0;
242
243 // Doesn't cost anything to move to ourselves :)
244 // Used when marking goals mainly. Could cause speed problems
245 if (unit->X == x && unit->Y == y) {
246 return 0;
247 }
248
249 // verify each tile of the unit.
250 for (i = x; i < x + unit->Type->TileWidth; ++i) {
251 for (j = y; j < y + unit->Type->TileHeight; ++j) {
252 flag = Map.Field(i, j)->Flags & mask;
253 if (flag && (AStarKnowUnseenTerrain || Map.IsFieldExplored(unit->Player, i, j))) {
254 if (flag & ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit)) {
255 // we can't cross fixed units and other unpassable things
256 return -1;
257 }
258 goal = UnitOnMapTile(i, j, unit->Type->UnitType);
259 if (!goal) {
260 // Shouldn't happen, mask says there is something on this tile
261 Assert(0);
262 return -1;
263 }
264
265 // The unit must not be blocked by itself.
266 // Please use UnmarkUnitFieldFlags and
267 // MarkUnitFieldFlags around pathfinder calls.
268 Assert(goal != unit);
269
270 if (goal->Moving) {
271 // moving unit are crossable
272 cost += AStarMovingUnitCrossingCost;
273 } else {
274 // for non moving unit Always Fail
275 // FIXME: Need support for moving a fixed unit to add cost
276 return -1;
277 //cost += AStarFixedUnitCrossingCost;
278 }
279 }
280 // Add cost of crossing unknown tiles if required
281 if (!AStarKnowUnseenTerrain && !Map.IsFieldExplored(unit->Player, i, j)) {
282 // Tend against unknown tiles.
283 cost += AStarUnknownTerrainCost;
284 }
285 if (unit->Type->UnitType != UnitTypeFly) {
286 // Add tile movement cost
287 cost += Map.Field(i, j)->Cost;
288 }
289 }
290 }
291 return cost;
292 }
293
294 /*----------------------------------------------------------------------------
295 -- REAL PATH-FINDER
296 ----------------------------------------------------------------------------*/
297
298 /**
299 ** Find new path.
300 **
301 ** The destination could be a unit or a field.
302 ** Range gives how far we must reach the goal.
303 **
304 ** @note The destination could become negative coordinates!
305 **
306 ** @param unit Path for this unit.
307 **
308 ** @pre The unit's field flags must have been unmarked
309 ** on the map; see UnmarkUnitFieldFlags.
310 **
311 ** @return >0 remaining path length, 0 wait for path, -1
312 ** reached goal, -2 can't reach the goal.
313 */
314 int NewPath(CUnit *unit)
315 {
316 int i;
317 int gw;
318 int gh;
319 int gx;
320 int gy;
321 int minrange;
322 int maxrange;
323 char *path;
324
325 // Please use UnmarkUnitFieldFlags and MarkUnitFieldFlags
326 // around NewPath calls.
327 Assert((Map.Field(unit->X, unit->Y)->Flags & unit->Type->FieldFlags) == 0);
328
329 if (unit->Orders[0]->Goal) {
330 gw = unit->Orders[0]->Goal->Type->TileWidth;
331 gh = unit->Orders[0]->Goal->Type->TileHeight;
332 gx = unit->Orders[0]->Goal->X;
333 gy = unit->Orders[0]->Goal->Y;
334 maxrange = unit->Orders[0]->Range;
335 minrange = unit->Orders[0]->MinRange;
336 } else {
337 // Take care of non square goals :)
338 // If goal is non square, range states a non-existant goal rather
339 // than a tile.
340 gw = unit->Orders[0]->Width;
341 gh = unit->Orders[0]->Height;
342 maxrange = unit->Orders[0]->Range;
343 minrange = unit->Orders[0]->MinRange;
344 // Large units may have a goal that goes outside the map, fix it here
345 if (unit->Orders[0]->X + unit->Type->TileWidth - 1 >= Map.Info.MapWidth) {
346 unit->Orders[0]->X = Map.Info.MapWidth - unit->Type->TileWidth;
347 }
348 if (unit->Orders[0]->Y + unit->Type->TileHeight - 1 >= Map.Info.MapHeight) {
349 unit->Orders[0]->Y = Map.Info.MapHeight - unit->Type->TileHeight;
350 }
351 gx = unit->Orders[0]->X;
352 gy = unit->Orders[0]->Y;
353 }
354 path = unit->Data.Move.Path;
355 i = AStarFindPath(unit->X, unit->Y, gx, gy, gw, gh,
356 unit->Type->TileWidth, unit->Type->TileHeight, minrange, maxrange, path, MAX_PATH_LENGTH, unit);
357 if (i == PF_FAILED) {
358 i = PF_UNREACHABLE;
359 }
360
361 // Update path if it was requested. Otherwise we may only want
362 // to know if there exists a path.
363
364 if (path != NULL) {
365 if (i >= MAX_PATH_LENGTH) {
366 unit->Data.Move.Length = MAX_PATH_LENGTH;
367 } else {
368 unit->Data.Move.Length = i;
369 }
370 if (unit->Data.Move.Length == 0) {
371 ++unit->Data.Move.Length;
372 }
373 }
374 return i;
375 }
376
377 /**
378 ** Returns the next element of a path.
379 **
380 ** @param unit Unit that wants the path element.
381 ** @param pxd Pointer for the x direction.
382 ** @param pyd Pointer for the y direction.
383 **
384 ** @pre The unit's field flags must have been unmarked
385 ** on the map; see UnmarkUnitFieldFlags.
386 **
387 ** @return >0 remaining path length, 0 wait for path, -1
388 ** reached goal, -2 can't reach the goal.
389 */
390 int NextPathElement(CUnit *unit, int *pxd, int *pyd)
391 {
392 int result;
393
394 // Please use UnmarkUnitFieldFlags and MarkUnitFieldFlags
395 // around NextPathElement calls.
396 Assert((Map.Field(unit->X, unit->Y)->Flags & unit->Type->FieldFlags) == 0);
397
398 // Attempt to use path cache
399 // FIXME: If there is a goal, it may have moved, ruining the cache
400 *pxd = 0;
401 *pyd = 0;
402
403 // Goal has moved, need to recalculate path or no cached path
404 if (unit->Data.Move.Length <= 0 ||
405 (unit->Orders[0]->Goal && (unit->Orders[0]->Goal->X != unit->Orders[0]->X ||
406 unit->Orders[0]->Goal->Y != unit->Orders[0]->Y))) {
407 result = NewPath(unit);
408
409 if (result == PF_UNREACHABLE) {
410 unit->Data.Move.Length = 0;
411 return result;
412 }
413 if (result == PF_REACHED) {
414 return result;
415 }
416 if (unit->Goal) {
417 // Update Orders
418 unit->Orders[0]->X = unit->Goal->X;
419 unit->Orders[0]->Y = unit->Goal->Y;
420 }
421 }
422
423 *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
424 *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
425 result = unit->Data.Move.Length;
426 unit->Data.Move.Length--;
427 if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) {
428 // If obstructing unit is moving, wait for a bit.
429 if (unit->Data.Move.Fast) {
430 unit->Data.Move.Fast--;
431 AstarDebugPrint("WAIT at %d\n" _C_ unit->Data.Move.Fast);
432 result = PF_WAIT;
433 } else {
434 unit->Data.Move.Fast = 10;
435 AstarDebugPrint("SET WAIT to 10\n");
436 result = PF_WAIT;
437 }
438 if (unit->Data.Move.Fast == 0 && result != 0) {
439 AstarDebugPrint("WAIT expired\n");
440 result = NewPath(unit);
441 if (result > 0) {
442 *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
443 *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]];
444 if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) {
445 // There may be unit in the way, Astar may allow you to walk onto it.
446 result = PF_UNREACHABLE;
447 *pxd = 0;
448 *pyd = 0;
449 } else {
450 result = unit->Data.Move.Length;
451 unit->Data.Move.Length--;
452 }
453 }
454 }
455 }
456 if (result != PF_WAIT) {
457 unit->Data.Move.Fast = 0;
458 }
459 return result;
460 }
461
462 //@}