Search This Blog

Wednesday, 26 March 2014

A* path-finding Examples in Python and Javascript (Not my own work)

A* Search Algorithms are used to find the shortest path from A to B while avoiding obstacles in the path.  

There are a number of such algorithms, and I'm not going to explain them here, but rather point you to some very good videos and some working Open Source Code that you can use in your own robot or game design.



Path Finding 0.1.1

A demo visualizing the execution of various path-finding algorithms

Curently five algorithms are included:
  1. A* (using Manhattan distance)
  2. A* (using Euclidean distance)
  3. A* (using Chebyshev distance)
  4. Dijkstra
  5. Bi-Directional Breadth-First-Search
This demo allows you to choose algorithms from above and visualize their execution.
Meanwhile, this is a Client/Server application. You should start the server first and then the client.
Also, you can start the server on one machine and run the client on a different machine, as long as the two machines are connected.
Screenshot:

Source:
Requires Python 2.6+ and Pygame
http://mycodeplayground.googlecode.com/files/pathfinding-0.1.1-src.tar.gz
Win32 Binary Distribution:
http://mycodeplayground.googlecode.com/files/pathfinding-0.1.1-win32-dist.zip
Note: There's a javascript version at http://qiao.github.com/PathFinding.js/visual/


Guiding a Robot with A*


Visual explanation of A* Algorithm 

For a tutorial on how A* Path finding works please check out --> https://www.youtube.com/watch?v=KNXfSOx4eEE



References:
Wikipedia: A* Search Algorithm
https://www.youtube.com/watch?v=KNXfSOx4eEE
https://www.youtube.com/watch?v=DINCL5cd_w0
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html