Scratch上級テクニック|経路探索と迷路の移動
経路探索では、マップを小さな区画に分け、移動可能な場所と目標までのルートを扱います。
考え方と準備
経路探索では、マップを小さな区画に分け、移動可能な場所と目標までのルートを扱います。
利用する端末、対象者、作品の目的を先に確認し、無理のない小さな目標に分けます。
進め方
最初に最小の動作を作って確認し、必要な機能を一つずつ加えます。試した結果と修正内容を記録すると、次の改善につながります。
- 通行可能・不可能のマップを用意
- 開始位置と目標位置を決める
- 探索済み・未探索の状態を管理
- 到達不能や探索上限を処理する
探索データと移動データを分ける
迷路をセルの格子で表し、各セルを通行可能・壁・訪問済みなどに分類します。探索アルゴリズムは経路を見つける処理、移動アニメーションはその経路をキャラクターに歩かせる処理として分けるとデバッグしやすくなります。
幅優先探索は同じ歩数の移動コストなら近い順に調べる方法です。A*など他の方法は評価値の設計が必要になるため、まず小さな迷路で探索順と訪問状態を表示して理解します。
- 開始セル・目標セル・隣接セルの規則を決める
- 訪問済みの印で同じセルを何度も探索しない
- 経路なし・開始点が壁・目標が壁の場合を扱う
経路を見えるようにする
探索中のセルを色で表示し、見つかった経路を別のリストへ保存すると、正しいルートか確認できます。
探索の基本手順
- 開始セルを探索待ちリストへ追加
- 待ちリストから先頭のセルを取り出す
- 未訪問の隣接セルを訪問済みにする
- 目標なら探索を終了する
- 目標でなければ隣接セルを待ちリストへ追加
動かすと:セルを重複して調べず、目標までの経路を探索できます。
確認してから公開する
ここに示す項目は設計のガイドです。特定のScratchバージョンや端末での動作を確認するまでは、実機確認済みとは扱いません。
この記事は学習のための案内です。Scratchの画面・利用条件は更新されることがあるため、操作前に公式情報もご確認ください。
学習に役立つ書籍・教材・グッズを見る →