Table of Contents
List of technologies / frameworks used during the project.
This project is a implementation of A* algorithm in Go. The goal is to compare the performance of the algorithm in Go and C++. Implementation in C++ is not asynchronous unlike the one in Go.
You need golang 1.21 for running this project.
To be more user-friendly, a Makefile is present at the root of the project. Even if you run with go run, you need to be at the root of the project and using img parameter with path of image you'd like to analyze.
$ make run img=ressources/first_level.png # Run the application using go run under the hood
$ make run-build img=ressources/first_level.png # Run the application from dist folder, build it before !
$ make clean-cache # Clean the cache of the project
$ make build # Run the clean cache before building
$ make time # Time the execution of the application
$ make benchmark # Run the benchmark of the application, from benchmark folder$ go run main.go img=path_to_img # Run the applicationCouleur selon H
Bidirectionnel
Node.Alreadyfor flag already visited nodes | -25%- Avoid to iterate over a list of several hundred/thousand nodes at each iteration
PriorityQueuemake us gain an exponential time, we found that it make us gain MINIMUM 10 000% on execution time
We would implement a bidirectional A* algorithm. The idea is to run two A* algorithms at the same time, one from the start and one from the end. Unfortunately, we didn't have time to finish, and it's still bugged. However, we have some results :
- On very small images, the launch of A* in bidirectional sometimes has no performance gain compared to classic A*.
- Indeed, depending on the system scheduler, it may be that a routine ends before the other has even started.
- On larger images, we observe a gain of up to 70% in some cases.
He would be interesting to base ourselves on these works to finalize / improve the bidirectional A* algorithm.
Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.
If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request
Distributed under the MIT License. See LICENSE.txt for more information.
Reach our at : gauron.dorian.pro@gmail.com, florian.savoure@gmail.com .
Project Link: https://github.com/P0SlX/go-star
This space is a list to resources i found helpful and would like to give credit to.