在2D游戏中计算网格中的可见点

我有一个游戏网格,我需要弄清楚哪些游戏网格点不在玩家视图的占用网格点之后。 可见的点 。 我想首先定义一个可见点,因为它可能意味着很多事情,我必须弄清楚:

  • 如果从参考点的中心到两个最近点的拐角的线不与任何占用点相交,我称之为点可见点。 在图像的下面,插图显示橙色不 可见,绿色可见
    图片描述

按照这个定义,我们可以制作这样的地图:

图片描述

传说:

  • 图片描述 – 可见像素
  • 图片描述 – 部分可见的像素
  • 图片描述 – 占用的像素
  • 图片描述 – 球员

我对部分可见的像素不感兴趣,但是我需要找出哪些像素是可见的。 我不知道从哪里开始。 我唯一的想法是循环角度,但这不适用于较大的地图,其中一个迭代跳过许多实际的像素。

我如何检查可见像素,或理想情况下只检查最远的可见像素,如下图所示:

图片描述

并且必须避免循环所有像素,这会消耗太多的性能。

诀窍是从源点投射光线到占用正方形的边缘。

然后按他们的角度排列光线。 然后,“扫掠”这些角度并剔除交点后面的像素。 有多种方法可以通过去除具有多个交点的光线来优化algorithm,因为这些光线总是在仅具有一个交点的光线之间。

另请参阅我在类似问题上的回答: 2D – 平滑光照和基于瓦片的游戏的阴影

下面是一个多边形环境下algorithm的例子: http : //ncase.me/sight-and-light/这个理论也很容易应用到一个网格中,因为这个网格可以用一些正方形的多边形来表示。