Advanced Strategic Command
|
A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel. More...
#include <astar2.h>
Classes | |
struct | hash_MapCoordinate |
struct | hash_MapCoordinate3D |
struct | Node |
class | OperationLimiter |
class | PathPoint |
class | VisitedContainer |
the reachable fields More... | |
Public Types | |
typedef float | DistanceType |
typedef deque< PathPoint > | Path |
Public Member Functions | |
AStar3D (GameMap *actmap, Vehicle *veh, bool markTemps_=true, int maxDistance=maxint) | |
void | registerOperationLimiter (OperationLimiter *ol) |
the search can be restricted to certain operations More... | |
bool | findPath (const MapCoordinate3D &dest) |
searches for a path from the unit's current position to dest More... | |
bool | findPath (const vector< MapCoordinate3D > &dest) |
searches for a path from the units current position to one of the dest fields More... | |
void | findPath (Path &path, const MapCoordinate3D &dest) |
searches for a path from the unit's current position to dest and stores it in path More... | |
bool | findPath (Path &path, const vector< MapCoordinate3D > &dest) |
searches for a path from the units current position to one of the dest fields and stores it in path More... | |
void | findAllAccessibleFields () |
searches for all fields that are within the range of maxDist and marks them. More... | |
bool | constructPath (Path &path, const Node *n) |
construct a path from a pointer to a visited node, return false if pointer is NULL, else true More... | |
bool | constructPath (Path &path, const MapCoordinate3D &pos) |
construct a path from a pointer to a visited node; return false if position doesn't exist, else true More... | |
int | getDistance () |
returns the distance of the last found path, or -1 on any error More... | |
int | getTravelTime () |
returns the number of turns that the unit will need to travel along the last found path More... | |
int | getFieldAccess (int x, int y) |
int | getFieldAccess (const MapCoordinate &mc) |
void | dumpVisited () |
for debugging: dumps the contents of the visited node to stdout More... | |
virtual | ~AStar3D () |
Public Attributes | |
VisitedContainer | visited |
Static Public Attributes | |
static const DistanceType | longestPath = 1e9 |
Protected Types | |
typedef boost::unordered_map < MapCoordinate, int, hash_MapCoordinate > | fieldAccessType |
Protected Member Functions | |
virtual DistanceType | getMoveCost (const MapCoordinate3D &start, const MapCoordinate3D &dest, const Vehicle *vehicle, bool &hasAttacked) |
DistanceType | dist (const MapCoordinate3D &a, const MapCoordinate3D &b) |
DistanceType | dist (const MapCoordinate3D &a, const vector< MapCoordinate3D > &b) |
int | initNode (Node &newN, const Node *oldN_ptr, const MapCoordinate3D &newpos, const vector< MapCoordinate3D > &B, bool disableAttack=false, bool enter=false, bool dock=false) |
Protected Attributes | |
OperationLimiter * | operationLimiter |
int | MAXIMUM_PATH_LENGTH |
GameMap * | tempsMarked |
Path * | _path |
Vehicle * | veh |
GameMap * | actmap |
float | vehicleSpeedFactor [8] |
float | maxVehicleSpeedFactor |
bool | markTemps |
WindMovement * | wind |
fieldAccessType | fieldAccess |
A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel.
typedef float AStar3D::DistanceType |
|
protected |
typedef deque<PathPoint> AStar3D::Path |
AStar3D::AStar3D | ( | GameMap * | actmap, |
Vehicle * | veh, | ||
bool | markTemps_ = true , |
||
int | maxDistance = maxint |
||
) |
Definition at line 128 of file astar2.cpp.
References _path, actmap, chfliegend, chhochfliegend, chtieffliegend, MapCoordinate3D::getNumericalHeight(), Vehicle::getPosition(), ContainerBaseType::height, longestPath, markTemps, max(), MAXIMUM_PATH_LENGTH, Vehicle::maxMovement(), maxVehicleSpeedFactor, VehicleType::movement, tempsMarked, Vehicle::typ, veh, vehicleSpeedFactor, GameMap::weather, wind, and GameMap::Weather::windSpeed.
|
virtual |
Definition at line 173 of file astar2.cpp.
References GameMap::cleartemps(), tempsMarked, and wind.
construct a path from a pointer to a visited node, return false if pointer is NULL, else true
Definition at line 546 of file astar2.cpp.
References AStar3D::Node::previous.
Referenced by MoveUnitCommand::calcPath(), and findPath().
|
inline |
construct a path from a pointer to a visited node; return false if position doesn't exist, else true
Definition at line 163 of file astar2.h.
References constructPath(), AStar3D::VisitedContainer::find(), and visited.
Referenced by constructPath().
|
protected |
Definition at line 184 of file astar2.cpp.
References beeline(), chfliegend, chhochfliegend, chtieffliegend, MapCoordinate3D::getBitmappedHeight(), MapCoordinate3D::getNumericalHeight(), minmalq, MapCoordinate::valid(), wind, and windbeeline().
Referenced by dist(), findPath(), initNode(), and AStar3D::PathPoint::read().
|
protected |
Definition at line 205 of file astar2.cpp.
References dist(), longestPath, maxVehicleSpeedFactor, and min().
void AStar3D::dumpVisited | ( | ) |
for debugging: dumps the contents of the visited node to stdout
Definition at line 619 of file astar2.cpp.
References AStar3D::VisitedContainer::begin(), dumpNode(), AStar3D::VisitedContainer::end(), and visited.
void AStar3D::findAllAccessibleFields | ( | ) |
searches for all fields that are within the range of maxDist and marks them.
On each field one bit for each level of height will be set. The Destructor removes all marks.
path | if non-null, all fields will be stored there |
Definition at line 562 of file astar2.cpp.
References actmap, AStar3D::VisitedContainer::begin(), GameMap::cleartemps(), AStar3D::VisitedContainer::end(), fieldAccess, findPath(), MapField::getaTemp(), GameMap::getField(), markTemps, MapField::setaTemp(), tempsMarked, and visited.
Referenced by testPathFinding(), and testPathFinding2().
bool AStar3D::findPath | ( | const MapCoordinate3D & | dest | ) |
searches for a path from the unit's current position to dest
Definition at line 335 of file astar2.cpp.
Referenced by MoveUnitCommand::calcPath(), findAllAccessibleFields(), findPath(), PathFinder::getMovementFields(), testHeightChangeAI(), and testPathFinding().
bool AStar3D::findPath | ( | const vector< MapCoordinate3D > & | dest | ) |
searches for a path from the units current position to one of the dest fields
Definition at line 341 of file astar2.cpp.
References actmap, AStar3D::VisitedContainer::add(), AStar3D::OperationLimiter::allowDocking(), AStar3D::OperationLimiter::allowHeightChange(), AStar3D::OperationLimiter::allowLeavingContainer(), AStar3D::OperationLimiter::allowMovement(), Vehicle::attacked, MapField::bdt, MapField::building, AStar3D::Node::canStop, cbbuildingentry, cgp_movefrominvalidfields, Player::diplomacy, ContainerBaseType::TransportationIO::disableAttack, dist(), VehicleType::HeightChangeMethod::dist, OpenContainer::empty(), AStar3D::Node::enterHeight, fieldAccessible(), AStar3D::VisitedContainer::find(), MapCoordinate3D::getBitmappedHeight(), MapField::getContainer(), getDirectionOrder(), GameMap::getField(), GameMap::getgameparameter(), Vehicle::getHeightChange(), ContainerBase::getMap(), getNeighbouringFieldCoordinate(), getnextdx(), getnextdy(), MapCoordinate3D::getNumericalHeight(), ContainerBase::getOwner(), GameMap::getPlayer(), Vehicle::getPosition3D(), getTerrainBitType(), AStar3D::Node::gval, AStar3D::Node::h, AStar3D::Node::hasAttacked, ContainerBaseType::hasFunction(), VehicleType::HeightChangeMethod::heightDelta, AStar3D::Node::hval, initNode(), DiplomaticStateVector::isAllied(), ContainerBaseType::OnlyMoveToAndFromTransports, operationLimiter, OpenContainer::pop(), AStar3D::Node::previous, OpenContainer::pushOrUpdate(), MapCoordinate3D::setNumericalHeight(), terrainaccessible(), OpenContainer::top(), Vehicle::typ, MapField::unitHere(), veh, MapField::vehicle, ContainerBase::vehicleDocking(), ContainerBase::vehicleUnloadable(), ContainerBase::vehicleUnloadSystem(), visited, MapCoordinate::x, and MapCoordinate::y.
void AStar3D::findPath | ( | Path & | path, |
const MapCoordinate3D & | dest | ||
) |
searches for a path from the unit's current position to dest and stores it in path
Definition at line 554 of file astar2.cpp.
References findPath().
bool AStar3D::findPath | ( | Path & | path, |
const vector< MapCoordinate3D > & | dest | ||
) |
searches for a path from the units current position to one of the dest fields and stores it in path
Definition at line 323 of file astar2.cpp.
References _path, AStar3D::VisitedContainer::back(), constructPath(), findPath(), and visited.
int AStar3D::getDistance | ( | ) |
returns the distance of the last found path, or -1 on any error
int AStar3D::getFieldAccess | ( | int | x, |
int | y | ||
) |
Definition at line 582 of file astar2.cpp.
int AStar3D::getFieldAccess | ( | const MapCoordinate & | mc | ) |
Definition at line 587 of file astar2.cpp.
References fieldAccess.
|
protectedvirtual |
Reimplemented in HiddenAStar3D, AntiMineAStar3D, and StratAStar3D.
Definition at line 221 of file astar2.cpp.
References calcMoveMalus(), MapCoordinate3D::getNumericalHeight(), longestPath, VehicleType::movement, Vehicle::typ, veh, vehicleSpeedFactor, and wind.
Referenced by StratAStar3D::getMoveCost(), AntiMineAStar3D::getMoveCost(), HiddenAStar3D::getMoveCost(), and initNode().
int AStar3D::getTravelTime | ( | ) |
returns the number of turns that the unit will need to travel along the last found path
|
protected |
Definition at line 242 of file astar2.cpp.
References actmap, AStar3D::Node::canStop, dist(), AStar3D::Node::enterHeight, fieldAccessible(), AStar3D::VisitedContainer::find(), MapCoordinate3D::getBitmappedHeight(), GameMap::getField(), getMoveCost(), MapCoordinate3D::getNumericalHeight(), AStar3D::Node::gval, AStar3D::Node::h, AStar3D::Node::hasAttacked, AStar3D::Node::hval, longestPath, MAXIMUM_PATH_LENGTH, AStar3D::Node::previous, MapCoordinate3D::setNumericalHeight(), veh, visited, MapCoordinate::x, GameMap::xsize, MapCoordinate::y, and GameMap::ysize.
Referenced by findPath().
|
inline |
the search can be restricted to certain operations
Definition at line 138 of file astar2.h.
References operationLimiter.
Referenced by MoveUnitCommand::calcPath(), and MoveUnitCommand::searchFields().
|
protected |
Definition at line 78 of file astar2.h.
Referenced by AStar3D(), and findPath().
|
protected |
Definition at line 80 of file astar2.h.
Referenced by AStar3D(), findAllAccessibleFields(), findPath(), PathFinder::getMovementFields(), and initNode().
|
protected |
Definition at line 89 of file astar2.h.
Referenced by findAllAccessibleFields(), and getFieldAccess().
|
static |
Definition at line 22 of file astar2.h.
Referenced by AStar3D(), dist(), getMoveCost(), and initNode().
|
protected |
Definition at line 83 of file astar2.h.
Referenced by AStar3D(), and findAllAccessibleFields().
|
protected |
Definition at line 76 of file astar2.h.
Referenced by AStar3D(), and initNode().
|
protected |
|
protected |
Definition at line 75 of file astar2.h.
Referenced by findPath(), and registerOperationLimiter().
|
protected |
Definition at line 77 of file astar2.h.
Referenced by AStar3D(), findAllAccessibleFields(), and ~AStar3D().
|
protected |
Definition at line 79 of file astar2.h.
Referenced by AStar3D(), findPath(), getMoveCost(), PathFinder::getMovementFields(), and initNode().
|
protected |
Definition at line 81 of file astar2.h.
Referenced by AStar3D(), and getMoveCost().
VisitedContainer AStar3D::visited |
Definition at line 122 of file astar2.h.
Referenced by MoveUnitCommand::calcPath(), constructPath(), dumpVisited(), findAllAccessibleFields(), findPath(), PathFinder::getMovementFields(), and initNode().
|
protected |
Definition at line 84 of file astar2.h.
Referenced by AStar3D(), dist(), getMoveCost(), and ~AStar3D().