3DPathFinder algorithm finds the shortest path from a start cell to a stop cell.
This program uses the dijkstra algorithm to traverse the 3D matrix in search of the shortest path. To do this, it uses the dijkstra3d package which, by using the distance from target as a heuristic (A* search), returns the best option.
The program has the ability to check the validity of the inputs and return an answer only if it is possible to find an optimal path without passing through obstacles in the maze.
- Problem Description
- dijkstra3d package
- Installation
- Program use
- Examples of visualization
- License
- References
- Links
The problem consists of a 3D grid of size (N x M x K).
Within the grid each node can be either an empty cell, noted as 0 or an obstacle, noted as 1.
The objective is to find the shortest possible path from the start cell to the stop cell in the grid given its coordinates (e. g., start = [0, 0, 0], end = [N-1, M-1, K-1]).
A Dutch computer scientist, Edsger Dijkstra, in 1959, proposed an algorithm that can be applied to a weighted graph. The graph can either be directed or undirected with the condition that the graph needs to embrace a non-negative value on its every edge. He named this algorithm “Dijkstra’s Algorithm” at his name [1].
This algorithm makes a tree of the shortest path from the starting node, the source, to all other nodes (points) in the graph. Dijkstra's algorithm makes use of weights of the edges for finding the path that minimizes the total distance (weight) among the source node and all other nodes. This algorithm is also known as the single-source shortest path algorithm [1].
Dijkstra’s algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph. It is important to note that Dijkstra’s algorithm is only applicable when all weights are positive because, during the execution, the weights of the edges are added to find the shortest path [1].
To find the most optimal path, 3DPathFinder uses the package dijkstra3d. 3DPathFinder implements the A* search algorithm to find the optimal answer. It uses the distance to the target as a heuristic. In Figure 1 it can be seen that its performance is much better compared to the other resolution methods that can be used with this package.
On the other hand, image 2 shows that this type of heuristic works very well when the grid is larger.
The dijkstra3d package uses cython to store the value of program variables using the C language. For this reason, by saving values using a compiled language, the access to the variables is much faster, thus increasing the performance considerably compared to a program written only in python.
3DPathFinder has been tested in an anaconda environment with python 3.9.16.
Create a new environment in anaconda with python=3.9.16:
conda create --name pathfinder python=3.9.16Activate the new environment:
conda activate pathfinderTo install 3DPathFinder you can download the program from its GitHub repository as follows:
git clone https://github.com/nucontreras/3d-maze.gitOpen the 3DPathFinder folder from the terminal
cd 3d-mazeTo use the program it is necessary to install the following packages using pip :
matplotlib==3.5.3
numpy==1.23.5
dijkstra3d==1.12.0Execute the following line of code in the command line:
pip install -r requirements.txtAt this step, you have everything installed to be able to use the program.
To use the program you have to open the 3dpathfinder/ folder in the command line:
cd 3dpathfinderThe execution of the program is performed with the following command:
python main.pyHowever, you must choose or write certain parameters inside the main.py file to test with different types of grids and input and stop cells.
First of all you must create a 3D grid and define start and stop coordinates. Make sure that the coordinates correspond to the size of the grid, otherwise the program will warn you to change the input.
In the following image there is an example of use:
To find the optimal path, the function find_path(grid, start=start_cell, stop=stop_cell) must be used into de main.py file.
Example:
output = my_path_finder.find_path(maze_3d, start=[0, 0, 0], stop=[35, 45, 51])To the find_path() function you can add the connectivity parameter to define the type of moves you want to make to find the solution. The options are 0: faces, 1: faces and edges, 2: faces, edges and corners.
Example:
output = my_path_finder.find_path(maze_3d, start=[0, 0, 0], stop=[35, 45, 51], connectivity=1) # search a path by moving along the faces and edges.To visualize the path within a 3D grid you can add the following line of code to the main.py file
my_path_finder.visualize()If the grid has more than 100 obstacle type cells, the display will not show the obstacles for a better visualization of the path found. In another case, the obstacle cells are represented by a red x. In section Examples of visualization you can see some animations of the viewer.
For the following three cases, the first image of each example uses the algorithm looking for possible paths considering only the faces of a voxel in the 3D matrix. The second image considers a connectivity of type faces and edges, i.e. diagonal movements within the same face. Finally, the third one considers faces, edges and corners, i.e. all diagonal movements from a node, including diagonal movements in 3D.
The 3DPathFinder is licensed under the terms of the GNU General Public License license and is available for free.
[1] Dijkstra, E. W. (1968). Go to statement considered harmful. Communications of the ACM.