clusterAbstraction Class Reference

Cluster abstraction for HPA* algorithm as described in (Botea,Mueller,Schaeffer 2004). More...

#include <clusterAbstraction.h>

Inheritance diagram for clusterAbstraction:

[legend]Collaboration diagram for clusterAbstraction:

[legend]List of all members.


Public Member Functions
	clusterAbstraction (Map *map, int _clusterSize)
	create a cluster abstraction for the given map.
	~clusterAbstraction ()
mapAbstraction *	clone (Map *map)
	return a new abstraction map of the same type as this map abstraction
int	getClusterSize ()
bool	pathable (node start, node goal)
	Check if there is a path between two nodes.
void	verifyHierarchy ()
	verify that the hierarchy is consistent
void	removeNodes (node start, node goal)
	remove a start or goal node after the search has been completed.
void	removeNode (node *)
	remove node from abstraction
void	removeEdge (edge *, unsigned int)
	remove edge from abstraction
void	addNode (node *)
	add node to abstraction
void	addEdge (edge *, unsigned int)
	add edge to abstraction
void	repairAbstraction ()
	This must be called after any of the above add/remove operations.
node *	insertNode (node *n, int &expanded, int &touched)
	insert a start or goal node in to the abstract graph (for searching purposes).
path *	getCachedPath (edge *e)
	get the map-level path that corresponds to abstract edge e
node *	getLowLevelNode (node *abstract)
	get the map-level node that is at the (x,y) coordinates of the abstract node
int	getClusterIdFromNode (node *n)
	Given a map node, return the ID of the cluster it's in.
int	getClusterIdFromCoord (int row, int col) const
	given a node's coordinates, find the cluster it's in
void	printMapCoord (node *n)
void	printPathAsCoord (path *p)
virtual void	openGLDraw ()
Private Member Functions
int	min (int, int)
void	createClustersAndEntrances ()
	create clusters on the abstract level and create corresponding entrances.
void	createAbstractGraph ()
void	addCluster (Cluster c)
void	createHorizEntrances (int, int, int, int, int)
	based on the function from HPA* abswizard.cpp with the same name
void	createVertEntrances (int, int, int, int, int)
	based on the function from HPA* abstiling.cpp with the same name
void	linkEntrancesAndClusters ()
	from original HPA* abstiling.cpp
void	addAbsNodes (graph *g)
	Add a node for cluster for each entrance.
void	computeClusterPaths (graph *g)
void	addEntrance (Entrance e)
int	getClusterId (int row, int col) const
	given a cluster row and column (NOT map row/column), return the cluster's ID.
Cluster &	getCluster (int id)
	get the cluster from it's ID
int	nodeExists (const Cluster &c, double x, double y, graph *g)
	check if a node already exists in a certain cluster with a particular set of coordinates
void	setUpParents (graph *g)
	Nodes are assigned the closest entrance node in the abstract graph as their parent.
void	buildNodeIntoParent (node n, node parent)
void	abstractionBFS (node which, node parent, int cluster, int numOrigNodes, int numNodesAfter)
	'borrowed' from mapQuadTreeAbstraction.cpp
void	createConnectivityGraph ()
	Add a 2nd level to the graph.
void	connectedBFS (node which, node parent)
Private Attributes
int	clusterSize
int	rows
int	columns
std::vector< Cluster >	clusters
std::vector< Entrance >	entrances
clusterUtil::PathLookupTable	paths
clusterUtil::PathLookupTable	temp
std::vector< path * >	newPaths

Detailed Description

Cluster abstraction for HPA* algorithm as described in (Botea,Mueller,Schaeffer 2004).

Source code based on HPA* code found at http://www.cs.ualberta.ca/~adib/Home/Download/hpa.tgz

Constructor & Destructor Documentation

clusterAbstraction::clusterAbstraction ( Map * map,

int _clusterSize

)

create a cluster abstraction for the given map.
Clusters are square, with height = width = clustersize.

clusterAbstraction::~clusterAbstraction ( )

Member Function Documentation

void clusterAbstraction::abstractionBFS ( node * which,

node * parent,

int cluster,

int numOrigNodes,

int numNodesAfter

) [private]

'borrowed' from mapQuadTreeAbstraction.cpp

void clusterAbstraction::addAbsNodes ( graph * g ) [private]

Add a node for cluster for each entrance.

void clusterAbstraction::addCluster ( Cluster c ) [private]

