A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel. More...

#include <astar2.h>

Inheritance diagram for AStar3D:

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

Detailed Description

A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel.

Definition at line 19 of file astar2.h.

Member Typedef Documentation

typedef float AStar3D::DistanceType

Definition at line 21 of file astar2.h.

typedef boost::unordered_map<MapCoordinate, int, hash_MapCoordinate> AStar3D::fieldAccessType

protected

Definition at line 88 of file astar2.h.

typedef deque<PathPoint> AStar3D::Path

Definition at line 48 of file astar2.h.

Constructor & Destructor Documentation

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.

AStar3D::~AStar3D ( )

virtual

Definition at line 173 of file astar2.cpp.

References GameMap::cleartemps(), tempsMarked, and wind.

Member Function Documentation

bool AStar3D::constructPath	(	Path &	path,
		const Node *	n
	)

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().

bool AStar3D::constructPath	(	Path &	path,
		const MapCoordinate3D &	pos
	)

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().

AStar3D::DistanceType AStar3D::dist	(	const MapCoordinate3D &	a,
		const MapCoordinate3D &	b
	)

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().

AStar3D::DistanceType AStar3D::dist	(	const MapCoordinate3D &	a,
		const vector< MapCoordinate3D > &	b
	)

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.

Parameters

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.

AStar3D::DistanceType AStar3D::getMoveCost	(	const MapCoordinate3D &	start,
		const MapCoordinate3D &	dest,
		const Vehicle *	vehicle,
		bool &	hasAttacked
	)

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

int AStar3D::initNode	(	Node &	newN,
		const Node *	oldN_ptr,
		const MapCoordinate3D &	newpos,
		const vector< MapCoordinate3D > &	B,
		bool	disableAttack = `false`,
		bool	enter = `false`,
		bool	dock = `false`
	)