#include <ST_PFEngine.H>

Classes
class	Map
	Extend the SimpleMap with set/access methods to allow multiple levels-of-detail. More...
Public Types
typedef uint4	LevelOfDetail
	index into the LOD array passed to the ctor
Public Member Functions
	PFEngine (sint4 tiles_x_, sint4 tiles_y_, sint4 tile_points_, const Vector< sint4 > &lods_needed)
Changes to the world.
void	insert_object (const Object *obj)
	Insert a given object to the internal world representation.
void	remove_object (const Object *obj)
void	update_object (const Object *obj)
void	insert_boundary (const Segment &line)
void	ir_path (const Object *obj, const Path &path, bool insert)
Perform path finding
bool	find_path (const Object *obj, const Loc &goal, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	Perform pathfinding to a location, return true iff path found, and the path itself in 'output'.
bool	find_path (const Object obj, const Object goal, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	Perform pathfinding to a target object, return true iff path found, and the path itself in 'output' If found then output is guaranteed to include at least one waypoint for the goal.
bool	find_path (const Loc loc, const Loc &goal, sint4 radius, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	MINE!!! Perform pathfinding on a small submap, loc to loc, return true iff path found, and the path itself in 'output'.
bool	sub_path (const Object obj, const Loc &topLeft, const Loc &bottomRight, const Object goal_obj, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	Perform pathfinding to a target object, return true iff path found, and the path itself in 'output' If found then output is guaranteed to include at least one waypoint for the goal.
bool	sub_path (const Object *obj, const Loc &topLeft, const Loc &bottomRight, const Loc &goal_loc, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	Perform pathfinding on a small submap, to a location, return true iff path found, and the path itself in 'output'.
bool	sub_path (const Loc loc, const Loc &topLeft, const Loc &bottomRight, const Loc &goal_loc, sint4 radius, Path &output, LevelOfDetail lod=0, ConsiderObjects consider=CONSIDER_ALL, uint4 stop_time=0)
	Perform pathfinding on a small submap, to a location, return true iff path found, and the path itself in 'output'.
Private Types
typedef ArbitraryResolutionSimpleMap < AStarCell >	AStarMap
typedef Vector < boost::shared_ptr< Map > >	MapsVector
Private Member Functions
boost::shared_ptr< const Map >	get_ground_map () const
	cost of passing though a square within the direction of another units x-second distance x-second distance: if a unit continues to move in a straight line it will be there in x-seconds
boost::shared_ptr< const Map >	get_air_map () const
Actual computation of paths
template<class GoalTester >
bool	find_path (const Object *obj, const Loc &start_position, const Loc &goal, GoalTester goal_tester, const Loc &topleft, const Loc &bottomright, LevelOfDetail lod, ConsiderObjects consider, Path &output, uint4 stop_time)
	This implementation can handle multiple target locations and can handle a target object.
Actual computation of paths. Loc to Loc
template<class GoalTester >
bool	find_path (const sint4 radius, const Loc &start_position, const Loc &goal, GoalTester goal_tester, const Loc &topleft, const Loc &bottomright, LevelOfDetail lod, ConsiderObjects consider, Path &output, uint4 stop_time)
	This implementation can handle multiple target locations and can handle a target location.
template<class GoalTester >
bool	simple_astar (const Map &world_view, AStarMap &astar_data, Bucket to_move, sint4 x2, sint4 y2, GoalTester goal_tester, const Loc &topleft, const Loc &bottomright, uint4 &end_of_path, uint4 stop_time)
	The actual A* implementation.
void	ignore_objects (ConsiderObjects consider, boost::shared_ptr< Map > map, const Object *moved_obj)
	Remove objects we wish to ignore for PFing from the world map.
void	reconsider_objects (ConsiderObjects consider, boost::shared_ptr< Map > map, const Object *moved_obj)
	Return the objects we ignored for the last PFing back to the world map.
void	ignore_objects (ConsiderObjects consider, boost::shared_ptr< Map > map)
	Remove objects we wish to ignore for PFing from the world map.
void	reconsider_objects (ConsiderObjects consider, boost::shared_ptr< Map > map)
	Return the objects we ignored for the last PFing back to the world map.
void	smoothen_path (Vector< Loc > &path)
	Remove redundant waypoints (that fall on a straight line)
uint4	estimate (sint4 x1, sint4 y1, sint4 x2, sint4 y2)
	Compute the octile distance between two points.
bool	on_line (const Loc &a, const Loc &b, const Loc &c)
	Check whether the given three points are on a straight line.
Static Private Member Functions
static void	init_sizes (SimpleMap< SizeCell > &smap)
	Initialize a given map to be empty with a blocked border.
Private Attributes
Vector< sint4 >	lods
	Levels Of Detail available.
LevelOfDetail	max_details_LOD
	The most detailed level.
MapsVector	ground_maps
MapsVector	air_maps
Vector< boost::shared_ptr < AStarMap > >	astar_maps
std::set< const Object * >	mobile_objects
	Set of all mobile objects, allows ignoring them during PFing.
Static Private Attributes
Cost constants
static const uint4	FACTOR = 128
	distance multiplier (real->int)
static const uint4	DIAG = sint4(FACTOR*1.4142)
static const sint4	UNIT_COST = 1000000
	cost of passing though a square occupied by another unit
static const sint4	BOUND_COST = 5000000
	cost of passing though a square occupied by and orts boundery
Friends
class	Map
class	SimpleTerrainWidget
class	SimpleTerrainOverlay
Predicates for testing arrival to different types of goals
class	IsTouchingTarget
class	IsAtLocation
class	IsAtClearLocation

Detailed Description

Definition at line 76 of file ST_PFEngine.H.

Member Typedef Documentation

typedef ArbitraryResolutionSimpleMap<AStarCell> SimpleTerrain::ST_Terrain::PFEngine::AStarMap [private]

Definition at line 220 of file ST_PFEngine.H.

typedef uint4 SimpleTerrain::ST_Terrain::PFEngine::LevelOfDetail

index into the LOD array passed to the ctor

Definition at line 133 of file ST_PFEngine.H.

typedef Vector< boost::shared_ptr<Map> > SimpleTerrain::ST_Terrain::PFEngine::MapsVector [private]

Definition at line 221 of file ST_PFEngine.H.

Constructor & Destructor Documentation

SimpleTerrain::ST_Terrain::PFEngine::PFEngine	(	sint4	tiles_x_,
		sint4	tiles_y_,
		sint4	tile_points_,
		const Vector< sint4 > &	lods_needed
	)

Parameters:

tiles_x_	Width of world in tiles.
tiles_y_	Height of world in tiles.
tile_points_	How many points per tile are in the full world representation.
lods_needed	Vector indicating levels of detail of inner world representation needed. 1 - full details, resolution as in the world rep; 2 - half resolution; 4 - quarter resultion; etc. (tiles_x_tile_points_) and (tiles_y_tile_points_) must be divisible by each LOD.

Definition at line 136 of file ST_PFEngine.C.

References air_maps, assert(), astar_maps, FORALL, ground_maps, init_sizes(), lods, Map, and max_details_LOD.

Member Function Documentation

uint4 SimpleTerrain::ST_Terrain::PFEngine::estimate	(	sint4	x1,
		sint4	y1,
		sint4	x2,
		sint4	y2
	)		`[private]`

Compute the octile distance between two points.

Definition at line 1033 of file ST_PFEngine.C.

References min().

bool SimpleTerrain::ST_Terrain::PFEngine::find_path	(	const Object *	obj,
		const Loc &	goal,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

Perform pathfinding to a location, return true iff path found, and the path itself in 'output'.

If found then output is guaranteed to include at least one waypoint for the goal. Waypoints are listed in reverse order, goal is in locs[0].

Definition at line 183 of file ST_PFEngine.C.

References SimpleTerrain::get_center_loc(), and TEST.

bool SimpleTerrain::ST_Terrain::PFEngine::find_path	(	const Loc	loc,
		const Loc &	goal,
		sint4	radius,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

MINE!!! Perform pathfinding on a small submap, loc to loc, return true iff path found, and the path itself in 'output'.

If found then output is guaranteed to include at least one waypoint for the goal. Waypoints are listed in reverse order, goal is in locs[0].

Definition at line 214 of file ST_PFEngine.C.

References TEST.

bool SimpleTerrain::ST_Terrain::PFEngine::find_path	(	const Object *	obj,
		const Object *	goal,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

Perform pathfinding to a target object, return true iff path found, and the path itself in 'output' If found then output is guaranteed to include at least one waypoint for the goal.

Waypoints are listed in reverse order, goal is in locs[0].

Definition at line 202 of file ST_PFEngine.C.

References SimpleTerrain::get_center_loc(), and TEST.

template<class GoalTester >

bool SimpleTerrain::ST_Terrain::PFEngine::find_path	(	const Object *	obj,
		const Loc &	start_position,
		const Loc &	goal,
		GoalTester	goal_tester,
		const Loc &	topleft,
		const Loc &	bottomright,
		LevelOfDetail	lod,
		ConsiderObjects	consider,
		Path &	output,
		uint4	stop_time
	)		`[private]`

This implementation can handle multiple target locations and can handle a target object.

To this end it accepts a predicate for testing whether a specific map location (inner coords + map pointer) is an allowable goal location. It currently doesn't support a pluggable distance huristic, but instead accepts 'the goal' location (probably the center of the target) and uses the usual octile distance huristic. This combination results in an inadmissible huristic, but should give reasonable results without resorting to the slower huristic h = min distance to all goal locations. stop and report failure when SDL_GetTicks() >= stop_time; 0 => no time limit

Parameters:

obj	the object to move
start_position	Move it from where (not necessarily its current position)
goal	the goal location used for distance estimation
goal_tester	a predicate for an AStarCell which is true iff it is a goal location
topleft	topleft corner of the submap to explore for this path; use Loc(0,0) to specify the entire map
bottomright	bottomright corner of the submap to explore for this path; use Loc(-1,-1) or smaller to specify the entire map
lod	the LOD to use
consider	what objects to consider/ignore as obstacles
output	output path is returned here

Definition at line 472 of file ST_PFEngine.C.

References assert(), SimpleTerrain::SimpleMap< T >::at(), SimpleTerrain::ST_Terrain::find_path(), found, SimpleTerrain::BucketFactory::get_bucket(), Object::get_radius(), Object::get_zcat(), TerrainBase::Path::locs, max(), min(), Object::ON_LAND, SimpleTerrain::Bucket::set_center(), TerrainBase::Loc::x, and TerrainBase::Loc::y.

template<class GoalTester >

bool SimpleTerrain::ST_Terrain::PFEngine::find_path	(	const sint4	radius,
		const Loc &	start_position,
		const Loc &	goal,
		GoalTester	goal_tester,
		const Loc &	topleft,
		const Loc &	bottomright,
		LevelOfDetail	lod,
		ConsiderObjects	consider,
		Path &	output,
		uint4	stop_time
	)		`[private]`

This implementation can handle multiple target locations and can handle a target location.

To this end it accepts a predicate for testing whether a specific map location (inner coords + map pointer) is an allowable goal location. It currently doesn't support a pluggable distance huristic, but instead accepts 'the goal' location (probably the center of the target) and uses the usual octile distance huristic. This combination results in an inadmissible huristic, but should give reasonable results without resorting to the slower huristic h = min distance to all goal locations. stop and report failure when SDL_GetTicks() >= stop_time; 0 => no time limit

Parameters:

radius	the radius to calculate
start_position	Move it from where (not necessarily its current position)
goal	the goal location used for distance estimation
goal_tester	a predicate for an AStarCell which is true iff it is a goal location
topleft	topleft corner of the submap to explore for this path; use Loc(0,0) to specify the entire map
bottomright	bottomright corner of the submap to explore for this path; use Loc(-1,-1) or smaller to specify the entire map
lod	the LOD to use
consider	what objects to consider/ignore as obstacles
output	output path is returned here

Definition at line 356 of file ST_PFEngine.C.

References assert(), SimpleTerrain::SimpleMap< T >::at(), SimpleTerrain::ST_Terrain::find_path(), found, SimpleTerrain::BucketFactory::get_bucket(), TerrainBase::Path::locs, max(), min(), SimpleTerrain::Bucket::set_center(), TerrainBase::Loc::x, and TerrainBase::Loc::y.

boost::shared_ptr<const Map> SimpleTerrain::ST_Terrain::PFEngine::get_air_map ( ) const [inline, private]

Definition at line 360 of file ST_PFEngine.H.

boost::shared_ptr<const Map> SimpleTerrain::ST_Terrain::PFEngine::get_ground_map ( ) const [inline, private]

cost of passing though a square within the direction of another units x-second distance x-second distance: if a unit continues to move in a straight line it will be there in x-seconds

Serving the graphical widget that is used for developement.

Definition at line 359 of file ST_PFEngine.H.

References ground_maps.

void SimpleTerrain::ST_Terrain::PFEngine::ignore_objects	(	ConsiderObjects	consider,
		boost::shared_ptr< Map >	map,
		const Object *	moved_obj
	)		`[private]`

Remove objects we wish to ignore for PFing from the world map.

void SimpleTerrain::SimpleGlobalPF::ignore_objects	(	ConsiderObjects	consider,
		boost::shared_ptr< Map >	map
	)		`[private]`

Remove objects we wish to ignore for PFing from the world map.

Definition at line 612 of file SimpleGlobalPF.C.

References ERR, FIND, FORALL, TerrainBase::IGNORE_ALL_MOBILE_OBJS, TerrainBase::IGNORE_MOBILE_FOES, TerrainBase::IGNORE_MOBILE_FRIENDS, TerrainBase::IGNORE_MOBILE_NEUTRALS, and SimpleTerrain::SimpleGlobalPF::mobile_objects.

void SimpleTerrain::ST_Terrain::PFEngine::init_sizes ( SimpleMap< SizeCell > & smap ) [static, private]

Initialize a given map to be empty with a blocked border.

Definition at line 1115 of file ST_PFEngine.C.

References FORS, FORU, SimpleTerrain::SimpleMap< T >::get_h(), SimpleTerrain::SimpleMap< T >::get_n(), and SimpleTerrain::SimpleMap< T >::get_w().

Referenced by PFEngine().

void SimpleTerrain::ST_Terrain::PFEngine::insert_boundary ( const Segment & line )

Definition at line 1099 of file ST_PFEngine.C.

void SimpleTerrain::ST_Terrain::PFEngine::insert_object ( const Object * obj )

Insert a given object to the internal world representation.

Pointers must remain valid until a respective remove_object() call.

Definition at line 1067 of file ST_PFEngine.C.

References Object::get_max_speed(), Object::get_zcat(), and Object::ON_LAND.

void SimpleTerrain::ST_Terrain::PFEngine::ir_path	(	const Object *	obj,
		const Path &	path,
		bool	insert
	)

Definition at line 1107 of file ST_PFEngine.C.

bool SimpleTerrain::ST_Terrain::PFEngine::on_line	(	const Loc &	a,
		const Loc &	b,
		const Loc &	c
	)		`[private]`

Check whether the given three points are on a straight line.

Definition at line 1057 of file ST_PFEngine.C.

References TerrainBase::Loc::x, and TerrainBase::Loc::y.

void SimpleTerrain::ST_Terrain::PFEngine::reconsider_objects	(	ConsiderObjects	consider,
		boost::shared_ptr< Map >	map,
		const Object *	moved_obj
	)		`[private]`

Return the objects we ignored for the last PFing back to the world map.

void SimpleTerrain::SimpleGlobalPF::reconsider_objects	(	ConsiderObjects	consider,
		boost::shared_ptr< Map >	map
	)		`[private]`

Return the objects we ignored for the last PFing back to the world map.

Definition at line 645 of file SimpleGlobalPF.C.

References ERR, FIND, FORALL, TerrainBase::IGNORE_ALL_MOBILE_OBJS, TerrainBase::IGNORE_MOBILE_FOES, TerrainBase::IGNORE_MOBILE_FRIENDS, TerrainBase::IGNORE_MOBILE_NEUTRALS, and SimpleTerrain::SimpleGlobalPF::mobile_objects.

void SimpleTerrain::ST_Terrain::PFEngine::remove_object ( const Object * obj )

Definition at line 1079 of file ST_PFEngine.C.

References Object::get_max_speed(), Object::get_zcat(), and Object::ON_LAND.

template<class GoalTester >

bool SimpleTerrain::ST_Terrain::PFEngine::simple_astar	(	const Map &	world_view,
		AStarMap &	astar_data,
		Bucket	to_move,
		sint4	x2,
		sint4	y2,
		GoalTester	goal_tester,
		const Loc &	topleft,
		const Loc &	bottomright,
		uint4 &	end_of_path,
		uint4	stop_time
	)		`[private]`

The actual A* implementation.

Return true iff a path was found, and the goal location (cell index in astar_map) that was flagged by 'goal_tester' in 'end_of_path'. Only exapnd nodes in the submap defined by 'topleft' and 'bottomright'.

Definition at line 588 of file ST_PFEngine.C.

References SimpleTerrain::HeapElement::cell, SimpleTerrain::Bucket::check_all_directions(), SimpleTerrain::AStarCell::closed, SimpleTerrain::HeapElement::f, FORS, SimpleTerrain::AStarCell::g, SimpleTerrain::HeapElement::g, SimpleTerrain::Bucket::get_center(), SimpleTerrain::SimpleMap< T >::get_d(), SimpleTerrain::SimpleMap< T >::get_magic(), SimpleTerrain::SimpleMap< T >::get_n(), SimpleTerrain::SimpleMap< T >::i2x(), SimpleTerrain::SimpleMap< T >::i2y(), if(), SimpleTerrain::SimpleMap< T >::index(), max(), SimpleTerrain::AStarCell::open, SimpleTerrain::AStarCell::parent, SimpleTerrain::Bucket::set_center(), SimpleTerrain::SimpleMap< T >::set_magic(), TEST, TerrainBase::Loc::x, and TerrainBase::Loc::y.

void SimpleTerrain::ST_Terrain::PFEngine::smoothen_path ( Vector< Loc > & path ) [private]

Remove redundant waypoints (that fall on a straight line)

bool SimpleTerrain::ST_Terrain::PFEngine::sub_path	(	const Loc	loc,
		const Loc &	topLeft,
		const Loc &	bottomRight,
		const Loc &	goal_loc,
		sint4	radius,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

Perform pathfinding on a small submap, to a location, return true iff path found, and the path itself in 'output'.

If found then output is guaranteed to include at least one waypoint for the goal. Waypoints are listed in reverse order, goal is in locs[0].

bool SimpleTerrain::ST_Terrain::PFEngine::sub_path	(	const Object *	obj,
		const Loc &	topLeft,
		const Loc &	bottomRight,
		const Loc &	goal_loc,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

Perform pathfinding on a small submap, to a location, return true iff path found, and the path itself in 'output'.

If found then output is guaranteed to include at least one waypoint for the goal. Waypoints are listed in reverse order, goal is in locs[0].

The next refinement doesn't work very well: If the target location is very near to an obstacle, such that the size of the moving object forbids it from being there, the PF will search the entire map (which is slow) before realizing this.

Definition at line 228 of file ST_PFEngine.C.

References SimpleTerrain::ST_Terrain::find_path(), found, SimpleTerrain::get_center_loc(), and TerrainBase::Path::locs.

bool SimpleTerrain::ST_Terrain::PFEngine::sub_path	(	const Object *	obj,
		const Loc &	topLeft,
		const Loc &	bottomRight,
		const Object *	goal_obj,
		Path &	output,
		LevelOfDetail	lod = `0`,
		ConsiderObjects	consider = `CONSIDER_ALL`,
		uint4	stop_time = `0`
	)

Perform pathfinding to a target object, return true iff path found, and the path itself in 'output' If found then output is guaranteed to include at least one waypoint for the goal.

Waypoints are listed in reverse order, goal is in locs[0].

void SimpleTerrain::ST_Terrain::PFEngine::update_object ( const Object * obj )

Definition at line 1091 of file ST_PFEngine.C.

References Object::get_zcat(), and Object::ON_LAND.