Warm tip: This article is reproduced from stackoverflow.com, please click
algorithm geometry grid path-finding

Linear path on a toriodal grid surface with obstacles and angle limitations

发布于 2020-03-28 23:14:16

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.

Questioner
Jyon Nyre
Viewed
103
user3386109 2020-01-31 17:36

This image may help

enter image description here

Green is the starting point, red is the target, the brown square is the obstacle, and the grey areas are the areas blocked by the obstacle.

Note that there is only one target and one obstacle. The target and obstacle are repeated to show what happens when you go off the right edge of the grid, and wrap back to the left edge.

You can see that each time the line wraps around the grid, the angle to the target, and the angles to the obstacle are reduced. Eventually, the obstacle starts shadowing itself. Beyond that point, there's no hope of ever reaching the target. So in this example, there are exactly two angles that reach the target.


Add another obstacle (purple), and all angles are blocked even sooner.

enter image description here

If the obstacle is at the same level as the target, it takes longer before all possible angles are blocked. But eventually the obstacle will shadow itself, and all target angles beyond that point are blocked.

enter image description here

And just for completeness, obstacles above the target can be ignored. The angle to the target will always be smaller than the angle to the obstacle.

enter image description here