C#: 2D sub-Tile Line 相交

Question

我在为我的游戏设置算法时遇到了一些问题，希望这里有人可以帮助我。 Google 似乎不是一个很好的帮助，因为大多数解决方案只适用于完整的图 block 。

在游戏中，单位可以在一个方 block 内占据不同的位置，即它们可以在方 block 的左上角、中间、右下角，...方 block 的位置 (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. 检查我在哪个方 block 上(floor(p.X)/floor(p.Y))
5. 从 2 开始重复

这个算法有效，但对我来说它看起来不是很有效，因为障碍物只能是一个完整的图 block ，而不是图 block 的一部分(单元不会发生碰撞)。如果我增加步长，我会开始错过仅略微交叉的瓷砖(即您只穿过左下角)。即使步长为 0.1，仍有可能错过障碍。

我试图找到一个解决方案来获取子 map (所有带有角的瓷砖(floor(start.X)/floor(start.Y))和(ceil(start.X)/ceil(start.Y) ), 遍历每个方 block 并用数学方法检查它是否被越过。遗憾的是我似乎缺乏进行此检查所需的数学知识。

我最后的想法是将 tile 的所有 4 个边界作为一条线并进行线相交，但这似乎比我原来的方法慢。

有什么提示吗？

谢谢。

Answer 1

不是通过沿着线步进来追踪路径 - 您想要直接跳到下一个可能的图 block (边界)。这可以相当简单地计算出来。我将使用上面的示例编号。

1. 计算线方程 (y= .286x + 2.471)
2. 您从方 block 2,3 开始，并向方 block 5,4 移动。因此，当 x 变为 3 时计算 y 值(紧靠右侧的图 block 边界)。它是 3.329。
3. 然后计算当 y 变为 4 时的 x 值(正上方方 block 的边界)。是 5.346。
4. 从 2,3 开始，向右移动到 3,3.329。向上移动到 5.346,4。您在右侧相交(在 x 上移动 2 -> 3 不会在 y 上移动瓷砖)。在 x 中的第 5 个方 block 上之前，您不会在上面相交。
5. 在 4 中计算出的瓷砖成为您的新比较 (3,3)。从第 2 步开始重复。

此过程只对移动的每个图 block 进行一次计算(无论您的精度或图 block 有多大)并且是准确的。请注意，计算出的值可以存储和重复使用，而不是盲目地一遍又一遍地计算两个交点。在上面我们知道(第 4 步)直到 x=5 才向上移动一个方 block 。因此无需其他计算即可推断出整个路径(2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4)。

也可以预先计算所有的转换而不是逐步进行，尽管这只有在您始终需要整个路径时才有用(您不需要，因为一旦发现障碍就想停止处理)。

两个注意事项。注意标志和线路的走向 - 许多错误都是由于没有密切注意负斜率而发生的。此外，使用实数你几乎永远不会对角线交叉(一次两个边界)但你应该意识到它(在代码中处理它)以防万一。

这个方法有一个名字，但我想不起来了。我相信它可能来自 Game Programming Gems 系列，但也许其他人可以提供更好的引用。