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 个点，每个点都会对存在的每个其他点进行数学运算。这将在每 0.1 秒的每个点上发生。我想这可能会减慢或在我使用的 3D 环境中产生延迟。

问题：这听起来像是执行此操作的最佳方式吗？您对如何更有效/更快地完成这项工作有什么想法？

4

2 回答 2

3

正如Alex Feinamn所说：看起来你正在制作自己的碰撞检测器，尽管它是一个原始的。

但是，我不确定您是否在 2D 或 3D 平面上有点。您说每个对象“在图表上都有一个 X、Y 位置”，并进一步谈论“我正在使用的 3D 环境中的滞后”。

嗯，2D 和 3D 物理——以及 Lua——都是发达的领域，所以不乏优化。

空间树

四叉树（或3D的八叉树）是一种数据结构，将您的整个 2 世界表示为一个分为四个正方形的正方形，每个正方形又分为四个正方形，依此类推。 四叉树的一个例​​子

您可以在这个方便的站点上自己试验一个交互式示例。

空间树通常为本地化点提供非常快速的访问。 在四叉树中搜索的示例

圆圈代表特定粒子的相互作用半径。如您所见，很容易准确地找到需要遍历哪些分支。

在处理点云时，您需要确保两个点不共享相同的位置，或者您的树有一个最大的划分深度；否则，它将尝试无限地划分分支。

我不知道 Lua 中的任何八叉树实现，但制作一个非常容易。如果需要示例，请查找 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 函数的原始调用可以完全优化。

由您决定代码应如何互操作：

  • 直接在脚本内（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 回答