MicroMouse Maze Library  3703225
公開型 | 公開メンバ関数 | 静的公開メンバ関数 | 静的公開変数類 | 限定公開メンバ関数 | 限定公開変数類 | 静的限定公開変数類 | 全メンバ一覧
MazeLib::StepMap クラス

区画ベースのステップマップを管理するクラス [詳解]

#include <StepMap.h>

公開型

using step_t = uint16_t
 ステップの型 [詳解]
 

公開メンバ関数

 StepMap ()
 デフォルトコンストラクタ [詳解]
 
void reset (const step_t step=STEP_MAX)
 ステップマップを初期化する関数 [詳解]
 
step_t getStep (const int8_t x, const int8_t y) const
 ステップの取得 [詳解]
 
step_t getStep (const Position p) const
 ステップの取得 [詳解]
 
void setStep (const int8_t x, const int8_t y, const step_t step)
 ステップの更新 [詳解]
 
void setStep (const Position p, const step_t step)
 ステップの更新 [詳解]
 
const auto & getMapArray () const
 ステップマップの生配列への参照を取得 (読み取り専用) [詳解]
 
const auto getScalingFactor () const
 ステップのスケーリング係数を取得 [詳解]
 
void print (const Maze &maze, const Position p=Position(-1, -1), const Direction d=Direction::Max, std::ostream &os=std::cout) const
 ステップの表示 [詳解]
 
void print (const Maze &maze, const Directions &dirs, const Position start=Position(0, 0), std::ostream &os=std::cout) const
 
void printFull (const Maze &maze, const Position p=Position(-1, -1), const Direction d=Direction::Max, std::ostream &os=std::cout) const
 
void printFull (const Maze &maze, const Directions &dirs, const Position start=Position(0, 0), std::ostream &os=std::cout) const
 
void update (const Maze &maze, const Positions &dest, const bool knownOnly, const bool simple)
 ステップマップの更新 [詳解]
 
Directions calcShortestDirections (const Maze &maze, const Position start, const Positions &dest, const bool knownOnly, const bool simple)
 与えられた区画間の最短経路を導出する関数 [詳解]
 
Directions calcShortestDirections (const Maze &maze, const bool knownOnly, const bool simple)
 スタートからゴールまでの最短経路を導出する関数 [詳解]
 
Pose calcNextDirections (const Maze &maze, const Pose &start, Directions &nextDirectionsKnown, Directions &nextDirectionCandidates) const
 ステップマップから次に行くべき方向を計算する関数 [詳解]
 
Directions getStepDownDirections (const Maze &maze, const Pose &start, Pose &end, const bool knownOnly, const bool simple, const bool breakUnknown) const
 ステップマップにより次に行くべき方向列を生成する [詳解]
 
Directions getNextDirectionCandidates (const Maze &maze, const Pose &focus) const
 引数区画の周囲の未知壁の確認優先順位を生成する関数 [詳解]
 

静的公開メンバ関数

static void appendStraightDirections (const Maze &maze, Directions &shortestDirections, const bool knownOnly, const bool diagEnabled)
 ゴール区画内を行けるところまで直進させる方向列を追加する関数 [詳解]
 

静的公開変数類

static constexpr step_t STEP_MAX
 最大ステップ値 [詳解]
 

限定公開メンバ関数

void calcStraightCostTable ()
 計算の高速化のために予め直進のコストテーブルを計算する関数 [詳解]
 

限定公開変数類

std::array< step_t, Position::SIZEstepMap
 迷路中のステップ数 [詳解]
 
std::array< step_t, MAZE_SIZEstepTable
 台形加速を考慮した移動コストテーブル (壁沿い方向) [詳解]
 

静的限定公開変数類

static constexpr int stepTableSize = MAZE_SIZE
 コストテーブルのサイズ [詳解]
 
static constexpr float scalingFactor = 2
 コストが最大値を超えないようにスケーリングする係数 [詳解]
 

詳解

区画ベースのステップマップを管理するクラス

型定義メンバ詳解

◆ step_t

