Skip to content

Commit

Permalink
Ignore buildings on source or destination when pathfinding.
Browse files Browse the repository at this point in the history 
Droids should now go to the nearest point instead of a point which might not even be accessible, when trying to build modules or derricks.

Fixes ticket:2978.
  • Loading branch information
@Cyp
Cyp committed Dec 12, 2011
1 parent 322bbc6 commit 0119eda
Show file tree
Hide file tree
Showing 3 changed files with 78 additions and 14 deletions.
42 changes: 33 additions & 9 deletions src/astar.cpp
View file
Expand Up @@ -116,28 +116,48 @@ struct PathBlockingMap
std::vector<bool> dangerMap; // using threatBits
};

struct PathNonblockingArea
{
PathNonblockingArea() {}
PathNonblockingArea(StructureTiles const &st) : x1(st.map.x), x2(st.map.x + st.size.x), y1(st.map.y), y2(st.map.y + st.size.y) {}
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;
};

// Data structures used for pathfinding, can contain cached results.
struct PathfindContext
{
PathfindContext() : myGameTime(0), iteration(0), blockingMap(NULL) {}
bool isBlocked(int x, int y) const
{
if (srcIgnore.isNonblocking(x, y) || dstIgnore.isNonblocking(x, y))
{
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).
}
// 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).
return x < 0 || y < 0 || x >= mapWidth || y >= mapHeight || blockingMap->map[x + y*mapWidth];
}
bool isDangerous(int x, int y) const
{
return !blockingMap->dangerMap.empty() && blockingMap->dangerMap[x + y*mapWidth];
}
bool matches(PathBlockingMap const *blockingMap_, PathCoord tileS_) const
bool matches(PathBlockingMap const *blockingMap_, PathCoord tileS_, PathNonblockingArea srcIgnore_, PathNonblockingArea dstIgnore_) const
{
// Must check myGameTime == blockingMap_->type.gameTime, otherwise blockingMap be a deleted pointer which coincidentally compares equal to the valid pointer blockingMap_.
return myGameTime == blockingMap_->type.gameTime && blockingMap == blockingMap_ && tileS == tileS_;
// Must check myGameTime == blockingMap_->type.gameTime, otherwise blockingMap could be a deleted pointer which coincidentally compares equal to the valid pointer blockingMap_.
return myGameTime == blockingMap_->type.gameTime && blockingMap == blockingMap_ && tileS == tileS_ && srcIgnore == srcIgnore_ && dstIgnore == dstIgnore_;
}
void assign(PathBlockingMap const *blockingMap_, PathCoord tileS_)
void assign(PathBlockingMap const *blockingMap_, PathCoord tileS_, PathNonblockingArea srcIgnore_, PathNonblockingArea dstIgnore_)
{
blockingMap = blockingMap_;
tileS = tileS_;
srcIgnore = srcIgnore_;
dstIgnore = dstIgnore_;
myGameTime = blockingMap->type.gameTime;
nodes.clear();

Expand All @@ -164,6 +184,8 @@ struct PathfindContext
std::vector<PathNode> nodes; ///< Edge of explored region of the map.
std::vector<PathExploredTile> map; ///< Map, with paths leading back to tileS.
PathBlockingMap const *blockingMap; ///< Map of blocking tiles for the type of object which needs a path.
PathNonblockingArea srcIgnore; ///< Area of structure at source which should be considered nonblocking.
PathNonblockingArea dstIgnore; ///< Area of structure at destination which should be considered nonblocking.
};

/// Last recently used list of contexts.
Expand Down Expand Up @@ -344,9 +366,9 @@ static PathCoord fpathAStarExplore(PathfindContext &context, PathCoord tileF)
return nearestCoord;
}

