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

#include <ClusterAbstraction.h>

Inheritance diagram for ClusterAbstraction:

Collaboration diagram for ClusterAbstraction:

Public Member Functions
	ClusterAbstraction (Map *map, int _clusterSize)
	create a cluster abstraction for the given map. More...

	~ClusterAbstraction ()

MapAbstraction *	Clone (Map *map)

int	getClusterSize ()

bool	Pathable (node start, node goal)
	Check if there is a path between two nodes. More...

void	VerifyHierarchy ()

void	removeNodes (node start, node goal)
	remove a start or goal node after the search has been completed. More...

void	RemoveNode (node *)

void	RemoveEdge (edge *, unsigned int)

void	AddNode (node *)

void	AddEdge (edge *, unsigned int)

void	RepairAbstraction ()

node *	insertNode (node *n, int &expanded, int &touched)
	insert a start or goal node in to the abstract Graph (for searching purposes). More...

path *	getCachedPath (edge *e)
	get the map-level path that corresponds to abstract edge e More...

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

int	getClusterIdFromNode (node *n)
	Given a map node, return the ID of the cluster it's in. More...

int	getClusterIdFromCoord (int row, int col) const
	given a node's coordinates, find the cluster it's in More...

void	printMapCoord (node *n)

void	printPathAsCoord (path *p)

virtual void	OpenGLDraw () const

Private Member Functions
int	min (int, int)

void	createClustersAndEntrances ()
	create clusters on the abstract level and create corresponding entrances. More...

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 More...

void	createVertEntrances (int, int, int, int, int)
	based on the function from HPA* abstiling.cpp with the same name More...

void	linkEntrancesAndClusters ()
	from original HPA* abstiling.cpp More...

void	addAbsNodes (Graph *g)
	Add a node for cluster for each entrance. More...

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. More...

Cluster &	getCluster (int id)
	get the cluster from it's ID More...

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 More...

void	setUpParents (Graph *g)
	Nodes are assigned the closest entrance node in the abstract Graph as their parent. More...

void	buildNodeIntoParent (node n, node parent)

void	abstractionBFS (node which, node parent, int cluster, int numOrigNodes, int numNodesAfter)
	'borrowed' from MapSectorAbstraction.cpp More...

void	createConnectivityGraph ()
	Add a 2nd level to the Graph. More...

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

Definition at line 122 of file ClusterAbstraction.h.

Constructor & Destructor Documentation

◆ ClusterAbstraction()

ClusterAbstraction::ClusterAbstraction	(	Map *	map,
		int	_clusterSize
	)

create a cluster abstraction for the given map.

Clusters are square, with height = width = clustersize.

Definition at line 95 of file ClusterAbstraction.cpp.

References createAbstractGraph(), createClustersAndEntrances(), GetMapGraph(), and linkEntrancesAndClusters().

Referenced by Clone().

◆ ~ClusterAbstraction()

ClusterAbstraction::~ClusterAbstraction ( )

Definition at line 104 of file ClusterAbstraction.cpp.

References Graph::edgeIterNext(), Graph::getEdgeIter(), paths, and temp.

Member Function Documentation

◆ abstractionBFS()

void ClusterAbstraction::abstractionBFS	(	node *	which,
		node *	parent,
		int	cluster,
		int	numOrigNodes,
		int	numNodesAfter
	)

private

'borrowed' from MapSectorAbstraction.cpp

Definition at line 911 of file ClusterAbstraction.cpp.

References Cluster::addParent(), buildNodeIntoParent(), getCluster(), getClusterIdFromNode(), node::GetLabelL(), node::getNeighborIter(), GraphAbstractionConstants::kParent, and node::nodeNeighborNext().

Referenced by setUpParents().

◆ addAbsNodes()

void ClusterAbstraction::addAbsNodes ( Graph * g )

private

Add a node for cluster for each entrance.

Definition at line 392 of file ClusterAbstraction.cpp.

References Graph::AddEdge(), Cluster::AddNode(), Graph::AddNode(), entrances, Entrance::getCenter1Col(), Entrance::getCenter1Row(), getCluster(), Entrance::getCluster1Id(), Entrance::getCluster2Id(), Map::GetOpenGLCoord(), Entrance::getOrientation(), HORIZONTAL, GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, GraphAbstractionConstants::kZCoordinate, nodeExists(), node::SetLabelF(), node::SetLabelL(), verbose, VERTICAL, recVec::x, recVec::y, and recVec::z.

