Benj - 3 months ago 16

C# Question

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.

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).

Given two points

`X=(x1,x2)`

`Y=(y1,y2)`

`X`

`Y`

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}"`

`P and Q`

`P`

`Q`

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.

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

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

... or applied to an in-game scenario

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.

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
```