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

Question

这个问题

对不起标题,似乎找不到更短/更好的描述..

情况就是这样:我正在制作一个简单的游戏,其中有一张大地图(简单,但尺寸非常大).该地图上还有很多敌人,但动作仅限于主角(在某个半径范围内,这是地图的一小部分).

在每个'tick'(或步骤,或者你称之为的任何东西)中,每个对象上都会调用一个函数来确定它们的下一步动作.出于性能原因,由于我不关心在我的视图范围之外发生了什么(或者至少是非常远的东西),我不想在非常外来的对象上调用该函数.

如何管理这些对象以确保我总是有一个附近对象的列表,当我在地图上移动时会更新这些对象？

(我知道它是用C++标记的,但任何语言都可以 - 我不是在寻找那么多的代码 - 更多的是关于这个想法)

我尝试了一些替代方案:

备选方案1:在"区域"中分隔我的地图,并在每个区域中存储敌人列表.问题就是当我在这些区域的边缘时发生的事情(更糟糕的是)当我在一个角落(我周围的4个不同区域)时.此外,如果我从一个区域跑到另一个区域,那么让敌人更难切换区域(但我已经找到了可以工作的东西......)
备选方案2:每次移动x距离时扫描整个地图并刷新活动的敌人列表.这有点好,因为我不必担心像备选方案1这样的大量界限,但我每次都必须扫描整个地图.

我现在正在研究备选方案3,即将这两种解决方案混合在一起.

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

Answer 1

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