Maze.h

[詳解]

 
#pragma once
 
#include <array>
#include <bitset>
#include <cmath>     //< for std::log2
#include <cstdint>   //< for uint8_t
#include <fstream>   //< for std::ifstream
#include <iostream>  //< for std::cout
#include <string>
#include <vector>
 
/* debug profiling option */
#define MAZE_DEBUG_PROFILING 0
#if MAZE_DEBUG_PROFILING
#warning "this is debug mode!"
#include <chrono>
static int microseconds() {
  return std::chrono::duration_cast<std::chrono::microseconds>(
             std::chrono::steady_clock::now().time_since_epoch())
      .count();
}
static int microseconds() __attribute__((unused));
#define MAZE_DEBUG_PROFILING_START(id) const auto t0_##id = microseconds();
#define MAZE_DEBUG_PROFILING_END(id)                                 \
  {                                                                  \
    const auto t1_##id = microseconds();                             \
    const auto dur = t1_##id - t0_##id;                              \
    static auto dur_max = 0;                                         \
    if (dur > dur_max) {                                             \
      dur_max = dur;                                                 \
      MAZE_LOGD << __func__ << "(" << #id << ")\t" << dur << " [us]" \
                << std::endl;                                        \
    }                                                                \
  }
#else
#define MAZE_DEBUG_PROFILING_START(id)
#define MAZE_DEBUG_PROFILING_END(id)
#endif
 
/*
 * 迷路のカラー表示切替
 */
#ifdef MAZE_COLOR_DISABLED
#define C_RE ""
#define C_GR ""
#define C_YE ""
#define C_BL ""
#define C_MA ""
#define C_CY ""
#define C_NO ""
#else
#define C_RE "\e[31m" 
#define C_GR "\e[32m" 
#define C_YE "\e[33m" 
#define C_BL "\e[34m" 
#define C_MA "\e[35m" 
#define C_CY "\e[36m" 
#define C_NO "\e[0m"  
#endif
 
#ifndef MAZE_LOG_LEVEL
#define MAZE_LOG_LEVEL 4
#endif
#define MAZE_LOG_STREAM_BASE(s, l, c) \
  (s << c "[" l "][" __FILE__ ":" << __LINE__ << "]" C_NO "\t")
#if MAZE_LOG_LEVEL >= 1
#define MAZE_LOGE MAZE_LOG_STREAM_BASE(std::cout, "E", C_RE)
#else
#define MAZE_LOGE std::ostream(0)
#endif
#if MAZE_LOG_LEVEL >= 2
#define MAZE_LOGW MAZE_LOG_STREAM_BASE(std::cout, "W", C_YE)
#else
#define MAZE_LOGW std::ostream(0)
#endif
#if MAZE_LOG_LEVEL >= 3
#define MAZE_LOGI MAZE_LOG_STREAM_BASE(std::cout, "I", C_GR)
#else
#define MAZE_LOGI std::ostream(0)
#endif
#if MAZE_LOG_LEVEL >= 4
#define MAZE_LOGD MAZE_LOG_STREAM_BASE(std::cout, "D", C_BL)
#else
#define MAZE_LOGD std::ostream(0)
#endif
 
namespace MazeLib {
 
static constexpr int MAZE_SIZE = 16;
static constexpr int MAZE_SIZE_BIT = std::ceil(std::log2(MAZE_SIZE));
static constexpr int MAZE_SIZE_MAX = std::pow(2, MAZE_SIZE_BIT);
 
class Direction {
 public:
  enum AbsoluteDirection : int8_t {
    East,
    NorthEast,
    North,
    NorthWest,
    West,
    SouthWest,
    South,
    SouthEast,
  };
  enum RelativeDirection : int8_t {
    Front,
    Left45,
    Left,
    Left135,
    Back,
    Right135,
    Right,
    Right45,
  };
  static constexpr const int8_t Max = 8;
 