Referenced by createAbstractGraph().

◆ addCluster()

void ClusterAbstraction::addCluster ( Cluster c )

private

Definition at line 202 of file ClusterAbstraction.cpp.

References clusters.

Referenced by createClustersAndEntrances().

◆ AddEdge()

void ClusterAbstraction::AddEdge	(	edge *	,
		unsigned int
	)

inline

Definition at line 136 of file ClusterAbstraction.h.

◆ addEntrance()

void ClusterAbstraction::addEntrance ( Entrance e )

private

Definition at line 210 of file ClusterAbstraction.cpp.

References entrances.

Referenced by createHorizEntrances(), and createVertEntrances().

◆ AddNode()

void ClusterAbstraction::AddNode ( node * )

inline

Definition at line 135 of file ClusterAbstraction.h.

◆ buildNodeIntoParent()

void ClusterAbstraction::buildNodeIntoParent	(	node *	n,
		node *	parent
	)

private

Definition at line 999 of file ClusterAbstraction.cpp.

References node::GetLabelL(), node::GetNum(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, and node::SetLabelL().

Referenced by abstractionBFS(), connectedBFS(), insertNode(), and setUpParents().

◆ Clone()

MapAbstraction* ClusterAbstraction::Clone ( Map * map )

inline

Definition at line 126 of file ClusterAbstraction.h.

References ClusterAbstraction(), and clusterSize.

◆ computeClusterPaths()

void ClusterAbstraction::computeClusterPaths ( Graph * g )

private

◆ connectedBFS()

void ClusterAbstraction::connectedBFS	(	node *	which,
		node *	parent
	)

private

Definition at line 965 of file ClusterAbstraction.cpp.

References buildNodeIntoParent(), node::GetLabelL(), node::getNeighborIter(), GraphAbstractionConstants::kParent, and node::nodeNeighborNext().

Referenced by createConnectivityGraph().

◆ createAbstractGraph()

void ClusterAbstraction::createAbstractGraph ( )

private

Definition at line 180 of file ClusterAbstraction.cpp.

References addAbsNodes(), computeClusterPaths(), createConnectivityGraph(), setUpParents(), and verbose.

Referenced by ClusterAbstraction().

◆ createClustersAndEntrances()

void ClusterAbstraction::createClustersAndEntrances ( )

private

create clusters on the abstract level and create corresponding entrances.

Definition at line 125 of file ClusterAbstraction.cpp.

References addCluster(), clusterSize, columns, createHorizEntrances(), createVertEntrances(), Map::GetMapHeight(), Map::GetMapWidth(), min(), rows, and verbose.

Referenced by ClusterAbstraction().

◆ createConnectivityGraph()

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.

Definition at line 933 of file ClusterAbstraction.cpp.

References Graph::AddNode(), connectedBFS(), Graph::getNodeIter(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kNodeBlocked, GraphAbstractionConstants::kNumAbstractedNodes, GraphAbstractionConstants::kParent, GraphAbstractionConstants::kUnknownPosition, GraphAbstractionConstants::kXCoordinate, node::SetLabelF(), and node::SetLabelL().

Referenced by createAbstractGraph().

◆ createHorizEntrances()

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.

Definition at line 221 of file ClusterAbstraction.cpp.

References addEntrance(), Graph::FindEdge(), Map::GetNodeNum(), HORIZONTAL, and MAX_ENTRANCE_WIDTH.

Referenced by createClustersAndEntrances().

◆ createVertEntrances()

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

Definition at line 284 of file ClusterAbstraction.cpp.

References addEntrance(), Graph::FindEdge(), Map::GetNodeNum(), MAX_ENTRANCE_WIDTH, and VERTICAL.

Referenced by createClustersAndEntrances().

◆ getCachedPath()

path * ClusterAbstraction::getCachedPath ( edge * e )

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

Definition at line 1263 of file ClusterAbstraction.cpp.

References paths, and temp.

◆ getCluster()

Cluster & ClusterAbstraction::getCluster ( int id )

private

get the cluster from it's ID

Definition at line 635 of file ClusterAbstraction.cpp.

References clusters.

Referenced by abstractionBFS(), addAbsNodes(), insertNode(), and removeNodes().

◆ getClusterId()

int ClusterAbstraction::getClusterId	(	int	row,
		int	col
	)		const

private

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

Definition at line 615 of file ClusterAbstraction.cpp.

References columns.

Referenced by getClusterIdFromCoord(), and linkEntrancesAndClusters().

◆ getClusterIdFromCoord()

int ClusterAbstraction::getClusterIdFromCoord	(	int	row,
		int	col
	)		const

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

Definition at line 624 of file ClusterAbstraction.cpp.

References clusterSize, and getClusterId().

Referenced by getClusterIdFromNode(), insertNode(), and removeNodes().

◆ getClusterIdFromNode()

int ClusterAbstraction::getClusterIdFromNode ( node * n )

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

Only works for map

Definition at line 671 of file ClusterAbstraction.cpp.

References getClusterIdFromCoord(), node::GetLabelF(), node::GetLabelL(), Map::GetPointFromCoordinate(), GraphAbstractionConstants::kAbstractionLevel, GraphAbstractionConstants::kFirstData, GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, and point3d.

Referenced by abstractionBFS(), and setUpParents().

◆ getClusterSize()

int ClusterAbstraction::getClusterSize ( )

inline

Definition at line 129 of file ClusterAbstraction.h.

References clusterSize.

◆ getLowLevelNode()

node * ClusterAbstraction::getLowLevelNode ( node * abstract )

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

Definition at line 1274 of file ClusterAbstraction.cpp.

References Map::GetPointFromCoordinate(), GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, and point3d.

Referenced by setUpParents().

◆ insertNode()

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

Definition at line 1015 of file ClusterAbstraction.cpp.

◆ linkEntrancesAndClusters()

void ClusterAbstraction::linkEntrancesAndClusters ( )

private

from original HPA* abstiling.cpp

Definition at line 351 of file ClusterAbstraction.cpp.

References entrances, getClusterId(), Entrance::getCol(), Entrance::getOrientation(), Entrance::getRow(), HORIZONTAL, Entrance::setCluster1Id(), Entrance::setCluster2Id(), verbose, and VERTICAL.

Referenced by ClusterAbstraction().

◆ min()

int ClusterAbstraction::min	(	int	i,
		int	j
	)

private

Definition at line 168 of file ClusterAbstraction.cpp.

Referenced by createClustersAndEntrances().

◆ nodeExists()

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

Definition at line 649 of file ClusterAbstraction.cpp.

References Cluster::getIthNodeNum(), node::GetLabelF(), Graph::GetNode(), Cluster::GetNumNodes(), GraphAbstractionConstants::kXCoordinate, and GraphAbstractionConstants::kYCoordinate.

Referenced by addAbsNodes(), insertNode(), and removeNodes().

◆ OpenGLDraw()

void ClusterAbstraction::OpenGLDraw ( ) const

virtual

Definition at line 1323 of file ClusterAbstraction.cpp.

References clusterSize, Map::GetMapHeight(), Map::GetMapWidth(), and Map::GetOpenGLCoord().

◆ Pathable()

bool ClusterAbstraction::Pathable	(	node *	start,
		node *	goal
	)

Check if there is a path between two nodes.

Definition at line 984 of file ClusterAbstraction.cpp.

References node::GetLabelL(), and GraphAbstractionConstants::kParent.

◆ printMapCoord()

void ClusterAbstraction::printMapCoord ( node * n )

Definition at line 1286 of file ClusterAbstraction.cpp.

References node::GetLabelF(), node::GetLabelL(), Graph::GetNode(), Map::GetPointFromCoordinate(), GraphAbstractionConstants::kParent, GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, point3d, px2, and py2.

Referenced by printPathAsCoord().

◆ printPathAsCoord()

void ClusterAbstraction::printPathAsCoord ( path * p )

Definition at line 1307 of file ClusterAbstraction.cpp.

References path::n, path::next, and printMapCoord().

◆ RemoveEdge()

void ClusterAbstraction::RemoveEdge	(	edge *	,
		unsigned int
	)

inline

Definition at line 134 of file ClusterAbstraction.h.

◆ RemoveNode()

void ClusterAbstraction::RemoveNode ( node * )

inline

Definition at line 133 of file ClusterAbstraction.h.

◆ removeNodes()

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.

Definition at line 1169 of file ClusterAbstraction.cpp.

References node::edgeIterNext(), getCluster(), getClusterIdFromCoord(), node::getEdgeIter(), node::GetLabelF(), node::GetLabelL(), node::GetNum(), node::GetNumEdges(), Graph::GetNumNodes(), Map::GetPointFromCoordinate(), GraphAbstractionConstants::kParent, GraphAbstractionConstants::kXCoordinate, GraphAbstractionConstants::kYCoordinate, newPaths, nodeExists(), point3d, px2, py2, Graph::RemoveEdge(), Graph::RemoveNode(), temp, and verbose.

◆ RepairAbstraction()

void ClusterAbstraction::RepairAbstraction ( )

inline

Definition at line 137 of file ClusterAbstraction.h.

◆ setUpParents()

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 MapSectorAbstraction.cpp

Definition at line 695 of file ClusterAbstraction.cpp.

Referenced by createAbstractGraph().

◆ VerifyHierarchy()

void ClusterAbstraction::VerifyHierarchy ( )

inline

Definition at line 131 of file ClusterAbstraction.h.

Member Data Documentation

◆ clusters

std::vector<Cluster> ClusterAbstraction::clusters

private

Definition at line 169 of file ClusterAbstraction.h.

Referenced by addCluster(), computeClusterPaths(), getCluster(), and setUpParents().

◆ clusterSize

int ClusterAbstraction::clusterSize

private

Definition at line 165 of file ClusterAbstraction.h.

Referenced by Clone(), createClustersAndEntrances(), getClusterIdFromCoord(), getClusterSize(), and OpenGLDraw().

◆ columns

int ClusterAbstraction::columns

private

Definition at line 167 of file ClusterAbstraction.h.

Referenced by createClustersAndEntrances(), and getClusterId().

◆ entrances

std::vector<Entrance> ClusterAbstraction::entrances

private

Definition at line 170 of file ClusterAbstraction.h.

Referenced by addAbsNodes(), addEntrance(), and linkEntrancesAndClusters().

◆ newPaths

std::vector<path*> ClusterAbstraction::newPaths

private

Definition at line 173 of file ClusterAbstraction.h.

Referenced by insertNode(), and removeNodes().

◆ paths

clusterUtil::PathLookupTable ClusterAbstraction::paths

private

Definition at line 171 of file ClusterAbstraction.h.

Referenced by computeClusterPaths(), getCachedPath(), and ~ClusterAbstraction().

◆ rows

int ClusterAbstraction::rows

private

Definition at line 166 of file ClusterAbstraction.h.

Referenced by createClustersAndEntrances().

◆ temp

clusterUtil::PathLookupTable ClusterAbstraction::temp

private

Definition at line 172 of file ClusterAbstraction.h.

Referenced by getCachedPath(), insertNode(), removeNodes(), and ~ClusterAbstraction().

The documentation for this class was generated from the following files:

/home/sturtevant/nightly/hog2/abstraction/ClusterAbstraction.h
/home/sturtevant/nightly/hog2/abstraction/ClusterAbstraction.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ClusterAbstraction()

◆ ~ClusterAbstraction()

Member Function Documentation

◆ abstractionBFS()

◆ addAbsNodes()

◆ addCluster()

◆ AddEdge()

◆ addEntrance()

◆ AddNode()

◆ buildNodeIntoParent()

◆ Clone()

◆ computeClusterPaths()

◆ connectedBFS()

◆ createAbstractGraph()

◆ createClustersAndEntrances()

◆ createConnectivityGraph()

◆ createHorizEntrances()

◆ createVertEntrances()

◆ getCachedPath()

◆ getCluster()

◆ getClusterId()

◆ getClusterIdFromCoord()

◆ getClusterIdFromNode()

◆ getClusterSize()

◆ getLowLevelNode()

◆ insertNode()

◆ linkEntrancesAndClusters()

◆ min()

◆ nodeExists()

◆ OpenGLDraw()

◆ Pathable()

◆ printMapCoord()

◆ printPathAsCoord()

◆ RemoveEdge()

◆ RemoveNode()

◆ removeNodes()

◆ RepairAbstraction()

◆ setUpParents()

◆ VerifyHierarchy()

Member Data Documentation

◆ clusters

◆ clusterSize

◆ columns

◆ entrances

◆ newPaths

◆ paths

◆ rows

◆ temp