1 /*************************************************************************** 2 * Free Heroes of Might and Magic II: https://github.com/ihhub/fheroes2 * 3 * Copyright (C) 2020 * 4 * * 5 * This program is free software; you can redistribute it and/or modify * 6 * it under the terms of the GNU General Public License as published by * 7 * the Free Software Foundation; either version 2 of the License, or * 8 * (at your option) any later version. * 9 * * 10 * This program is distributed in the hope that it will be useful, * 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 13 * GNU General Public License for more details. * 14 * * 15 * You should have received a copy of the GNU General Public License * 16 * along with this program; if not, write to the * 17 * Free Software Foundation, Inc., * 18 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * 19 ***************************************************************************/ 20 21 #include "battle_pathfinding.h" 22 #include "battle_arena.h" 23 #include "battle_bridge.h" 24 #include "battle_troop.h" 25 #include "castle.h" 26 #include "logging.h" 27 #include <algorithm> 28 29 namespace Battle 30 { resetNode()31 void ArenaNode::resetNode() 32 { 33 _from = -1; 34 _cost = MAX_MOVE_COST; 35 _objectID = 0; 36 _isOpen = true; 37 _isLeftDirection = false; 38 } 39 ArenaPathfinder()40 ArenaPathfinder::ArenaPathfinder() 41 { 42 _cache.resize( ARENASIZE ); 43 } 44 reset()45 void ArenaPathfinder::reset() 46 { 47 _start.Set( -1, false, false ); 48 for ( size_t i = 0; i < _cache.size(); ++i ) { 49 _cache[i].resetNode(); 50 } 51 } 52 hexIsPassable(int targetCell) const53 bool ArenaPathfinder::hexIsPassable( int targetCell ) const 54 { 55 const size_t index = static_cast<size_t>( targetCell ); 56 return index < _cache.size() && nodeIsPassable( _cache[index] ); 57 } 58 nodeIsPassable(const ArenaNode & node) const59 bool ArenaPathfinder::nodeIsPassable( const ArenaNode & node ) const 60 { 61 return node._cost == 0 || ( node._isOpen && node._from != -1 ); 62 } 63 getAllAvailableMoves(uint32_t moveRange) const64 Indexes ArenaPathfinder::getAllAvailableMoves( uint32_t moveRange ) const 65 { 66 Indexes result; 67 result.reserve( moveRange * 2u ); 68 69 for ( size_t index = 0; index < _cache.size(); ++index ) { 70 const ArenaNode & node = _cache[index]; 71 if ( nodeIsPassable( node ) && node._cost <= moveRange ) { 72 result.push_back( static_cast<int>( index ) ); 73 } 74 } 75 return result; 76 } 77 buildPath(int targetCell) const78 Indexes ArenaPathfinder::buildPath( int targetCell ) const 79 { 80 Indexes path; 81 82 if ( static_cast<size_t>( targetCell ) >= _cache.size() ) 83 return path; 84 85 int currentNode = targetCell; 86 while ( _cache[currentNode]._cost != 0 && !_start.contains( currentNode ) ) { 87 const ArenaNode & node = _cache[currentNode]; 88 path.push_back( currentNode ); 89 currentNode = node._from; 90 } 91 std::reverse( path.begin(), path.end() ); 92 93 return path; 94 } 95 findTwoMovesOverlap(int targetCell,uint32_t movementRange) const96 Indexes ArenaPathfinder::findTwoMovesOverlap( int targetCell, uint32_t movementRange ) const 97 { 98 Indexes path; 99 if ( static_cast<size_t>( targetCell ) >= _cache.size() ) 100 return path; 101 102 const uint32_t pathCost = _cache[targetCell]._cost; 103 if ( pathCost >= movementRange * 2 ) 104 return path; 105 106 int currentNode = targetCell; 107 uint32_t nodeCost = pathCost; 108 109 while ( nodeCost != 0 && !_start.contains( currentNode ) ) { 110 const ArenaNode & node = _cache[currentNode]; 111 // Upper limit 112 if ( movementRange == 0 || node._cost <= movementRange ) { 113 path.push_back( currentNode ); 114 } 115 currentNode = node._from; 116 nodeCost = _cache[currentNode]._cost; 117 118 // Lower limit 119 if ( movementRange > 0 && !path.empty() && pathCost - nodeCost >= movementRange ) 120 break; 121 } 122 std::reverse( path.begin(), path.end() ); 123 124 return path; 125 } 126 calculate(const Unit & unit)127 void ArenaPathfinder::calculate( const Unit & unit ) 128 { 129 reset(); 130 131 const bool unitIsWide = unit.isWide(); 132 133 _start = unit.GetPosition(); 134 const Cell * unitHead = _start.GetHead(); 135 const Cell * unitTail = _start.GetTail(); 136 if ( !unitHead || ( unitIsWide && !unitTail ) ) { 137 DEBUG_LOG( DBG_BATTLE, DBG_WARN, "Pathfinder: Invalid unit is passed in! " << unit.GetName() ); 138 return; 139 } 140 141 const Bridge * bridge = Arena::GetBridge(); 142 const Castle * castle = Arena::GetCastle(); 143 144 const bool isPassableBridge = bridge == nullptr || bridge->isPassable( unit ); 145 const bool isMoatBuilt = castle && castle->isBuild( BUILD_MOAT ); 146 const uint32_t moatPenalty = unit.GetSpeed(); 147 148 // Initialize the starting cells 149 const int32_t pathStart = unitHead->GetIndex(); 150 _cache[pathStart]._cost = 0; 151 _cache[pathStart]._isOpen = false; 152 _cache[pathStart]._isLeftDirection = unitIsWide && unit.isReflect(); 153 154 if ( unitIsWide ) { 155 const int32_t tailIdx = unitTail->GetIndex(); 156 _cache[tailIdx]._from = pathStart; 157 _cache[tailIdx]._cost = 0; 158 _cache[tailIdx]._isOpen = true; 159 _cache[tailIdx]._isLeftDirection = !unit.isReflect(); 160 } 161 162 if ( unit.isFlying() ) { 163 const Board & board = *Arena::GetBoard(); 164 165 // Find all free spaces on the battle board - flyers can move to any of them 166 for ( Board::const_iterator it = board.begin(); it != board.end(); ++it ) { 167 const int32_t idx = it->GetIndex(); 168 ArenaNode & node = _cache[idx]; 169 170 // isPassable3 checks if there's space for unit tail (for wide units) 171 if ( it->isPassable3( unit, false ) && ( isPassableBridge || !Board::isBridgeIndex( it - board.begin(), unit ) ) ) { 172 node._isOpen = true; 173 node._from = pathStart; 174 node._cost = Battle::Board::GetDistance( pathStart, idx ); 175 } 176 else { 177 node._isOpen = false; 178 } 179 } 180 // Once board movement is determined we look for units save shortest flight path to them 181 for ( Board::const_iterator it = board.begin(); it != board.end(); ++it ) { 182 const Unit * boardUnit = it->GetUnit(); 183 if ( boardUnit && boardUnit->GetUID() != unit.GetUID() ) { 184 const int32_t unitIdx = it->GetIndex(); 185 ArenaNode & unitNode = _cache[unitIdx]; 186 187 const Indexes & around = Battle::Board::GetAroundIndexes( unitIdx ); 188 for ( const int32_t cell : around ) { 189 const uint32_t flyingDist = Battle::Board::GetDistance( pathStart, cell ); 190 if ( hexIsPassable( cell ) && ( flyingDist < unitNode._cost ) ) { 191 unitNode._isOpen = false; 192 unitNode._from = cell; 193 unitNode._cost = flyingDist; 194 } 195 } 196 } 197 } 198 } 199 else { 200 // Walkers - explore moves sequentially from both head and tail cells 201 std::vector<int32_t> nodesToExplore; 202 nodesToExplore.push_back( pathStart ); 203 if ( unitIsWide ) 204 nodesToExplore.push_back( unitTail->GetIndex() ); 205 206 for ( size_t lastProcessedNode = 0; lastProcessedNode < nodesToExplore.size(); ++lastProcessedNode ) { 207 const int32_t fromNode = nodesToExplore[lastProcessedNode]; 208 const ArenaNode & previousNode = _cache[fromNode]; 209 210 Indexes availableMoves; 211 if ( !unitIsWide ) 212 availableMoves = Board::GetAroundIndexes( fromNode ); 213 else if ( previousNode._from < 0 ) 214 availableMoves = Board::GetMoveWideIndexes( fromNode, unit.isReflect() ); 215 else 216 availableMoves = Board::GetMoveWideIndexes( fromNode, ( RIGHT_SIDE & Board::GetDirection( fromNode, previousNode._from ) ) != 0 ); 217 218 for ( const int32_t newNode : availableMoves ) { 219 const Cell * headCell = Board::GetCell( newNode ); 220 const bool isLeftDirection = unitIsWide && Board::IsLeftDirection( fromNode, newNode, previousNode._isLeftDirection ); 221 222 const int32_t newTailIndex = isLeftDirection ? newNode + 1 : newNode - 1; 223 const Cell * tailCell = ( unitIsWide && !_start.contains( newTailIndex ) ) ? Board::GetCell( newTailIndex ) : nullptr; 224 225 // Special case: headCell is *allowed* to have another unit in it, that's why we check isPassable1( false ) instead of isPassable4 226 if ( headCell->isPassable1( false ) && ( !tailCell || tailCell->isPassable1( true ) ) 227 && ( isPassableBridge || !Board::isBridgeIndex( newNode, unit ) ) ) { 228 const uint32_t cost = previousNode._cost; 229 ArenaNode & node = _cache[newNode]; 230 231 // Check if we're turning back. No movement at all. 232 uint32_t additionalCost = 1u; 233 if ( isLeftDirection != previousNode._isLeftDirection ) { 234 additionalCost = 0; 235 } 236 // Moat penalty consumes all remaining movement. Be careful when dealing with unsigned values. 237 else if ( isMoatBuilt && ( Board::isMoatIndex( newNode, unit ) || Board::isMoatIndex( newTailIndex, unit ) ) 238 && moatPenalty > previousNode._cost ) { 239 additionalCost = moatPenalty - cost; 240 } 241 242 // Now we check if headCell has a unit - this determines if hex is passable or just accessible (for attack) 243 if ( headCell->GetUnit() && cost < node._cost ) { 244 node._isOpen = false; 245 node._from = fromNode; 246 node._cost = cost; 247 node._isLeftDirection = isLeftDirection; 248 } 249 else if ( cost + additionalCost < node._cost ) { 250 node._isOpen = true; 251 node._from = fromNode; 252 node._cost = cost + additionalCost; 253 node._isLeftDirection = isLeftDirection; 254 nodesToExplore.push_back( newNode ); 255 } 256 } 257 } 258 } 259 } 260 } 261 } 262