using MazeLib::StepMap::step_t = uint16_t

ステップの型

構築子と解体子

◆ StepMap()

MazeLib::StepMap::StepMap ( )

デフォルトコンストラクタ

台形加速のコストテーブルを計算する処理を含む

17  {
19  reset();
20 }
void calcStraightCostTable()
計算の高速化のために予め直進のコストテーブルを計算する関数
Definition: StepMap.cpp:417
void reset(const step_t step=STEP_MAX)
ステップマップを初期化する関数
Definition: StepMap.h:35
呼び出し関係図:

関数詳解

◆ appendStraightDirections()

void MazeLib::StepMap::appendStraightDirections ( const Maze maze,
Directions shortestDirections,
const bool  knownOnly,
const bool  diagEnabled 
)
static

ゴール区画内を行けるところまで直進させる方向列を追加する関数

引数
[in]maze使用する迷路
[in,out]shortestDirections追記元の方向列。これ自体に追記される。
[in]knownOnly未知壁は壁ありとみなし、既知壁のみを使用する
[in]diagEnabled斜めありなし
363  {
364  /* ゴール区画までたどる */
365  auto p = maze.getStart();
366  for (const auto d : shortestDirections) p = p.next(d);
367  if (shortestDirections.size() < 2) return;
368  auto prev_dir = shortestDirections[shortestDirections.size() - 1 - 1];
369  auto dir = shortestDirections[shortestDirections.size() - 1];
370  /* ゴール区画内を行けるところまで直進(斜め考慮)する */
371  bool loop = true;
372  while (loop) {
373  loop = false;
374  /* 斜めを考慮した進行方向を列挙する */
375  Directions dirs;
376  const auto rel_dir = Direction(dir - prev_dir);
377  if (diagEnabled && rel_dir == Direction::Left)
378  dirs = {Direction(dir + Direction::Right), dir};
379  else if (diagEnabled && rel_dir == Direction::Right)
380  dirs = {Direction(dir + Direction::Left), dir};
381  else
382  dirs = {dir};
383  /* 候補のうち行ける方向に行く */
384  for (const auto d : dirs) {
385  if (!maze.isWall(p, d) && (!knownOnly || maze.isKnown(p, d))) {
386  shortestDirections.push_back(d);
387  p = p.next(d);
388  prev_dir = dir;
389  dir = d;
390  loop = true;
391  break;
392  }
393  }
394  }
395 }
unsigned int d
壁の方向
Definition: Maze.h:609
@ Right
Definition: Maze.h:170
@ Left
Definition: Maze.h:166
std::vector< Direction > Directions
Direction 構造体の動的配列、集合
Definition: Maze.h:248
呼び出し関係図:

◆ calcNextDirections()

Pose MazeLib::StepMap::calcNextDirections ( const Maze maze,
const Pose start,
Directions nextDirectionsKnown,
Directions nextDirectionCandidates 
) const

ステップマップから次に行くべき方向を計算する関数

引数
[in]maze使用する迷路
[in]start移動開始位置
[out]nextDirectionsKnown既知区間移動方向列
[out]nextDirectionCandidates既知区間移動後の移動方向の優先順位
戻り値
既知区間の最終区画
236  {
237  Pose end;
238  nextDirectionsKnown =
239  getStepDownDirections(maze, start, end, false, false, true);
240  nextDirectionCandidates = getNextDirectionCandidates(maze, end);
241  return end;
242 }
Directions getNextDirectionCandidates(const Maze &maze, const Pose &focus) const
引数区画の周囲の未知壁の確認優先順位を生成する関数
Definition: StepMap.cpp:330
Directions getStepDownDirections(const Maze &maze, const Pose &start, Pose &end, const bool knownOnly, const bool simple, const bool breakUnknown) const
ステップマップにより次に行くべき方向列を生成する
Definition: StepMap.cpp:243
呼び出し関係図:

◆ calcShortestDirections() [1/2]

Directions MazeLib::StepMap::calcShortestDirections ( const Maze maze,
const bool  knownOnly,
const bool  simple 
)
inline

