AStar Namespace Reference

Holds data structures for search context, results, and implementation of A★ path planning algorithm, see AStar::astar. More...

Classes
struct	Node
	Stores user state along with search context. More...
struct	StateCmp
	For efficient lookup of existance of states in open or closed list, uses user's Cmp on the user state within the search node. More...
struct	StateHash
	Calls State::hash(), which should return value distributed over size_t. More...
struct	StateEq
	Tests equality of states using State::operator==. More...
struct	Results
	Search results, including unexpanded nodes. More...
Functions
template<class Context , class State , class Expand , class Heuristic , class Validate , class Cmp >
Results< State, Cmp >	astar (const Context &ctxt, const State &initial, const State &goal, Expand expand, Heuristic heuristic, Validate validate, const Cmp &, float bound=0)
	A★ search using custom comparison on State type.
template<class Context , class State , class Expand , class Heuristic , class Validate >
Results< State, std::less < State > >	astar (const Context &ctxt, const State &initial, const State &goal, Expand expand, Heuristic heuristic, Validate validate, float bound=0)
	A★ search using operator< to sort user State type.
template<class Context , class State >
Results< State, std::less < State > >	astar (const Context &ctxt, const State &initial, const State &goal, float bound=0)
	A★ search using operator< to sort user State type, assumes Context has functions named "expand" and "heuristic".
template<class Node , class State >
void	reconstruct (const Node *n, std::vector< State > &path, size_t depth=1)
	constructs path by following parent pointers from n; the specified node is included in the path

---

Detailed Description

Holds data structures for search context, results, and implementation of A★ path planning algorithm, see AStar::astar.

---

Function Documentation

template<class Context , class State >

Results<State, std::less<State> > AStar::astar	(	const Context &	ctxt,
		const State &	initial,
		const State &	goal,
		float	bound = 0
	)

A★ search using operator< to sort user State type, assumes Context has functions named "expand" and "heuristic".

Definition at line 174 of file AStar.h.

template<class Context , class State , class Expand , class Heuristic , class Validate >

Results<State, std::less<State> > AStar::astar	(	const Context &	ctxt,
		const State &	initial,
		const State &	goal,
		Expand	expand,
		Heuristic	heuristic,
		Validate	validate,
		float	bound = 0
	)

A★ search using operator< to sort user State type.

Expand is expected to be compatible with const std::vector<std::pair<float,State> >& (Context::*expand)(const State& st, const State& goal) const
Heuristic is expected to be compatible with float (Context::*heuristic)(const State& st, const State& goal) const

Definition at line 167 of file AStar.h.

template<class Context , class State , class Expand , class Heuristic , class Validate , class Cmp >

Results<State,Cmp> AStar::astar	(	const Context &	ctxt,
		const State &	initial,
		const State &	goal,
		Expand	expand,
		Heuristic	heuristic,
		Validate	validate,
		const Cmp &	,
		float	bound = 0
	)

A★ search using custom comparison on State type.

Expand is expected to be compatible with const std::vector<std::pair<float,State> >& (Context::*expand)(const State& st, const State& goal) const
Heuristic is expected to be compatible with float (Context::*heuristic)(const State& st, const State& goal) const
The Cmp argument is not actually used, but the function accepts an instance so you can avoid specifying all of the template parameters

Definition at line 102 of file AStar.h.

Referenced by astar().

template<class Node , class State >

void AStar::reconstruct	(	const Node *	n,
		std::vector< State > &	path,
		size_t	depth = 1
	)

constructs path by following parent pointers from n; the specified node is included in the path

Definition at line 180 of file AStar.h.

Referenced by astar().