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

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

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

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

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

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

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

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

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

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

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

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

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

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