# Finding Shortest Path in the Plane with Obstacles

### Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Among the games I have developed on CodinGame, one of my favorites is Ghost in the Cell because it gave me the opportunity to solve a very interesting problem: finding the shortest path in a plane while avoiding obstacles. This is an algorithm I've been taught during a robot motion planning class when I was a student but I never had the opportunity to implement it.

In this article, I will show you how to compute a path from one factory to another while avoiding other factories. A factory is simply a round obstacle.

The algorithm will be divided in 3 steps:

- computing polygons for each round obstacle
- construction of the visibility graph (that's the tricky part)
- computing the shortest path

## Computation of the Polygons

The obstacles are round, however we need a discrete amount of vertices to build the visibility graph. A circle can easily be approximated by a regular polygon.

First, some vocabulary:

- A regular polygon is a polygon equiangular and equilateral
- The apothem (a$a$) is the distance from the center to the midpoint of one of its sides
- The circumradius (R$R$) is the distance from the center to one of its vertices
- The inscribed circle of a regular polygon is a circle with the same center and radius a$a$

We are looking for a polygon for which the inscribed circle is the radius of a factory, plus a gap to forbid a path to go too close to an obstacle (too dangerous). The apothem of the polygon is : a=obstacle.radius+extraSpace$a=obstacle.radius+extraSpace$. The circumradius can be calculated from the apothem and the number of edges: R=acos(Ï€/n)$R=\frac{a}{cos(\mathrm{\xcf\u20ac}/n)}$.

The coordinates of the vertices of a polygon of n$n$ edges are:

Here's the implementation of the `polygon`

function:

Feel free to play with the number of edges.

## Visibility Graph

From the set of vertices of all the polygons, we create a graph called Visibility Graph. Each vertex is connected to all the vertices that can be reached by a direct line without crossing any obstacle.

For this, we need a function to detect an intersection between two segments. We'll also use a function to detect an intersection with a circle but it was not strictly necessary (this simplifies the code). The function `directPath`

returns true when two points can be connected without intersecting a polygon.

The function `buildGraph`

iterates over all the vertices of all the polygons and create a bidirectional edge when `directPath`

returns true. We also add a unidirectional edge from each center (these edges only allows to exit a factory).

## Shortest Path

Any conventional shortest path algorithm can be used to compute the path from a factory to another using the visibility graph. Here's the implementation of an A*. For the sake of simplicity, I've used a sorted array instead of a priority queue, feel free to improve that part.

By increasing the number of edges for each polygon, the path become smoother.