C#:2D子平铺线交叉点

Question

我有一些问题让我的游戏算法工作,希望这里有人可以帮助我.谷歌似乎并不是一个很好的帮助,因为大多数解决方案只适用于完整的瓷砖.

在游戏中,单位可以占据拼图内部的不同位置,即它们可以位于拼图的左上角,中间,右下角,...位置(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. 检查我在哪个瓷砖(地板(pX)/地板(pY))
5. 重复2

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

我试图找到一个解决方案,采取分图(与弯道所有瓷砖(地板(start.X)/楼(start.Y))和(小区(start.X)/小区(start.Y)),移动通过每个瓷砖并以数学方式检查它是否越过.可悲的是,我似乎缺乏这项检查所需的数学知识.

我的最后一个想法是将一个瓷砖的所有4个边框作为一条线并进行直线交叉,但这似乎比我原来的方法慢.

任何提示？

谢谢.

Answer 1

而不是通过沿着线踩踏来追踪路径 - 您想要直接跳到下一个可能的图块(边框).这可以相当简单地计算.我将使用上面的示例数字.

1. 计算线eqn(y = .286x + 2.471)
2. 你是从2,3号铺开始,向瓦片5,4移动.因此,当x变为3时(右边的瓷砖边框),计算y值.它是3.329.
3. 然后当y变为4(紧邻上面的瓷砖的边界)时计算x值.这是5.346.
4. 从2,3开始向右移动到3,3.329.向上移动到5.346,4.你在右边相交(在x上移动2 - > 3不会在y上移动一个平铺).在x中的tile 5之前,您不会在上面相交.
5. 以4计算的图块将成为您的新比较(3,3).从第2步开始重复.

这个过程只会导致每个瓷砖移动一次计算(无论您的精确度或瓷砖有多大),都是精确的.请注意,计算的值可以存储和重复使用,而不是一遍又一遍地盲目计算两个交叉点.在上面我们知道(步骤4)我们在x = 5之前不会向上移动.因此,无需另外计算即可推断出整个路径(2,3 - > 3,3 - > 4,3 - > 5,3 - > 5,4).

也可以预先计算所有的转换,而不是逐步进行转换,尽管这只有在你总是需要整个路径时才有用(你不会因为你想要在找到障碍物时停止处理).

两个警告.注意标志以及生产线的走向 - 通过不密切关注负斜率会发生很多错误.另外,使用实数你几乎不会对角交叉(两个边框一次)但你应该知道它(在代码中处理它)以防万一.

这个方法有一个名字,但我不记得它在我的头顶.我相信它可能来自Game Programming Gems系列,但也许其他人可以提供更好的参考.