Scratch(スクラッチ)で経路探索を作る入り口|敵が迷路を追う仕組み
📌 このページでわかること
経路探索は「マップをマス目で管理し、ゴールから何歩で着くかを数えて、数字が小さい方向へ進む」考え方が基本です。まずは小さな格子マップで仕組みを体験しましょう。
「まっすぐ追う」だけでは壁に引っかかる
「プレイヤーへ向ける」「5歩動かす」だけだと、間に壁があるときに敵が壁にぶつかって止まってしまいます。壁をよけて目的地へたどり着くための考え方が経路探索(パスファインディング)です。
Scratchでいきなり複雑なアルゴリズムを書く必要はありません。まずはマップを縦横のマス目(グリッド)に分け、リストで「壁」と「通路」を表すところから始めます。
- マップを縦横のマス目(例:10×8マス)に区切る
- リストに「0=通路」「1=壁」のように記録する
- ゴールから隣り合う通路へ「1歩、2歩、3歩…」と距離を書き込む
- 敵は上下左右のマスを見て、距離の数字が一番小さいマスへ進む
進め方:小さなマス目で距離を広げる
ゴールから波紋のように距離を広げる方法は「幅優先探索(BFS)」の考え方です。Scratchでは2つのリスト(マップ用・距離用)と、次に調べるマスを入れる「待ち行列(キュー)」のリストを使うと整理できます。
- 距離リストをすべて大きな数(例:999)で初期化する
- ゴールのマスの距離を0にして、調べるリストへ追加する
- 調べるリストの先頭を取り出し、上下左右の通路に「今の距離+1」を書き込む
- 敵は現在地の上下左右を調べ、一番数字が小さいマスへ1マス移動する
敵が距離リストを見て次のマスを選ぶイメージ
- 「最小距離」を 999 にする
- もし <(「距離リスト」の 上の番号 番目) (最小距離) なら
- 「最小距離」を (「距離リスト」の 上の番号 番目) にする
- 「次の向き」を 0 にする
- (下・左・右も同じように比べて、一番小さい向きへ1マス進む)
動かすとこうなるよ: 壁があっても回り道をしてゴールへ向かえるようになります。まずは5×5マスの小さな迷路で動きを確かめるのがおすすめです。
重くならないための工夫と次のステップ
毎フレーム距離を計算し直すと処理が重くなります。プレイヤーが別のマスへ動いたときだけ再計算し、計算ブロックは「画面を再描画せずに実行する」ブロック定義にまとめるとスムーズに動きます。
よくある質問
ScratchでA*(エースター)アルゴリズムも作れますか?
リストとブロック定義を使えば実装可能ですが、まずはゴールからの距離を順に数える幅優先探索(距離マップ)で仕組みをつかむのが確実です。
敵が複数いる場合は敵ごとに計算が必要ですか?
ゴール(プレイヤー)から距離マップを1回作れば、すべての敵が同じ距離マップを見て追いかけられるため計算が軽く済みます。
この記事は学習のための案内です。Scratchの画面・利用条件は更新されることがあるため、操作前に公式情報もご確認ください。
学習に役立つ書籍・教材・グッズを見る →