Example project using the a-star and a-star-rs extension modules, comparing their performance to a pure python implementation.
- git
- uv (Making it work without should be easily possible, but requires some adjustments)
- A C++ toolchain
- A Rust toolchain
git clone https://github.com/Tastaturtaste/mazesolver.git
Run the mazesolver script against one of the included mazes:
uv run mazesolver mazes/maze_small.png
uv will automatically download a compatible python version if necessary, create a virtual environment, install dependencies including compilation and finally run the script.
The script performs the following steps: First it reads in the three color channels of the picture representing the maze. The start position for the maze should be marked in red, the exit in blue. Then the picture is converted to gray-scale. Per default grey values of 0 (completely black) are considered unpassable, values above (lighter color) are considered passable. Grey values that are passable are translated to pathing costs.
Then it calls and times the respective functions for the A*-Algorithm of the C++, Rust and pure python implementation and prints the runtime to the console.
The resulting path as well as the explored area is drawn into the maze and saved to a file for all implementations seperately. The default directory to save to is the directory of the input file.
The behaviour can be influenced via the commandline arguments passed to mazesolve. These can be explored with python mazesolve.py -h
Depending on the size of the maze the C++ module is about 10 to 30 time faster than the pure python module. This gain gets smaller the larger the maze is.
The following are times measured for the mazes maze_small.png and maze_large.png in the mazes directory. The times were measured in one run on my laptop with some other applications (e.g. a webbrowser, a code editor) open. So they should at most be seen as indications of orders of magnitude.
- C++: 3.8s
- Rust: 1.5s
- Python: 53s
- C++: 11s
- Rust: 4s
- Python: 120s