読者です 読者をやめる 読者になる 読者になる

2D マップ上の最短パスを求める新しいアルゴリズム S* の提案

はじめに

ゲームのキャラクタを自動で移動させる場合などに、 2D マップ上の2点間の最短パスを求めることが行われます。

典型的なやり方としては、マップを格子状のマス目に分割し、マス目ごとに通れるか通れないかを決定しておき、キャラクタの現在地である開始点と、目的地となる終了点との2点間のパス(経路)を A* アルゴリズムで求める、という方法が一般的かと思います。

しかし、マップをマス目に分割するのは、本当に必要なことなのでしょうか? もっと直接的に、幾何学的な最短パスを A* で求めればいいのではないでしょうか? ちょっと実装して実験してみました。

デモ

未署名の Java アップレットですすんません。 Java の設定でセキュリティを下げて実行してくださいすんません。

 

線の色は、パスの長さを表しています。パスが切り替わったときにも線の色が不連続には変化していないことから、等しい長さのパスの間で切り替わっていることが確認できます。

2点を変化させながらリアルタイムに探索していますが、 CPU をほとんど使っていないことがわかります。

S* アルゴリズム

上のデモで実装したアルゴリズムを、とりあえず「S*」と呼ぶことにします。「 Saito の A*」 の略です。単純なアルゴリズムなので、考え付いたのは私が最初というわけでもないでしょうし、既にちゃんとした名前があるようにも思いますが、知りません。

アルゴリズムの内容は、上のデモから一目瞭然なのですが、次のような感じです。

準備

  1. マップ上の障害物を、多角形で近似する。(上のデモでは、障害物の形状自体を三角形にしています。)
  2. 多角形の頂点同士を結ぶ線分のうち、多角形の内部を通過しないもののリスト(頂点間リスト)を作成する。

探索

  1. 頂点間リストに、開始点と終了点を一時的に追加する。
  2. 開始点から終了点に向かって、頂点間リストに A* アルゴリズムを適用する。このとき、 A* のヒューリスティック関数には、終了点までのユークリッド距離を用いる。

以上です。とてもシンプルですね!

マス目 A* との比較

従来の探索方法を、ここでは「マス目 A* 」と呼ぶことにします。

S* の利点

  • マス目に分割する必要がない。(マス目 A* では、マス目の分割のパラメータ(特にマス目の大きさ)で探索結果が変化しうるが、 S* はそのようなパラメータの影響がない。)
  • 常にユークリッド距離での最短パスが求まる。(マス目 A* では、通過するマス目の数が最小になるようなパスが求まるが、必ずしもユークリッド距離で最短とはならない…ですよね?)
  • パスが最初から折れ線で求まるので、折れ線化するための後工程が不要。(マス目 A* では、折れ線化が必要。)

S* の欠点

  • 見晴らしの良い広大なマップでは、頂点間リストを素朴に作ると、遠くの多角形同士の頂点間で無駄に多い線分が頂点間リストに登録されるので、工夫が必要。
  • 移動する障害物が多数あるような場合には不向きかも。
  • ていうか、実際のゲームなどのアプリケーションで試したことがないので、本当に実用に耐えうるのか疑問。誰かやってみてください!

S* アルゴリズムの利用について

S* アルゴリズムに関しては、私は、何らの主張もしません。しかし、他者が特許を取っている(またはこれから取る)可能性などについては関知しませんので、その点は自己責任でお願いします。

デモアプレットについては、著作権を主張します。 All rights reserved です。ていうか、突貫で作ったウンコードなので恥ずかしいから解析するな、ってことです。