Benj Benj - 1 month ago 9
C# Question

(Eucledian Shortest Path) Detecting corners of obstacles in plane

Problem History/ Origin



Lately I stumbled over channels on Twitch.TV from players that perform speedruns of classic games. One of them played The Legend of Zelda - A Link to the Past. I saw many inefficient movements and I started to wonder if - given the world map data - it would be possible to write a bot that performs perfect speedruns. One quite frequently arising subproblem would be to find shortest paths between two points in a plane which I figured was such an interesting problem that I started to do more research on this.

Similar Stackoverflow Questions have been posted



How can I can I detect the shortest path from point A to point B without going through the obstacles?

Finding path obstacles in a 2D image

Algorithm to detect corners of paper sheet in photo

... and more

Of which the answers always provided a different solution to the Superproblem (described below) like using a grid based approach but not the actual Subproblem I am interested in (described below).

Superproblem Solution Description



Given two points
X=(x1,x2)
and
Y=(y1,y2)
in a plane - What is the shortest path from
X
to
Y
if the plane contains obstacles/ regions through which the path may not lead?

Differently/ More visually What is the shortest path from Link`s current position to the second red dot on the map given he cannot climb over walls or walk through bushes?

Problem Visualisation - Shortest Path in Eucledian Plane

This problem is generally known as the Eucledian Shortest Path Problem and can be solved in Polynomial time in the 2-dimensional case. Awesome!

To achieve this, a so called Visibility Graph with
V= {X,Y} U {"Corner-Points of obstacles}"
is constructed. Edges are inserted between points
P and Q
if and only if it is possible to draw a straight line from
P
to
Q
without crossing any obstacle. Each edge is weighted by the Eucledian Distance between the points it connects.

In the example above the Visibility Graph would look something like this. I omitted a few edges and weights for the sake of readability. Shaded areas illustrate obstacles.

Solution Visualisation - Shortest Path in Eucledian Plane

Then a shortest path can be computed using the developer's favourite Shortest Path Algorithm on the Visibility Graph.

Subproblem Description



Let us start by defining an obstacle as a continuous region of impassable terrain. How would one find the minimal number of required corners of all obstacles (and the coordinates of the corners as well) to construct the smallest possible Visibility Graph required to perform Shortest Path calculations?

For rectangular obstacles it is rather easy to find the corners as there are only few sharp edges as shown in the sketch ...

Find Corners of Obstacles - Rectangular Obstacles

... or applied to an in-game scenario

Link to Hera

However, as soon as the obstacles have diagonal "fronts", obtaining the corners becomes non-trivial due to the induced jigsaw-pattern (no matter the angle). The following screenshot illustrates this problem: The left hand side image shows at which coordinates points should be identified as corners whereas the right hand side picture shows where additional points would be inserted due to the "jigsaw"-pattern of diagonal lines.

Too many corner points

The question now is: How can I exclude/ prevent these unnecessary corner points from (being inserted into) the possibly very large Visibility Graph?

Answer

How about looking at points around each point, and if you find two points which are exactly in opposite directions but do not cross a "solid" then you know that you actually have a removal candidate. Do this for all points before removing any, then remove all these candidates in one go.

This would take care of horizontal, vertical and diagonals. If you extend the radius to two or more, you could also detect redundant points on "lines" of other angles.

The time complexity is pretty much O(n) (when n is the number of points), since you will check a fixed number of points around each point to find the removal candidates, e.g.:

Radius 1 - 8 check per point:

123
4X5
678

Radius 2 - 21 checks per point:

 123
45678
9AXBC
DEFGH
 IJK