それなりブログ

とあるWebエンジニアのそれなりのブログ、JavaScript/Node.js/Python/PHP/ゲーム作成 など

pathsearcher.js ゲーム用移動経路探索ライブラリ

pathsearcher.js

pathsearcher.js というSRPGなどのゲームで使うことを想定した
JavaScript用移動経路探索ライブラリを作成しました

例えば、ファイアーエムブレムライクなSRPGにて
ユニット移動時の最短経路探索や移動コスト算出に使うことが出来ます

使い方の例

// 二次元配列で表現されたあなたのゲームのマップデータ
var yourSquares = [[マス,マス,マス, ..], [マス, ..], [マス, ..], ..];

// インスタンス生成
var ps = new PathSearcher();

// あなたのマップデータを取り込み
ps.load(yourSquares, function(あなたのマス){
    if (あなたのマス.進入禁止条件) {
        return false; // falseを返すと進入不可として認識される
    }
    return あなたのマス.移動コスト;
});

// 移動経路探索
ps.search(始点座標, 移動力上限);

// 結果インスタンス取得
var result = ps.getResult();

// 結果インスタンスを操作してデータを取得
result.hasPathData(終点座標); // 終点に到達できるかを判定する
result.getPathData(終点座標); // 終点に到達できるならその情報を返す
result.getStepIndexes(終点座標); // 終点に到達できるなら経路の座標マップを返す
// ...等々、結果操作メソッドは他にもある

ご注意:ダイクストラ法に準拠していない理由

コードを見られちゃうとわかってしまうのですが
ダイクストラ法
に完全準拠したアルゴリズムになっていません

なんでそれを素直にコード化しなかったの?という点については
単なる調査不足に過ぎないので、全然良いことでは無いっす
(性能向上の為に、一部を意図的に変えるとかならともかく)

SRPG用の移動経路探索アルゴリズム自体は
大昔に、それこそエンジニア成りたての頃に調べたことがあって
一応5分ぐらいはググったけど、概ねその記憶を元に作ってしまっただけです

事後に追加で15分位ググったら、ダイクストラ法のみならず
JavaScriptでダイクストラ法 というベストマッチなエントリまで発見してしまい・・・

ただ、「ノードを合計移動コストが低い順に走査してゆく」という
基本的なアルゴリズム自体は一緒で(というか、普通に自分で考えてもこうなる)
四方マップに限れば、2次元配列による ネイティブな [行][列] 操作が可能なので
おそらくは、ダイクストラ法を素直に表現するよりも処理は早くなってると思います

蛇足

「斜め移動」や「移動方向によってコストが変わる」(いわゆる高さの概念)を実現する場合
「マスが隣接マスリストを持ってそれを走査して行く」という
よりダイクストラ法的な形に作り直さないと無理、というか逆に非効率になりそうだと思いました
Node は neighbors を持ち、間に Route がある的な感じですね

そうすると遅くなるので、その対策をして・・・、となると結構大変なので
今度こそは、誰か作った物が無いかをちゃんと探そうと思います!



コメントを残す

メールアドレスが公開されることはありません。

Categories

Archives