1

我正在做一个模拟，我需要能够处理更新每个循环的数千个潜在的数百万个对象。所有对象都需要具有称为（AI）的逻辑功能。但是根据对象的位置决定了逻辑的详细程度。例如：

[使用 100 个对象保持简单]

  • 所有对象都有一个位置 (x,y)
  • 20对象距离“兴趣点”位置 500 点。
  • 50对象距离对象 500 点20（距离 1000 点）。
  • 30对象距离兴趣点 100 点以内。

现在说这是一个详细的城市模拟，对象是虚拟公民。下午 6 点，每个人都该下班回家睡觉了。

所以我们遍历所有公民，但我希望他们做不同的事情。

  • 最远的物体 (50) 下班回家睡觉直到早上。
  • 较近的物体 (20) 下班回家，吃点东西，然后睡到早上。
  • 最近的物体 (30) 下班回家，吃点东西，刷牙，然后睡到早上。

正如您所看到的，它们越接近兴趣点，逻辑就越详细。

我正在尝试找出迭代所有对象的最佳和最高效的方法是什么。用满手的物体，这将是相对容易的，但由于这需要有效地处理至少 500,000 个物体，我需要一些建议。

此外，我不确定是否应该在每个循环中遍历所有对象，或者最好在每个循环中遍历最近的对象，但每 10 个循环仅遍历更远的对象？

由于需要对象在靠近它们的其他对象之间进行交互的额外要求，我一直在想最好的方法可能是将它们组织成四叉树，但我不确定。似乎四叉树更适合静态内容，但我正在处理的对象，如前所述，有一个位置，需要移动到其他位置。我是否走在正确的思考轨道上？或者，还有更好的方法？

如果有人认为它相关，我也在使用 c++ 工作。

任何建议将不胜感激。

笔记：

  1. 兴趣点定期变化，将其视为相机视图。
  2. 对象是动态创建和销毁的
4

4 回答 4

1

如果您想从特定点快速选择特定半径内的对象，那么四叉树或简单的方形网格会有所帮助。

如果您的问题是如何存储数百万个对象以有效地通过它们进行迭代，那么您可能可以使用基于列的技术，而不是每个具有 5 个字段的 100 万个对象，而是每个具有 100 万个元素的 5 个数组。在这种情况下，每个对象只是范围 0 .. 999999 中的一个索引。因此，例如，您要存储 100 万个具有以下结构的对象：

struct resident
{
    int x;
    int y;
    int flags;
    int age;
    int health; // This is computer game, right?
}

然后，不是声明，而是resident residents [1000000]声明 5 个数组：

int resident_x [1000000];
int resident_y [1000000];
int resident_flags [1000000];
int resident_age [1000000];
int resident_health [1000000];

然后，而不是，说，residents [n].x你使用resident_x [n]. 当您需要遍历相同类型的所有对象并对每个对象中的几个字段（每个对象中具有相同的字段集）执行某些操作时，这种存储对象的方式可能会更快。

于 2013-02-14T21:02:58.460 回答
0

您需要将问题分解为“类”，就像在现实世界中一样。每个人的班级都是根据距离计算的。所以下层人远，上层人近。或者更准确地说是“远类”、近类和“这里类”或任何你想命名的东西。

1）为每个班级制作一个带有一个插槽的数组。该插槽将保存该班级中每个人的“链接列表”。当一个人的类别改变者（社交攀登者）时，将对象移动到另一个列表是非常迅速的。

2）所以把每个人都放到适当的类中，只迭代你附近的类。在适当的情况下，有些对象需要关心很远，因此您可以将它们放回磁盘并仅在您靠近时重新加载。

于 2013-02-14T21:13:01.873 回答
0

有几个问题嵌入其中： - 如何处理大量的对象？如果有固定数量的固定对象，您可以简单地创建它们的数组，只要您有足够的内存。如果您需要动态地创建和销毁它们，那么如果没有仔细处理被销毁的对象，您就会面临内存泄漏的风险。在某个时候，您可能会问自己，使用其他应用程序（例如数据库）来存储对象并仅执行 C++ 代码中的逻辑是否更好。数据库将提供我将重点介绍的其他功能。

-如何在与他人的给定距离内找到对象。这是地理信息系统（GIS）的经典问题；听起来您正在尝试操作一个简单的 GIS 来存储您的对象和属性，因此它是适用的。在每个点上测试距离公式 SQRT((Xx)^2+(Yy)^2) 需要计算能力。相反，通常使用“窗口函数”来提取包含您想要的所有点的正方形，然后在其中搜索以找到特定位于给定半径内的点。一些数据库经过优化以执行各种 GIS 功能，包括返回给定半径内的点，或返回一些其他几何形状（如多边形）内的点。否则，您必须自己编写此功能。

- 对象的树存储。这可以提高速度，但是如果对象不断地四处移动，您将需要权衡，其中必须经常重组树。这完全取决于事物移动的频率与您希望对其进行计算的频率。

-人工智能代码。如果您尝试对数百万个对象进行 AI，这可能是您对性能的最大使用，而不是用于存储和搜索对象的方法。你是对的，对于更远的点，更简单的代码会提高性能，对于更远的点执行逻辑的频率也会降低。这有时使用蒙特卡洛分析来处理，其中逻辑将在任何给定迭代期间对点的随机子集执行，并且随着与感兴趣点的距离增加，执行的概率可能会降低。

于 2013-02-14T21:13:19.120 回答
0

我会考虑使用带有 Morton 编码/Z-Order 索引的线性四叉树。您可以通过使用位数组来表示包含数据并非常快速地执行计算的节点来进一步优化此结构。

我使用 Javascript 在浏览器中非常有效地完成了这项工作，并且可以在亚秒内遍历 6700 万个节点。一旦我将其缩小到感兴趣的区域，我就会以不同的结构查找数据。所有这一切仍以毫秒为单位。我将它用于空间矢量动画。

于 2014-04-05T19:00:13.550 回答