AI::Pathfinding::AStar - Perl implementation of the A* pathfinding algorithm

Location : Home > Languages > Perl > Package
Title : AI::Pathfinding::AStar

　AI::Pathfinding::AStar - A* Pathfinding アルゴリズムの実装

package My::Map::Package;
use base AI::Pathfinding::AStar;

# AI::Pathfinding::AStar で要請されるメソッド
sub getSurrounding { ... }

package main;
use My::Map::Package;

my $map = My::Map::Package->new or die "No map for you!";
my $path = $map->findPath($start, $target);
print join(', ', @$path), "\n";

説明

　本モジュールは A* pathfinding アルゴリズムを実装している。マップオブジェクトからのベースクラスとして稼動する。マップオブジェクトから getSurrounding（後述）と言う名前のサブルーチンを必要とし、オブジェクトに findPath（後述）と言う名前のルーチンを提供する。AI::Pathfinding::AStar は findPath ルーチンによってのみ利用される２つのサブルーチン（calcF 及び calcG）を定義する。

　AI::Pathfinding::AStar はマップオブジェクトが、経路を求めたい始点ノードと終点ノードのIDを受け取る getSurrounding と言う名前のルーチンを定義することを要請する。返り値には以下の情報を含む配列参照が含まれる。

ノード ID
ノードに入るコスト
ヒューリスティック

　基本的には [ [$node1, $cost1, $h1], [$node2, $cost2, $h2], [...], ...]; のような配列参照が返り値となるが、ヒューリスティックやそれらを計算する最善の方法に関するさらなる情報は後述する参考資料セクションに掲げたリストを訪問すること。ルーチンの書き方に関する短い説明はテストに含まれているものを参照のこと。

　前述したように AI::Pathfinding::AStar は始点と終点を入力として必要とするルーチン findPath を提供する。findPath ルーチンはノード ID の選択のフォーマットを問題にしない。それぞれユニークであり、Perl の exists $hash{$nodeid} で識別できるならそれで動く。返り値には、終点までの最小コスト経路を示すノードが配列（または参照）として含まれる。空配列が返り値の場合は、所与の資源では到達できないことを意味する。

必要条件

　本モジュールは機能するのに Heap::Simple を必要とする。最大の互換性を確保するのに現在では Makefile.PL で Heap::Simple::Perl を必要とする。しかし、もしユーザの環境に C コンパイラがあるのであれば、最速の結果を得るには Heap::Simple::XS をインストールするとよい。

参考資料

　Heap::Simple, http://www.policyalmanac.org/games/aStarTutorial.htm、http://xenon.stanford.edu/~amitp/gameprog.html を参照のこと。

著者

　Aaron Dalton - aaron@daltons.ca

　このモジュールは、私にとってまったく最初の CPAN への貢献であり、私は職業的なプログラマではない。スタイルの問題も含めてフィードバックは歓迎する。それを採用することを希望する。

著作権とライセンス

　本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

Updated : 2006/11/24