スタートからゴールまでの最短経路を導出する関数

引数
[in]maze使用する迷路
[in]knownOnly未知壁は壁ありとみなし、既知壁のみを使用する
[in]simple台形加速を考慮せず、隣接区画のコストをすべて1にする
戻り値
スタートからゴールへの最短経路の方向列。 経路がない場合は空配列となる。
123  {
124  return calcShortestDirections(maze, maze.getStart(), maze.getGoals(),
125  knownOnly, simple);
126  }
Directions calcShortestDirections(const Maze &maze, const Position start, const Positions &dest, const bool knownOnly, const bool simple)
与えられた区画間の最短経路を導出する関数
Definition: StepMap.cpp:221
呼び出し関係図:

◆ calcShortestDirections() [2/2]

Directions MazeLib::StepMap::calcShortestDirections ( const Maze maze,
const Position  start,
const Positions dest,
const bool  knownOnly,
const bool  simple 
)

与えられた区画間の最短経路を導出する関数

引数
[in]maze使用する迷路
[in]start始点区画
[in]dest目的地区画の集合(順不同)
[in]knownOnly未知壁は壁ありとみなし、既知壁のみを使用する
[in]simple台形加速を考慮せず、隣接区画のコストをすべて1にする
戻り値
始点区画から目的地区画への最短経路の方向列。 経路がない場合は空配列となる。
225  {
226  /* ステップマップを更新 */
227  update(maze, dest, knownOnly, simple);
228  Pose end;
229  const auto shortestDirections = getStepDownDirections(
230  maze, {start, Direction::Max}, end, knownOnly, simple, false);
231  /* ゴール判定 */
232  return stepMap[end.p.getIndex()] == 0 ? shortestDirections : Directions{};
233 }
static constexpr const int8_t Max
方向の総数。for文などで使える。
Definition: Maze.h:178
std::array< step_t, Position::SIZE > stepMap
迷路中のステップ数
Definition: StepMap.h:177
void update(const Maze &maze, const Positions &dest, const bool knownOnly, const bool simple)
ステップマップの更新
Definition: StepMap.cpp:136
呼び出し関係図:

◆ calcStraightCostTable()

void MazeLib::StepMap::calcStraightCostTable ( )
protected

計算の高速化のために予め直進のコストテーブルを計算する関数

417  {
418  const float vs = 420.0f; //< 基本速度 [mm/s]
419  const float am_a = 4200.0f; //< 最大加速度 [mm/s/s]
420  const float vm_a = 1500.0f; //< 飽和速度 [mm/s]
421  const float seg_a = 90.0f; //< 区画の長さ [mm]
422  const float t_turn = 287.0f; //< 小回り90度ターンの時間 [ms]
423  stepTable[0] = 0; //< [0] は使用しない
424  for (int i = 1; i < stepTableSize; ++i) {
425  /* 1歩目は90度ターンとみなす */
426  stepTable[i] = t_turn + calcStraightCost(i - 1, am_a, vs, vm_a, seg_a);
427  }
428  /* コストの合計が 65,535 [ms] を超えないようにスケーリング */
429  for (int i = 0; i < stepTableSize; ++i) {
430  stepTable[i] /= scalingFactor;
431 #if 0
432  MAZE_LOGI << "stepTable[" << i << "]:\t" << stepTable[i] << std::endl;
433 #endif
434  }
435 }
#define MAZE_LOGI
Definition: Maze.h:88
std::array< step_t, MAZE_SIZE > stepTable
台形加速を考慮した移動コストテーブル (壁沿い方向)
Definition: StepMap.h:183
static constexpr float scalingFactor
コストが最大値を超えないようにスケーリングする係数
Definition: StepMap.h:181
static constexpr int stepTableSize
コストテーブルのサイズ
Definition: StepMap.h:179
static StepMap::step_t calcStraightCost(const int i, const float am, const float vs, const float vm, const float seg)
台形加速を考慮したコストを生成する関数
Definition: StepMap.cpp:406
呼び出し関係図:

◆ getMapArray()

