This project was developed for the MatchBoxDAO Hackathon, the idea is to develop in Cairo an algorithm that solves the path search problem for a map represented in 2D grids. The map may contain obstacles, furthermore we assume that the movement in the squares is bidirectional with a uniform movement cost.
It is currently uploaded to Testnet and you can test how it works by entering the following link (credits to Rohith), in this example we will be able to set obstacles in a map of n*m that will later work as input in the algorithm. Once finished, the jump points that were chosen to reach the goal will be displayed.
- Using view function Cairo Contract.
The position (0,0) on the map starts at the top left, positions increase in the opposite direction
start_x: int
start_y: int
end_x: int
end_y: int
grids: int[] // Example: [0, 0 , 0, 1, 1, ..., 0], 0 = walkable, 1 = obstacle
width: int // This value determines how many divisions the grid array will have.
height: int
Input example in test
- Using the web app in link.
The following grid shows approximate values just to get an idea of the response performance as the size of the map grows. The maps were generated in the visualizer that we mentioned earlier.
| Map dimension | Clean map | Random maze | Recursive division maze | Vertical division maze | Horizontal division maze |
|---|---|---|---|---|---|
| 10 x 10 | 1.80s | 2.23s | 1.86s | 3.17s | 1.82s |
| 15 x 15 | 4.12s | 3.95s | 3.36s | 2.98s | 2.85s |
| 20 x 20 | 4.65s | 3.89s | 7.45s | 9.04s | 8.19s |
| 25 x 25 | 11.00s | 8.92s | 9.82s | 8.60s | 8.35s |
| 30 x 30 | 18.59s | 12.26s | 8.97s | 10.47s | 13.05s |
Given that we had a limited time to understand, program and show the algorithm, things were pending that we would like to develop in the future:
- Optimize the JPS algorithm currently implemented (look for improvements in terms of data structure management, variables, steps).
- From a map of size 25 *25 we notice that the contract cannot solve the problem, due to the amount of resources consumed by the algorithm.
- Implement different path search algorithms such as BFS, A*, Dijkstra, HPA*, etc.
The implementation of the presented algorithm was based on the paper Online Graph Pruning for Pathfinding on Grid Maps by Daniel Harabor and Alban Grastien.
We also mention Nathan Witmer that thanks to his article we were able to have a first approach to the algorithm in a friendly way.