gamedev中最基本的规则之一是通过利用游戏玩法定义的所有可能限制来优化算法中的优势 - 这是您没有看到基于任何给定公司游戏引擎构建的截然不同的游戏的主要原因,他们如此有效地利用了他们的约束,以至于他们无法处理不受这些限制的任何事情。
也就是说,你说单位是直线移动的 - 你说玩家可以有3000个单位 - 即使我假设有8个玩家的3000个单位,每个玩家375个单位,所以我认为我可以安全地假设游戏步骤(我假设每个步骤都涉及您在上面描述的计算) 的 更多的单位不会改变他们的方向 强> 比改变方向的单位。
所以,如果这是真的,那么你想把你的所有作品分成两组 - 那些在最后一步改变方向的那些,以及那些没有改变方向的那些。
对于那些做过的人,你需要做一些计算 - 对于任何两个相反力量的单位,你想问'单位A何时会看到单位B给出单位A和单位B都没有改变方向或速度?(你可以处理加速/减速,但后来变得更加复杂) - 要计算这个,首先要确定单位A和单位B正在行进的向量是否会相交(简单的2D线交点计算,结合计算告诉你当每个单位都到达这个交叉点时 - 如果他们没有,并且他们现在无法看到对方,那么他们永远不会看到对方,除非他们中至少有一个改变方向。如果它们相交,那么你需要计算第一个和第二个单位通过交叉点之间的时间差 - 如果这个距离大于LOS范围,那么除非改变方向,否则这些单位将永远不会看到对方 - 如果这个差异小于LOS范围,那么再多(大力挥手)计算会告诉你 的 什么时候 强> 这个有福的活动将会举行。
现在,你所拥有的是一系列信息,这些信息分成了永远不会看到彼此的元素以及将来某个时间相互看到的元素 - 每一步,你只需处理改变方向的单位并计算他们的与其他单位的互动。 (哦,处理以前的计算告诉你的那些单位会相互看到 - 记住将它们保存在一个可插入的有序结构中)你有效地做了什么利用系统的线性行为来改变你的问题 的 “请问 强> 单位A见B'单位 的 '什么时候 强> 单位A见单位B'
现在,所有这些都说,这不是打折空间数据结构的答案 - 这是一个很好的答案 - 但是,它也能够处理随机运动中的单位,所以你想要考虑如何进一步优化这个过程 - 你还需要小心处理交叉区域的可见性,即两个不同区域边界的单位可能能够看到彼此 - 如果你有碎片倾向于聚集,使用具有可变维度的空间数据结构可能是答案是,不在同一地区的作品保证不能互相见到。
我用网格做这个。我认为商业RTS游戏是如何解决这个问题的。
现在,当一个单位从一个可见区域移动到另一个区域时,执行检查:
这很快但需要一些记忆。但是,使用BitArrays和指针列表,内存使用量不应该那么糟糕。
在Game Programming Gems的一本书中有一篇关于此的文章(我认为前三本书之一)。