如何实现D&D 4e的视线algorithm?

D&D第四版(桌面游戏)在2D地图上进行了方块拼图战斗。 一个生物占据整个单一的瓷砖。

攻击者对防守者有清楚的认识,如果线路可以从攻击者的正方形的一个角落被引到防御者正方形的所有四个角落,并且这些线没有被阻拦。

规则如下:

要确定一个目标是否有遮盖,请select您的正方形的一个角并跟踪从该角到该目标的正方形的每个角的虚线。 如果其中一条或两条线被障碍物阻挡,则目标有掩护。 (如果它沿着障碍物或敌人的方格的边缘行,则不会被阻挡。)如果其中三条或四条被阻挡,但是具有效果线,则目标具有优越的掩护。

所以,在以下情况下:

D&D情况的地图

  • A可以完全看到B,但是C具有A的优越覆盖(未被阻挡的线从A的右上角到C的右上角),并且A根本看不到D.
  • B可以完全看到A,C和D.

我怎样才能实现呢?

多年来,我已经尝试了几种解决scheme:Bresenham的一些线条,逐个像素地testing墙壁,在角落附近给出一些宽容,甚至将地图划分为线段,并使用线将攻击者的线条与这些线段进行比较交互公式。 但是,一切都不够规则准确或计算过于昂贵。

这个视线algorithm是否可以高效地执行(足以使每秒100×100个贴图的地图可以执行数百次检查),并且准确无误地执行,如果是这样的话,怎么办?

我们可以通过将正方形和线段划分为4个线段来检查是否相交,然后使用下面的公式:

s = (1/d) ((x00 - x10) y01 - (y00 - y10) x01) t = (1/d) -(-(x00 - x10) y11 + (y00 - y10) x11) 

(x00, y00)是第一个线段的第一个点, (x01, y01)是第一个线段的第二个点,类似地(x10, y10)(x11, y11)分别是第二个线段的第一个点和第二个点。

如果这两个值都在[0, 1]范围内,则线段相交。

首先,你应该从地图上提取封面广场,然后当你需要检查可见性时,你把当前玩家所在的方块的4个点,为他们每个创建一个线段与四敌人所在的方格点(即16条线段),然后尝试将它们与每个封面正方形的边相交。

如果你想知道,这是64 *的碰撞检查,考虑如何简单的公式是没有多less