■ - rieslingの日記

本当はこっちが今日書こうと思ってたこと。メモだけ。
今週はちょっと忙しいので明日書けるかは不明。

ダイクストラ法のデータ保持構造について書いたけど、ゲームに使うことを考えるとそれほど問題を一般化する必要はないわけで。とりあえず経路探索が必要そうなの考えてみると。

SRPG：せいぜいMAPサイズ100×100程度だろうし配列で確保しておけば…速度はあんまり気にしなくてよさそう。
FPS：物にもよるけどまあ普通にやってれば問題なさそう。環境変化も少ないだろうしナビゲーションメッシュやウェイポイントの前計算しておけばいいだろう。それより操作なんかに対する応答性の方が重要そう。
RTS：まともに相手してたらどうしようもない。

と、まあRTS以外にはほとんど関係ない気がするけれども。

なんか話がずれたけど、ダイクストラ法とA*の違いはヒューリスティック関数h()。A*でｈ()が0の場合がダイクストラ法となる。ってのは前書いたとおり。
で、同様にA*でもデータ構造としてバイナリヒープ等が有効ってのは変わらない。フィボナッチヒープは…ノード数の関係上、微妙かも。

ただしA*ではh()という要素が加わったことによって最適なデータ構造ってのにちょっと違いが出てくる。

続きはまた今度。