1

オブジェクトのリストを（.1）秒ごとに更新するプログラムに取り組んでいます。プログラムがリストの更新を終了すると、プログラムは、オブジェクトが他のオブジェクトから特定の距離内にあるかどうかを認識します。すべてのオブジェクトには、グラフ上でX、Yの位置があります。すべてのオブジェクトには、「範囲」と呼ばれる値があります。ティック（.1s）ごとに、プログラムは距離式を使用して、他のオブジェクトが処理中のオブジェクトの範囲以下であるかどうかを計算します。

たとえば、ポイントAの範囲が4で、（1,1）にあり、ポイントBが（1,2）にある場合、距離の数式は〜1を返します。これは、ポイントBがポイントAの範囲内にあることを意味します。これに似たものになります：

objects = { A = {X = 1,Y = 1,Range = 4}, B = {X = 1,Y = 2,Range = 3}, C = {X = 4,Y = 7,Range = 9} }

while(true) do
 for i,v in pairs(objects) do
   v:CheckDistance()
 end
wait()
end

-- Point:CheckDistance() calculates the distance of all other points from Point "self".
-- Returns true if a point is within range of the Point "self", otherwise false.
--

問題：グラフには200を超えるポイントが含まれている可能性があり、各ポイントには、存在する他のすべてのポイントに数学が適用されます。これは、すべてのポイントで.1秒ごとに発生します。私が使用している3D環境では、これにより速度が低下したり、ラグが発生したりする可能性があると思います。

質問：これはこれを行うための最適な方法のように聞こえますか？これをより効率的/迅速に行う方法について、あなたはどのように考えていますか？

4

2 に答える 2

3

Alex Feinamnが言ったように、原始的なものではありますが、独自の衝突検出器を作成しているようです。

ただし、2D または 3D 平面上にポイントがあるかどうかはわかりません。あなたは、すべてのオブジェクトが「グラフ上に X、Y 位置を持っている」と言い、さらに「私が使用している 3D 環境でのラグ」について話します。

2D と 3D の両方の物理学 (および Lua) はよく発達した分野であるため、最適化に事欠きません。

空間ツリー

四分木(または3Dの八分木) は、2 つの世界全体を 4 つの正方形に分割された正方形として表し、それぞれが 4 つの正方形に分割されるなどのデータ構造です。 四分木の例

この便利なサイトでインタラクティブな例を自分で試すことができます。

一般に、空間ツリーは、ローカライズされたポイントへの非常に高速なアクセスを提供します。 四分木で検索する例

円は、特定の粒子の相互作用半径を表します。ご覧のとおり、トラバースする必要があるブランチを正確に見つけるのは簡単です。

点群を扱うときは、2 つの点が同じ場所を共有していないこと、またはツリーに最大分割深度があることを確認する必要があります。そうしないと、枝を無限に分割しようとします。

Lua での octree の実装については知りませんが、作成するのはかなり簡単です。例が必要な場合は、Python または C の実装を探してください。テンプレートの狂気を処理できない限り、C++ で検索しないでください。または、Lua API バインディングまたは FFI ライブラリを介して C または C++ 実装を使用することもできます (推奨、バインディング セクションを参照)。

LuaJIT

LuaJITはカスタム Lua 5.1 インタープリターおよびジャストインタイム コンパイラーであり、大幅な速度とストレージの最適化を提供するだけでなく、整数などの C 関数と型を簡単かつ効率的に使用できるようにする FFI ライブラリーも提供します。

C 型を使用してポイントと空間ツリーを表すと、パフォーマンスが大幅に向上します。

local ffi = require"ffi"
ffi.cdef[[
    // gp = graphing project
    struct gp_point_s {
        double x, y;
        double range;
    };
    
    struct gp_quadtree_root_s {
        // This would be extensive
    };
    struct gp_quadtree_node_s {
        // 
    };
]]

gp_point_mt = {
    __add = function(a, b)
        return gp_point(a.x+b.x, a.y+b.y)
    end,
    __tostring = function(self)
        return self.x..", "..self.y
    end
    __index = {
        -- I couldn't think of anything you might need here!
        something = function(self) return self.range^27 end,
    },
}
gp_point = ffi.metatype("struct gp_point_s", gp_point_mt)

-- Now use gp_point at will

local p = gp_point(22.5, 5.4, 6)
print(p)
print(p+gp_point(1, 1, 0))
print(p:something())

LuaJIT は、gp_point の実行時の使用法をネイティブ アセンブリにコンパイルします。これは、場合によっては C のような速度を意味します。

Lua API と FFI

これはトリッキーです...

Lua API を介した呼び出しは、Lua 状態に対して権限があるため、適切に最適化できません。一方、LuaJIT の FFI を介した C 関数への raw 呼び出しは完全に最適化できます。

コードの相互運用方法を決定するのはあなた次第です。

  • スクリプト内で直接 ( Lua、制限要因: 動的言語はある程度しか最適化できません)
  • スクリプト -> アプリケーション バインディング ( Lua -> C/C++、制限要因: Lua API)
  • スクリプト -> 外部ライブラリ ( Lua -> C、制限要因: なし、FFI 呼び出しは JIT コンパイル)

デルタ時間

本当の最適化ではありませんが、重要です。

ユーザー インタラクション用に設計されたアプリケーションを作成している場合は、タイム ステップを修正しないでください。つまり、すべての反復に正確に 0.1 秒かかると想定することはできません。代わりに、すべての時間依存操作に時間を掛ける必要があります。

pos = pos+vel*delta
vel = vel+accel*delta
accel = accel+jerk*delta
-- and so on!

ただし、これは物理シミュレーションです。Glenn Fiedler によって議論されているように、物理学の固定時間ステップと可変時間ステップの両方に明確な問題があります。

タイムステップを修正するか爆発する

... 車のシミュレーションで、ショックアブソーバーに一連の非常に硬いスプリング制約がある場合、dt のわずかな変化によって実際にシミュレーションが爆発する可能性があります。...

固定の時間ステップを使用する場合、シミュレーションは理論的には毎回同じように実行されます。可変時間ステップを使用すると、非常に滑らかになりますが、予測できません。ご教授をお願いしたいと思います。（これは大学のプロジェクトですよね？）

于 2012-10-15T04:20:55.920 に答える
0

特定の状況でそれが可能かどうかはわかりませんが、ループではなくイベントを使用することは間違いありません。これは、ポイントがその位置を変更したときに追跡し、それに反応することを意味します。これは、必要な処理が少なく、1 秒ごとよりも速く位置を更新するため、はるかに効率的です。これらのイベントが非常に頻繁に呼び出されるため、ポイントが変動する場合は、おそらく時間あたりの関数呼び出しの上限を設定する必要があります。

于 2012-10-08T18:45:04.187 に答える