 public:
  constexpr Direction(const AbsoluteDirection d = East) : d(d) {}
  constexpr Direction(const int8_t d) : d(d & 7) {}
  constexpr operator int8_t() const { return d; }
  bool isAlong() const { return !(d & 1); }
  bool isDiag() const { return (d & 1); }
  char toChar() const { return ">'^`<,v.X"[d]; }
  friend std::ostream& operator<<(std::ostream& os, const Direction d) {
    return os << d.toChar();
  }
  static constexpr const std::array<Direction, 4> Along4() {
    return {
        Direction::East,
        Direction::North,
        Direction::West,
        Direction::South,
    };
  }
  static constexpr const std::array<Direction, 4> Diag4() {
    return {
        Direction::NorthEast,
        Direction::NorthWest,
        Direction::SouthWest,
        Direction::SouthEast,
    };
  }
 
 private:
  int8_t d;
};
static_assert(sizeof(Direction) == 1, "size error");
 
using Directions = std::vector<Direction>;
std::ostream& operator<<(std::ostream& os, const Directions& obj);
 
struct Position {
 public:
  static constexpr int SIZE = MAZE_SIZE_MAX * MAZE_SIZE_MAX;
 
 public:
  union {
    struct {
      int8_t x; 
      int8_t y; 
    };
    uint16_t data; 
  };
 
 public:
  constexpr Position() : data(0) {}
  constexpr Position(const int8_t x, const int8_t y) : x(x), y(y) {}
  uint16_t getIndex() const { return (x << MAZE_SIZE_BIT) | y; }
  static Position getPositionFromIndex(const uint16_t index) {
    return {int8_t(index >> MAZE_SIZE_BIT),
            int8_t(index & (MAZE_SIZE_MAX - 1))};
  }
  Position operator+(const Position p) const {
    return Position(x + p.x, y + p.y);
  }
  Position operator-(const Position p) const {
    return Position(x - p.x, y - p.y);
  }
  bool operator==(const Position p) const {
    // return x == p.x && y == p.y;
    return data == p.data;  //< 高速化
  }
  bool operator!=(const Position p) const {
    // return x != p.x || y != p.y;
    return data != p.data;  //< 高速化
  }
  Position next(const Direction d) const;
  bool isInsideOfField() const {
    // return x >= 0 && x < MAZE_SIZE && y >= 0 && y < MAZE_SIZE;
    /* 高速化 */
    return (static_cast<uint8_t>(x) < MAZE_SIZE) &&
           (static_cast<uint8_t>(y) < MAZE_SIZE);
  }
  Position rotate(const Direction d) const;
  Position rotate(const Direction d, const Position center) const {
    return center + (*this - center).rotate(d);
  }
  friend std::ostream& operator<<(std::ostream& os, const Position p);
  const char* toString() const {
    static char str[32];
    snprintf(str, sizeof(str), "(%02d, %02d)", x, y);
    return str;
  }
};
static_assert(sizeof(Position) == 2, "size error");
 
using Positions = std::vector<Position>;
 
struct Pose {
 public:
  Position p;  
  Direction d; 
 public:
  Pose() {}
  Pose(const Position p, const Direction d) : p(p), d(d) {}
  Pose next(const Direction nextDirection) const {
    return Pose(p.next(nextDirection), nextDirection);
  }
  friend std::ostream& operator<<(std::ostream& os, const Pose& pose);
  const char* toString() const {
    static char str[32];
    snprintf(str, sizeof(str), "(%02d, %02d, %c)", p.x, p.y, d.toChar());
    return str;
  }
};
static_assert(sizeof(Pose) == 4, "size error");
 
struct WallIndex {
  static constexpr int SIZE = MAZE_SIZE_MAX * MAZE_SIZE_MAX * 2;
 
 public:
  union {
    struct {
      int8_t x;      
      int8_t y : 7;  
      uint8_t z : 1; 
    };
    uint16_t data; 
  };
  static_assert(MAZE_SIZE < std::pow(2, 6), "MAZE_SIZE is too large!");
 
