Grid.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------------ File Grid.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_Grid
 #define __PBeFS_Grid
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cmath>
 
#include <cstddef>
 
#include <cstdint>
 
#include <cstdlib>
 
#include <iosfwd>
 
#include <stdexcept>
 
#include <type_traits>
 
#include <vector>
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/astar/Structures.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS GridMap ------------------------------*/
/*--------------------------------------------------------------------------*/

 
class GridMap {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:

 
 GridMap( int width = 0 , int height = 0 );
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] static GridMap random( int width , int height , double p ,
                                      std::uint64_t seed ,
                                      int max_cost = 1 );
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] static GridMap read_movingai( std::istream & in );
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int width( void ) const noexcept { return( f_width ); }

 
 [[nodiscard]] int height( void ) const noexcept { return( f_height ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int cost( int x , int y ) const noexcept {
  if( ( x < 0 ) || ( y < 0 ) || ( x >= f_width ) || ( y >= f_height ) )
   return( 0 );
  return( v_cost[ std::size_t( y ) * f_width + x ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void set_cost( int x , int y , int c );
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int min_cost( void ) const noexcept;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const std::vector< std::uint8_t > & costs( void ) const
  noexcept {
  return( v_cost );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 int f_width;                                    
 int f_height;                                   
 std::vector< std::uint8_t > v_cost;             
 
 };  // end( class( GridMap ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- CONSTANTS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
inline constexpr double grid_sqrt2 = 1.41421356237309504880;
 
/*--------------------------------------------------------------------------*/
 
#if defined( PBEFS_STRUCTURES_STD ) || defined( PBEFS_STRUCTURES_BOOST )
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS GridAdjacency ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int Moves >
class GridAdjacency {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:

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

 
 explicit GridAdjacency( const GridMap & map ) : f_map( map ) {}
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each( std::uint32_t , int x , int y , F && f ) const {
  static constexpr int dx[ 8 ] = { 0 , -1 , 1 , 0 , -1 , 1 , -1 , 1 };
  static constexpr int dy[ 8 ] = { -1 , 0 , 0 , 1 , -1 , -1 , 1 , 1 };
  const int w = f_map.width();
  const cost_type c = cost_type( f_map.cost( x , y ) );
  for( int k = 0 ; k < Moves ; ++k ) {
   const int nx = x + dx[ k ] , ny = y + dy[ k ];
   if( ! f_map.cost( nx , ny ) )
    continue;
   if( ( k >= 4 ) &&                  // a diagonal: no corner cutting
       ( ! f_map.cost( nx , y ) || ! f_map.cost( x , ny ) ) )
    continue;
   f( std::uint32_t( ny ) * std::uint32_t( w ) + std::uint32_t( nx ) ,
      nx , ny , k >= 4 ? cost_type( c * grid_sqrt2 ) : c );
   }
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 const GridMap & f_map;                                         
 
 };  // end( class( GridAdjacency ) )
 
#endif  /* PBEFS_STRUCTURES_STD and PBEFS_STRUCTURES_BOOST */
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
/*------------------ THE ADJACENCY OF THE OTHER STRUCTURES -----------------*/
/*--------------------------------------------------------------------------*/
 
#if defined( PBEFS_STRUCTURES_ADS )
 #include "PBeFS/astar/structures/ads/GridAdjacency.h"
#endif
 
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------------- CLASS Grid -------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int Moves = 4 >
class Grid {
 
 static_assert( ( Moves == 4 ) || ( Moves == 8 ) ,
                "Grid: the moves are either 4 or 8" );
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using state_type = std::uint32_t;                     
 using cost_type = std::conditional_t< Moves == 4 , int , double >;
 
/*------------------------------ CONSTRUCTOR -------------------------------*/


 
 Grid( const GridMap & map , int sx , int sy , int gx , int gy ,
       int block = 100 , int nblock_side = 20 )
  : f_map( map ) , f_adj( map ) , f_w( map.width() ) , f_h( map.height() ) ,
    f_start( index( sx , sy ) ) , f_goal( index( gx , gy ) ) ,
    f_gx( gx ) , f_gy( gy ) , f_min( map.min_cost() ) ,
    f_block( block ) , f_nside( nblock_side ) {
  if( ! map.cost( sx , sy ) || ! map.cost( gx , gy ) )
   throw( std::invalid_argument( "Grid::Grid: blocked start or goal" ) );
  if( ( block <= 0 ) || ( nblock_side <= 0 ) )
   throw( std::invalid_argument( "Grid::Grid: blocks of side <= 0" ) );
  f_bw = ( f_w + f_block - 1 ) / f_block;
  f_bh = ( f_h + f_block - 1 ) / f_block;
  f_nw = ( f_w + f_nside - 1 ) / f_nside;
  f_nh = ( f_h + f_nside - 1 ) / f_nside;
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] state_type initial_state( void ) const noexcept {
  return( f_start );
  }

 
 [[nodiscard]] bool is_goal( state_type s ) const noexcept {
  return( s == f_goal );
  }

 
 [[nodiscard]] std::uint64_t hash( state_type s ) const noexcept {
  return( ADS::splitmix64( s ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] cost_type heuristic( state_type s ) const noexcept {
  return( distance( int( s % f_w ) , int( s / f_w ) , f_gx , f_gy ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( state_type s , cost_type , F && f ) const {
  const int x = int( s % f_w ) , y = int( s / f_w );
  f_adj.for_each( s , x , y , [ & ]( state_type t , int nx , int ny ,
                                     cost_type c ) {
   f( t , c , distance( nx , ny , f_gx , f_gy ) );
   } );
  }
 
/*---------------------- FEATURES FOR ZOBRIST HASHING ----------------------*/
 
 [[nodiscard]] std::size_t num_features( void ) const noexcept {
  return( std::size_t( f_w ) + f_h );
  }

 
 template< class F >
 void for_each_feature( state_type s , F && f ) const {
  f( std::size_t( s % f_w ) );
  f( std::size_t( f_w ) + s / f_w );
  }

 
 [[nodiscard]] std::size_t num_abstract_features( void ) const noexcept {
  return( std::size_t( f_bw ) + f_bh );
  }

 
 [[nodiscard]] std::size_t abstract_feature( std::size_t i ) const noexcept
 {
  if( i < std::size_t( f_w ) )
   return( i / f_block );
  return( std::size_t( f_bw ) + ( i - f_w ) / f_block );
  }
 
/*--------------------------- STATE ABSTRACTIONS ---------------------------*/
 
 [[nodiscard]] std::uint64_t abstract_state( state_type s ) const noexcept {
  return( std::uint64_t( s / f_w / f_block ) * f_bw + s % f_w / f_block );
  }

 
 [[nodiscard]] std::size_t num_nblocks( void ) const noexcept {
  return( std::size_t( f_nw ) * f_nh );
  }

 
 [[nodiscard]] std::size_t nblock( state_type s ) const noexcept {
  return( std::size_t( s / f_w / f_nside ) * f_nw + s % f_w / f_nside );
  }

 
 template< class F >
 void for_each_nblock_successor( std::size_t b , F && f ) const {
  const int bx = int( b % f_nw ) , by = int( b / f_nw );
  for( int dy = -1 ; dy <= 1 ; ++dy )
   for( int dx = -1 ; dx <= 1 ; ++dx ) {
    if( ( ! dx && ! dy ) || ( ( Moves == 4 ) && dx && dy ) )
     continue;
    const int nx = bx + dx , ny = by + dy;
    if( ( nx >= 0 ) && ( ny >= 0 ) && ( nx < f_nw ) && ( ny < f_nh ) )
     f( std::size_t( ny ) * f_nw + nx );
    }
  }

 
 [[nodiscard]] int nblock_side( void ) const noexcept { return( f_nside ); }

 
 [[nodiscard]] int block( void ) const noexcept { return( f_block ); }
 
/*---------------------- OTHER HEURISTICS AND HASHES -----------------------*/
 
 [[nodiscard]] cost_type pairwise_heuristic( state_type s , state_type t )
  const noexcept {
  return( distance( int( s % f_w ) , int( s / f_w ) ,
                    int( t % f_w ) , int( t / f_w ) ) );
  }

 
 [[nodiscard]] std::uint64_t perfect_hash( state_type s ) const noexcept {
  return( s );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] state_type index( int x , int y ) const noexcept {
  return( state_type( y ) * state_type( f_w ) + state_type( x ) );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 static constexpr double c_sqrt2 = grid_sqrt2;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the Manhattan or octile distance times the smallest cost
 
 [[nodiscard]] cost_type distance( int x , int y , int u , int v )
  const noexcept {
  const int ax = std::abs( x - u ) , ay = std::abs( y - v );
  if constexpr( Moves == 4 )
   return( ( ax + ay ) * f_min );
  else
   return( ( std::max( ax , ay ) + ( c_sqrt2 - 1 ) * std::min( ax , ay ) )
           * f_min );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const GridMap & f_map;                           
 GridAdjacency< Moves > f_adj;                    
 int f_w;                                         
 int f_h;                                         
 state_type f_start;                              
 state_type f_goal;                               
 int f_gx;                                        
 int f_gy;                                        
 int f_min;                                  
 int f_block;                          
 int f_nside;                          
 int f_bw;                             
 int f_bh;                             
 int f_nw;                             
 int f_nh;                             
 
 };  // end( class( Grid ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_Grid */
 
/*--------------------------------------------------------------------------*/
/*---------------------------- End File Grid.h -----------------------------*/
/*--------------------------------------------------------------------------*/