|
| | 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
|
| state_type | initial_state (void) const noexcept |
| | the start cell
|
| bool | is_goal (state_type s) const noexcept |
| | true if s is the goal cell
|
| std::uint64_t | hash (state_type s) const noexcept |
| | the hash of a cell: its index, mixed
|
| cost_type | heuristic (state_type s) const noexcept |
| | the Manhattan (4 moves) or octile (8 moves) distance to the goal
|
| template<class F> |
| 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
|
| std::size_t | num_features (void) const noexcept |
| | the number of features: the columns and the rows
|
| template<class F> |
| 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
|
| std::size_t | num_abstract_features (void) const noexcept |
| | the number of abstract features: the columns and rows of blocks
|
| std::size_t | abstract_feature (std::size_t i) const noexcept |
| | the abstract feature of a feature: the column or row of its block
|
| std::uint64_t | abstract_state (state_type s) const noexcept |
| | the abstract state of AHDA*: the block of the cell
|
| std::size_t | num_nblocks (void) const noexcept |
| | the number of nblocks
|
| 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> |
| void | for_each_nblock_successor (std::size_t b, F &&f) const |
| | calls f( b' ) for each nblock b' next to the nblock b
|
| int | nblock_side (void) const noexcept |
| | the side of the nblocks
|
| int | block (void) const noexcept |
| | the side of the blocks of AZH and AHDA*
|
| cost_type | pairwise_heuristic (state_type s, state_type t) const noexcept |
| | the heuristic of PA*SE: the distance between two cells
|
| std::uint64_t | perfect_hash (state_type s) const noexcept |
| | the perfect hash of HDA*[P]: the cell index
|
| state_type | index (int x, int y) const noexcept |
| | the cell index of ( x , y )
|
template<int Moves = 4>
class PBeFS_di_unipi_it::Grid< Moves >
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.
template<int Moves = 4>
| Grid |
( |
const GridMap & | map, |
|
|
int | sx, |
|
|
int | sy, |
|
|
int | gx, |
|
|
int | gy, |
|
|
int | block = 100, |
|
|
int | nblock_side = 20 ) |
|
inline |
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.
1.15.0