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.
该图像可能会有所帮助
绿色是起点,红色是目标,棕色正方形是障碍物,灰色区域是被障碍物阻挡的区域。
注意,只有一个目标和一个障碍。重复目标和障碍物以显示当您离开网格的右边缘并返回左边缘时会发生什么。
您可以看到,每条线围绕网格缠绕时,与目标的角度以及与障碍物的角度都会减小。最终,障碍物开始掩盖自身。超过这一点,就没有希望达到目标。因此,在此示例中,正好有两个角度到达目标。
添加另一个障碍物(紫色),所有角度将被更快地阻塞。
如果障碍物与目标在同一水平线上,则所有可能的角度都将被阻止之前需要更长的时间。但是最终障碍物会自行遮挡,并且超出该点的所有目标角度都将被遮挡。
仅出于完整性考虑,可以忽略目标上方的障碍。与目标的角度将始终小于与障碍物的角度。
因为这是一个圆环而不是圆柱,所以如果目标位于起点下方,则由于底部边缘通向顶部边缘,因此还必须考虑目标上方的对象以及目标下方的对象。不过,对象阴影本身的想法最终将非常有帮助。