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.

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

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

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

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

  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.

  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.

  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.

  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.

var results = astar({
    initial: initial,
    fgoal: isOurGoal,
    fsuccessors: whatCanWeDo,
    fdistance: effort,
    fheuristic: remainingChange,
    fidentity: whatMakesItTheSame
});

Try it bellow or the experiment.

N = Go