温馨提示:本文翻译自stackoverflow.com,查看原文请点击:algorithm - Linear path on a toriodal grid surface with obstacles and angle limitations
algorithm geometry grid path-finding

algorithm - 具有障碍物和角度限制的弧形网格表面上的线性路径

发布于 2020-03-29 13:14:08

I have a grid. If something goes off one edge, it reappears on the other side, in the same way as on a gluing diagram of a torus. There are two arbitrary points on the grid I want to find a straight line between using an algorithm. The line must completely avoid going through any obstacle squares. It must also be inside a specified range of angles from the x-axis. It should return the slope of the linear path that it finds. The starting position is already known, so only the slope is necessary. If no such path exists, the algorithm must return some exceptional data value indicating a lack of possible path. It should also be something better than searching all the angles the program is capable of processing. How do I make this algorithm? I have tried just searching all the angles the program is capable of processing and extending the line until it hits something or reaches some maximum length, but this is rather inefficient and I don't really want there to be a maximum length. It is not necessary for the path that is found to be the shortest path. It just needs to be a path that is linear, has a certain range of angle from the x-axis and does not hit any obstacle squares.

查看更多

查看更多

提问者
Jyon Nyre
被浏览
151
user3386109 2020-01-31 17:36

该图像可能会有所帮助

在此处输入图片说明

绿色是起点,红色是目标,棕色正方形是障碍物,灰色区域是被障碍物阻挡的区域。

注意,只有一个目标和一个障碍。重复目标和障碍物以显示当您离开网格的右边缘并返回左边缘时会发生什么。

您可以看到,每条线围绕网格缠绕时,与目标的角度以及与障碍物的角度都会减小。最终,障碍物开始掩盖自身。超过这一点,就没有希望达到目标。因此,在此示例中,正好有两个角度到达目标。


添加另一个障碍物(紫色),所有角度将被更快地阻塞。

在此处输入图片说明

如果障碍物与目标在同一水平线上,则所有可能的角度都将被阻止之前需要更长的时间。但是最终障碍物会自行遮挡,并且超出该点的所有目标角度都将被遮挡。

在此处输入图片说明

仅出于完整性考虑,可以忽略目标上方的障碍。与目标的角度将始终小于与障碍物的角度。

在此处输入图片说明