有效地迭代和存储数以千计/数百万个对象

我正在开发一个模拟器，我需要能够处理数千个潜在数百万个更新每个循环的对象。所有对象都需要具有称为（AI）的逻辑功能。但取决于对象的位置决定了逻辑的详细程度。例如：有效地迭代和存储数以千计/数百万个对象

[100个对象合作，以保持它的简单]

所有对象都有一个位置（x，y）的
20对象是500点远离从'的景点位置。
50对象是500点从20对象（1000点的距离）。
30对象内的兴趣点100个点。

现在说这是一个详细的城市仿真的对象是虚拟的公民。在下午6点，每个人都应该从工作中回家睡觉。

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

更远离物体（50）回到家中从他们的工作和睡觉直到早晨。
较近的物体（20）从他们的工作回家，有一个咬吃，然后睡觉，直到早晨。
最接近的对象（30）去从他们的工作家，得一口一口吃，刷牙然后睡觉，直到早上。

正如你可以看到他们是接近的兴趣点的更详细的逻辑变。

我正在努力研究什么是最好和最有效的方式来遍历所有对象将是。这将是一个相对容易的手充满对象，但因为这需要处理至少500,000对象有效，我需要一些建议。

而且我不知道我是否应该通过所有对象的每一个循环迭代或者它会更好地迭代通过最近的物体的每一个循环，但每10个循环只有itereate通过渐行渐远的对象？

与需要的对象与其它对象之间的互动接近他们的附加要求，我一直在想这样做可能是组织他们在四叉树的最佳方式，但我不知道。看起来好像四叉树对于静态内容更多，但我所处理的对象具有一个位置，并且需要移动到其他位置。我是否正在思考的正确轨道？或者，还有更好的方法？

我也在C++中工作，如果有人认为它的相关。

任何意见，将不胜感激。

注：

的兴趣变化点定期，认为它是一个摄像头视图。
对象是动态创建和

来源

2013-02-14 xyz

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

如果你的问题是如何存储数以百万计的对象来有效地迭代它们，那么你可能可以使用基于列的技术，而不是每个拥有5个字段的100万个对象时，有5个包含100万个元素的数组每。在这种情况下，每个对象只是在范围0 999999因此，举例来说，要存储以下结构的百万对象的索引..：

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-14 21:02:58

因此，第一个数组最接近点，第二个数组接近第二个数组......然后在数组之间移动对象，取决于对象与点的距离如何？我忘记提及的唯一问题是感兴趣的点会改变，所以会有很多数组交换。 – xyz 2013-02-14 21:06:49

@xyz号只需添加更多细节。 – 2013-02-14 21:25:39

对不起，我想知道。谢谢你为我清理这个。 – xyz 2013-02-14 21:27:50

您需要将问题分解为“类”，就像在现实世界中一样。每个人的课程都是从距离计算的。所以低阶层的人远离上流社会。或者更准确地说是“远距离课堂”，近距离课堂和“这里上课”，或者任何你想要给他们命名的东西。

1）为每个类创建一个插槽。该插槽将保存该班级中每个人的“链接列表”。当一个阶级转换者（社会登山者），那么将这个对象转移到另一个列表是非常迅速的。

2）因此，把每个人都放到适当的类中，只迭代接近你的类。在适当的场景中，有些对象需要远离关心，因此您可以将这些对象放回到磁盘上，并在距离较近时重新加载。

来源

2013-02-14 21:13:01

我不知道计算时间是否会有好处？由于每个循环都需要检查所有对象类的关联，以确保它们仍然属于正确的类，并且不会改变它们的类。如果（citizen [i] - > class == far && citizen [i] - > distance> = 1000）继续，则为（i = 0; i xyz 2013-02-15 02:30:30

当分配距离或类时，班级是否改变。不在循环中。所以当你设置距离时，或者类创建一个名为update class的函数并在那里检查它。因为列表链接交换类是快速的。 – 2013-02-15 13:57:50

是的，使用链表，没有for循环与我整数。使用链表来循环它。它必须是一个链表，以便类可以快速更改。 – 2013-02-15 13:58:33

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

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

- 对象的存储。这可以提高速度，但是如果物体不断移动，你就会进行权衡，其中树必须经常重构。这一切都取决于事情多久发生一次，以及你想多久进行一次计算。

-AI代码。如果您想要对数百万个对象执行AI，这可能是您最大的性能使用，而不是用于存储和搜索对象的方法。对于远离点的较简单的代码会提高性能，正如对较远点执行逻辑的次数较少一样。有时使用Monte Carlo分析来处理这个问题，在任何给定的迭代中，逻辑将在随机子集上执行，并且随着距兴趣点距离的增加，执行概率可能会降低。

来源

2013-02-14 21:13:19

我会考虑使用带莫顿编码/ Z顺序索引的线性四叉树。您可以通过使用位阵列来表示包含数据的节点并快速执行计算，从而进一步优化此结构。

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

来源

2014-04-05 19:00:13 theoutlander

有效地迭代和存储数以千计/数百万个对象

回答

相关问题