static void fpathInitContext(PathfindContext &context, PathBlockingMap const *blockingMap, PathCoord tileS, PathCoord tileRealS, PathCoord tileF)
static void fpathInitContext(PathfindContext &context, PathBlockingMap const *blockingMap, PathCoord tileS, PathCoord tileRealS, PathCoord tileF, PathNonblockingArea srcIgnore, PathNonblockingArea dstIgnore)
{
context.assign(blockingMap, tileS);
context.assign(blockingMap, tileS, srcIgnore, dstIgnore);

// Add the start point to the open list
fpathNewNode(context, tileF, tileRealS, 0, tileRealS);
Expand All @@ -361,13 +383,15 @@ ASR_RETVAL fpathAStarRoute(MOVE_CONTROL *psMove, PATHJOB *psJob)

const PathCoord tileOrig(map_coord(psJob->origX), map_coord(psJob->origY));
const PathCoord tileDest(map_coord(psJob->destX), map_coord(psJob->destY));
const PathNonblockingArea srcIgnore(psJob->srcStructure);
const PathNonblockingArea dstIgnore(psJob->dstStructure);

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)
{
if (!contextIterator->matches(psJob->blockingMap, tileDest))
if (!contextIterator->matches(psJob->blockingMap, tileDest, srcIgnore, dstIgnore))
{
// This context is not for the same droid type and same destination.
continue;
Expand Down Expand Up @@ -410,7 +434,7 @@ ASR_RETVAL fpathAStarRoute(MOVE_CONTROL *psMove, PATHJOB *psJob)

// 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.
fpathInitContext(*contextIterator, psJob->blockingMap, tileOrig, tileOrig, tileDest);
fpathInitContext(*contextIterator, psJob->blockingMap, tileOrig, tileOrig, tileDest, srcIgnore, dstIgnore);
endCoord = fpathAStarExplore(*contextIterator, tileDest);
contextIterator->nearestCoord = endCoord;
}
Expand Down Expand Up @@ -492,7 +516,7 @@ ASR_RETVAL fpathAStarRoute(MOVE_CONTROL *psMove, PATHJOB *psJob)
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.
fpathInitContext(context, psJob->blockingMap, tileDest, context.nearestCoord, tileOrig);
fpathInitContext(context, psJob->blockingMap, tileDest, context.nearestCoord, tileOrig, srcIgnore, dstIgnore);
}
}
else
Expand Down
42 changes: 37 additions & 5 deletions src/fpath.cpp
View file
Expand Up @@ -350,9 +350,31 @@ void fpathRemoveDroidData(int id)
wzMutexUnlock(fpathMutex);
}

static StructureTiles getTilesOfStructure(BASE_OBJECT *object)
{
StructureTiles ret;
ret.size = Vector2i(-65535, -65535); // Default to an invalid area.
ret.map = Vector2i(32767, 32767);

STRUCTURE *psStructure = castStructure(object);
FEATURE *psFeature = castFeature(object);

if (psStructure != NULL)
{
ret.size = getStructureSize(psStructure);
ret.map = map_coord(removeZ(psStructure->pos)) - ret.size/2;
}
else if (psFeature != NULL)
{
ret.size = Vector2i(psFeature->psStats->baseWidth, psFeature->psStats->baseBreadth);
ret.map = map_coord(removeZ(psFeature->pos)) - ret.size/2;
}

return ret;
}

