Euclidean Pathfinding

Build Status

Overview

This program computes optimal paths between two points. Any direction movement is allowed but paths must circumvent obstacles.

It differs from (but uses) Dijkstra's algorithm which enables only horizontal and vertical movements (image on the left), by allowing to go straight from one point to a distant other one (image on the right). It uses the Euclidean distance to determine which paths are best.

Running

The application is written in Java using Maven. To build it, install Java and Maven, cd into the repository, and run:

mvn package
cd target
java -jar euclideanPathfinding-1.0-SNAPSHOT.jar

Principle

Algorithm

A matrix of the size of the image is created, where each cell will contain Manhattan distances from the departure (only including horizontal and vertical moves). Cells are filled step by step with distances using the following rule:

When the arrival is reached and marked with a distance , the algorithm still continues to fill cells having distances smaller than or equal to , and then stops.

This defines an area that contains all possible Dijkstra's solutions. However, the Euclidean best path might not reside in it, as in this example :

We need to enlarge the area enough to make sure that it contains the best Euclidean path. As proved in the next section, using as the new limit suffices. The algorithm contains also an optimization that shortens this enlarged area by additionally taking into account cells' positions.

Then, it skeletonizes it, creates a graph of possible paths, and smoothes each one. The shortest income is the best Euclidean path.

Enlarged area proof

For a category of paths that circumvent obstacles in the same way, we will notate the size of Dijstra's solutions, and the size of the best Euclidean solutions.

Let's define the Dijktra's solution, and another Manhattan solution. Let's assume that . We want to make sure that is contained in the area.

For any category , we have .

Thus:

• 
• 

Since , we deduce that .

It comes that .

So, using as the limit for the area ensures that it will contain the Euclidean solution we are looking for.

Usage

• Open a map: Load an image that will serve as a map. Non-white pixels are considered to be obstacles. This is not necessary because a default map is created with no obstacles. You can try images under resources/examples.
• < & >: Select the previous or next category of paths when "Task to perform" is positionned to "Graph with paths", "Graph with smoothed paths" or "Smoothed paths".
• Select the departure & Select the arrival: Place the departure or the arrival. Press a button, and then click somewhere on the map area to choose their positions.
• Switch obstacles: Create or delete obstacles. Press the button and then click at different places on the map area.
• Task to perform: Choose the algorithm to apply.
• Display mode: Show or hide the grid. Please zoom in first for the grid to be legible.
• + & -: Zoom in or zoom out.
• Color iso-lines: Colour area cells depending on their distances.

TODOs

• Translate code to English
• Replace DoubleMaillon with LinkedList
• Fix ability for segments to cross diagonal blocks
• Harmonize indentation
• Add braces for all code blocks
• Clean code and split large functions

License

This project is protected under the terms of GPLv3.

Please contact me at codoscopus@gmail.com for further questions.