A* Algorithm in Java with GUI

What does the app do?

The user enters a weighted directed graph. The application runs the A* algorithm, visually displays the process of the algorithm step by step, finds the shortest path from vertex A to vertex B and outputs its length.

Installation and launch

Make sure you have JDK (version 17+) and Maven (version 3.3+) installed and configured. Then go to the project folder and type the following to create a modular runtime image:

mvn clean javafx:jlink

It will create a folder with the application which you can launch:

Windows:

.\target\AStar\bin\AStar.bat (cmd)

./target/AStar/bin/AStar.bat (PowerShell)

Linux:

./target/AStar/bin/AStar

If instead you just want to build and run the project:

mvn clean javafx:run

Running tests

After building the project enter the command:

mvn clean tests

Input data

Weighted directed graph (created by mouse clicks / import from file)

Output data

Visualization of the step-by-step process of the A* algorithm

The shortest path from A to B and its length

App's features

Create graph by mouse clicks / import from file (number of vertices + vertices coordinates + adjacency matrix with weights)

Heuristic choice: Euclidean distance, Manhattan distance and Chebyshev distance

Move to the next step in the algorithm and pause during rendering

Explanatory notes for the user

User's Guide

Do you need to find the shortest path in a graph from vertex A to vertex B?

Then, define the graph in one of two ways: a) By clicking on the window, choosing the necessary actions: create a vertex, connect vertices, delete a vertex. b) Import the graph from a text file that should contain the following information about the graph: ~ number of vertices in the graph ~ coordinates of the vertices ~ adjacency matrix of graph with weights

Next, choose the heuristic to be used in the A* algorithm: a) Chebyshev distance b) Manhattan Metric c) Euclidean distance

Press the "Run" button to run the algorithm. Select the start and end vertex of the path. The algorithm is running. You can pause the process of the algorithm and proceed to the next step of the algorithm.

As a result, you will get the shortest path from A to B and the length of this path. You can also output the resulting graph along with the results to a text file.

Possible problems

If you have problems with building the project, the issue may be as follows:

• Wrong JDK version (should be at least JDK 17)
• Wrong Maven version (should be at least Maven 3.3)
• Maven not properly configured (\maven\bin\ path should be added to PATH environment variable, and JAVA_HOME variable should be set to the \jdk path of the suitable JDK version)