static FPATH_RETVAL fpathRoute(MOVE_CONTROL *psMove, int id, int startX, int startY, int tX, int tY, PROPULSION_TYPE propulsionType,
DROID_TYPE droidType, FPATH_MOVETYPE moveType, int owner, bool acceptNearest)
DROID_TYPE droidType, FPATH_MOVETYPE moveType, int owner, bool acceptNearest, BASE_OBJECT *srcStructure, BASE_OBJECT *dstStructure)
{
objTrace(id, "called(*,id=%d,sx=%d,sy=%d,ex=%d,ey=%d,prop=%d,type=%d,move=%d,owner=%d)", id, startX, startY, tX, tY, (int)propulsionType, (int)droidType, (int)moveType, owner);

Expand Down Expand Up @@ -424,6 +446,8 @@ static FPATH_RETVAL fpathRoute(MOVE_CONTROL *psMove, int id, int startX, int sta
job.droidID = id;
job.destX = tX;
job.destY = tY;
job.srcStructure = getTilesOfStructure(srcStructure);
job.dstStructure = getTilesOfStructure(dstStructure);
job.droidType = droidType;
job.propulsion = propulsionType;
job.moveType = moveType;
Expand Down Expand Up @@ -472,10 +496,18 @@ FPATH_RETVAL fpathDroidRoute(DROID* psDroid, SDWORD tX, SDWORD tY, FPATH_MOVETYP
// Check whether the start and end points of the route are blocking tiles and find an alternative if they are.
Position startPos = psDroid->pos;
Position endPos = Position(tX, tY, 0);
BASE_OBJECT *srcStructure = worldTile(startPos)->psObject;
BASE_OBJECT *dstStructure = worldTile(endPos)->psObject;
if (psDroid->sMove.Status != MOVEWAITROUTE)
{
startPos = findNonblockingPosition(startPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
endPos = findNonblockingPosition(endPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
if (srcStructure == NULL) // If there's a structure over the source, ignore it, otherwise pathfind from somewhere around the obstruction.
{
startPos = findNonblockingPosition(startPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
}
if (dstStructure == NULL) // If there's a structure over the destination, ignore it, otherwise pathfind from somewhere around the obstruction.
{
endPos = findNonblockingPosition(endPos, getPropulsionStats(psDroid)->propulsionType, psDroid->player, moveType);
}
objTrace(psDroid->id, "Want to go to (%d, %d) -> (%d, %d), going (%d, %d) -> (%d, %d)", map_coord(psDroid->pos.x), map_coord(psDroid->pos.y), map_coord(tX), map_coord(tY), map_coord(startPos.x), map_coord(startPos.y), map_coord(endPos.x), map_coord(endPos.y));
}
switch (psDroid->order)
Expand All @@ -492,7 +524,7 @@ FPATH_RETVAL fpathDroidRoute(DROID* psDroid, SDWORD tX, SDWORD tY, FPATH_MOVETYP
break;
}
return fpathRoute(&psDroid->sMove, psDroid->id, startPos.x, startPos.y, endPos.x, endPos.y, psPropStats->propulsionType,
psDroid->droidType, moveType, psDroid->player, acceptNearest);
psDroid->droidType, moveType, psDroid->player, acceptNearest, srcStructure, dstStructure);
}

// Run only from path thread
Expand Down Expand Up @@ -595,7 +627,7 @@ static int fpathResultQueueLength(void)
// Only used by fpathTest.
static FPATH_RETVAL fpathSimpleRoute(MOVE_CONTROL *psMove, int id, int startX, int startY, int tX, int tY)
{
return fpathRoute(psMove, id, startX, startY, tX, tY, PROPULSION_TYPE_WHEELED, DROID_WEAPON, FMT_BLOCK, 0, true);
return fpathRoute(psMove, id, startX, startY, tX, tY, PROPULSION_TYPE_WHEELED, DROID_WEAPON, FMT_BLOCK, 0, true, NULL, NULL);
}

void fpathTest(int x, int y, int x2, int y2)
Expand Down
8 changes: 8 additions & 0 deletions src/fpath.h
View file
Expand Up @@ -41,12 +41,20 @@ enum FPATH_MOVETYPE

struct PathBlockingMap;

struct StructureTiles
{
Vector2i map; ///< Map coordinates of upper left corner of structure.
Vector2i size; ///< Size (in map coordinates) of the structure.
};

struct PATHJOB
{
PROPULSION_TYPE propulsion;
DROID_TYPE droidType;
int destX, destY;
int origX, origY;
StructureTiles srcStructure;
StructureTiles dstStructure;
UDWORD droidID;
FPATH_MOVETYPE moveType;
int owner; ///< Player owner
Expand Down

0 comments on commit 0119eda

Please sign in to comment.