Scratch上級テクニック|経路探索と迷路の移動

経路探索では、マップを小さな区画に分け、移動可能な場所と目標までのルートを扱います。

考え方と準備

経路探索では、マップを小さな区画に分け、移動可能な場所と目標までのルートを扱います。

利用する端末、対象者、作品の目的を先に確認し、無理のない小さな目標に分けます。

進め方

最初に最小の動作を作って確認し、必要な機能を一つずつ加えます。試した結果と修正内容を記録すると、次の改善につながります。

  • 通行可能・不可能のマップを用意
  • 開始位置と目標位置を決める
  • 探索済み・未探索の状態を管理
  • 到達不能や探索上限を処理する

探索データと移動データを分ける

迷路をセルの格子で表し、各セルを通行可能・壁・訪問済みなどに分類します。探索アルゴリズムは経路を見つける処理、移動アニメーションはその経路をキャラクターに歩かせる処理として分けるとデバッグしやすくなります。

幅優先探索は同じ歩数の移動コストなら近い順に調べる方法です。A*など他の方法は評価値の設計が必要になるため、まず小さな迷路で探索順と訪問状態を表示して理解します。

  • 開始セル・目標セル・隣接セルの規則を決める
  • 訪問済みの印で同じセルを何度も探索しない
  • 経路なし・開始点が壁・目標が壁の場合を扱う

経路を見えるようにする

探索中のセルを色で表示し、見つかった経路を別のリストへ保存すると、正しいルートか確認できます。

探索の基本手順
  1. 開始セルを探索待ちリストへ追加
  2. 待ちリストから先頭のセルを取り出す
  3. 未訪問の隣接セルを訪問済みにする
  4. 目標なら探索を終了する
  5. 目標でなければ隣接セルを待ちリストへ追加

動かすと:セルを重複して調べず、目標までの経路を探索できます。

確認してから公開する

ここに示す項目は設計のガイドです。特定のScratchバージョンや端末での動作を確認するまでは、実機確認済みとは扱いません。

この記事は学習のための案内です。Scratchの画面・利用条件は更新されることがあるため、操作前に公式情報もご確認ください。

学習に役立つ書籍・教材・グッズを見る →