const auto& MazeLib::StepMap::getMapArray ( ) const
inline

ステップマップの生配列への参照を取得 (読み取り専用)

67 { return stepMap; }

◆ getNextDirectionCandidates()

Directions MazeLib::StepMap::getNextDirectionCandidates ( const Maze maze,
const Pose focus 
) const

引数区画の周囲の未知壁の確認優先順位を生成する関数

引数
[in]maze使用する迷路
[in]focus注目する区画の位置姿勢
戻り値
行くべき方向の優先順位
331  {
332  /* 直線優先で進行方向の候補を抽出。全方位 STEP_MAX だと空になる */
333  Directions dirs;
334  dirs.reserve(4);
335  for (const auto d : {focus.d + Direction::Front, focus.d + Direction::Left,
336  focus.d + Direction::Right, focus.d + Direction::Back})
337  if (!maze.isWall(focus.p, d) && getStep(focus.p.next(d)) != STEP_MAX)
338  dirs.push_back(d);
339  /* コストの低い順に並べ替え */
340  std::sort(dirs.begin(), dirs.end(),
341  [&](const Direction d1, const Direction d2) {
342  return getStep(focus.p.next(d1)) < getStep(focus.p.next(d2));
343  });
344 #if 1
345  /* 未知壁優先で並べ替え(未知壁同士ならばコストが低い順) */
346  std::sort(dirs.begin(), dirs.end(),
347  [&](const Direction d1, const Direction d2) {
348  return (maze.unknownCount(focus.p.next(d1)) &&
349  !maze.unknownCount(focus.p.next(d2)));
350  });
351 #endif
352 #if 1
353  /* 直進優先に並べ替え */
354  std::sort(dirs.begin(), dirs.end(),
355  [&](const Direction d1, const Direction d2
356  __attribute__((unused))) { return d1 == focus.d; });
357 #endif
358  return dirs;
359 }
@ Back
Definition: Maze.h:168
@ Front
Definition: Maze.h:164
static constexpr step_t STEP_MAX
最大ステップ値
Definition: StepMap.h:22
step_t getStep(const int8_t x, const int8_t y) const
ステップの取得
Definition: StepMap.h:40
呼び出し関係図:

◆ getScalingFactor()

const auto MazeLib::StepMap::getScalingFactor ( ) const
inline

ステップのスケーリング係数を取得

ステップにこの数をかけるとミリ秒に変換できる

72 { return scalingFactor; }

◆ getStep() [1/2]

step_t MazeLib::StepMap::getStep ( const int8_t  x,
const int8_t  y 
) const
inline

ステップの取得

盤面外なら STEP_MAX を返す

40  {
41  return getStep(Position(x, y));
42  }
int y
区画のy座標
Definition: Maze.h:608
int x
区画のx座標
Definition: Maze.h:607

◆ getStep() [2/2]

step_t MazeLib::StepMap::getStep ( const Position  p) const
inline

ステップの取得

盤面外なら STEP_MAX を返す

47  {
48  return p.isInsideOfField() ? stepMap[p.getIndex()] : STEP_MAX;
49  }
呼び出し関係図:

◆ getStepDownDirections()

Directions MazeLib::StepMap::getStepDownDirections ( const Maze maze,
const Pose start,
Pose end,
const bool  knownOnly,
const bool  simple,
const bool  breakUnknown 
) const

ステップマップにより次に行くべき方向列を生成する

