Finding Shortest Path in the Plane with Obstacles


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.

Expected Result

The algorithm will be divided in 3 steps:

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$) is the distance from the center to the midpoint of one of its sides
  • The circumradius ($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$

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$. The circumradius can be calculated from the apothem and the number of edges: $R = \frac{a}{cos(\pi / n)}$.

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

$$\left \{ \begin{matrix} x = obstacle.x + R \cdot cos(t) \\ y = obstacle.y + R \cdot sin(t) \end{matrix} \right .\quad\text{with}\quad t \in [0, \frac{2\pi}{n}, 2\frac{2\pi}{n}, 3\frac{2\pi}{n}, ..., (n - 1)\frac{2\pi}{n}] $$

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.

Create your playground on
This playground was created on, our hands-on, knowledge-sharing platform for developers.
Go to