游戏的棘手线算法(语言不可知)

Question

我需要帮助创建一个专门的线碰撞算法,允许在某些角度"切角".

在下面的图片中,让蓝色方块代表玩家,黑色方块代表墙壁.然后,白色方块表示玩家"视线"中的方块(有效方块),灰色方块是玩家"视线"外的方块(无效方块):

第二张图片是我们开始偷工减料时事情变得更有趣的地方:

让我们仔细看看这条线尽管经过墙角但仍允许这条线:

该行是允许的,因为:

• dx <= 0.5(正方形为1x1)
• dx/dy超过一定的比例(比如,2 - 我不确定这些图像中表示的确切值.)

不允许使用相反的行,因为比率(在这种情况下为dy/dx)太低:

或许我应该谈谈进入的角度与广场的退出......

我遇到的主要问题是我无法弄清楚如何对网格上两点之间以任意角度行进的向量进行推广.我无法决定是否应该使用三角法或什么.到目前为止,我最接近的解决方案是使用每个方格的线截取的小数部分作为dx和dy,并根据线的斜率和它所在的象限检查是否允许它.

有人可以帮忙吗？

我也看过借用或从其他线算法开始,但我没有发现任何有用的东西.我见过的大多数人希望从(x1,y1)到(x2,y2)的行与从(x2,y2)到(x1,y1)的行相同,这使得这个问题大不相同.

Answer 1

我建议使用圆圈，它们在拐角方面是非常理想的。

我假设坐标是在每个像素的中心获取的。

了解 (xo,yo) 是否隐藏从 (xa,ya) 到 (xb,yb) 的视图的算法如下：

• 计算 (xc,yc) 从 (xa,ya) 到 (xb,yb) 的直线上最接近 (xo,yo) 的点
• 计算从 (xo,yo) 到 (xc,yc) 的距离 d
• 如果 d < 半个像素，则视图被隐藏

您可以通过直接计算点和线之间的距离来简化前两个阶段http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line并最终计算平方距离（如果您想避免 sqrt）