C#: 2D子图块线相交

Question

C#: 2D子图块线相交

3

我遇到了一些问题，需要一个关于游戏算法的解决方案。谷歌上的大部分解决方案只适用于整个瓦片。在我的游戏中，单位可以占据瓦片内不同的位置，例如左上角、中间、右下角等（2/3），即（2.2/3.1）、（2.5/3.5）、（2.8/3.9）。如果它们从（2.2/3.1）移动到（5.7/4.1），我需要检查路径中是否有障碍物。我的当前算法是：1.从（2.2/3.1）开始；2.计算运动的角度（例如70度）；3.向该方向移动0.1步；4.检查我所在的瓦片（floor(p.X)/floor(p.Y)）；5.从第2步重复执行。这个算法可以工作，但我觉得它不太高效，因为障碍物只能是整个瓦片，而不是瓦片的一部分（单位不会相撞）。如果我增加步长，我会错过一些仅轻微穿过的瓦片（例如只穿过左下角最低点）。即使步长为0.1，也有可能错过障碍物。我试图找到一个解决方案，以获取子地图（所有带有角落（floor(start.X)/floor(start.Y))和（ceil(start.X)/ceil(start.Y))的瓦片），穿过每个瓦片并通过数学计算检查是否被穿过。不幸的是，我似乎缺乏这个检查所需的数学知识。我的最后一个想法是将一个瓦片的所有4条边作为一条线，并进行线相交，但这似乎比我的原始方法更慢。有什么建议吗？谢谢。

- user253984

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ktharsis · Accepted Answer

不要沿着线条一步步地追踪路径，而是要跳到下一个可能的方格（边界）上。这可以相对简单地计算出来。我将使用您上面提供的数字作为示例。

计算线性方程（y = .286x + 2.471）
您从2,3开始向5,4移动。因此，请计算当x到达3（右侧立即相邻的方格的边界）时的y值。它是3.329。
然后计算当y到达4（上方立即相邻的方格的边界）时的x值。它是5.346。
从2,3开始向右移动，可到达3,3.329。向上移动可到达5.346,4。您在右侧相交（在x轴上移动2 -> 3不会在y轴上移动一个方格）。直到在x轴上到达第5个方格，才在上面相交。
在步骤4中计算出的方格成为新的比较对象（3,3）。从步骤2开始重复。

每移动一个方格只会产生一次计算（无论精度或方格大小如何），并且是准确的。请注意，可以存储并重复使用计算出的值，而不是盲目地反复计算两个交点。在步骤4中，我们知道不会向上移动一个方格，直到x = 5。因此，可以推断出整个路径而无需进行其他计算（2,3->3,3->4,3->5,3->5,4）。

也可以预先计算所有转换，而不是逐步执行它们，尽管只有在您始终需要整个路径时才有益处（您不需要，因为您希望在找到障碍物后停止处理）。

两个注意事项。要注意符号和线条的方向 - 许多错误都是由于没有仔细注意负斜率引起的。此外，使用实数几乎永远不会对角线穿过（一次穿越两个边界），但您应该意识到这一点（在代码中处理它），以防万一。

这种方法有一个名称，但我记不起来了。我认为它可能来自游戏编程宝典系列，但也许其他人可以提供更好的参考。