# Generic A* Algorithm

While searching Google for “javascript astar algorithm” I got a a few results but was surprised to see that all implementations where so tied up with the pathfinding and graph-traversal domains. So I had to create yet another implementation but one that is more generic and does not depend on a graph structure or a matrix in any way. You can check the experiment here, where the generic implementation is used for – guess what – solving the typical pathfinding problem.

The Wikipedia article, about A*, effectively says it is widely used in those two domains and the algorithm’s history is tighly coupled with Dijkstra. But although many problems can be reduced to a graph traversal it’s convenient to avoid that step. Let the search alghoritm deal with connecting the nodes and keeping a graph. I don’t want to map my problem if I have a way of answering some questions and get the path traversal for free. In the end I’m still reducing the problem but without converting my structure into a graph or matrix and the having to deal with interpreting the results.

For example, consider the change-making problem. If we have a set of coins {c1, c2, …, cn} and want to change a N value bill we could create a graph with all possible uses of the coins and search for the node that sums to the desired amount or we could answer a few questions we need to answer anyway and try not to worry with the graph at all.

• Where do we start? With an amount of 0 and a bag of coins.

• What is hour goal? Get an amount of N.

• What can we do? Take a coin and add it to the amount.

• What does it cost to take a coin? Taking a coin and adding the value takes more or less the same time for every coin.

• How close am I to complete the change? The bigger the amount the closer I get. Unless I overshot, in which case I have to go back and choose another coin.

• Are some changes the same? Sure. It does not matter if I first take a coin of 50 or of 1 as long as it sums the same.

So, after answering the questions – and converting the answers to Javascript – we should be able to perform the search with as few additional information as possible. In fact, executing the generic implementation of A* requires no other information.

Try it bellow or the experiment.

N =