引数
[in]maze使用する迷路
[in]start移動開始位置
[out]end移動後の位置姿勢
[in]knownOnly未知壁は壁ありとみなし、既知壁のみを使用する
[in]simple台形加速を考慮せず、隣接区画のコストをすべて1にする
[in]breakUnknown未知壁を含む区画に到達したら終了する(探索用)
246  {
247 #if 1
248  /* 最短経路となるスタートからの方向列 */
249  Directions shortestDirections;
250  auto& focus = end;
251  /* start から順にステップマップを下る */
252  focus = start;
253  /* 確認 */
254  if (!start.p.isInsideOfField()) return {};
255  /* 周辺の走査; 未知壁の有無と最小ステップの方向を求める */
256  while (1) {
257  const auto focus_step = stepMap[focus.p.getIndex()];
258  /* 終了条件 */
259  if (focus_step == 0) break;
260  /* 周辺を走査 */
261  auto min_p = focus.p;
262  auto min_d = Direction::Max;
263  for (const auto d : Direction::Along4()) {
264  /* 直線で行けるところまで探す */
265  auto next = focus.p; //< 隣接
266  for (int8_t i = 1;; ++i) {
267  /* 壁あり or 既知壁のみで未知壁 ならば次へ */
268  if (maze.isWall(next, d) || (knownOnly && !maze.isKnown(next, d)))
269  break;
270  next = next.next(d); //< 移動
271  /* 直線加速を考慮したステップを算出 */
272  const step_t next_step = focus_step - (simple ? i : stepTable[i]);
273  /* エッジコストと一致するか確認 */
274  if (stepMap[next.getIndex()] == next_step) {
275  min_p = next, min_d = d;
276  goto loop_exit;
277  }
278  }
279  }
280  loop_exit:
281  /* 現在地よりステップが大きかったらなんかおかしい */
282  if (focus_step <= stepMap[min_p.getIndex()]) break;
283  /* 移動分を結果に追加 */
284  while (focus.p != min_p) {
285  /* breakUnknown のとき、未知壁を含むならば既知区間は終了 */
286  if (breakUnknown && maze.unknownCount(focus.p)) return shortestDirections;
287  focus = focus.next(min_d);
288  shortestDirections.push_back(min_d);
289  }
290  }
291  return shortestDirections;
292 #else
293  /* ステップマップから既知区間進行方向列を生成 */
294  Directions shortestDirections;
295  /* start から順にステップマップを下る */
296  end = start;
297  /* 確認 */
298  if (!start.p.isInsideOfField()) return {};
299  while (1) {
300  /* 周辺の走査; 未知壁の有無と、最小ステップの方向を求める */
301  auto min_pose = end;
302  auto min_step = STEP_MAX;
303  for (const auto d : Direction::Along4()) {
304  auto next = end.p; //< 隣接
305  for (int8_t i = 1; i < MAZE_SIZE; ++i) {
306  /* 壁あり or 既知壁のみで未知壁 ならば次へ */
307  if (maze.isWall(next, d) || (knownOnly && !maze.isKnown(next, d)))
308  break;
309  next = next.next(d); //< 隣接区画へ移動
310  /* 現時点の min_step よりステップが小さければ更新 */
311  const auto next_step = stepMap[next.getIndex()];
312  if (min_step <= next_step) break;
313  min_step = next_step;
314  min_pose = Pose{next, d};
315  }
316  }
317  /* 現在地よりステップが大きかったらなんかおかしい */
318  if (stepMap[end.p.getIndex()] <= min_step) break;
319  /* 移動分を結果に追加 */
320  while (end.p != min_pose.p) {
321  /* breakUnknown のとき、未知壁を含むならば既知区間は終了 */
322  if (breakUnknown && maze.unknownCount(end.p)) return shortestDirections;
323  end = end.next(min_pose.d);
324  shortestDirections.push_back(min_pose.d);
325  }
326  }
327  return shortestDirections;
328 #endif
329 }
static constexpr const std::array< Direction, 4 > Along4()
斜めではない4方向の配列 (for文などで使用)
Definition: Maze.h:216
uint16_t step_t
ステップの型
Definition: StepMap.h:21
static constexpr int MAZE_SIZE
迷路の1辺の区画数の定数。
Definition: Maze.h:106
呼び出し関係図:

◆ print() [1/2]

