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 tightly coupled with Dijkstra. But although many problems can be reduced to a graph traversal it’s convenient to avoid that step. Let the search algorithm 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
    10
    function 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
    6
    function 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
    3
    function 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
2
3
4
5
6
7
8
var results = astar({
initial: initial,
fgoal: isOurGoal,
fsuccessors: whatCanWeDo,
fdistance: effort,
fheuristic: remainingChange,
fidentity: whatMakesItTheSame
});

Try it bellow or the experiment.

N =