 public:
  constexpr WallIndex() : data(0) {}
  constexpr WallIndex(const int8_t x, const int8_t y, const uint8_t z)
      : x(x), y(y), z(z) {}
  constexpr WallIndex(const Position p, const Direction d) : x(p.x), y(p.y) {
    uniquify(d);
  }
  constexpr WallIndex(const uint16_t i)
      : x(i & (MAZE_SIZE_MAX - 1)),
        y((i >> MAZE_SIZE_BIT) & (MAZE_SIZE_MAX - 1)),
        z(i >> (2 * MAZE_SIZE_BIT)) {}
  bool operator==(const WallIndex i) const {
    // return x == i.x && y == i.y && z == i.z;
    return data == i.data;  //< 高速化
  }
  bool operator!=(const WallIndex i) const {
    // return x != i.x || y != i.y || z != i.z;
    return data != i.data;  //< 高速化
  }
  uint16_t getIndex() const {
    // return (z << (2 * MAZE_SIZE_BIT)) | (y << MAZE_SIZE_BIT) | x;
    return (z << (MAZE_SIZE_BIT << 1)) | (y << MAZE_SIZE_BIT) | x;  //< 高速化
  }
  Position getPosition() const { return Position(x, y); }
  Direction getDirection() const {
    // return z == 0 ? Direction::East : Direction::North;
    return z << 1;  //< 高速化
  }
  friend std::ostream& operator<<(std::ostream& os, const WallIndex i);
  bool isInsideOfField() const {
    /* x,y が フィールド内かつ、外周上にいない */
    // return !(x < 0 || y < 0 || x >= MAZE_SIZE || y >= MAZE_SIZE ||
    //          (z == 0 && (x == MAZE_SIZE - 1)) ||
    //          (z == 1 && (y == MAZE_SIZE - 1)));
    /* 高速化 */
    return (static_cast<uint8_t>(x) < MAZE_SIZE - 1 + z) &&
           (static_cast<uint8_t>(y) < MAZE_SIZE - z);
  }
  WallIndex next(const Direction d) const;
  std::array<Direction, 6> getNextDirection6() const {
    const auto d = getDirection();
    return {{
        d + Direction::Front,
        d + Direction::Back,
        d + Direction::Left45,
        d + Direction::Right45,
        d + Direction::Left135,
        d + Direction::Right135,
    }};
  }
 
