# 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.1

var initial = { amount: 0, coins: [ 1, 2, 5, 10, 20, 50 ] };

**What is hour goal?**Get an amount of N.1

function isOurGoal(x) { return x.amount == N };

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

2

3

4

5

6

7

8

9

10function whatCanWeDo(x) {

var possibilities = [];

for (var c = 0; c < x.coins.length; c++) {

possibilities.push({

amount: x.amount + x.coins[c],

coins: x.coins

});

}

return possibilities;

}**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.1

function effort(a, b) { return 1; };

**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.1

2

3

4

5

6function remainingChange(x) {

if (x.amount > N)

return N; // because I must have counted wrongly

else

return N - x.amount;

}**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.1

2

3function whatMakesItTheSame(x) {

return x.amount;

}

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.

1 | var results = astar({ |

Try it bellow or the experiment.

N =