Home

golang-astar

Go implementation of the A search algorithm*

What is the A* algorithm ?

As per wiki:

A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs: starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.

Why have you decided to create another implementation ?

Plenty of A* implementation already exists, written in JS, C, Lua, to name just a few.

However, all of them suffer from the same reasons:

• sequential execution
• lack of genericity
• imposition of graph precomputation

That's why we've decided to create alternative implementation in Go. We'd like to try out:

• Goroutines/Channels, to make it concurrent
• on-demand state computation