有效发现远程目标

我正在创建一个自上而下的二维战略游戏,一个正方形的网格地图。 到目前为止,我已经使用Bresenham的线画algorithm来确定每个单元的LOS中的什么,然后设置圆中的一个目标。 现在我发现,这限制了我的部队只射击他们看到的目标。 我想扩展我的瞄准algorithm,使我的武器范围内的任何其他单位都瞄准目标,即使他们在这个给定单位的视距范围之外,如果他们被另一个友方单位“发现”的话。 换句话说,我希望能够使用距离比视距更远的武器。 有没有比遍历所有有视觉的单位和计算范围和LOS到每一个更好的方法?

如果你把四边的单位存放在一个四叉树中,你可以很便宜地避免迭代超出范围的敌方单位(假设你的单位不能超过一半的单位)。

如果你在每个四叉树中存放你的单位列表,按其是否被看到(例如,只有两个列表),你只需要计算一个单位和一个敌人之间的视距(LoS),如果它可能没有被盯住。

如果你跟踪谁先看谁,你只需要在其中一个移动时重新计算LoS。

切线相关,这里是如何有效地计算单位(我的博客)的可见 。 如果你只想计算单位之间的LoS,并且不需要瓦片可见度(例如雾战),那么使用Bresenhams检查LoS可能是更好的select。

小复杂:Bresenhams实际上并没有访问一行中的所有瓷砖! 它会错过一些。 如果你需要一个精确的计算,看看我自己的问题 (3D,但在2D中的问题是相同的)。