|
| virtual | ~Pathfinder () |
| |
| virtual float | costOfEdge (const Node &A, const Node &B) const |
| | Returns the exact cost of traversing the directed edge from A to B, which are two nodes known to be neighbors. More...
|
| |
| virtual float | estimateCost (const Node &A, const Node &B) const =0 |
| | Returns an estimate of the cost of traversing from A to B. More...
|
| |
| virtual bool | findPath (const Node &start, const Node &goal, Path &path, StepTable &bestPathTo) const |
| | Finds a good path from start to goal, and returns it as a list of nodes to visit. More...
|
| |
| bool | findPath (const Node &start, const Node &goal, Path &path) const |
| |
| virtual void | getNeighbors (const Node &N, NodeList &neighbors) const =0 |
| | Identifies all nodes (directionally) adjacent to N. More...
|
| |
template<typename Node, class HashFunc = HashTrait<Node>>
class G3D::Pathfinder< Node, HashFunc >
Finds good paths between nodes in an arbitrary directed graph.
Subclass and override estimateCost(), costOfEdge(), and getNeighbors().
- Parameters
-
| Node | must support hashCode (or provide a HashFunc) and operator== (see G3D::Table). Two Nodes must be == if and only if they describe the same location in the graph. For a regular grid, use a class like G3D::Point2int32. For an arbitrary graph, Node may be a pointer or shared_ptr to a node, or an arbitrary unique ID. Node should be a relatively small object because it will be copied a lot during Pathfinding. |
- Referenced Code: Ported from Morgan McGuire's Javascript implementation
- at http://codeheartjs.com/examples/pathfinding/findPath.js
Example:
class Map :
public Pathfinder<Point2int32> {
protected:
shared_ptr<Image> m_grid;
}
if (isOpen(P)) { neighborArray.append(P); }
}
public:
}
return abs(A.x - B.x) +
abs(A.y - B.y);
}
neighborArray.clear();
}
const shared_ptr<Image>& image = m_grid->clone();
printf("Path has length %d\n", path.length());
for (int i = 0; i < path.length(); ++i) {
}
image->save(filename);
}
};
int main(int argc, char** argv) {
Map::Path path;
Map::StepTable bestPathTo;
if (map.findPath(A, B, path, bestPathTo)) {
map.drawPath(A, B, path, "result.png");
} else {
printf("No path found!\n");
}
for (Map::StepTable::Iterator it = bestPathTo.begin(); it.hasMore(); ++it) {
printf(" %s <- %s\n", it->value.to.toString().c_str(), it->value.from.isNull() ? "nullptr" : it->value.from.node().toString().c_str());
}
return 0;
}
template<typename Node , class HashFunc = HashTrait<Node>>
| virtual float G3D::Pathfinder< Node, HashFunc >::costOfEdge |
( |
const Node & |
A, |
|
|
const Node & |
B |
|
) |
| const |
|
inlinevirtual |
Returns the exact cost of traversing the directed edge from A to B, which are two nodes known to be neighbors.
The default implementation returns 1.0f for all pairs.
Referenced by G3D::Pathfinder< Node, HashFunc >::findPath().
template<typename Node , class HashFunc = HashTrait<Node>>
| virtual bool G3D::Pathfinder< Node, HashFunc >::findPath |
( |
const Node & |
start, |
|
|
const Node & |
goal, |
|
|
Path & |
path, |
|
|
StepTable & |
bestPathTo |
|
) |
| const |
|
inlinevirtual |
Finds a good path from start to goal, and returns it as a list of nodes to visit.
Returns null if there is no path.
The default implementation uses the A* algorithm.
For visualization purposes, findPathBestPathTo contains information about the other explored paths when the function returns.
- Parameters
-
| bestPathTo | Maps each Node to the Step on the best known path to that Node. Provided for visualization purposes. Cleared at the start. Note that the overloaded version of findPath() does not require a StepTable. |
- Returns
- True if a path was found, otherwise false
Referenced by G3D::Pathfinder< Node, HashFunc >::findPath().
Contents
