找到最近移动 "enemy" 的最有效方法是什么？
What is the most efficient method to finding the closest moving "enemy"?
我见过一些类似的问题，但他们更侧重于比较两种不同的方法，而不是从更一般的意义上问。
但是当 "enemy" 和当前 player/NPC 都可以自由移动时，找到最近的 "enemy" 的最有效方法是什么？
如果敌人的位置是静态的，我想确定最接近的最有效的方法是根据他们的位置排序列表，然后使用二分搜索算法找到最接近的。然而，由于他们四处移动，我能想到的唯一解决方案是一个简单的 for 循环，它遍历每个敌人并将距离与最近的距离进行比较，运行时间为 O(n)。
这并不理想，尤其是当两个团队中都有多个实体时。假设 A 队有 100 个实体，B 队有 100 个实体。所有实体都不是用户控制的。这意味着团队 A 中的每个实体将每隔 x 秒迭代一次团队 B 中的所有实体，反之亦然。那是每 x 秒进行 20,000 次比较（如果我没记错的话）。
我没有任何代码可以分享，因为这是一个更普遍的问题，但几年前我在制作一个非常简单的游戏时确实使用了 for 循环方法，并且它对实体数量很少，但我相信我注意到大约 30-40 个实体存在性能问题。
感谢任何帮助。
您尝试解决的问题看起来像 最近邻搜索 或 n 体模拟。
如果您考虑需要在 n 个元素列表中找到最接近的元素的问题，那么您需要遍历所有元素。因此，最终的复杂度为 O(n)。你不能做得更好，因为你需要读取整个输入（n 个元素）。
如果您考虑这样一种情况，您想要在给定的 n 个元素列表中找到 每个 个元素 中最接近的元素，那么与测试所有可能的距离（复杂度为 O(n^2)）相比，您可以以更快的方式执行此操作。解决这个问题的常用方法是将所有元素放在 BSP-Tree data structure (such as Quadtree or Octree 中。这样的数据结构可以帮助您在 O(log(n)) 时间内找到某个位置附近最近的元素。因此，该方法的整体复杂度为 O(nlog(n))!
请注意，更新 BSP 树中元素的位置最多需要 O(log(n)) 次操作。因此，更新 n 个元素是在 O(nlog(n)) 时间内计算出来的。这比简单地更新第 n 个元素的位置（在 O(n) 中）的成本要高一些，但仍然相对便宜！
我见过一些类似的问题，但他们更侧重于比较两种不同的方法，而不是从更一般的意义上问。
但是当 "enemy" 和当前 player/NPC 都可以自由移动时，找到最近的 "enemy" 的最有效方法是什么？
如果敌人的位置是静态的，我想确定最接近的最有效的方法是根据他们的位置排序列表，然后使用二分搜索算法找到最接近的。然而，由于他们四处移动，我能想到的唯一解决方案是一个简单的 for 循环，它遍历每个敌人并将距离与最近的距离进行比较，运行时间为 O(n)。
这并不理想，尤其是当两个团队中都有多个实体时。假设 A 队有 100 个实体，B 队有 100 个实体。所有实体都不是用户控制的。这意味着团队 A 中的每个实体将每隔 x 秒迭代一次团队 B 中的所有实体，反之亦然。那是每 x 秒进行 20,000 次比较（如果我没记错的话）。
我没有任何代码可以分享，因为这是一个更普遍的问题，但几年前我在制作一个非常简单的游戏时确实使用了 for 循环方法，并且它对实体数量很少，但我相信我注意到大约 30-40 个实体存在性能问题。
感谢任何帮助。
您尝试解决的问题看起来像 最近邻搜索 或 n 体模拟。
如果您考虑需要在 n 个元素列表中找到最接近的元素的问题，那么您需要遍历所有元素。因此，最终的复杂度为 O(n)。你不能做得更好，因为你需要读取整个输入（n 个元素）。
如果您考虑这样一种情况，您想要在给定的 n 个元素列表中找到 每个 个元素 中最接近的元素，那么与测试所有可能的距离（复杂度为 O(n^2)）相比，您可以以更快的方式执行此操作。解决这个问题的常用方法是将所有元素放在 BSP-Tree data structure (such as Quadtree or Octree 中。这样的数据结构可以帮助您在 O(log(n)) 时间内找到某个位置附近最近的元素。因此，该方法的整体复杂度为 O(nlog(n))!
请注意，更新 BSP 树中元素的位置最多需要 O(log(n)) 次操作。因此，更新 n 个元素是在 O(nlog(n)) 时间内计算出来的。这比简单地更新第 n 个元素的位置（在 O(n) 中）的成本要高一些，但仍然相对便宜！