void MazeLib::StepMap::print ( const Maze maze,
const Directions dirs,
const Position  start = Position(0, 0),
std::ostream &  os = std::cout 
) const
26  {
27  /* preparation */
28  std::vector<Pose> path;
29  path.reserve(dirs.size());
30  Position p = start;
31  for (const auto d : dirs) path.push_back({p, d}), p = p.next(d);
32  const int mazeSize = MAZE_SIZE;
33  step_t maxStep = 0;
34  for (const auto step : stepMap)
35  if (step != STEP_MAX) maxStep = std::max(maxStep, step);
36  const bool simple = (maxStep < 999);
37  const step_t scaler =
39  const auto find = [&](const WallIndex& i) {
40  return std::find_if(path.cbegin(), path.cend(), [&](const Pose& pose) {
41  return WallIndex(pose.p, pose.d) == i;
42  });
43  };
44  /* start to draw maze */
45  for (int8_t y = mazeSize; y >= 0; --y) {
46  /* Vertical Wall Line */
47  if (y != mazeSize) {
48  for (uint8_t x = 0; x <= mazeSize; ++x) {
49  /* Vertical Wall */
50  const auto w = maze.isWall(x, y, Direction::West);
51  const auto k = maze.isKnown(x, y, Direction::West);
52  const auto it = find(WallIndex(Position(x, y), Direction::West));
53  if (it != path.cend())
54  os << C_YE "\e[1m" << it->d << C_NO;
55  else
56  os << (k ? (w ? "|" : " ") : (C_RE "." C_NO));
57  /* Cell */
58  if (x != mazeSize) {
59  step_t step = getStep(x, y);
60  step = std::min(999, simple ? step : step / scaler);
61  os << (step == 0 ? C_YE : C_BL) << std::setw(3) << step << C_NO;
62  }
63  }
64  os << "\e[0K" << std::endl; // clear from cursor position to end of line
65  }
66  /* Horizontal Wall Line */
67  for (uint8_t x = 0; x < mazeSize; ++x) {
68  /* Pillar */
69  os << '+';
70  /* Horizontal Wall */
71  const auto w = maze.isWall(x, y, Direction::South);
72  const auto k = maze.isKnown(x, y, Direction::South);
73  const auto it = find(WallIndex(Position(x, y), Direction::South));
74  if (it != path.cend())
75  os << C_YE "\e[1m " << it->d << " " C_NO;
76  else
77  os << (k ? (w ? "---" : " ") : (C_RE " . " C_NO));
78  }
79  os << '+' << "\e[0K" << std::endl;
80  }
81 }
#define C_YE
ANSI Escape Sequence YELLOW
Definition: Maze.h:61
#define C_BL
ANSI Escape Sequence BLUE
Definition: Maze.h:62
#define C_NO
ANSI Escape Sequence RESET
Definition: Maze.h:65
#define C_RE
ANSI Escape Sequence RED
Definition: Maze.h:59
@ South
Definition: Maze.h:157
@ West
Definition: Maze.h:155
呼び出し関係図:

◆ print() [2/2]

void MazeLib::StepMap::print ( const Maze maze,
const Position  p = Position(-1, -1),
const Direction  d = Direction::Max,
std::ostream &  os = std::cout 
) const

ステップの表示

引数
[in]maze表示する迷路
[in]pハイライト区画
[in]dハイライト方向
[in,out]osoutput-stream
22  {
23  return print(maze, {d}, p.next(d + Direction::Back), os);
24 }
void print(const Maze &maze, const Position p=Position(-1, -1), const Direction d=Direction::Max, std::ostream &os=std::cout) const
ステップの表示
Definition: StepMap.cpp:21
呼び出し関係図:

◆ printFull() [1/2]

