1 /*
2 * Copyright 2010-2014 OpenXcom Developers.
3 *
4 * This file is part of OpenXcom.
5 *
6 * OpenXcom 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 3 of the License, or
9 * (at your option) any later version.
10 *
11 * OpenXcom 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 OpenXcom. If not, see <http://www.gnu.org/licenses/>.
18 */
19 #include <list>
20 #include "Pathfinding.h"
21 #include "PathfindingNode.h"
22 #include "PathfindingOpenSet.h"
23 #include "../Savegame/SavedBattleGame.h"
24 #include "../Savegame/Tile.h"
25 #include "../Ruleset/Armor.h"
26 #include "../Ruleset/Ruleset.h"
27 #include "../Savegame/BattleUnit.h"
28 #include "../Savegame/BattleItem.h"
29 #include "../Engine/Game.h"
30 #include "../Engine/Options.h"
31 #include "../Battlescape/TileEngine.h"
32 #include "../Battlescape/BattlescapeGame.h"
33 #include "../Battlescape/BattlescapeState.h"
34
35 namespace OpenXcom
36 {
37
38 /**
39 * Sets up a Pathfinding.
40 * @param save pointer to SavedBattleGame object.
41 */
Pathfinding(SavedBattleGame * save)42 Pathfinding::Pathfinding(SavedBattleGame *save) : _save(save), _nodes(), _unit(0), _pathPreviewed(false), _strafeMove(false), _totalTUCost(0), _modifierUsed(false), _movementType(MT_WALK)
43 {
44 _size = _save->getMapSizeXYZ();
45 // Initialize one node per tile
46 _nodes.reserve(_size);
47 Position p;
48 for (int i = 0; i < _size; ++i)
49 {
50 _save->getTileCoords(i, &p.x, &p.y, &p.z);
51 _nodes.push_back(PathfindingNode(p));
52 }
53 }
54
55 /**
56 * Deletes the Pathfinding.
57 * @internal This is required to be here because it requires the PathfindingNode class definition.
58 */
~Pathfinding()59 Pathfinding::~Pathfinding()
60 {
61 // Nothing more to do here.
62 }
63
64 /**
65 * Gets the Node on a given position on the map.
66 * @param pos Position.
67 * @return Pointer to node.
68 */
getNode(const Position & pos)69 PathfindingNode *Pathfinding::getNode(const Position& pos)
70 {
71 return &_nodes[_save->getTileIndex(pos)];
72 }
73
74 /**
75 * Calculates the shortest path.
76 * @param unit Unit taking the path.
77 * @param endPosition The position we want to reach.
78 * @param target Target of the path.
79 * @param maxTUCost Maximum time units the path can cost.
80 */
calculate(BattleUnit * unit,Position endPosition,BattleUnit * target,int maxTUCost)81 void Pathfinding::calculate(BattleUnit *unit, Position endPosition, BattleUnit *target, int maxTUCost)
82 {
83 _totalTUCost = 0;
84 _path.clear();
85 // i'm DONE with these out of bounds errors.
86 if (endPosition.x > _save->getMapSizeX() - unit->getArmor()->getSize() || endPosition.y > _save->getMapSizeY() - unit->getArmor()->getSize() || endPosition.x < 0 || endPosition.y < 0) return;
87
88 bool sneak = Options::sneakyAI && unit->getFaction() == FACTION_HOSTILE;
89
90 Position startPosition = unit->getPosition();
91 _movementType = unit->getArmor()->getMovementType();
92 if (target != 0 && maxTUCost == -1) // pathfinding for missile
93 {
94 _movementType = MT_FLY;
95 maxTUCost = 10000;
96 }
97 _unit = unit;
98
99 Tile *destinationTile = _save->getTile(endPosition);
100
101 // check if destination is not blocked
102 if (isBlocked(destinationTile, MapData::O_FLOOR, target) || isBlocked(destinationTile, MapData::O_OBJECT, target)) return;
103
104 // the following check avoids that the unit walks behind the stairs if we click behind the stairs to make it go up the stairs.
105 // it only works if the unit is on one of the 2 tiles on the stairs, or on the tile right in front of the stairs.
106 if (isOnStairs(startPosition, endPosition))
107 {
108 endPosition.z++;
109 destinationTile = _save->getTile(endPosition);
110 }
111 while (endPosition.z != _save->getMapSizeZ() && destinationTile->getTerrainLevel() == -24)
112 {
113 endPosition.z++;
114 destinationTile = _save->getTile(endPosition);
115 }
116 // check if we have floor, else lower destination (for non flying units only, because otherwise they never reached this place)
117 while (canFallDown(destinationTile, _unit->getArmor()->getSize()) && _movementType != MT_FLY)
118 {
119 endPosition.z--;
120 destinationTile = _save->getTile(endPosition);
121 }
122 int size = unit->getArmor()->getSize()-1;
123 if (size >= 1)
124 {
125 int its = 0;
126 const int dir[3] = {4,2,3};
127 for (int x = 0; x <= size; x += size)
128 {
129 for (int y = 0; y <= size; y += size)
130 {
131 if (x || y)
132 {
133 Tile *checkTile = _save->getTile(endPosition + Position(x, y, 0));
134 if ((isBlocked(destinationTile, checkTile, dir[its], unit) &&
135 isBlocked(destinationTile, checkTile, dir[its], target))||
136 (checkTile->getUnit() &&
137 checkTile->getUnit() != unit &&
138 checkTile->getUnit()->getVisible() &&
139 checkTile->getUnit() != target))
140 return;
141 if (x && y)
142 {
143 if ((checkTile->getMapData(MapData::O_NORTHWALL) && checkTile->getMapData(MapData::O_NORTHWALL)->isDoor()) ||
144 (checkTile->getMapData(MapData::O_WESTWALL) && checkTile->getMapData(MapData::O_WESTWALL)->isDoor()))
145 return;
146 }
147 ++its;
148 }
149 }
150 }
151 }
152 // Strafing move allowed only to adjacent squares on same z. "Same z" rule mainly to simplify walking render.
153 _strafeMove = Options::strafe && (SDL_GetModState() & KMOD_CTRL) != 0 && (startPosition.z == endPosition.z) &&
154 (abs(startPosition.x - endPosition.x) <= 1) && (abs(startPosition.y - endPosition.y) <= 1);
155
156 // look for a possible fast and accurate bresenham path and skip A*
157 if (startPosition.z == endPosition.z && bresenhamPath(startPosition,endPosition, target, sneak))
158 {
159 std::reverse(_path.begin(), _path.end()); //paths are stored in reverse order
160 return;
161 }
162 else
163 {
164 abortPath(); // if bresenham failed, we shouldn't keep the path it was attempting, in case A* fails too.
165 }
166 // Now try through A*.
167 if (!aStarPath(startPosition, endPosition, target, sneak, maxTUCost))
168 {
169 abortPath();
170 }
171 }
172
173 /**
174 * Calculates the shortest path using a simple A-Star algorithm.
175 * The unit information and movement type must have already been set.
176 * The path information is set only if a valid path is found.
177 * @param startPosition The position to start from.
178 * @param endPosition The position we want to reach.
179 * @param target Target of the path.
180 * @param sneak Is the unit sneaking?
181 * @param maxTUCost Maximum time units the path can cost.
182 * @return True if a path exists, false otherwise.
183 */
aStarPath(const Position & startPosition,const Position & endPosition,BattleUnit * target,bool sneak,int maxTUCost)184 bool Pathfinding::aStarPath(const Position &startPosition, const Position &endPosition, BattleUnit *target, bool sneak, int maxTUCost)
185 {
186 // reset every node, so we have to check them all
187 for (std::vector<PathfindingNode>::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
188 it->reset();
189
190 // start position is the first one in our "open" list
191 PathfindingNode *start = getNode(startPosition);
192 start->connect(0, 0, 0, endPosition);
193 PathfindingOpenSet openList;
194 openList.push(start);
195 bool missile = (target && maxTUCost == -1);
196 // if the open list is empty, we've reached the end
197 while(!openList.empty())
198 {
199 PathfindingNode *currentNode = openList.pop();
200 Position const ¤tPos = currentNode->getPosition();
201 currentNode->setChecked();
202 if (currentPos == endPosition) // We found our target.
203 {
204 _path.clear();
205 PathfindingNode *pf = currentNode;
206 while (pf->getPrevNode())
207 {
208 _path.push_back(pf->getPrevDir());
209 pf = pf->getPrevNode();
210 }
211 return true;
212 }
213
214 // Try all reachable neighbours.
215 for (int direction = 0; direction < 10; direction++)
216 {
217 Position nextPos;
218 int tuCost = getTUCost(currentPos, direction, &nextPos, _unit, target, missile);
219 if (tuCost >= 255) // Skip unreachable / blocked
220 continue;
221 if (sneak && _save->getTile(nextPos)->getVisible()) tuCost *= 2; // avoid being seen
222 PathfindingNode *nextNode = getNode(nextPos);
223 if (nextNode->isChecked()) // Our algorithm means this node is already at minimum cost.
224 continue;
225 _totalTUCost = currentNode->getTUCost(missile) + tuCost;
226 // If this node is unvisited or has only been visited from inferior paths...
227 if ((!nextNode->inOpenSet() || nextNode->getTUCost(missile) > _totalTUCost) && _totalTUCost <= maxTUCost)
228 {
229 nextNode->connect(_totalTUCost, currentNode, direction, endPosition);
230 openList.push(nextNode);
231 }
232 }
233 }
234 // Unble to reach the target
235 return false;
236 }
237
238 /**
239 * Gets the TU cost to move from 1 tile to the other (ONE STEP ONLY).
240 * But also updates the endPosition, because it is possible
241 * the unit goes upstairs or falls down while walking.
242 * @param startPosition The position to start from.
243 * @param direction The direction we are facing.
244 * @param endPosition The position we want to reach.
245 * @param unit The unit moving.
246 * @param target The target unit.
247 * @param missile Is this a guided missile?
248 * @return TU cost or 255 if movement is impossible.
249 */
getTUCost(const Position & startPosition,int direction,Position * endPosition,BattleUnit * unit,BattleUnit * target,bool missile)250 int Pathfinding::getTUCost(const Position &startPosition, int direction, Position *endPosition, BattleUnit *unit, BattleUnit *target, bool missile)
251 {
252 _unit = unit;
253 directionToVector(direction, endPosition);
254 *endPosition += startPosition;
255 bool fellDown = false;
256 bool triedStairs = false;
257 int size = _unit->getArmor()->getSize() - 1;
258 int cost = 0;
259 int numberOfPartsGoingUp = 0;
260 int numberOfPartsGoingDown = 0;
261 int numberOfPartsFalling = 0;
262 int numberOfPartsChangingHeight = 0;
263 int totalCost = 0;
264
265 for (int x = 0; x <= size; ++x)
266 for (int y = 0; y <= size; ++y)
267 {
268 Position offset = Position (x, y, 0);
269 Tile *startTile = _save->getTile(startPosition + offset);
270 Tile *destinationTile = _save->getTile(*endPosition + offset);
271 Tile *belowDestination = _save->getTile(*endPosition + offset + Position(0,0,-1));
272 Tile *aboveDestination = _save->getTile(*endPosition + offset + Position(0,0,1));
273
274 // this means the destination is probably outside the map
275 if (startTile == 0 || destinationTile == 0)
276 return 255;
277
278 if (direction < DIR_UP && startTile->getTerrainLevel() > - 16)
279 {
280 // check if we can go this way
281 if (isBlocked(startTile, destinationTile, direction, target))
282 return 255;
283 if (startTile->getTerrainLevel() - destinationTile->getTerrainLevel() > 8)
284 return 255;
285 }
286
287 // this will later be used to re-cast the start tile again.
288 Position verticalOffset (0, 0, 0);
289
290 // if we are on a stairs try to go up a level
291 if (direction < DIR_UP && startTile->getTerrainLevel() <= -16 && !aboveDestination->hasNoFloor(destinationTile) && !triedStairs)
292 {
293 numberOfPartsGoingUp++;
294
295 if (numberOfPartsGoingUp > size)
296 {
297 verticalOffset.z++;
298 endPosition->z++;
299 destinationTile = _save->getTile(*endPosition + offset);
300 belowDestination = _save->getTile(*endPosition + Position(x,y,-1));
301 triedStairs = true;
302 }
303 }
304 else if (!fellDown && _movementType != MT_FLY && belowDestination && canFallDown(destinationTile) && belowDestination->getTerrainLevel() <= -12)
305 {
306 numberOfPartsGoingDown++;
307
308 if (numberOfPartsGoingDown == (size + 1)*(size + 1))
309 {
310 endPosition->z--;
311 destinationTile = _save->getTile(*endPosition + offset);
312 belowDestination = _save->getTile(*endPosition + Position(x,y,-1));
313 fellDown = true;
314 }
315 }
316 else if (_movementType == MT_FLY && belowDestination && belowDestination->getUnit() && belowDestination->getUnit() != unit)
317 {
318 // 2 or more voxels poking into this tile = no go
319 if (belowDestination->getUnit()->getHeight() + belowDestination->getUnit()->getFloatHeight() - belowDestination->getTerrainLevel() > 26)
320 {
321 return 255;
322 }
323 }
324
325 // this means the destination is probably outside the map
326 if (!destinationTile)
327 return 255;
328
329 if (direction < DIR_UP && endPosition->z == startTile->getPosition().z)
330 {
331 // check if we can go this way
332 if (isBlocked(startTile, destinationTile, direction, target))
333 return 255;
334 if (startTile->getTerrainLevel() - destinationTile->getTerrainLevel() > 8)
335 return 255;
336 }
337 else if (direction >= DIR_UP)
338 {
339 // check if we can go up or down through gravlift or fly
340 if (validateUpDown(unit, startPosition + offset, direction))
341 {
342 cost = 8; // vertical movement by flying suit or grav lift
343 }
344 else
345 {
346 return 255;
347 }
348 }
349
350 // check if we have floor, else fall down
351 if (_movementType != MT_FLY && !fellDown && canFallDown(startTile))
352 {
353 numberOfPartsFalling++;
354
355 if (numberOfPartsFalling == (size+1)*(size+1))
356 {
357 *endPosition = startPosition + Position(0,0,-1);
358 destinationTile = _save->getTile(*endPosition + offset);
359 belowDestination = _save->getTile(*endPosition + Position(x,y,-1));
360 fellDown = true;
361 direction = DIR_DOWN;
362 }
363 }
364 startTile = _save->getTile(startTile->getPosition() + verticalOffset);
365
366
367 if (direction < DIR_UP && numberOfPartsGoingUp != 0)
368 {
369 // check if we can go this way
370 if (isBlocked(startTile, destinationTile, direction, target))
371 return 255;
372 if (startTile->getTerrainLevel() - destinationTile->getTerrainLevel() > 8)
373 return 255;
374 }
375
376 int wallcost = 0; // walking through rubble walls, but don't charge for walking diagonally through doors (which is impossible),
377 // they're a special case unto themselves, if we can walk past them diagonally, it means we can go around,
378 // as there is no wall blocking us.
379 if (direction == 0 || direction == 7 || direction == 1)
380 wallcost += startTile->getTUCost(MapData::O_NORTHWALL, _movementType);
381 if (direction == 2 || direction == 1 || direction == 3)
382 wallcost += destinationTile->getTUCost(MapData::O_WESTWALL, _movementType);
383 if (direction == 4 || direction == 3 || direction == 5)
384 wallcost += destinationTile->getTUCost(MapData::O_NORTHWALL, _movementType);
385 if (direction == 6 || direction == 5 || direction == 7)
386 wallcost += startTile->getTUCost(MapData::O_WESTWALL, _movementType);
387
388 // don't let tanks phase through doors.
389 if (x && y)
390 {
391 if ((destinationTile->getMapData(MapData::O_NORTHWALL) && destinationTile->getMapData(MapData::O_NORTHWALL)->isDoor()) ||
392 (destinationTile->getMapData(MapData::O_WESTWALL) && destinationTile->getMapData(MapData::O_WESTWALL)->isDoor()))
393 {
394 return 255;
395 }
396 }
397 // check if the destination tile can be walked over
398 if (isBlocked(destinationTile, MapData::O_FLOOR, target) || isBlocked(destinationTile, MapData::O_OBJECT, target))
399 {
400 return 255;
401 }
402
403 // if we don't want to fall down and there is no floor, we can't know the TUs so it's default to 4
404 if (direction < DIR_UP && !fellDown && destinationTile->hasNoFloor(0))
405 {
406 cost = 4;
407 }
408 // calculate the cost by adding floor walk cost and object walk cost
409 if (direction < DIR_UP)
410 {
411 cost += destinationTile->getTUCost(MapData::O_FLOOR, _movementType);
412 if (!fellDown && !triedStairs && destinationTile->getMapData(MapData::O_OBJECT))
413 {
414 cost += destinationTile->getTUCost(MapData::O_OBJECT, _movementType);
415 }
416 // climbing up a level costs one extra
417 if (verticalOffset.z > 0)
418 {
419 cost++;
420 }
421 }
422
423 // diagonal walking (uneven directions) costs 50% more tu's
424 if (direction < DIR_UP && direction & 1)
425 {
426 wallcost /= 2;
427 cost = (int)((double)cost * 1.5);
428 }
429 cost += wallcost;
430 if (_unit->getFaction() == FACTION_HOSTILE &&
431 destinationTile->getFire() > 0)
432 cost += 32; // try to find a better path, but don't exclude this path entirely.
433
434 // Strafing costs +1 for forwards-ish or sidewards, propose +2 for backwards-ish directions
435 // Maybe if flying then it makes no difference?
436 if (Options::strafe && _strafeMove) {
437 if (size) {
438 // 4-tile units not supported.
439 // Turn off strafe move and continue
440 _strafeMove = false;
441 }
442 else
443 {
444 if (std::min(abs(8 + direction - _unit->getDirection()), std::min( abs(_unit->getDirection() - direction), abs(8 + _unit->getDirection() - direction))) > 2) {
445 // Strafing backwards-ish currently unsupported, turn it off and continue.
446 _strafeMove = false;
447 }
448 else
449 {
450 if (_unit->getDirection() != direction) {
451 cost += 1;
452 }
453 }
454 }
455 }
456 totalCost += cost;
457 cost = 0;
458 }
459
460 // for bigger sized units, check the path between part 1,1 and part 0,0 at end position
461 if (size)
462 {
463 totalCost /= (size+1)*(size+1);
464 Tile *startTile = _save->getTile(*endPosition + Position(1,1,0));
465 Tile *destinationTile = _save->getTile(*endPosition);
466 int tmpDirection = 7;
467 if (isBlocked(startTile, destinationTile, tmpDirection, target))
468 return 255;
469 if (!fellDown && abs(startTile->getTerrainLevel() - destinationTile->getTerrainLevel()) > 10)
470 return 255;
471 // also check if we change level, that there are two parts changing level,
472 // so a big sized unit can not go up a small sized stairs
473 if (numberOfPartsChangingHeight == 1)
474 return 255;
475 }
476
477 if (missile)
478 return 0;
479 else
480 return totalCost;
481 }
482
483 /**
484 * Converts direction to a vector. Direction starts north = 0 and goes clockwise.
485 * @param direction Source direction.
486 * @param vector Pointer to a position (which acts as a vector).
487 */
directionToVector(const int direction,Position * vector)488 void Pathfinding::directionToVector(const int direction, Position *vector)
489 {
490 int x[10] = {0, 1, 1, 1, 0, -1, -1, -1,0,0};
491 int y[10] = {-1, -1, 0, 1, 1, 1, 0, -1,0,0};
492 int z[10] = {0, 0, 0, 0, 0, 0, 0, 0, 1, -1};
493 vector->x = x[direction];
494 vector->y = y[direction];
495 vector->z = z[direction];
496 }
497
498 /**
499 * Converts direction to a vector. Direction starts north = 0 and goes clockwise.
500 * @param vector Pointer to a position (which acts as a vector).
501 * @param dir Resulting direction.
502 */
vectorToDirection(const Position & vector,int & dir)503 void Pathfinding::vectorToDirection(const Position &vector, int &dir)
504 {
505 dir = -1;
506 int x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
507 int y[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
508 for (int i = 0; i < 8; ++i)
509 {
510 if (x[i] == vector.x && y[i] == vector.y)
511 {
512 dir = i;
513 return;
514 }
515 }
516 }
517
518 /**
519 * Checks whether a path is ready and gives the first direction.
520 * @return Direction where the unit needs to go next, -1 if it's the end of the path.
521 */
getStartDirection()522 int Pathfinding::getStartDirection()
523 {
524 if (_path.empty()) return -1;
525 return _path.back();
526 }
527
528 /**
529 * Dequeues the next path direction. Ie returns the direction and removes it from queue.
530 * @return Direction where the unit needs to go next, -1 if it's the end of the path.
531 */
dequeuePath()532 int Pathfinding::dequeuePath()
533 {
534 if (_path.empty()) return -1;
535 int last_element = _path.back();
536 _path.pop_back();
537 return last_element;
538 }
539
540 /**
541 * Aborts the current path. Clears the path vector.
542 */
abortPath()543 void Pathfinding::abortPath()
544 {
545 _totalTUCost = 0;
546 _path.clear();
547 }
548
549
550 /**
551 * Determines whether a certain part of a tile blocks movement.
552 * @param tile Specified tile, can be a null pointer.
553 * @param part Part of the tile.
554 * @param missileTarget Target for a missile.
555 * @return True if the movement is blocked.
556 */
isBlocked(Tile * tile,const int part,BattleUnit * missileTarget,int bigWallExclusion)557 bool Pathfinding::isBlocked(Tile *tile, const int part, BattleUnit *missileTarget, int bigWallExclusion)
558 {
559 if (tile == 0) return true; // probably outside the map here
560
561 if (part == O_BIGWALL)
562 {
563 if (tile->getMapData(MapData::O_OBJECT) &&
564 tile->getMapData(MapData::O_OBJECT)->getBigWall() != 0 &&
565 tile->getMapData(MapData::O_OBJECT)->getBigWall() <= BIGWALLNWSE &&
566 tile->getMapData(MapData::O_OBJECT)->getBigWall() != bigWallExclusion)
567 return true; // blocking part
568 else
569 return false;
570 }
571 if (part == MapData::O_WESTWALL)
572 {
573 if (tile->getMapData(MapData::O_OBJECT) &&
574 tile->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLWEST)
575 return true; // blocking part
576 Tile *tileWest = _save->getTile(tile->getPosition() + Position(-1, 0, 0));
577 if (!tileWest) return true; // do not look outside of map
578 if (tileWest->getMapData(MapData::O_OBJECT) &&
579 (tileWest->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLEAST ||
580 tileWest->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLEASTANDSOUTH))
581 return true; // blocking part
582 }
583 if (part == MapData::O_NORTHWALL)
584 {
585 if (tile->getMapData(MapData::O_OBJECT) &&
586 tile->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLNORTH)
587 return true; // blocking part
588 Tile *tileNorth = _save->getTile(tile->getPosition() + Position(0, -1, 0));
589 if (!tileNorth) return true; // do not look outside of map
590 if (tileNorth->getMapData(MapData::O_OBJECT) &&
591 (tileNorth->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLSOUTH ||
592 tileNorth->getMapData(MapData::O_OBJECT)->getBigWall() == BIGWALLEASTANDSOUTH))
593 return true; // blocking part
594 }
595 if (part == MapData::O_FLOOR)
596 {
597 BattleUnit *unit = tile->getUnit();
598 if (unit != 0)
599 {
600 if (unit == _unit || unit == missileTarget || unit->isOut()) return false;
601 if (_unit && _unit->getFaction() == FACTION_PLAYER && unit->getVisible()) return true; // player know all visible units
602 if (_unit && _unit->getFaction() == unit->getFaction()) return true;
603 if (_unit && _unit->getFaction() == FACTION_HOSTILE &&
604 std::find(_unit->getUnitsSpottedThisTurn().begin(), _unit->getUnitsSpottedThisTurn().end(), unit) != _unit->getUnitsSpottedThisTurn().end()) return true;
605 }
606 else if (tile->hasNoFloor(0) && _movementType != MT_FLY) // this whole section is devoted to making large units not take part in any kind of falling behaviour
607 {
608 Position pos = tile->getPosition();
609 while (pos.z >= 0)
610 {
611 Tile *t = _save->getTile(pos);
612 BattleUnit *unit = t->getUnit();
613
614 if (unit != 0 && unit != _unit)
615 {
616 // don't let large units fall on other units
617 if (_unit && _unit->getArmor()->getSize() > 1)
618 {
619 return true;
620 }
621 // don't let any units fall on large units
622 if (unit != _unit && unit != missileTarget && !unit->isOut() && unit->getArmor()->getSize() > 1)
623 {
624 return true;
625 }
626 }
627 // not gonna fall any further, so we can stop checking.
628 if (!t->hasNoFloor(0))
629 {
630 break;
631 }
632 pos.z--;
633 }
634 }
635 }
636 // missiles can't pathfind through closed doors.
637 if (missileTarget != 0 && tile->getMapData(part) &&
638 (tile->getMapData(part)->isDoor() ||
639 (tile->getMapData(part)->isUFODoor() &&
640 !tile->isUfoDoorOpen(part))))
641 {
642 return true;
643 }
644 if (tile->getTUCost(part, _movementType) == 255) return true; // blocking part
645 return false;
646 }
647
648 /**
649 * Determines whether going from one tile to another blocks movement.
650 * @param startTile The tile to start from.
651 * @param endTile The tile we want to reach.
652 * @param direction The direction we are facing.
653 * @param missileTarget Target for a missile.
654 * @return True if the movement is blocked.
655 */
isBlocked(Tile * startTile,Tile *,const int direction,BattleUnit * missileTarget)656 bool Pathfinding::isBlocked(Tile *startTile, Tile * /* endTile */, const int direction, BattleUnit *missileTarget)
657 {
658
659 // check if the difference in height between start and destination is not too high
660 // so we can not jump to the highest part of the stairs from the floor
661 // stairs terrainlevel goes typically -8 -16 (2 steps) or -4 -12 -20 (3 steps)
662 // this "maximum jump height" is therefore set to 8
663
664 const Position currentPosition = startTile->getPosition();
665 static const Position oneTileNorth = Position(0, -1, 0);
666 static const Position oneTileEast = Position(1, 0, 0);
667 static const Position oneTileSouth = Position(0, 1, 0);
668 static const Position oneTileWest = Position(-1, 0, 0);
669
670 switch(direction)
671 {
672 case 0: // north
673 if (isBlocked(startTile, MapData::O_NORTHWALL, missileTarget)) return true;
674 break;
675 case 1: // north-east
676 if (isBlocked(startTile,MapData::O_NORTHWALL, missileTarget)) return true;
677 if (isBlocked(_save->getTile(currentPosition + oneTileNorth + oneTileEast),MapData::O_WESTWALL, missileTarget)) return true;
678 if (isBlocked(_save->getTile(currentPosition + oneTileEast),MapData::O_WESTWALL, missileTarget)) return true;
679 if (isBlocked(_save->getTile(currentPosition + oneTileEast),MapData::O_NORTHWALL, missileTarget)) return true;
680 if (isBlocked(_save->getTile(currentPosition + oneTileEast), O_BIGWALL, missileTarget, BIGWALLNESW)) return true;
681 if (isBlocked(_save->getTile(currentPosition + oneTileNorth), O_BIGWALL, missileTarget, BIGWALLNESW)) return true;
682 break;
683 case 2: // east
684 if (isBlocked(_save->getTile(currentPosition + oneTileEast), MapData::O_WESTWALL, missileTarget)) return true;
685 break;
686 case 3: // south-east
687 if (isBlocked(_save->getTile(currentPosition + oneTileEast), MapData::O_WESTWALL, missileTarget)) return true;
688 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), MapData::O_NORTHWALL, missileTarget)) return true;
689 if (isBlocked(_save->getTile(currentPosition + oneTileSouth + oneTileEast), MapData::O_NORTHWALL, missileTarget)) return true;
690 if (isBlocked(_save->getTile(currentPosition + oneTileSouth + oneTileEast), MapData::O_WESTWALL, missileTarget)) return true;
691 if (isBlocked(_save->getTile(currentPosition + oneTileEast), O_BIGWALL, missileTarget, BIGWALLNWSE)) return true;
692 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), O_BIGWALL, missileTarget, BIGWALLNWSE)) return true;
693 break;
694 case 4: // south
695 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), MapData::O_NORTHWALL, missileTarget)) return true;
696 break;
697 case 5: // south-west
698 if (isBlocked(startTile, MapData::O_WESTWALL, missileTarget)) return true;
699 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), MapData::O_WESTWALL, missileTarget)) return true;
700 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), MapData::O_NORTHWALL, missileTarget)) return true;
701 if (isBlocked(_save->getTile(currentPosition + oneTileSouth), O_BIGWALL, missileTarget, BIGWALLNESW)) return true;
702 if (isBlocked(_save->getTile(currentPosition + oneTileWest), O_BIGWALL, missileTarget, BIGWALLNESW)) return true;
703 if (isBlocked(_save->getTile(currentPosition + oneTileSouth + oneTileWest), MapData::O_NORTHWALL, missileTarget)) return true;
704 break;
705 case 6: // west
706 if (isBlocked(startTile, MapData::O_WESTWALL, missileTarget)) return true;
707 break;
708 case 7: // north-west
709 if (isBlocked(startTile, MapData::O_WESTWALL, missileTarget)) return true;
710 if (isBlocked(startTile, MapData::O_NORTHWALL, missileTarget)) return true;
711 if (isBlocked(_save->getTile(currentPosition + oneTileWest), MapData::O_NORTHWALL, missileTarget)) return true;
712 if (isBlocked(_save->getTile(currentPosition + oneTileNorth), MapData::O_WESTWALL, missileTarget)) return true;
713 if (isBlocked(_save->getTile(currentPosition + oneTileNorth), O_BIGWALL, missileTarget, BIGWALLNWSE)) return true;
714 if (isBlocked(_save->getTile(currentPosition + oneTileWest), O_BIGWALL, missileTarget, BIGWALLNWSE)) return true;
715 break;
716 }
717
718 return false;
719 }
720
721 /**
722 * Determines whether a unit can fall down from this tile.
723 * We can fall down here, if the tile does not exist, the tile has no floor
724 * the current position is higher than 0, if there is no unit standing below us.
725 * @param here The current tile.
726 * @return True if a unit can fall down.
727 */
canFallDown(Tile * here)728 bool Pathfinding::canFallDown(Tile *here)
729 {
730 if (here->getPosition().z == 0)
731 return false;
732 Tile* tileBelow = _save->getTile(here->getPosition() - Position (0,0,1));
733
734 return here->hasNoFloor(tileBelow);
735 }
736
737 /**
738 * Determines whether a unit can fall down from this tile.
739 * We can fall down here, if the tile does not exist, the tile has no floor
740 * the current position is higher than 0, if there is no unit standing below us.
741 * @param here The current tile.
742 * @param size The size of the unit.
743 * @return True if a unit can fall down.
744 */
canFallDown(Tile * here,int size)745 bool Pathfinding::canFallDown(Tile *here, int size)
746 {
747 for (int x = 0; x != size; ++x)
748 {
749 for (int y = 0; y != size; ++y)
750 {
751 Position checkPos = here->getPosition() + Position(x,y,0);
752 Tile *checkTile = _save->getTile(checkPos);
753 if (!canFallDown(checkTile))
754 return false;
755 }
756 }
757 return true;
758 }
759 /**
760 * Determines whether the unit is going up a stairs.
761 * @param startPosition The position to start from.
762 * @param endPosition The position we wanna reach.
763 * @return True if the unit is going up a stairs.
764 */
isOnStairs(const Position & startPosition,const Position & endPosition)765 bool Pathfinding::isOnStairs(const Position &startPosition, const Position &endPosition)
766 {
767 //condition 1 : endposition has to the south a terrainlevel -16 object (upper part of the stairs)
768 if (_save->getTile(endPosition + Position(0, 1, 0)) && _save->getTile(endPosition + Position(0, 1, 0))->getTerrainLevel() == -16)
769 {
770 // condition 2 : one position further to the south there has to be a terrainlevel -8 object (lower part of the stairs)
771 if (_save->getTile(endPosition + Position(0, 2, 0)) && _save->getTile(endPosition + Position(0, 2, 0))->getTerrainLevel() != -8)
772 {
773 return false;
774 }
775
776 // condition 3 : the start position has to be on either of the 3 tiles to the south of the endposition
777 if (startPosition == endPosition + Position(0, 1, 0) || startPosition == endPosition + Position(0, 2, 0) || startPosition == endPosition + Position(0, 3, 0))
778 {
779 return true;
780 }
781 }
782
783 // same for the east-west oriented stairs.
784 if (_save->getTile(endPosition + Position(1, 0, 0)) && _save->getTile(endPosition + Position(1, 0, 0))->getTerrainLevel() == -16)
785 {
786 if (_save->getTile(endPosition + Position(2, 0, 0)) && _save->getTile(endPosition + Position(2, 0, 0))->getTerrainLevel() != -8)
787 {
788 return false;
789 }
790 if (startPosition == endPosition + Position(1, 0, 0) || startPosition == endPosition + Position(2, 0, 0) || startPosition == endPosition + Position(3, 0, 0))
791 {
792 return true;
793 }
794 }
795 return false;
796 }
797
798 /**
799 * Checks, for the up/down button, if the movement is valid. Either there is a grav lift or the unit can fly and there are no obstructions.
800 * @param bu Pointer to unit.
801 * @param startPosition Unit starting position.
802 * @param direction Up or Down
803 * @return bool Whether it's valid.
804 */
validateUpDown(BattleUnit * bu,Position startPosition,const int direction)805 bool Pathfinding::validateUpDown(BattleUnit *bu, Position startPosition, const int direction)
806 {
807 Position endPosition;
808 directionToVector(direction, &endPosition);
809 endPosition += startPosition;
810 Tile *startTile = _save->getTile(startPosition);
811 Tile *belowStart = _save->getTile(startPosition + Position(0,0,-1));
812 Tile *destinationTile = _save->getTile(endPosition);
813 if (startTile->getMapData(MapData::O_FLOOR) && destinationTile && destinationTile->getMapData(MapData::O_FLOOR) &&
814 (startTile->getMapData(MapData::O_FLOOR)->isGravLift() && destinationTile->getMapData(MapData::O_FLOOR)->isGravLift()))
815 {
816 return true;
817 }
818 else
819 {
820 if (bu->getArmor()->getMovementType() == MT_FLY)
821 {
822 if ((direction == DIR_UP && destinationTile && !destinationTile->getMapData(MapData::O_FLOOR)) // flying up only possible when there is no roof
823 || (direction == DIR_DOWN && destinationTile && startTile->hasNoFloor(belowStart)) // falling down only possible when there is no floor
824 )
825 {
826 return true;
827 }
828 }
829 }
830
831 return false;
832 }
833
834 /**
835 * Marks tiles for the path preview.
836 * @param bRemove Remove preview?
837 * @return True, if a path is previewed.
838 */
previewPath(bool bRemove)839 bool Pathfinding::previewPath(bool bRemove)
840 {
841 if (_path.empty())
842 return false;
843
844 if (!bRemove && _pathPreviewed)
845 return false;
846
847 _pathPreviewed = !bRemove;
848
849 Position pos = _unit->getPosition();
850 Position destination;
851 int tus = _unit->getTimeUnits();
852 if (_unit->isKneeled())
853 {
854 tus -= 8;
855 }
856 int energy = _unit->getEnergy();
857 int size = _unit->getArmor()->getSize() - 1;
858 int total = _unit->isKneeled() ? 8 : 0;
859 bool switchBack = false;
860 if (_save->getBattleGame()->getReservedAction() == BA_NONE)
861 {
862 switchBack = true;
863 _save->getBattleGame()->setTUReserved(BA_AUTOSHOT, false);
864 }
865 _modifierUsed = (SDL_GetModState() & KMOD_CTRL) != 0;
866 bool running = Options::strafe && _modifierUsed && _unit->getArmor()->getSize() == 1 && _path.size() > 1;
867 for (std::vector<int>::reverse_iterator i = _path.rbegin(); i != _path.rend(); ++i)
868 {
869 int dir = *i;
870 int tu = getTUCost(pos, dir, &destination, _unit, 0, false); // gets tu cost, but also gets the destination position.
871 if (running)
872 {
873 tu *= 0.75;
874 }
875 if (dir < Pathfinding::DIR_UP)
876 {
877 energy -= tu / 2;
878 }
879
880 tus -= tu;
881 total += tu;
882 bool reserve = _save->getBattleGame()->checkReservedTU(_unit, total, true);
883 pos = destination;
884 for (int x = size; x >= 0; x--)
885 {
886 for (int y = size; y >= 0; y--)
887 {
888 Tile *tile = _save->getTile(pos + Position(x,y,0));
889 Tile *tileAbove = _save->getTile(pos + Position(x,y,1));
890 if (!bRemove)
891 {
892 if (i == _path.rend() - 1)
893 {
894 tile->setPreview(10);
895 }
896 else
897 {
898 int nextDir = *(i + 1);
899 tile->setPreview(nextDir);
900 }
901 tile->setTUMarker(tus);
902 if (tileAbove && tileAbove->getPreview() == 0 && tu == 0 && _movementType != MT_FLY) //unit fell down, retroactively make the tile above's direction marker to DOWN
903 {
904 tileAbove->setPreview(DIR_DOWN);
905 }
906 }
907 else
908 {
909 tile->setPreview(-1);
910 tile->setTUMarker(0);
911 }
912 tile->setMarkerColor(bRemove?0:((tus>=0 && energy>=0)?(reserve?4:10):3));
913 }
914 }
915 }
916 if (switchBack)
917 {
918 _save->getBattleGame()->setTUReserved(BA_NONE, false);
919 }
920 return true;
921 }
922
923 /**
924 * Unmarks the tiles used for the path preview.
925 * @return True, if the previewed path was removed.
926 */
removePreview()927 bool Pathfinding::removePreview()
928 {
929 if (!_pathPreviewed)
930 return false;
931 previewPath(true);
932 return true;
933 }
934
935 /**
936 * Calculates the shortest path using Brensenham path algorithm.
937 * @note This only works in the X/Y plane.
938 * @param origin The position to start from.
939 * @param target The position we want to reach.
940 * @param targetUnit Target of the path.
941 * @param sneak Is the unit sneaking?
942 * @param maxTUCost Maximum time units the path can cost.
943 * @return True if a path exists, false otherwise.
944 */
bresenhamPath(const Position & origin,const Position & target,BattleUnit * targetUnit,bool sneak,int maxTUCost)945 bool Pathfinding::bresenhamPath(const Position& origin, const Position& target, BattleUnit *targetUnit, bool sneak, int maxTUCost)
946 {
947 int xd[8] = {0, 1, 1, 1, 0, -1, -1, -1};
948 int yd[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
949
950 int x, x0, x1, delta_x, step_x;
951 int y, y0, y1, delta_y, step_y;
952 int z, z0, z1, delta_z, step_z;
953 int swap_xy, swap_xz;
954 int drift_xy, drift_xz;
955 int cx, cy, cz;
956 Position lastPoint(origin);
957 int dir;
958 int lastTUCost = -1;
959 Position nextPoint;
960 _totalTUCost = 0;
961
962 //start and end points
963 x0 = origin.x; x1 = target.x;
964 y0 = origin.y; y1 = target.y;
965 z0 = origin.z; z1 = target.z;
966
967 //'steep' xy Line, make longest delta x plane
968 swap_xy = abs(y1 - y0) > abs(x1 - x0);
969 if (swap_xy)
970 {
971 std::swap(x0, y0);
972 std::swap(x1, y1);
973 }
974
975 //do same for xz
976 swap_xz = abs(z1 - z0) > abs(x1 - x0);
977 if (swap_xz)
978 {
979 std::swap(x0, z0);
980 std::swap(x1, z1);
981 }
982
983 //delta is Length in each plane
984 delta_x = abs(x1 - x0);
985 delta_y = abs(y1 - y0);
986 delta_z = abs(z1 - z0);
987
988 //drift controls when to step in 'shallow' planes
989 //starting value keeps Line centred
990 drift_xy = (delta_x / 2);
991 drift_xz = (delta_x / 2);
992
993 //direction of line
994 step_x = 1; if (x0 > x1) { step_x = -1; }
995 step_y = 1; if (y0 > y1) { step_y = -1; }
996 step_z = 1; if (z0 > z1) { step_z = -1; }
997
998 //starting point
999 y = y0;
1000 z = z0;
1001
1002 //step through longest delta (which we have swapped to x)
1003 for (x = x0; x != (x1+step_x); x += step_x)
1004 {
1005 //copy position
1006 cx = x; cy = y; cz = z;
1007
1008 //unswap (in reverse)
1009 if (swap_xz) std::swap(cx, cz);
1010 if (swap_xy) std::swap(cx, cy);
1011
1012 if (x != x0 || y != y0 || z != z0)
1013 {
1014 Position realNextPoint = Position(cx, cy, cz);
1015 nextPoint = realNextPoint;
1016 // get direction
1017 for (dir = 0; dir < 8; ++dir)
1018 {
1019 if (xd[dir] == cx-lastPoint.x && yd[dir] == cy-lastPoint.y) break;
1020 }
1021 int tuCost = getTUCost(lastPoint, dir, &nextPoint, _unit, targetUnit, (targetUnit && maxTUCost == 10000));
1022
1023 if (sneak && _save->getTile(nextPoint)->getVisible()) return false;
1024
1025 // delete the following
1026 bool isDiagonal = (dir&1);
1027 int lastTUCostDiagonal = lastTUCost + lastTUCost / 2;
1028 int tuCostDiagonal = tuCost + tuCost / 2;
1029 if (nextPoint == realNextPoint && tuCost < 255 && (tuCost == lastTUCost || (isDiagonal && tuCost == lastTUCostDiagonal) || (!isDiagonal && tuCostDiagonal == lastTUCost) || lastTUCost == -1)
1030 && !isBlocked(_save->getTile(lastPoint), _save->getTile(nextPoint), dir, targetUnit))
1031 {
1032 _path.push_back(dir);
1033 }
1034 else
1035 {
1036 return false;
1037 }
1038 if (targetUnit == 0 && tuCost != 255)
1039 {
1040 lastTUCost = tuCost;
1041 _totalTUCost += tuCost;
1042 }
1043 lastPoint = Position(cx, cy, cz);
1044 }
1045 //update progress in other planes
1046 drift_xy = drift_xy - delta_y;
1047 drift_xz = drift_xz - delta_z;
1048
1049 //step in y plane
1050 if (drift_xy < 0)
1051 {
1052 y = y + step_y;
1053 drift_xy = drift_xy + delta_x;
1054 }
1055
1056 //same in z
1057 if (drift_xz < 0)
1058 {
1059 z = z + step_z;
1060 drift_xz = drift_xz + delta_x;
1061 }
1062 }
1063
1064 return true;
1065 }
1066
1067 /**
1068 * Locates all tiles reachable to @a *unit with a TU cost no more than @a tuMax.
1069 * Uses Dijkstra's algorithm.
1070 * @param unit Pointer to the unit.
1071 * @param tuMax The maximum cost of the path to each tile.
1072 * @return An array of reachable tiles, sorted in ascending order of cost. The first tile is the start location.
1073 */
findReachable(BattleUnit * unit,int tuMax)1074 std::vector<int> Pathfinding::findReachable(BattleUnit *unit, int tuMax)
1075 {
1076 const Position &start = unit->getPosition();
1077 int energyMax = unit->getEnergy();
1078 for (std::vector<PathfindingNode>::iterator it = _nodes.begin(); it != _nodes.end(); ++it)
1079 {
1080 it->reset();
1081 }
1082 PathfindingNode *startNode = getNode(start);
1083 startNode->connect(0, 0, 0);
1084 PathfindingOpenSet unvisited;
1085 unvisited.push(startNode);
1086 std::vector<PathfindingNode*> reachable;
1087 while (!unvisited.empty())
1088 {
1089 PathfindingNode *currentNode = unvisited.pop();
1090 Position const ¤tPos = currentNode->getPosition();
1091
1092 // Try all reachable neighbours.
1093 for (int direction = 0; direction < 10; direction++)
1094 {
1095 Position nextPos;
1096 int tuCost = getTUCost(currentPos, direction, &nextPos, unit, 0, false);
1097 if (tuCost == 255) // Skip unreachable / blocked
1098 continue;
1099 if (currentNode->getTUCost(false) + tuCost > tuMax ||
1100 (currentNode->getTUCost(false) + tuCost) / 2 > energyMax) // Run out of TUs/Energy
1101 continue;
1102 PathfindingNode *nextNode = getNode(nextPos);
1103 if (nextNode->isChecked()) // Our algorithm means this node is already at minimum cost.
1104 continue;
1105 int totalTuCost = currentNode->getTUCost(false) + tuCost;
1106 // If this node is unvisited or visited from a better path.
1107 if (!nextNode->inOpenSet() || nextNode->getTUCost(false) > totalTuCost)
1108 {
1109 nextNode->connect(totalTuCost, currentNode, direction);
1110 unvisited.push(nextNode);
1111 }
1112 }
1113 currentNode->setChecked();
1114 reachable.push_back(currentNode);
1115 }
1116 std::sort(reachable.begin(), reachable.end(), MinNodeCosts());
1117 std::vector<int> tiles;
1118 tiles.reserve(reachable.size());
1119 for (std::vector<PathfindingNode*>::const_iterator it = reachable.begin(); it != reachable.end(); ++it)
1120 {
1121 tiles.push_back(_save->getTileIndex((*it)->getPosition()));
1122 }
1123 return tiles;
1124 }
1125
1126 /**
1127 * Gets the strafe move setting.
1128 * @return Strafe move.
1129 */
getStrafeMove() const1130 bool Pathfinding::getStrafeMove() const
1131 {
1132 return _strafeMove;
1133 }
1134
1135 /**
1136 * Gets the path preview setting.
1137 * @return True, if paths are previewed.
1138 */
isPathPreviewed() const1139 bool Pathfinding::isPathPreviewed() const
1140 {
1141 return _pathPreviewed;
1142 }
1143
1144 /**
1145 * Sets _unit in order to abuse low-level pathfinding functions from outside the class.
1146 * @param unit Unit taking the path.
1147 */
setUnit(BattleUnit * unit)1148 void Pathfinding::setUnit(BattleUnit* unit)
1149 {
1150 _unit = unit;
1151 if (unit != 0)
1152 {
1153 _movementType = unit->getArmor()->getMovementType();
1154 }
1155 else
1156 {
1157 _movementType = MT_WALK;
1158 }
1159 }
1160
1161 /**
1162 * Checks whether a modifier key was used to enable strafing or running.
1163 * @return True, if a modifier was used.
1164 */
isModifierUsed() const1165 bool Pathfinding::isModifierUsed() const
1166 {
1167 return _modifierUsed;
1168 }
1169
1170 /**
1171 * Gets a reference to the current path.
1172 * @return the actual path.
1173 */
getPath()1174 const std::vector<int> &Pathfinding::getPath()
1175 {
1176 return _path;
1177 }
1178
1179 /**
1180 * Makes a copy of the current path.
1181 * @return a copy of the path.
1182 */
copyPath() const1183 std::vector<int> Pathfinding::copyPath() const
1184 {
1185 return _path;
1186 }
1187 }
1188