C#：2D子Tile线相交
我在让我的游戏运行算法时遇到一些问题，希望这里有人可以帮助我。谷歌似乎没有提供很好的帮助，因为大多数解决方案仅适用于完整的图块。
在游戏中，单位可以占据图块内的不同位置，即它们可以位于图块的左上角、中心、右下角……位置（2/3），即（2.2/3.1）、（2.5/3.5） ），（2.8/3.9）。
如果它们从位置（2.2/3.1）移动到（5.7/4.1），我需要检查路径中是否有障碍物。
我当前的算法是：
- 从 (2.2/3.1) 开始
- 计算移动的角度（即 70 度） 朝
- 该方向移动 0.1 步
- 检查我在哪个图块上 (floor(pX)/floor(pY))
- 从 2 开始重复
该算法有效，但对我来说它看起来不是很有效，因为障碍物只能是完整的图块，而不是图块的一部分（单位不会碰撞）。如果我增加步长，我就会开始错过仅轻微交叉的瓷砖（即仅穿过左下角）。即使步长为 0.1，仍然有可能错过障碍物。
我试图找到一个解决方案来获取子地图（所有带有角的图块（floor（start.X）/floor（start.Y））和（ceil（start.X）/ceil（start.Y）），移动遍历每个图块并以数学方式检查它是否交叉。遗憾的是，我似乎缺乏此检查所需的数学知识。
我的最后一个想法是将图块的所有 4 个边界作为一条线并进行线相交，但这似乎较慢。比我原来的方法
有什么提示吗
？
I have some problems getting an algorithm for my game to work and hope someone here can help me. Google didn't seem to be a good help as most solutions just work for full tiles.
In the game units can occupy different positions inside a tile, i.e. they can be in the upper left corner, center, bottom right, ... position of tile (2/3), i.e. (2.2/3.1), (2.5/3.5), (2.8/3.9).
If they move from position (2.2/3.1) to (5.7/4.1) i require a check to see if there is an obstacle in the path.
My current algorithm is:
- Starting from (2.2/3.1)
- Calculate the angle of the movement (i.e. 70 degree)
- Move 0.1 steps in that direction
- Check which tile i'm on (floor(p.X)/floor(p.Y))
- Repeat from 2
This algorithm works but to me it doesn't look very efficient as an obstacle can be only a full tile, not a part of a tile (units don't collide). If i increase the step size i begin to miss tiles that are only crossed slightly (i.e. you only cross the lowest left corner). Even with a step size of 0.1 it's still possible to miss an obstacle.
I tried to find a solution to take the sub map (all tiles with the corners (floor(start.X)/floor(start.Y)) and (ceil(start.X)/ceil(start.Y)), move through every tile and check mathmatically if it gets crossed. Sadly i seem to lack the required math knowledge for this check.
My last idea was to take all 4 borders of a tile as a line and do line-intersection but that seems to be slower than my original approach.
Any hints?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您不想通过沿着线步进来追踪路径 - 您想要直接跳到下一个可能的图块（边界）。这可以相当简单地计算。我将使用您上面的样本编号。
此过程仅对每个移动的图块进行一次计算（无论您的精度如何或图块有多大）并且是准确的。请注意，计算出的值可以存储并重复使用，而不是盲目地一遍又一遍地计算两个交点。在上面我们知道（步骤 4），直到 x=5 为止我们不会向上移动一个图块。因此无需再次计算即可推断出整个路径（2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4）。
也可以预先计算所有转换，而不是逐步进行转换，尽管这只有在您始终需要整个路径时才有用（您不需要，因为一旦发现障碍就想停止处理）。
两个警告。小心标志和线路走向——许多错误都是由于不密切注意负坡度而发生的。另外，使用实数你几乎永远不会跨越对角线（一次两个边界），但你应该意识到这一点（在代码中处理它）以防万一。
这个方法有一个名字，但我一时想不起来。我相信它可能来自游戏编程宝石系列，但也许其他人可以提供更好的参考。
Instead of tracing the path by stepping along the line - you want to jump right to the next possible tile (the border). This can be calculated fairly simply. I will use your sample numbers above.
This process only incurs one calculation per tile moved (regardless of your precision or how big the tiles are) and is exact. Note that the values calculated can be stored and reused instead of blindly calculating both intersections over and over. In the above we know (step 4) that we don't move up a tile until x=5. So the entire path can be inferred without another calculation (2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4).
It is also possible to precalculate all the transistions instead of doing them stepwise although this would only be beneficial if you always need the entire path (you don't since you want to stop processing once you find an obstacle).
Two caveats. Be careful about signs and which way the line is going - many a bug happen by not paying close attention to negative slopes. Also, using reals you almost never will cross diagonally (two borders at once) but you should be aware of it (handle it in the code) just in case.
There is a name for this method but I can't remember it off the top of my head. I believe it might be from Game Programming Gems series but maybe someone else can provide a better reference.