TLpath (日本語)

TLpath について

TLpath は LÖVE へ経路探索を追加します。それは多数の商用ゲームにて使用されている優秀な 探索アルゴリズムを最適化実装にて使用します。それには 50 ノード以上から成る迷路において 0.015 秒ほどで最適経路探索能力を実証するデモが付属しています。TLpath はスレッディングを使用しており、 LÖVE version 0.7.1 以降でのみ動作するという意味であり、さらに TSerial (同梱済み) を要求します。

このライブラリの使用条件は ZLIB ライセンスです。

入手先

Dropbox から直接入手

連絡先

準備

モジュールにある全ての関数は TLpath 名前空間に存在しており、従ってグローバル変数への干渉を心配する必要はありません。それは通常においてホストとなるゲームの継続的実行を可能にするために、個別のスレッドにて動作を行います。

  1. あなたのゲームのフォルダへ TLpath.lua および TSerial.lua を配置します。
  2. main.lua の先頭へ、 require"TLpath" の行を追加します。
  3. love.update() へ、 TLpath.update() の行を追加します。

よくある質問と回答

Q) ノードとはなんですか?
A) A* は、ほぼ全ての経路探索アルゴリズムと同様に、速度の増加に対してノードを使用します。それらは単に別のノードへの接続を行う地点です。 TLpath では、それらはテーブルのリストであると想定されており、例えば、 {{x=1,y=1}, {x=5,y=3}, {x=2,y=8}, {x=9,y=6}} です。技術的な言及として、ノードは x および y の値は不要であるが、なんらかの関連する情報を内包している場合があります。さらにノードには dests テーブルを内包している場合があり、それは到達可能なノードの indexen およびその接続の g 計数を内包しています。
Q) g 計数とはなんですか? h 計数? f 計数?
A) この説明には Wikipedia に掲載されている A* アルゴリズムの記事を読まれることを強くお勧めします。
Q) TLpath にて g 計数および h 計数を計算するために異なる関数を使用することができますか?
A) はい。 TLpath.setGfunction() および TLpath.setHfunction() にて可能です。
Q) ゲームにおいて単体関数では複雑すぎて計算不能なノード関係があります。それらを自身で設定できますか?
A) TLpath.calcNodes() にてノードの一覧が既にdest テーブルにある場合は、テーブルはそのままにしておいてください。 Dests は node.dests = {neighbor_index = g_factor_number} の形式を要求します。
Q) 動的および静的ノードの間にある違いは何ですか?
A) 静的ノードはノードグラフおよび g 計数の事前計算を行うため、全ての経路探索に対する高速計算を可能にしますが、この計算が完了するまで時間が掛かる場合があります (この時間の間はゲームがフリーズしたままになります)。この遅延は動的ノードにはありませんが、経ー路検出までに時間が掛かります。ゲームがノードおよび・または接続を頻繁に変更しない場合は一般的には静的方式が望ましいです。
Q) どうすれば TLpath の処理状況を検知できますか? エラー発生時に何が起こりますか?
A) TLpath は処理状況の詳述するためのメッセージとして TLpath.status の文字列を更新します (love.timer が利用可能であれば時間間隔情報も内包します)。 TLpath またはスレッドでエラーが発生した場合は、 LOVE の標準エラー画面を呼び出します。

関数

TLpath.calcNodes

TLpath.calcNodes(nodes, dynamic)

この関数は TLpath が使用するノードグラフを更新します。ノードまたは接続が変更される場合は常に使用してください。非動的ノードは計算に時間が必要ですが、動的ノードより一般的には好ましいです。

table nodes
ノードの一覧。用例としては: {{x=1,y=1}, {x=5,y=3}, {x=2,y=8}, {x=9,y=6}}
boolean dynamic
true ならば、ノード関係は事前計算されず、条件変更下にて経路即時計算開始を可能することで、静的ノードより処理時間を短縮します。非動的ノードを推奨します。

TLpath.setGfunction

TLpath.setGfunction(f)

この関数は g 関数の指定に使用されます。 g 関数はノートが別の場所へ到達できるかどうかを決定するために呼び出されるため、方法としては "高価な" 結果の経路になります。これを適合させるには恐らくゲームへ変更を加える必要があります。

string f
ノード・グラフ計算時に呼び出される関数に対する Lua コードの文字列。関数の引数として二つのノードが渡され、 nil (経路が一番目から二番目へ達することができない場合)または数値 (経路の g 係数)のいずれかを返すことが想定されています。デフォルト値では、 [[local d = ((b.x-a.x)^2+(b.y-a.y)^2)^0.5 return d<=100 and d or nil]] であり、間隔が 100 ピクセル未満ならばノードはその間の移動のみができること意味します。

TLpath.setHfunction

TLpath.setHfunction(f)

TLpath.setGfunction() と非常に似ていますが、ゴールからノードへのヒューリスティックな要因の計算を除いたものです。この関数はノードからゴールの経路の実質対価を表す以下または等価 (以上ではない) の数値を必ず返します。標準の h 係数が経路の実質対価に近接しているほど経路探査の計算はより高速になります。h 関数はただノードとゴール間の距離を計算するなので、それは高速でありほとんどのゲームにおいて適しています。

string f
[[return ((goal.x-a.x)^2+(goal.y-a.y)^2)^0.5]] へのデフォルト値。

TLpath.findPath

TLpath.findPath(ent, goal)

この関数は ent から goal までの経路計算を TLpath へ命じます。 ent は経路のリストを内包するテーブルであり、 goal はノードのインデックスです。パスは要求された順に一括計算、および検索するために少し時間が掛かる場合には、パスの要求および受信にて小規模の遅延が発声する場合があります。パスの検出時、 ent のパステーブルを更新します。 goal が ent の現在位置へ到達できない場合は、 ent.path.unreachable は true と等価であり現在の ent における残りのパスは変更されません。

table ent
テーブルには最低でも一つのノード・インデックスのリストがあるパス・テーブルを内包しています (つまり、 現在 ent が設置されている場所)。
number goal
到達先のノード (すなわち、 nodes[goal] = 希望するノード)。

TLpath.cancelPathfinding

TLpath.cancelPathfinding()

これを呼び出すと経路探索キューを空にして現在行われている探索探索処理を全て取り消します: TLpath.calcNodes は経路検索の最中にノード・グラフの変更により発生する奇妙な挙動を防止するために自動的に呼び出します。

TLpath.update

TLpath.update()

これは TLpath のイベント (経路要求のスプーリング、スレッドからのデータ受信、など) を扱うために love.update() にて呼び出してください。

そのほかの言語