Grid

Declared in astar/Grid.h; the same class on the site of Doxygen.

template<int Moves = 4>
class Grid

pathfinding on a GridMap with 4 (Moves == 4) or 8 (Moves == 8) moves

A state is the index \( y W + x \) of a cell. With 4 moves the costs are integers and leaving a cell costs its cost; with 8 moves a diagonal move costs \( \sqrt{2} \) times the cost of the cell left, and it is allowed only if both the cells it cuts are free [see GridAdjacency]. The heuristic is the Manhattan distance (4 moves) or the octile distance (8 moves) times the smallest cost of a free cell.

The features of Zobrist hashing are the column and the row of the cell; the abstract features of Abstract Zobrist hashing are the column and the row of the block of \( b \times b \) cells containing it, \( b \) being block(), and the abstract state of AHDA* is that block, which for this domain coincide [see Jinnai and Fukunaga, JAIR 2017, section 4.1]. The nblocks of PBNF are the blocks of \( s \times s \) cells, \( s \) being nblock_side(), and the perfect hash is the index of the cell.

Public Types

using state_type = std::uint32_t

a cell index

using cost_type = std::conditional_t<Moves == 4, int, double>

the cost type

Public Functions

inline Grid(const GridMap &map, int sx, int sy, int gx, int gy, int block = 100, int nblock_side = 20)

constructor, taking the map (which must outlive the Grid) and the cells

Constructs the instance of going from ( sx , sy ) to ( gx , gy ) on map; block is the side of the blocks of AZH and AHDA*, and nblock_side that of the nblocks of PBNF. Throws std::invalid_argument if the start or the goal is blocked.

inline state_type initial_state(void) const noexcept

the start cell

inline bool is_goal(state_type s) const noexcept

true if s is the goal cell

inline std::uint64_t hash(state_type s) const noexcept

the hash of a cell: its index, mixed

inline cost_type heuristic(state_type s) const noexcept

the Manhattan (4 moves) or octile (8 moves) distance to the goal

template<class F>
inline void for_each_successor(state_type s, cost_type, F &&f) const

calls f( t , c , h( t ) ) for each free cell t next to s

inline std::size_t num_features(void) const noexcept

the number of features: the columns and the rows

template<class F>
inline void for_each_feature(state_type s, F &&f) const

calls f( x ) and f( W + y ) for the cell \( ( x , y ) \) of the state s

inline std::size_t num_abstract_features(void) const noexcept

the number of abstract features: the columns and rows of blocks

inline std::size_t abstract_feature(std::size_t i) const noexcept

the abstract feature of a feature: the column or row of its block

inline std::uint64_t abstract_state(state_type s) const noexcept

the abstract state of AHDA*: the block of the cell

inline std::size_t num_nblocks(void) const noexcept

the number of nblocks

inline std::size_t nblock(state_type s) const noexcept

the nblock of PBNF: the block of \( s \times s \) cells, \( s \) being nblock_side()

template<class F>
inline void for_each_nblock_successor(std::size_t b, F &&f) const

calls f( b’ ) for each nblock b’ next to the nblock b

inline int nblock_side(void) const noexcept

the side of the nblocks

inline int block(void) const noexcept

the side of the blocks of AZH and AHDA*

inline cost_type pairwise_heuristic(state_type s, state_type t) const noexcept

the heuristic of PA*SE: the distance between two cells

inline std::uint64_t perfect_hash(state_type s) const noexcept

the perfect hash of HDA*[P]: the cell index

inline state_type index(int x, int y) const noexcept

the cell index of ( x , y )