#include <clusterAbstraction.h>
Inheritance diagram for clusterAbstraction:
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 |
Source code based on HPA* code found at http://www.cs.ualberta.ca/~adib/Home/Download/hpa.tgz
|
create a cluster abstraction for the given map. Clusters are square, with height = width = clustersize. |
|
|
|
'borrowed' from mapQuadTreeAbstraction.cpp
|
|
Add a node for cluster for each entrance.
|
|
|
|
add edge to abstraction
Implements graphAbstraction. |
|
|
|
add node to abstraction
Implements graphAbstraction. |
|
|
|
return a new abstraction map of the same type as this map abstraction
Implements mapAbstraction. |
|
|
|
|
|
|
|
create clusters on the abstract level and create corresponding entrances.
|
|
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. |
|
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. |
|
based on the function from HPA* abstiling.cpp with the same name create vertical entrances |
|
get the map-level path that corresponds to abstract edge e
|
|
get the cluster from it's ID
|
|
given a cluster row and column (NOT map row/column), return the cluster's ID.
|
|
given a node's coordinates, find the cluster it's in
|
|
Given a map node, return the ID of the cluster it's in. Only works for map |
|
|
|
get the map-level node that is at the (x,y) coordinates of the abstract node
|
|
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 |
|
from original HPA* abstiling.cpp
|
|
|
|
check if a node already exists in a certain cluster with a particular set of coordinates
|
|
Reimplemented from mapAbstraction. |
|
Check if there is a path between two nodes.
Implements graphAbstraction. |
|
|
|
|
|
remove edge from abstraction
Implements graphAbstraction. |
|
remove node from abstraction
Implements graphAbstraction. |
|
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. |
|
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. |
|
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 |
|
verify that the hierarchy is consistent
Implements graphAbstraction. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|