PBeFS
Parallel Best-First Search
Loading...
Searching...
No Matches
GridAdjacency.h
Go to the documentation of this file.
1/*--------------------------------------------------------------------------*/
2/*-------------------------- File GridAdjacency.h --------------------------*/
3/*--------------------------------------------------------------------------*/
17/*--------------------------------------------------------------------------*/
18/*------------------------------ DEFINITIONS -------------------------------*/
19/*--------------------------------------------------------------------------*/
20
21#ifndef __PBeFS_ads_GridAdjacency
22 #define __PBeFS_ads_GridAdjacency
23 /* self-identification: #endif at the end of the file */
24
25/*--------------------------------------------------------------------------*/
26/*-------------------------------- INCLUDES --------------------------------*/
27/*--------------------------------------------------------------------------*/
28
29#include <cstdint>
30
31#include <optional>
32
33#include <type_traits>
34
35#include "ADS/graph/GridGraph.h"
36
37/*--------------------------------------------------------------------------*/
38/*------------------------------- NAMESPACE --------------------------------*/
39/*--------------------------------------------------------------------------*/
40
42namespace PBeFS_di_unipi_it
43{
44
45/*--------------------------------------------------------------------------*/
46/*-------------------------- CLASS GridAdjacency ---------------------------*/
47/*--------------------------------------------------------------------------*/
50
56
57template< int Moves >
58class GridAdjacency {
59
60/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
61
62 public:
63
65 using cost_type = std::conditional_t< Moves == 4 , int , double >;
66
68
69 explicit GridAdjacency( const GridMap & map )
70 : f_w( map.width() ) ,
71 f_g( map.height() , map.width() , map.costs() ,
72 Moves == 4 ? ADS::GridMoves::FOUR : ADS::GridMoves::EIGHT ,
73 ADS::Corners::NO_CUT , cost_type( 1 ) ,
74 Moves == 4 ? std::optional< cost_type >() :
75 std::optional< cost_type >( cost_type( grid_sqrt2 ) ) ,
76 ADS::MoveCost::LEFT ) {}
77
78/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
81
82 template< class F >
83 void for_each( std::uint32_t s , int x , int y , F && f ) const {
84 const int u = int( s ) , row = u - x;
85 f_g.forEachEdge( u , [ & ]( int v , cost_type c ) {
86 const int dy = v < row ? -1 : ( v >= row + f_w ? 1 : 0 );
87 f( std::uint32_t( v ) , v - u - dy * f_w + x , y + dy , c );
88 } );
89 }
90
91/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
92
93 private:
94
95 int f_w;
96 ADS::GridGraph< cost_type , std::uint8_t > f_g;
97
98 }; // end( class( GridAdjacency ) )
99
100/*--------------------------------------------------------------------------*/
101
102} // end( namespace PBeFS_di_unipi_it )
103
104/*--------------------------------------------------------------------------*/
105
106#endif /* __PBeFS_ads_GridAdjacency */
107
108/*--------------------------------------------------------------------------*/
109/*------------------------ End File GridAdjacency.h ------------------------*/
110/*--------------------------------------------------------------------------*/
PBeFS_di_unipi_it::GridAdjacency::GridAdjacency
GridAdjacency(const GridMap &map)
constructor, copying the costs of the cells of the map
Definition GridAdjacency.h:69
PBeFS_di_unipi_it::GridAdjacency::cost_type
std::conditional_t< Moves==4, int, double > cost_type
the cost of a move: an integer with 4 moves, a real with 8
Definition GridAdjacency.h:65
PBeFS_di_unipi_it::GridAdjacency::for_each
void for_each(std::uint32_t s, int x, int y, F &&f) const
calls f( t , x' , y' , c ) for each free cell t = ( x' , y' ) next to the free cell s = ( x ,...
Definition GridAdjacency.h:83
PBeFS_di_unipi_it::GridMap
a rectangular map of cells, each with a cost of traversal
Definition Grid.h:73
PBeFS_di_unipi_it
namespace for the Parallel Best-First Search library
Definition AStar.h:83
PBeFS_di_unipi_it::grid_sqrt2
constexpr double grid_sqrt2
, the cost of a diagonal move per unit of cost of a cell
Definition Grid.h:159