如何在C++游戏中处理大量对象

6

问题

抱歉标题有点长,但我实在找不到更好的描述方式了。

这是情况:我正在制作一个简单的游戏,其中有一张大地图(简单,但非常大)。地图上也有很多敌人,但行动范围仅限于主角周围的某个半径(这个半径只占地图的很小一部分)。

每次“打勾”(或步骤,或任何你想称呼的东西),都会对这些对象中的每一个调用某个特定函数来确定它们的下一步移动。出于性能考虑,因为我不关心视野范围之外的内容(或者至少是非常遥远的东西),所以我希望不要对那些非常遥远的对象调用该函数。

我该如何管理这些对象,以确保我始终拥有一个附近对象列表,并在我移动地图时得到更新?

(我知道它被标记为C ++,但任何语言都可以 - 我不需要太多代码 - 更多的是关于思路)


我已经尝试过的方法

我尝试了几种替代方案:

  • 替代方案1:将我的地图分成“区域”,并在每个区域中存储敌人列表。问题在于当我处于这些区域的边缘时会发生什么情况,以及当我处于角落时会发生什么情况(周围有4个不同的区域)。此外,如果我从一个区域跑到另一个区域,那么让敌人切换区域就会更加困难(但我已经想出了一些可行的方法...)
  • 替代方案2:扫描整张地图,并在每次移动x距离时刷新活动敌人列表。这个方法比替代方案1好一点,因为我不必担心边界问题,但我需要每次扫描整张地图。

现在,我正在考虑替代方案3,即将这两种解决方案混合在一起。

但是,我想确保是否有更明显的解决方案。


4
据我所知,Minecraft使用了替代方案1,因此这肯定是一个可行的解决方案。它可以同时保持多个区域处于活跃状态(比如说,一个8x8的正方形)。这消除了当你靠近一个区域的边缘时,旁边有一个被冻结在非活跃区域中的敌人的问题。 - Kevin
3个回答

4

将你的敌人存储在一个k-d树中,并每隔几次迭代进行空间范围搜索。但是,您需要一个相当复杂的实现来支持条目的移动和重新平衡 - 有时称为自适应k-d树。


1
看来我有些阅读要做(我早就预料到了)。非常感谢你的答案。 - OneMore

2

好的,如果您能回答以下问题,我相信我们中的一些人可以帮助您确定正确的数据结构和程序。 地图有多大?实际尺寸是多少? 请告诉我们敌人的密度有多高?平均有多少个敌人?我猜您将为每个游戏使用随机数量的敌人,或者每个等级增加敌人的数量。无论如何,请问您计划拥有的最大敌人数量是多少?

如果所有角色/敌人都动起来而不仅仅是围绕主角移动,那将是非常好的,这样才会使游戏真正激动人心。我相信您将使用许多随机数进行移动,但请尝试看看是否可以想出简单而现实的算法来控制它们的移动,而不是完全依靠随机移动。我已经尝试过随机移动,它们绝对没有趣味。也许您可以使距离主角非常近的敌人移动缓慢,而远离主角的敌人则快速移动。您可以在等级增加时增加敌人的速度和力量。尽可能使其激动人心。您可以尝试玩一下凯撒三游戏,看看人物的动作如何,简单而不失美观。 最重要的是,请考虑如何移动敌人,并尽可能地在每个时间段内移动所有敌人,以使游戏真正激动人心。


我不确定如何回答关于维度的问题,但如果主角是1x1的话,视野范围大约是20x20,整个地图超过200x200(因此视野范围小于地图的1%)。敌人的密度实际上取决于你所处地图的部分。给你一个平均值并不是一个很好的衡量标准,因为那些包含较少敌人的区域通常会有具有“更好”人工智能的敌人(因此每一步的资源更多)。目前我没有任何最大敌人数量的限制。谢谢您的回答。 - OneMore

0

200x200不算大。对于每个位置,如果在范围内,更新敌人将有效,除非你打算在计算器上运行它,或者想要每秒钟进行数千次更新。

不要过度设计,保持简单。只需使其易于更改,如果需要的话。


我通常遵循KISS原则。然而,我说200x200只是一个估计值。这不是平铺游戏,所以我不能只给你一个大小。但是,动作绝对是在地图的不到1%的区域内局限的,而且地图上几乎都是物体/敌人。这就是我想要表达的。我不能在每次更新时扫描整个地图(成千上万的敌人和环境物体),因为我需要经常更新游戏(可能不是1000次/秒,但肯定超过30次/秒)。但还是谢谢你的回答。 - OneMore
@OneMore 你想要支持的尺寸确实很重要。是200x200吗?2000x2000?20000x20000?2百万x 2百万?2十亿x 2十亿?在不同的规模下,处理这种情况的基本不同方法是最优的。 - Yakk - Adam Nevraumont
这不是一个基于瓷砖的游戏。我可以将其制作为1x1或5000x5000,对于我能够容纳多少内容以及算法如何工作都没有任何影响(无论如何都没有实际的“单位”)。我会相应地调整一切(我的视野范围将是0.0005x0.0005“单位”或其他)。如果不清楚,我的敌人不是存储在2D矩阵中。感谢您的时间,我将使用先前建议的k-d树。 - OneMore

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接