Implementation of Pathfinding Algorithms on road map of Wuhan for my 2022AI course final project. You can have a shot at it at https://liuhaozhe6788.github.io/pathfinding.
Here is the webpage for Pathfinding Algorithms:
After selecting the algorithm and moving the start and target nodes, click "Start progress". After that, a window would show the execution time and the map would display extended edges and the final path. For ALT Search and ALT Search improved, the map would also show two landmarks, which are inportant for pathfinding. A demo result of ALT Search improved looks like this:
Uniform Cost Search: aka Dijkstra Algorithm.
A* Search: with euclidean bounds.
ALT Search: with triangular inequality lower bounds in this, the landmarks are selected using avoid methods in this.
ALT Search Improved: based on ALT search, one can select a subset of two landmarks that are close to and after the target node from all the landmarks before each pathfinding search.
Generally, ALT Search Improved is the fastest among all four algorithms.
-
Install node.js
-
Install live-server with npm command
npm i live-server
- Run the website with
live-server
The C++ code is binded with javascript using Emscripten and Embind, so you need to install Emscripten if you want to modify the C++ code. Install Emscripten
After modifying the C++ code, run
./build.sh
- Please refresh the page a couple of times if the map and markers are not rendered
- Please use a VPN if the map is not rendered completely