 private:
  constexpr void uniquify(const Direction d) {
    z = (d >> 1) & 1;  //< {East,West} => 0, {North,South} => 1
    switch (d) {
      case Direction::West:
        x--;
        break;
      case Direction::South:
        y--;
        break;
    }
  }
};
static_assert(sizeof(WallIndex) == 2, "size error");
 
using WallIndexes = std::vector<WallIndex>;
 
struct WallRecord {
  union {
    struct {
      int x : 6;          
      int y : 6;          
      unsigned int d : 3; 
      unsigned int b : 1; 
    } __attribute__((__packed__));
    uint16_t data; 
  };
  static_assert(MAZE_SIZE < std::pow(2, 6), "MAZE_SIZE is too large!");
  WallRecord() {}
  WallRecord(const int8_t x, const int8_t y, const Direction d, const bool b)
      : x(x), y(y), d(d), b(b) {}
  WallRecord(const Position p, const Direction d, const bool b)
      : x(p.x), y(p.y), d(d), b(b) {}
  const Position getPosition() const { return Position(x, y); }
  const Direction getDirection() const { return d; }
  friend std::ostream& operator<<(std::ostream& os, const WallRecord& obj);
};
static_assert(sizeof(WallRecord) == 2, "size error");
 
using WallRecords = std::vector<WallRecord>;
 
class Maze {
 public:
  Maze(const Positions& goals = Positions(),
       const Position start = Position(0, 0))
      : goals(goals), start(start) {
    reset();
  }
  void reset(const bool set_start_wall = true,
             const bool set_range_full = false);
  bool isWall(const WallIndex i) const { return isWallBase(wall, i); }
  bool isWall(const Position p, const Direction d) const {
    return isWallBase(wall, WallIndex(p, d));
  }
  bool isWall(const int8_t x, const int8_t y, const Direction d) const {
    return isWallBase(wall, WallIndex(Position(x, y), d));
  }
  void setWall(const WallIndex i, const bool b) {
    return setWallBase(wall, i, b);
  }
  void setWall(const Position p, const Direction d, const bool b) {
    return setWallBase(wall, WallIndex(p, d), b);
  }
  void setWall(const int8_t x, const int8_t y, const Direction d,
               const bool b) {
    return setWallBase(wall, WallIndex(Position(x, y), d), b);
  }
  bool isKnown(const WallIndex i) const { return isWallBase(known, i); }
  bool isKnown(const Position p, const Direction d) const {
    return isWallBase(known, WallIndex(p, d));
  }
  bool isKnown(const int8_t x, const int8_t y, const Direction d) const {
    return isWallBase(known, WallIndex(Position(x, y), d));
  }
  void setKnown(const WallIndex i, const bool b) {
    return setWallBase(known, i, b);
  }
  void setKnown(const Position p, const Direction d, const bool b) {
    return setWallBase(known, WallIndex(p, d), b);
  }
  void setKnown(const int8_t x, const int8_t y, const Direction d,
                const bool b) {
    return setWallBase(known, WallIndex(Position(x, y), d), b);
  }
  bool canGo(const WallIndex i) const { return !isWall(i) && isKnown(i); }
  bool canGo(const Position p, const Direction d) const {
    return canGo(WallIndex(p, d));
  }
  bool canGo(const WallIndex& i, bool knownOnly) const {
    return !isWall(i) && (isKnown(i) || !knownOnly);
  }
  bool updateWall(const Position p, const Direction d, const bool b,
                  const bool pushRecords = true);
  void resetLastWalls(const int num, const bool set_start_wall = true);
  int8_t wallCount(const Position p) const;
  int8_t unknownCount(const Position p) const;
  void print(std::ostream& os = std::cout,
             const int mazeSize = MAZE_SIZE) const;
  void print(const Directions& dirs, const Position start = Position(0, 0),
             std::ostream& os = std::cout,
             const int mazeSize = MAZE_SIZE) const;
  void print(const Positions& positions, std::ostream& os = std::cout,
             const int mazeSize = MAZE_SIZE) const;
  bool parse(std::istream& is);
  bool parse(const std::string& filepath) {
    std::ifstream ifs(filepath);
    return ifs ? parse(ifs) : false;
  }
  friend std::istream& operator>>(std::istream& is, Maze& maze) {
    maze.parse(is);
    return is;
  }
  bool parse(const std::vector<std::string>& data, const int mazeSize);
  void setGoals(const Positions& goals) { this->goals = goals; }
  void setStart(const Position start) { this->start = start; }
  const Positions& getGoals() const { return goals; }
  const Position& getStart() const { return start; }
  const WallRecords& getWallRecords() const { return wallRecords; }
  int8_t getMinX() const { return min_x; }
  int8_t getMinY() const { return min_y; }
  int8_t getMaxX() const { return max_x; }
  int8_t getMaxY() const { return max_y; }
  bool backupWallRecordsToFile(const std::string& filepath,
                               const bool clear = false);
  bool restoreWallRecordsFromFile(const std::string& filepath);
 
 protected:
  std::bitset<WallIndex::SIZE> wall;  
  std::bitset<WallIndex::SIZE> known; 
  Positions goals;                    
  Position start;                     
  WallRecords wallRecords;            
  int8_t min_x;                       
  int8_t min_y;                       
  int8_t max_x;                       
  int8_t max_y;                       
  int wallRecordsBackupCounter; 
  bool isWallBase(const std::bitset<WallIndex::SIZE>& wall,
                  const WallIndex i) const {
    return !i.isInsideOfField() || wall[i.getIndex()];  //< 範囲外は壁ありに
  }
  void setWallBase(std::bitset<WallIndex::SIZE>& wall, const WallIndex i,
                   const bool b) const {
    if (i.isInsideOfField())  //< 範囲外アクセスの防止
      wall[i.getIndex()] = b;
  }
};
 
}  // namespace MazeLib