void MazeLib::StepMap::printFull ( const Maze maze,
const Directions dirs,
const Position  start = Position(0, 0),
std::ostream &  os = std::cout 
) const
87  {
88  /* preparation */
89  std::vector<Pose> path;
90  path.reserve(dirs.size());
91  Position p = start;
92  for (const auto d : dirs) path.push_back({p, d}), p = p.next(d);
93  const int mazeSize = MAZE_SIZE;
94  const auto find = [&](const WallIndex& i) {
95  return std::find_if(path.cbegin(), path.cend(), [&](const Pose& pose) {
96  return WallIndex(pose.p, pose.d) == i;
97  });
98  };
99  /* start to draw maze */
100  for (int8_t y = mazeSize; y >= 0; --y) {
101  /* Vertical Wall Line */
102  if (y != mazeSize) {
103  for (uint8_t x = 0; x <= mazeSize; ++x) {
104  /* Vertical Wall */
105  const auto w = maze.isWall(x, y, Direction::West);
106  const auto k = maze.isKnown(x, y, Direction::West);
107  const auto it = find(WallIndex(Position(x, y), Direction::West));
108  if (it != path.cend())
109  os << C_YE "\e[1m" << it->d << C_NO;
110  else
111  os << (k ? (w ? "|" : " ") : (C_RE "." C_NO));
112  /* Cell */
113  if (x != mazeSize) {
114  auto step = std::min((step_t)99999, getStep(x, y));
115  os << (step == 0 ? C_YE : C_BL) << std::setw(5) << step << C_NO;
116  }
117  }
118  os << std::endl;
119  }
120  /* Horizontal Wall Line */
121  for (uint8_t x = 0; x < mazeSize; ++x) {
122  /* Pillar */
123  os << '+';
124  /* Horizontal Wall */
125  const auto w = maze.isWall(x, y, Direction::South);
126  const auto k = maze.isKnown(x, y, Direction::South);
127  const auto it = find(WallIndex(Position(x, y), Direction::South));
128  if (it != path.cend())
129  os << C_YE "\e[1m " << it->d << " " C_NO;
130  else
131  os << (k ? (w ? "-----" : " ") : (C_RE " . " C_NO));
132  }
133  os << '+' << std::endl;
134  }
135 }
呼び出し関係図:

◆ printFull() [2/2]

void MazeLib::StepMap::printFull ( const Maze maze,
const Position  p = Position(-1, -1),
const Direction  d = Direction::Max,
std::ostream &  os = std::cout 
) const
83  {
84  return printFull(maze, {d}, p.next(d + Direction::Back), os);
85 }
void printFull(const Maze &maze, const Position p=Position(-1, -1), const Direction d=Direction::Max, std::ostream &os=std::cout) const
Definition: StepMap.cpp:82
呼び出し関係図:

◆ reset()

void MazeLib::StepMap::reset ( const step_t  step = STEP_MAX)
inline

ステップマップを初期化する関数

引数
[in]stepこの値で全マップを初期化する
35 { stepMap.fill(step); }

◆ setStep() [1/2]

void MazeLib::StepMap::setStep ( const int8_t  x,
const int8_t  y,
const step_t  step 
)
inline

ステップの更新

盤面外なら何もしない

54  {
55  return setStep(Position(x, y), step);
56  }
void setStep(const int8_t x, const int8_t y, const step_t step)
ステップの更新
Definition: StepMap.h:54

◆ setStep() [2/2]

void MazeLib::StepMap::setStep ( const Position  p,
const step_t  step 
)
inline

ステップの更新

盤面外なら何もしない

61  {
62  if (p.isInsideOfField()) stepMap[p.getIndex()] = step;
63  }
呼び出し関係図:

◆ update()

void MazeLib::StepMap::update ( const Maze maze,
const Positions dest,
const bool  knownOnly,
const bool  simple 
)

ステップマップの更新