void clusterAbstraction::addEdge ( edge * ,

unsigned int

) [inline, virtual]

add edge to abstraction

Implements graphAbstraction.

void clusterAbstraction::addEntrance ( Entrance e ) [private]

void clusterAbstraction::addNode ( node * ) [inline, virtual]

add node to abstraction

Implements graphAbstraction.

void clusterAbstraction::buildNodeIntoParent ( node * n,

node * parent

) [private]

mapAbstraction* clusterAbstraction::clone ( Map * map ) [inline, virtual]

return a new abstraction map of the same type as this map abstraction

Implements mapAbstraction.

void clusterAbstraction::computeClusterPaths ( graph * g ) [private]

void clusterAbstraction::connectedBFS ( node * which,

node * parent

) [private]

void clusterAbstraction::createAbstractGraph ( ) [private]

void clusterAbstraction::createClustersAndEntrances ( ) [private]

create clusters on the abstract level and create corresponding entrances.

void clusterAbstraction::createConnectivityGraph ( ) [private]

Add a 2nd level to the graph.
If two nodes in the abstract (level 1) graph have the same parent, there is a path between them.

void clusterAbstraction::createHorizEntrances ( int start,

int end,

int latitude,

int row,

int col

) [private]

based on the function from HPA* abswizard.cpp with the same name
Create horizontal entrances. Between 2 obstacles, there is either one or two entrances, depending on how many tiles there are between these obstacles.

void clusterAbstraction::createVertEntrances ( int start,

int end,

int meridian,

int row,

int col

) [private]

based on the function from HPA* abstiling.cpp with the same name
create vertical entrances

path * clusterAbstraction::getCachedPath ( edge * e )

get the map-level path that corresponds to abstract edge e

Cluster & clusterAbstraction::getCluster ( int id ) [private]

get the cluster from it's ID

int clusterAbstraction::getClusterId ( int row,

int col

) const [private]

given a cluster row and column (NOT map row/column), return the cluster's ID.

int clusterAbstraction::getClusterIdFromCoord ( int row,

int col

) const

given a node's coordinates, find the cluster it's in

int clusterAbstraction::getClusterIdFromNode ( node * n )

Given a map node, return the ID of the cluster it's in.
Only works for map

int clusterAbstraction::getClusterSize ( ) [inline]

node * clusterAbstraction::getLowLevelNode ( node * abstract )

get the map-level node that is at the (x,y) coordinates of the abstract node

node * clusterAbstraction::insertNode ( node * n,

int & expanded,

int & touched

)

insert a start or goal node in to the abstract graph (for searching purposes).
The node is inserted in the same location as it is in on the map-graph. Edges are added between this node and all entrance nodes in its cluster when there is a path between the nodes. The weight of the edge is set to the distance of the map-level path

void clusterAbstraction::linkEntrancesAndClusters ( ) [private]

from original HPA* abstiling.cpp

int clusterAbstraction::min ( int ,

int

) [private]

int clusterAbstraction::nodeExists ( const Cluster & c,

double x,

double y,

graph * g

) [private]

check if a node already exists in a certain cluster with a particular set of coordinates

void clusterAbstraction::openGLDraw ( ) [virtual]

Reimplemented from mapAbstraction.

bool clusterAbstraction::pathable ( node * from,

node * to

) [virtual]

Check if there is a path between two nodes.

Implements graphAbstraction.

void clusterAbstraction::printMapCoord ( node * n )

void clusterAbstraction::printPathAsCoord ( path * p )

void clusterAbstraction::removeEdge ( edge * ,

unsigned int

) [inline, virtual]

remove edge from abstraction

Implements graphAbstraction.

void clusterAbstraction::removeNode ( node * ) [inline, virtual]

remove node from abstraction

Implements graphAbstraction.

void clusterAbstraction::removeNodes ( node * start,

node * goal

)

remove a start or goal node after the search has been completed.
The node is removed, as well as all the edges that were added to connect it to the cluster. The edges are also removed from the cache.

void clusterAbstraction::repairAbstraction ( ) [inline, virtual]

This must be called after any of the above add/remove operations.
But the operations can be stacked followed by a single repairAbstraction call.
Implements graphAbstraction.

void clusterAbstraction::setUpParents ( graph * g ) [private]

Nodes are assigned the closest entrance node in the abstract graph as their parent.
Connected components that cannot reach any entrance nodes will be assigned their own parent node.
Connected component code borrowed from mapQuadTreeAbstraction.cpp