今回エンジニアブロクを担当する小瀬です。 経路探索アルゴリズムといえば、A*(エースター)が有名ですが、タワーディフェンスやRTSなど平面的なものに使われる事が多いかと思います。複雑な立体交差などに対応するのは難しいですが、SFC向けに発売されたタクティクスオウガのような地形であれば多少の変更で実現可能です。 A*自体はそれほど難しいものでも無いとは思いますが、基本的な部分としては 開始地点から検索を始め、周囲にあるグリッドの移動量とゴールまでの直線距離を求め、その合計をウェイト値として求める。 移動先のグリッドからは移動元のグリッドへの方向(または座標)を持たせておく ウェイト値計算の行われたグリッドは、探索対象としてリストなどに保持しておく リスト中で最もウェイト値の低いグリッドへ移動し、移動元のグリッドはリストから外す 隣接グリッドが壁や、既に計算済みのグリッドに囲まれた場合はそのま
![経路探索アルゴリズムA*を立体地形に対応させてみる - WonderPlanet DEVELOPER BLOG](https://cdn-ak-scissors.b.st-hatena.com/image/square/02e2d4045b881bfb77ac1cdf7ebff4df05d052a0/height=288;version=1;width=512/https%3A%2F%2Fs3-ap-northeast-1.amazonaws.com%2Fwp-devblog%2F2013%2F11%2Fgrid01f.png)