astar/Node.h

Header of the layer astar, in the group Data structures; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
Node	A node of the search graph

Functions

template<class Cost>
constexpr Cost PBeFS_di_unipi_it::infinite_cost(void) noexcept

the largest value of a cost type, used as “no incumbent yet”

template<class Cost>
constexpr std::uint64_t PBeFS_di_unipi_it::packed_fg(Cost g, Cost h) noexcept

with integer costs, f = g + h in the high half of a word and the complement of g in the low one, so that the smaller word has the smaller f and, on the ties of f, the larger g, as the OPEN of AStar

Pre:

\( 0 \leq g \) and \( 0 \leq g + h < 2^{32} \)

template<class NodeT>
auto PBeFS_di_unipi_it::trace_path(const NodeT *goal)

the states from the root to goal, following the parent pointers

Description of the header

Header file for the class template Node, a node of the search graph, for the class template NodePool, the arena the nodes are allocated from, taken from the set of data structures chosen [see Structures.h], and for the infinite cost and the path to a goal.

A NodePool< NodeT > has a constructor taking the number of nodes of a chunk, allocate(), which returns a new uninitialized node, size() and bytes(); the nodes are never freed one by one, and their addresses never change, which the parent pointers rely on.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli