Friday, October 30, 2015

Comparing Dijkstra's Algorithm and A*


Source
Using Dijkstra's algorithm and Astar with a Probabilistic Road Map to navigate a 3D space. The large green sphere is the goal, the large red sphere is the AI, the large black sphere are obstacles, and the small blue spheres are the points found by the probabilistic road map. Use WASD to move the camera in mode 0, the AI in mode 1, and the goal in mode 2. Drag the mouse to rotate camera. Set modes by pressing the corresponding number. Press enter or return to have the AI search. Press r to reset the AI's position. Press spacebar to swap between using dijkstra's algorithm and astar. In the video, both algorithms find the same path, but Astar ound it in 23 miliseconds, while dijkstra's algorithm found it in 88 milliseconds.

Dijksra's Algorithm


Source
Using Dijkstra's algorithm and a Probabilistic Road Map to navigate a 3D space. The large green sphere is the goal, the large red sphere is the AI, the large black sphere is an obstacle, and the small green spheres are the points found by the probabilistic road map. Use WASD to move the camera in mode 0, the AI in mode 1, and the goal in mode 2. Drag the mouse to rotate camera. Set modes by pressing the corresponding number. Press enter or return to have the AI search. I accidentally made the obstacle too large, but this does not impact the algorithm much.