Sunday, October 16, 2016

A* (A-star, or Astar) for Arduino et al

I've become increasingly interested in robotics, specifically autonomous such, and started tinkering quite a lot with Arduino-based things. During the past year I have been collecting quite a few Arduino-variants, different sensors and lots of other components, and will be covering some of the experiments and other results in this blog from now on.

A few days ago, I had the need to perform path-finding in a partially obstructed 2-dimensional grid. There are many ways to approach this problem, and while reading up on algorithms and solutions, I eventually came across A* (Astar). A* is derived from the original Dijkstra's algorithm, for which there are numerous variants, and solves the path finding problem by measuring distance and difficulty for a particular move, and ends up with an optimal path (given the circumstances and rules) from A to B.

In order to be able to use this algorithm on an Arduino, it needs to be as memory-efficient and small as possible, which led me to implement it (again) with these considerations in mind. Hence, a new repository has been published on GitHub: https://allbinmani.github.io/aastar/

The code is written with Arduino in primary focus, but it compiles and works just as well on Linux and OS/X. Please feel free to try it out, and post any issues you might have on GitHub. Enjoy!