引数
[in]maze更新に使用する迷路情報
[in]destステップを0とする目的地の区画の集合(順不同)
[in]knownOnlytrue:未知壁は通過不可能、false:未知壁は通過可能とする
[in]simple台形加速を考慮せず、隣接区画のコストをすべて1にする
137  {
139  /* 計算を高速化するため、迷路の大きさを制限 */
140  int8_t min_x = maze.getMinX();
141  int8_t max_x = maze.getMaxX();
142  int8_t min_y = maze.getMinY();
143  int8_t max_y = maze.getMaxY();
144  for (const auto p : dest) { //< ゴールを含めないと導出不可能になる
145  min_x = std::min(p.x, min_x);
146  max_x = std::max(p.x, max_x);
147  min_y = std::min(p.y, min_y);
148  max_y = std::max(p.y, max_y);
149  }
150  min_x -= 1, min_y -= 1, max_x += 2, max_y += 2; //< 外周を許す
151  /* 全区画のステップを最大値に設定 */
152  reset();
153  /* ステップの更新予約のキュー */
154 #define STEP_MAP_USE_PRIORITY_QUEUE 1
155 #if STEP_MAP_USE_PRIORITY_QUEUE
156  struct Element {
157  Position p;
158  step_t s;
159  bool operator<(const Element& e) const { return s > e.s; }
160  };
161  std::priority_queue<Element> q;
162 #else
163  std::queue<Position> q;
164 #endif
165  /* destのステップを0とする */
166  for (const auto p : dest)
167  if (p.isInsideOfField())
168 #if STEP_MAP_USE_PRIORITY_QUEUE
169  setStep(p, 0), q.push({p, 0});
170 #else
171  setStep(p, 0), q.push(p);
172 #endif
173  /* ステップの更新がなくなるまで更新処理 */
174  while (!q.empty()) {
175 #if MAZE_DEBUG_PROFILING
176  queueSizeMax = std::max(queueSizeMax, static_cast<int>(q.size()));
177 #endif
178  /* 注目する区画を取得 */
179 #if STEP_MAP_USE_PRIORITY_QUEUE
180  const auto focus = q.top().p;
181  const auto focus_step_q = q.top().s;
182 #else
183  const auto focus = q.front();
184 #endif
185  q.pop();
186  /* 計算を高速化するため展開範囲を制限 */
187  if (focus.x > max_x || focus.y > max_y || focus.x < min_x ||
188  focus.y < min_y)
189  continue;
190  const auto focus_step = stepMap[focus.getIndex()];
191 #if STEP_MAP_USE_PRIORITY_QUEUE
192  /* 枝刈り */
193  if (focus_step < focus_step_q) continue;
194 #endif
195  /* 周辺を走査 */
196  for (const auto d : Direction::Along4()) {
197  /* 直線で行けるところまで更新する */
198  auto next = focus;
199  for (int8_t i = 1;; ++i) {
200  /* 壁あり or 既知壁のみで未知壁 ならば次へ */
201  const auto next_wi = WallIndex(next, d);
202  if (maze.isWall(next_wi) || (knownOnly && !maze.isKnown(next_wi)))
203  break;
204  next = next.next(d); //< 移動
205  /* 直線加速を考慮したステップを算出 */
206  const step_t next_step = focus_step + (simple ? i : stepTable[i]);
207  const auto next_index = next.getIndex();
208  if (stepMap[next_index] <= next_step) break; //< 更新の必要がない
209  stepMap[next_index] = next_step; //< 更新
210  /* 再帰的に更新するためにキューにプッシュ */
211 #if STEP_MAP_USE_PRIORITY_QUEUE
212  q.push({next, next_step});
213 #else
214  q.push(next);
215 #endif
216  }
217  }
218  }
220 }
#define MAZE_DEBUG_PROFILING_START(id)
Definition: Maze.h:43
#define MAZE_DEBUG_PROFILING_END(id)
Definition: Maze.h:44
呼び出し関係図:

メンバ詳解

◆ scalingFactor

constexpr float MazeLib::StepMap::scalingFactor = 2
staticconstexprprotected

コストが最大値を超えないようにスケーリングする係数

◆ STEP_MAX

constexpr step_t MazeLib::StepMap::STEP_MAX
staticconstexpr
初期値:
=
std::numeric_limits<step_t>::max()

最大ステップ値

◆ stepMap

std::array<step_t, Position::SIZE> MazeLib::StepMap::stepMap
protected

迷路中のステップ数

◆ stepTable

std::array<step_t, MAZE_SIZE> MazeLib::StepMap::stepTable
protected

台形加速を考慮した移動コストテーブル (壁沿い方向)

◆ stepTableSize

constexpr int MazeLib::StepMap::stepTableSize = MAZE_SIZE
staticconstexprprotected

コストテーブルのサイズ


このクラス詳解は次のファイルから抽出されました: