2010-07-01 02:56:32 -07:00
/*
This file is part of Warzone 2100.
Copyright ( C ) 1999 - 2004 Eidos Interactive
2013-01-16 12:34:57 -08:00
Copyright ( C ) 2005 - 2013 Warzone 2100 Project
2010-07-01 02:56:32 -07:00
Warzone 2100 is free software ; you can redistribute it and / or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation ; either version 2 of the License , or
( at your option ) any later version .
Warzone 2100 is distributed in the hope that it will be useful ,
but WITHOUT ANY WARRANTY ; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE . See the
GNU General Public License for more details .
You should have received a copy of the GNU General Public License
along with Warzone 2100 ; if not , write to the Free Software
Foundation , Inc . , 51 Franklin St , Fifth Floor , Boston , MA 02110 - 1301 USA
*/
/** @file
* A * based path finding
* See http : //en.wikipedia.org/wiki/A*_search_algorithm for more information.
2010-07-04 01:19:52 -07:00
* How this works :
* * First time ( in a given tick ) that some droid wants to pathfind to a particular
* destination , the A * algorithm from source to destination is used . The desired
* destination , and the nearest reachable point to the destination is saved in a
* Context .
* * Second time ( in a given tick ) that some droid wants to pathfind to a particular
* destination , the appropriate Context is found , and the A * algorithm is used to
* find a path from the nearest reachable point to the destination ( which was saved
* earlier ) , to the source .
* * Subsequent times ( in a given tick ) that some droid wants to pathfind to a parti -
* cular destination , the path is looked up in appropriate Context . If the path is
* not already known , the A * weights are adjusted , and the previous A * pathfinding
* is continued until the new source is reached . If the new source is not reached ,
* the droid is on a different island than the previous droid , and pathfinding is
* restarted from the first step .
* Up to 30 pathfinding maps from A * are cached , in a LRU list . The PathNode heap con -
* tains the priority - heap - sorted nodes which are to be explored . The path back is
* stored in the PathExploredTile 2 D array of tiles .
2010-07-01 02:56:32 -07:00
*/
# ifndef WZ_TESTING
# include "lib/framework/frame.h"
# include "astar.h"
# include "map.h"
# endif
2010-07-04 01:19:52 -07:00
# include <list>
2010-07-01 02:56:32 -07:00
# include <vector>
# include <algorithm>
2010-08-15 11:23:56 -07:00
# include "lib/framework/crc.h"
# include "lib/netplay/netplay.h"
2010-07-01 02:56:32 -07:00
/// A coordinate.
struct PathCoord
{
PathCoord ( ) { }
PathCoord ( int16_t x_ , int16_t y_ ) : x ( x_ ) , y ( y_ ) { }
bool operator = = ( PathCoord const & z ) const { return x = = z . x & & y = = z . y ; }
bool operator ! = ( PathCoord const & z ) const { return ! ( * this = = z ) ; }
int16_t x , y ;
} ;
/** The structure to store a node of the route in node table
*
* @ ingroup pathfinding
*/
struct PathNode
{
bool operator < ( PathNode const & z ) const
{
// Sort decending est, fallback to ascending dist, fallback to sorting by position.
2010-07-11 23:42:36 -07:00
if ( est ! = z . est ) return est > z . est ;
if ( dist ! = z . dist ) return dist < z . dist ;
if ( p . x ! = z . p . x ) return p . x < z . p . x ;
return p . y < z . p . y ;
2010-07-01 02:56:32 -07:00
}
PathCoord p ; // Map coords.
unsigned dist , est ; // Distance so far and estimate to end.
} ;
2010-07-04 01:19:52 -07:00
struct PathExploredTile
2010-07-01 02:56:32 -07:00
{
2010-07-04 01:19:52 -07:00
PathExploredTile ( ) : iteration ( 0xFFFF ) { }
2010-07-01 02:56:32 -07:00
uint16_t iteration ;
int8_t dx , dy ; // Offset from previous point in the route.
unsigned dist ; // Shortest known distance to tile.
bool visited ;
} ;
2010-07-12 07:17:55 -07:00
struct PathBlockingType
{
uint32_t gameTime ;
PROPULSION_TYPE propulsion ;
int owner ;
FPATH_MOVETYPE moveType ;
} ;
/// Pathfinding blocking map
struct PathBlockingMap
{
bool operator = = ( PathBlockingType const & z ) const
{
return type . gameTime = = z . gameTime & &
fpathIsEquivalentBlocking ( type . propulsion , type . owner , type . moveType ,
z . propulsion , z . owner , z . moveType ) ;
}
PathBlockingType type ;
std : : vector < bool > map ;
2010-10-17 08:04:11 -07:00
std : : vector < bool > dangerMap ; // using threatBits
2010-07-12 07:17:55 -07:00
} ;
2011-12-12 11:17:49 -08:00
struct PathNonblockingArea
{
PathNonblockingArea ( ) { }
2011-12-24 11:07:31 -08:00
PathNonblockingArea ( StructureBounds const & st ) : x1 ( st . map . x ) , x2 ( st . map . x + st . size . x ) , y1 ( st . map . y ) , y2 ( st . map . y + st . size . y ) { }
2011-12-12 11:17:49 -08:00
bool operator = = ( PathNonblockingArea const & z ) const { return x1 = = z . x1 & & x2 = = z . x2 & & y1 = = z . y1 & & y2 = = z . y2 ; }
bool operator ! = ( PathNonblockingArea const & z ) const { return ! ( * this = = z ) ; }
bool isNonblocking ( int x , int y ) const
{
return x > = x1 & & x < x2 & & y > = y1 & & y < y2 ;
}
int16_t x1 , x2 , y1 , y2 ;
} ;
2010-07-04 01:19:52 -07:00
// Data structures used for pathfinding, can contain cached results.
struct PathfindContext
{
2010-07-13 12:04:32 -07:00
PathfindContext ( ) : myGameTime ( 0 ) , iteration ( 0 ) , blockingMap ( NULL ) { }
2010-07-12 07:17:55 -07:00
bool isBlocked ( int x , int y ) const
{
2012-01-11 12:12:19 -08:00
if ( dstIgnore . isNonblocking ( x , y ) )
2011-12-12 11:17:49 -08:00
{
return false ; // The path is actually blocked here by a structure, but ignore it since it's where we want to go (or where we came from).
}
2010-07-12 07:17:55 -07:00
// Not sure whether the out-of-bounds check is needed, can only happen if pathfinding is started on a blocking tile (or off the map).
2010-10-26 06:26:07 -07:00
return x < 0 | | y < 0 | | x > = mapWidth | | y > = mapHeight | | blockingMap - > map [ x + y * mapWidth ] ;
2010-07-12 07:17:55 -07:00
}
2010-10-17 08:04:11 -07:00
bool isDangerous ( int x , int y ) const
{
return ! blockingMap - > dangerMap . empty ( ) & & blockingMap - > dangerMap [ x + y * mapWidth ] ;
}
2012-01-11 12:12:19 -08:00
bool matches ( PathBlockingMap const * blockingMap_ , PathCoord tileS_ , PathNonblockingArea dstIgnore_ ) const
2010-07-12 07:17:55 -07:00
{
2011-12-12 11:17:49 -08:00
// Must check myGameTime == blockingMap_->type.gameTime, otherwise blockingMap could be a deleted pointer which coincidentally compares equal to the valid pointer blockingMap_.
2012-01-11 12:12:19 -08:00
return myGameTime = = blockingMap_ - > type . gameTime & & blockingMap = = blockingMap_ & & tileS = = tileS_ & & dstIgnore = = dstIgnore_ ;
2010-07-12 07:17:55 -07:00
}
2012-01-11 12:12:19 -08:00
void assign ( PathBlockingMap const * blockingMap_ , PathCoord tileS_ , PathNonblockingArea dstIgnore_ )
2010-07-04 01:19:52 -07:00
{
2010-07-12 07:17:55 -07:00
blockingMap = blockingMap_ ;
tileS = tileS_ ;
2011-12-12 11:17:49 -08:00
dstIgnore = dstIgnore_ ;
2010-07-12 07:17:55 -07:00
myGameTime = blockingMap - > type . gameTime ;
2010-07-04 01:19:52 -07:00
nodes . clear ( ) ;
2010-07-01 02:56:32 -07:00
2010-07-04 01:19:52 -07:00
// Make the iteration not match any value of iteration in map.
if ( + + iteration = = 0xFFFF )
{
map . clear ( ) ; // There are no values of iteration guaranteed not to exist in map, so clear the map.
iteration = 0 ;
}
map . resize ( mapWidth * mapHeight ) ; // Allocate space for map, if needed.
}
PathCoord tileS ; // Start tile for pathfinding. (May be either source or target tile.)
uint32_t myGameTime ;
PathCoord nearestCoord ; // Nearest reachable tile to destination.
/** Counter to implement lazy deletion from map.
*
* @ see fpathTableReset
*/
uint16_t iteration ;
std : : vector < PathNode > nodes ; ///< Edge of explored region of the map.
std : : vector < PathExploredTile > map ; ///< Map, with paths leading back to tileS.
2010-07-12 07:17:55 -07:00
PathBlockingMap const * blockingMap ; ///< Map of blocking tiles for the type of object which needs a path.
2011-12-12 11:17:49 -08:00
PathNonblockingArea dstIgnore ; ///< Area of structure at destination which should be considered nonblocking.
2010-07-04 01:19:52 -07:00
} ;
/// Last recently used list of contexts.
static std : : list < PathfindContext > fpathContexts ;
2010-07-01 02:56:32 -07:00
2010-07-12 07:17:55 -07:00
/// Lists of blocking maps from current tick.
static std : : list < PathBlockingMap > fpathBlockingMaps ;
/// Lists of blocking maps from previous tick, will be cleared next tick (since it will be no longer needed after that).
static std : : list < PathBlockingMap > fpathPrevBlockingMaps ;
2010-08-15 11:23:56 -07:00
/// Game time for all blocking maps in fpathBlockingMaps.
static uint32_t fpathCurrentGameTime ;
2010-07-12 07:17:55 -07:00
2010-07-01 02:56:32 -07:00
// Convert a direction into an offset
// dir 0 => x = 0, y = -1
static const Vector2i aDirOffset [ ] =
{
2010-12-21 12:51:29 -08:00
Vector2i ( 0 , 1 ) ,
Vector2i ( - 1 , 1 ) ,
Vector2i ( - 1 , 0 ) ,
Vector2i ( - 1 , - 1 ) ,
Vector2i ( 0 , - 1 ) ,
Vector2i ( 1 , - 1 ) ,
Vector2i ( 1 , 0 ) ,
Vector2i ( 1 , 1 ) ,
2010-07-01 02:56:32 -07:00
} ;
void fpathHardTableReset ( )
{
2010-07-04 01:19:52 -07:00
fpathContexts . clear ( ) ;
2010-07-12 07:17:55 -07:00
fpathBlockingMaps . clear ( ) ;
fpathPrevBlockingMaps . clear ( ) ;
2010-07-01 02:56:32 -07:00
}
/** Get the nearest entry in the open list
*/
2010-07-04 01:19:52 -07:00
/// Takes the current best node, and removes from the node heap.
2010-07-01 02:56:32 -07:00
static inline PathNode fpathTakeNode ( std : : vector < PathNode > & nodes )
{
// find the node with the lowest distance
// if equal totals, give preference to node closer to target
PathNode ret = nodes . front ( ) ;
// remove the node from the list
2010-07-04 01:19:52 -07:00
std : : pop_heap ( nodes . begin ( ) , nodes . end ( ) ) ; // Move the best node from the front of nodes to the back of nodes, preserving the heap properties, setting the front to the next best node.
2010-07-01 02:56:32 -07:00
nodes . pop_back ( ) ; // Pop the best node (which we will be returning).
return ret ;
}
/** Estimate the distance to the target point
*/
static inline unsigned WZ_DECL_CONST fpathEstimate ( PathCoord s , PathCoord f )
{
2012-01-29 12:58:38 -08:00
// Cost of moving horizontal/vertical = 70*2, cost of moving diagonal = 99*2, 99/70 = 1.41428571... ≈ √2 = 1.41421356...
2010-07-01 02:56:32 -07:00
unsigned xDelta = abs ( s . x - f . x ) , yDelta = abs ( s . y - f . y ) ;
2012-01-29 12:58:38 -08:00
return std : : min ( xDelta , yDelta ) * ( 198 - 140 ) + std : : max ( xDelta , yDelta ) * 140 ;
}
static inline unsigned WZ_DECL_CONST fpathGoodEstimate ( PathCoord s , PathCoord f )
{
// Cost of moving horizontal/vertical = 70*2, cost of moving diagonal = 99*2, 99/70 = 1.41428571... ≈ √2 = 1.41421356...
return iHypot ( ( s . x - f . x ) * 140 , ( s . y - f . y ) * 140 ) ;
2010-07-01 02:56:32 -07:00
}
/** Generate a new node
*/
2010-07-04 01:19:52 -07:00
static inline void fpathNewNode ( PathfindContext & context , PathCoord dest , PathCoord pos , unsigned prevDist , PathCoord prevPos )
2010-07-01 02:56:32 -07:00
{
2011-12-04 08:33:06 -08:00
ASSERT_OR_RETURN ( , ( unsigned ) pos . x < ( unsigned ) mapWidth & & ( unsigned ) pos . y < ( unsigned ) mapHeight , " X (%d) or Y (%d) coordinate for path finding node is out of range! " , pos . x , pos . y ) ;
2010-07-01 02:56:32 -07:00
// Create the node.
PathNode node ;
2010-10-17 08:04:11 -07:00
unsigned costFactor = context . isDangerous ( pos . x , pos . y ) ? 5 : 1 ;
2010-07-01 02:56:32 -07:00
node . p = pos ;
2010-10-17 08:04:11 -07:00
node . dist = prevDist + fpathEstimate ( prevPos , pos ) * costFactor ;
2012-01-29 12:58:38 -08:00
node . est = node . dist + fpathGoodEstimate ( pos , dest ) ;
Vector2i delta = Vector2i ( pos . x - prevPos . x , pos . y - prevPos . y ) * 64 ;
bool isDiagonal = delta . x & & delta . y ;
2010-07-01 02:56:32 -07:00
2010-07-04 01:19:52 -07:00
PathExploredTile & expl = context . map [ pos . x + pos . y * mapWidth ] ;
2012-01-29 12:58:38 -08:00
if ( expl . iteration = = context . iteration )
2010-07-01 02:56:32 -07:00
{
2012-01-29 12:58:38 -08:00
if ( expl . visited )
{
return ; // Already visited this tile. Do nothing.
}
Vector2i deltaA = delta ;
Vector2i deltaB = Vector2i ( expl . dx , expl . dy ) ;
Vector2i deltaDelta = deltaA - deltaB ; // Vector pointing from current considered source tile leading to pos, to the previously considered source tile leading to pos.
if ( abs ( deltaDelta . x ) + abs ( deltaDelta . y ) = = 64 )
{
// prevPos is tile A or B, and pos is tile P. We were previously called with prevPos being tile B or A, and pos tile P.
// We want to find the distance to tile P, taking into account that the actual shortest path involves coming from somewhere between tile A and tile B.
// +---+---+
// | | P |
// +---+---+
// | A | B |
// +---+---+
unsigned distA = node . dist - ( isDiagonal ? 198 : 140 ) * costFactor ; // If isDiagonal, node is A and expl is B.
unsigned distB = expl . dist - ( isDiagonal ? 140 : 198 ) * costFactor ;
if ( ! isDiagonal )
{
std : : swap ( distA , distB ) ;
std : : swap ( deltaA , deltaB ) ;
}
int gradientX = int ( distB - distA ) / costFactor ;
if ( gradientX > 0 & & gradientX < = 98 ) // 98 = floor(140/√2), so gradientX <= 98 is needed so that gradientX < gradientY.
{
// The distance gradient is now known to be somewhere between the direction from A to P and the direction from B to P.
static const uint8_t gradYLookup [ 99 ] = { 140 , 140 , 140 , 140 , 140 , 140 , 140 , 140 , 140 , 140 , 140 , 140 , 139 , 139 , 139 , 139 , 139 , 139 , 139 , 139 , 139 , 138 , 138 , 138 , 138 , 138 , 138 , 137 , 137 , 137 , 137 , 137 , 136 , 136 , 136 , 136 , 135 , 135 , 135 , 134 , 134 , 134 , 134 , 133 , 133 , 133 , 132 , 132 , 132 , 131 , 131 , 130 , 130 , 130 , 129 , 129 , 128 , 128 , 127 , 127 , 126 , 126 , 126 , 125 , 125 , 124 , 123 , 123 , 122 , 122 , 121 , 121 , 120 , 119 , 119 , 118 , 118 , 117 , 116 , 116 , 115 , 114 , 113 , 113 , 112 , 111 , 110 , 110 , 109 , 108 , 107 , 106 , 106 , 105 , 104 , 103 , 102 , 101 , 100 } ;
int gradientY = gradYLookup [ gradientX ] ; // = sqrt(140² - gradientX²), rounded to nearest integer
unsigned distP = gradientY * costFactor + distB ;
node . est - = node . dist - distP ;
node . dist = distP ;
delta = ( deltaA * gradientX + deltaB * ( gradientY - gradientX ) ) / gradientY ;
}
}
if ( expl . dist < = node . dist )
{
return ; // A different path to this tile is shorter.
}
2010-07-01 02:56:32 -07:00
}
// Remember where we have been, and remember the way back.
2010-07-04 01:19:52 -07:00
expl . iteration = context . iteration ;
2012-01-29 12:58:38 -08:00
expl . dx = delta . x ;
expl . dy = delta . y ;
2010-07-01 02:56:32 -07:00
expl . dist = node . dist ;
expl . visited = false ;
2010-07-04 01:19:52 -07:00
// Add the node to the node heap.
context . nodes . push_back ( node ) ; // Add the new node to nodes.
std : : push_heap ( context . nodes . begin ( ) , context . nodes . end ( ) ) ; // Move the new node to the right place in the heap.
2010-07-01 02:56:32 -07:00
}
2010-07-04 01:19:52 -07:00
/// Recalculates estimates to new tileF tile.
static void fpathAStarReestimate ( PathfindContext & context , PathCoord tileF )
{
for ( std : : vector < PathNode > : : iterator node = context . nodes . begin ( ) ; node ! = context . nodes . end ( ) ; + + node )
{
2012-01-29 12:58:38 -08:00
node - > est = node - > dist + fpathGoodEstimate ( node - > p , tileF ) ;
2010-07-04 01:19:52 -07:00
}
// Changing the estimates breaks the heap ordering. Fix the heap ordering.
std : : make_heap ( context . nodes . begin ( ) , context . nodes . end ( ) ) ;
}
2010-07-01 02:56:32 -07:00
2010-07-04 01:19:52 -07:00
/// Returns nearest explored tile to tileF.
static PathCoord fpathAStarExplore ( PathfindContext & context , PathCoord tileF )
2010-07-01 02:56:32 -07:00
{
PathCoord nearestCoord ( 0 , 0 ) ;
unsigned nearestDist = 0xFFFFFFFF ;
// search for a route
2012-03-17 07:35:45 -07:00
bool foundIt = false ;
while ( ! context . nodes . empty ( ) & & ! foundIt )
2010-07-01 02:56:32 -07:00
{
2010-07-04 01:19:52 -07:00
PathNode node = fpathTakeNode ( context . nodes ) ;
if ( context . map [ node . p . x + node . p . y * mapWidth ] . visited )
2010-07-01 02:56:32 -07:00
{
continue ; // Already been here.
}
2010-07-04 01:19:52 -07:00
context . map [ node . p . x + node . p . y * mapWidth ] . visited = true ;
2010-07-01 02:56:32 -07:00
// note the nearest node to the target so far
if ( node . est - node . dist < nearestDist )
{
nearestCoord = node . p ;
nearestDist = node . est - node . dist ;
}
if ( node . p = = tileF )
{
// reached the target
nearestCoord = node . p ;
2012-03-17 07:35:45 -07:00
foundIt = true ; // Break out of loop, but not before inserting neighbour nodes, since the neighbours may be important if the context gets reused.
2010-07-01 02:56:32 -07:00
}
// loop through possible moves in 8 directions to find a valid move
2010-07-04 01:19:52 -07:00
for ( unsigned dir = 0 ; dir < ARRAY_SIZE ( aDirOffset ) ; + + dir )
2010-07-01 02:56:32 -07:00
{
2012-03-13 09:16:46 -07:00
// Try a new location
int x = node . p . x + aDirOffset [ dir ] . x ;
int y = node . p . y + aDirOffset [ dir ] . y ;
2010-07-01 02:56:32 -07:00
/*
5 6 7
\ | /
4 - I - 0
/ | \
3 2 1
odd : orthogonal - adjacent tiles even : non - orthogonal - adjacent tiles
*/
2012-03-13 09:16:46 -07:00
if ( dir % 2 ! = 0 & & ! context . dstIgnore . isNonblocking ( node . p . x , node . p . y ) & & ! context . dstIgnore . isNonblocking ( x , y ) )
2010-07-01 02:56:32 -07:00
{
int x , y ;
// We cannot cut corners
x = node . p . x + aDirOffset [ ( dir + 1 ) % 8 ] . x ;
y = node . p . y + aDirOffset [ ( dir + 1 ) % 8 ] . y ;
2010-07-04 01:19:52 -07:00
if ( context . isBlocked ( x , y ) )
2010-07-01 02:56:32 -07:00
{
continue ;
}
x = node . p . x + aDirOffset [ ( dir + 7 ) % 8 ] . x ;
y = node . p . y + aDirOffset [ ( dir + 7 ) % 8 ] . y ;
2010-07-04 01:19:52 -07:00
if ( context . isBlocked ( x , y ) )
2010-07-01 02:56:32 -07:00
{
continue ;
}
}
// See if the node is a blocking tile
2010-07-04 01:19:52 -07:00
if ( context . isBlocked ( x , y ) )
2010-07-01 02:56:32 -07:00
{
// tile is blocked, skip it
continue ;
}
// Now insert the point into the appropriate list, if not already visited.
2010-07-04 01:19:52 -07:00
fpathNewNode ( context , tileF , PathCoord ( x , y ) , node . dist , node . p ) ;
}
}
return nearestCoord ;
}
2012-01-11 12:12:19 -08:00
static void fpathInitContext ( PathfindContext & context , PathBlockingMap const * blockingMap , PathCoord tileS , PathCoord tileRealS , PathCoord tileF , PathNonblockingArea dstIgnore )
2010-07-04 01:19:52 -07:00
{
2012-01-11 12:12:19 -08:00
context . assign ( blockingMap , tileS , dstIgnore ) ;
2010-07-04 01:19:52 -07:00
// Add the start point to the open list
fpathNewNode ( context , tileF , tileRealS , 0 , tileRealS ) ;
ASSERT ( ! context . nodes . empty ( ) , " fpathNewNode failed to add node. " ) ;
}
2010-12-05 08:25:43 -08:00
ASR_RETVAL fpathAStarRoute ( MOVE_CONTROL * psMove , PATHJOB * psJob )
2010-07-04 01:19:52 -07:00
{
2010-12-05 08:25:43 -08:00
ASR_RETVAL retval = ASR_OK ;
2010-07-04 01:19:52 -07:00
bool mustReverse = true ;
const PathCoord tileOrig ( map_coord ( psJob - > origX ) , map_coord ( psJob - > origY ) ) ;
const PathCoord tileDest ( map_coord ( psJob - > destX ) , map_coord ( psJob - > destY ) ) ;
2011-12-12 11:17:49 -08:00
const PathNonblockingArea dstIgnore ( psJob - > dstStructure ) ;
2010-07-04 01:19:52 -07:00
PathCoord endCoord ; // Either nearest coord (mustReverse = true) or orig (mustReverse = false).
std : : list < PathfindContext > : : iterator contextIterator = fpathContexts . begin ( ) ;
for ( contextIterator = fpathContexts . begin ( ) ; contextIterator ! = fpathContexts . end ( ) ; + + contextIterator )
{
2012-01-11 12:12:19 -08:00
if ( ! contextIterator - > matches ( psJob - > blockingMap , tileDest , dstIgnore ) )
2010-07-04 01:19:52 -07:00
{
// This context is not for the same droid type and same destination.
continue ;
}
// We have tried going to tileDest before.
if ( contextIterator - > map [ tileOrig . x + tileOrig . y * mapWidth ] . iteration = = contextIterator - > iteration
& & contextIterator - > map [ tileOrig . x + tileOrig . y * mapWidth ] . visited )
{
// Already know the path from orig to dest.
endCoord = tileOrig ;
}
else
{
// Need to find the path from orig to dest, continue previous exploration.
fpathAStarReestimate ( * contextIterator , tileOrig ) ;
endCoord = fpathAStarExplore ( * contextIterator , tileOrig ) ;
}
if ( endCoord ! = tileOrig )
{
// orig turned out to be on a different island than what this context was used for, so can't use this context data after all.
continue ;
2010-07-01 02:56:32 -07:00
}
2010-07-04 01:19:52 -07:00
mustReverse = false ; // We have the path from the nearest reachable tile to dest, to orig.
break ; // Found the path! Don't search more contexts.
}
if ( contextIterator = = fpathContexts . end ( ) )
{
// We did not find an appropriate context. Make one.
if ( fpathContexts . size ( ) < 30 )
{
fpathContexts . push_back ( PathfindContext ( ) ) ;
}
- - contextIterator ;
// Init a new context, overwriting the oldest one if we are caching too many.
// We will be searching from orig to dest, since we don't know where the nearest reachable tile to dest is.
2012-01-11 12:12:19 -08:00
fpathInitContext ( * contextIterator , psJob - > blockingMap , tileOrig , tileOrig , tileDest , dstIgnore ) ;
2010-07-04 01:19:52 -07:00
endCoord = fpathAStarExplore ( * contextIterator , tileDest ) ;
contextIterator - > nearestCoord = endCoord ;
2010-07-01 02:56:32 -07:00
}
2010-07-04 01:19:52 -07:00
PathfindContext & context = * contextIterator ;
2010-07-01 02:56:32 -07:00
// return the nearest route if no actual route was found
2010-07-04 01:19:52 -07:00
if ( context . nearestCoord ! = tileDest )
2010-07-01 02:56:32 -07:00
{
retval = ASR_NEAREST ;
}
// Get route, in reverse order.
2010-07-04 01:19:52 -07:00
static std : : vector < Vector2i > path ; // Declared static to save allocations.
path . clear ( ) ;
2012-01-29 12:58:38 -08:00
Vector2i newP ;
for ( Vector2i p ( world_coord ( endCoord . x ) + TILE_UNITS / 2 , world_coord ( endCoord . y ) + TILE_UNITS / 2 ) ; true ; p = newP )
2010-07-01 02:56:32 -07:00
{
2012-01-29 12:58:38 -08:00
ASSERT_OR_RETURN ( ASR_FAILED , worldOnMap ( p . x , p . y ) , " Assigned XY coordinates (%d, %d) not on map! " , ( int ) p . x , ( int ) p . y ) ;
2010-07-11 23:42:36 -07:00
ASSERT_OR_RETURN ( ASR_FAILED , path . size ( ) < ( unsigned ) mapWidth * mapHeight , " Pathfinding got in a loop. " ) ;
2010-07-01 02:56:32 -07:00
2012-01-29 12:58:38 -08:00
path . push_back ( p ) ;
2010-07-11 14:48:40 -07:00
2012-01-29 12:58:38 -08:00
PathExploredTile & tile = context . map [ map_coord ( p . x ) + map_coord ( p . y ) * mapWidth ] ;
newP = p - Vector2i ( tile . dx , tile . dy ) * ( TILE_UNITS / 64 ) ;
2012-06-13 04:07:18 -07:00
Vector2i mapP = map_coord ( newP ) ;
int xSide = newP . x - world_coord ( mapP . x ) > TILE_UNITS / 2 ? 1 : - 1 ; // 1 if newP is on right-hand side of the tile, or -1 if newP is on the left-hand side of the tile.
int ySide = newP . y - world_coord ( mapP . y ) > TILE_UNITS / 2 ? 1 : - 1 ; // 1 if newP is on bottom side of the tile, or -1 if newP is on the top side of the tile.
if ( context . isBlocked ( mapP . x + xSide , mapP . y ) )
{
newP . x = world_coord ( mapP . x ) + TILE_UNITS / 2 ; // Point too close to a blocking tile on left or right side, so move the point to the middle.
}
if ( context . isBlocked ( mapP . x , mapP . y + ySide ) )
{
newP . y = world_coord ( mapP . y ) + TILE_UNITS / 2 ; // Point too close to a blocking tile on rop or bottom side, so move the point to the middle.
}
2012-01-29 12:58:38 -08:00
if ( map_coord ( p ) = = Vector2i ( context . tileS . x , context . tileS . y ) | | p = = newP )
2010-07-11 14:48:40 -07:00
{
2011-12-24 12:24:56 -08:00
break ; // We stopped moving, because we reached the destination or the closest reachable tile to context.tileS. Give up now.
2010-07-11 14:48:40 -07:00
}
2010-07-01 02:56:32 -07:00
}
2011-12-24 12:24:56 -08:00
if ( retval = = ASR_OK )
2010-07-01 02:56:32 -07:00
{
// Found exact path, so use exact coordinates for last point, no reason to lose precision
2010-12-21 12:51:29 -08:00
Vector2i v ( psJob - > destX , psJob - > destY ) ;
2010-07-04 01:19:52 -07:00
if ( mustReverse )
{
path . front ( ) = v ;
}
else
{
path . back ( ) = v ;
}
2010-07-01 02:56:32 -07:00
}
2011-02-27 03:10:40 -08:00
// TODO FIXME once we can change numPoints to something larger than int
psMove - > numPoints = std : : min < size_t > ( INT32_MAX - 1 , path . size ( ) ) ;
2010-07-01 02:56:32 -07:00
// Allocate memory
psMove - > asPath = static_cast < Vector2i * > ( malloc ( sizeof ( * psMove - > asPath ) * path . size ( ) ) ) ;
ASSERT ( psMove - > asPath , " Out of memory " ) ;
if ( ! psMove - > asPath )
{
fpathHardTableReset ( ) ;
return ASR_FAILED ;
}
// get the route in the correct order
// If as I suspect this is to reverse the list, then it's my suspicion that
// we could route from destination to source as opposed to source to
// destination. We could then save the reversal. to risky to try now...Alex M
//
// The idea is impractical, because you can't guarentee that the target is
// reachable. As I see it, this is the reason why psNearest got introduced.
// -- Dennis L.
//
// If many droids are heading towards the same destination, then destination
// to source would be faster if reusing the information in nodeArray. --Cyp
2010-07-04 01:19:52 -07:00
if ( mustReverse )
{
// Copy the list, in reverse.
std : : copy ( path . rbegin ( ) , path . rend ( ) , psMove - > asPath ) ;
if ( ! context . isBlocked ( tileOrig . x , tileOrig . y ) ) // If blocked, searching from tileDest to tileOrig wouldn't find the tileOrig tile.
{
// Next time, search starting from nearest reachable tile to the destination.
2012-01-11 12:12:19 -08:00
fpathInitContext ( context , psJob - > blockingMap , tileDest , context . nearestCoord , tileOrig , dstIgnore ) ;
2010-07-04 01:19:52 -07:00
}
}
else
{
// Copy the list.
std : : copy ( path . begin ( ) , path . end ( ) , psMove - > asPath ) ;
}
// Move context to beginning of last recently used list.
if ( contextIterator ! = fpathContexts . begin ( ) ) // Not sure whether or not the splice is a safe noop, if equal.
{
fpathContexts . splice ( fpathContexts . begin ( ) , fpathContexts , contextIterator ) ;
}
2010-07-01 02:56:32 -07:00
2011-01-07 15:20:12 -08:00
psMove - > destination = psMove - > asPath [ path . size ( ) - 1 ] ;
2010-07-01 02:56:32 -07:00
return retval ;
}
2010-07-12 07:17:55 -07:00
void fpathSetBlockingMap ( PATHJOB * psJob )
{
if ( fpathCurrentGameTime ! = gameTime )
{
// New tick, remove maps which are no longer needed.
fpathCurrentGameTime = gameTime ;
fpathPrevBlockingMaps . swap ( fpathBlockingMaps ) ;
fpathBlockingMaps . clear ( ) ;
}
// Figure out which map we are looking for.
PathBlockingType type ;
type . gameTime = gameTime ;
type . propulsion = psJob - > propulsion ;
type . owner = psJob - > owner ;
type . moveType = psJob - > moveType ;
// Find the map.
std : : list < PathBlockingMap > : : iterator i = std : : find ( fpathBlockingMaps . begin ( ) , fpathBlockingMaps . end ( ) , type ) ;
if ( i = = fpathBlockingMaps . end ( ) )
{
// Didn't find the map, so i does not point to a map.
fpathBlockingMaps . push_back ( PathBlockingMap ( ) ) ;
- - i ;
// i now points to an empty map with no data. Fill the map.
i - > type = type ;
std : : vector < bool > & map = i - > map ;
map . resize ( mapWidth * mapHeight ) ;
2010-11-24 03:23:03 -08:00
uint32_t checksumMap = 0 , checksumDangerMap = 0 , factor = 0 ;
2010-07-12 07:17:55 -07:00
for ( int y = 0 ; y < mapHeight ; + + y )
for ( int x = 0 ; x < mapWidth ; + + x )
{
map [ x + y * mapWidth ] = fpathBaseBlockingTile ( x , y , type . propulsion , type . owner , type . moveType ) ;
2010-11-24 03:23:03 -08:00
checksumMap ^ = map [ x + y * mapWidth ] * ( factor = 3 * factor + 1 ) ;
2010-07-12 07:17:55 -07:00
}
2010-10-17 08:04:11 -07:00
if ( ! isHumanPlayer ( type . owner ) & & type . moveType = = FMT_MOVE )
{
std : : vector < bool > & dangerMap = i - > dangerMap ;
dangerMap . resize ( mapWidth * mapHeight ) ;
for ( int y = 0 ; y < mapHeight ; + + y )
for ( int x = 0 ; x < mapWidth ; + + x )
{
2010-11-21 14:21:23 -08:00
dangerMap [ x + y * mapWidth ] = auxTile ( x , y , type . owner ) & AUXBITS_THREAT ;
2012-02-04 07:12:45 -08:00
checksumDangerMap ^ = dangerMap [ x + y * mapWidth ] * ( factor = 3 * factor + 1 ) ;
2010-10-17 08:04:11 -07:00
}
}
2010-11-24 03:23:03 -08:00
syncDebug ( " blockingMap(%d,%d,%d,%d) = %08X %08X " , gameTime , psJob - > propulsion , psJob - > owner , psJob - > moveType , checksumMap , checksumDangerMap ) ;
2010-07-12 07:17:55 -07:00
}
2010-11-30 14:04:22 -08:00
else
{
syncDebug ( " blockingMap(%d,%d,%d,%d) = cached " , gameTime , psJob - > propulsion , psJob - > owner , psJob - > moveType ) ;
}
2010-07-12 07:17:55 -07:00
// i now points to the correct map. Make psJob->blockingMap point to it.
psJob - > blockingMap = & * i ;
}