01
MAZE DATA
15×15の迷路と、外側のゴール
通常セルはX,Yとも0〜14。ゴールだけは出口としてX=15またはY=15の外側セルを許します。
S=スタート G=出口 濃色=壁
最初に届く情報
CMD_MAZE_SIZE → mazeW=15, mazeH=15
CMD_GOAL → goalX, goalY
CMD_START → startX, startY
solveMaze();isValidTarget() が通常セルとゴール出口を区別します。02
SENSE / MOVE
見るだけと、実際に進むを使い分ける
maze.sense(x,y)壁か通路かを問い合わせる。現在位置は変わらない。
maze.moveTo(x,y)そのマスへ移動を要求。通路なら現在位置が変わる。
RESULT_*OPEN / WALL / GOAL / START / OUT がWebから返る。
UIAPduinoSENSEを送信
Web迷路を確認
RESULT結果を返す
UIAPduino次を判断
03
DEPTH FIRST SEARCH
DFSは一本道を奥まで進み、詰まったら戻る
stackX/Y が通ってきた道、visited が探索済み、nextDir が次に試す方向です。
水色=訪問済み 緑=現在のスタック
バックトラック
進める隣接セルあり → stackへpush
全方向を試した → sp--
moveTo(親の座標)戻る移動もWebに送るため、画面上のプレイヤーとスタックの先頭は常に一致します。
04
GREEDY DFS
ゴールに近づく方向から試す
配布スケッチは通常のDFSではなく、未試行の隣接マスをゴールまでのマンハッタン距離で並べるGreedy DFSです。
距離 5右へ進む候補
距離 7下へ進む候補
最小を選択ただし壁なら次の候補へ
distance = abs(nx-goalX) + abs(ny-goalY); 未試行の候補で distance が最小の方向を選ぶ;
近そうな方向を優先するだけなので最短経路の保証はありません。行き止まりならDFSと同じように戻ります。
05
BREADTH FIRST SEARCH
BFSはスタートから波紋のように広がる
キューの先頭から近いマスを順番に調べるため、最初にゴールへ届いた経路が最短になります。
薄い水色→濃い水色の順に探索が広がる
qx[tail]=startX; qy[tail]=startY;
while (head < tail) {
x=qx[head]; y=qy[head]; head++;
未訪問の通路を tail に追加;
}探索中は sense() だけを使い、ゴールまでの道が確定してから実際に移動します。
06
PATH RESTORATION
ゴールから親を逆にたどり、順番を反転する
parentDir[y][x] には、そのマスへどの方向から来たかを保存します。
GOAL親方向を読む
逆向きSTARTまで戻る
path[]座標を保存
反転START→GOALへ移動
最後に
CMD_SOLVED を送り、Webが次の迷路へ進みます。✓
SUMMARY
探索方法の違い
右手法壁に沿う。記憶は少ないが、迷路によって遠回り。DFS奥まで進み、行き止まりで戻る。Greedy DFSゴールに近い方向を優先するDFS。BFS全方向へ広がり、最短経路を復元する。