All files / src/search graphSearch.js

100% Statements 25/25
91.67% Branches 11/12
100% Functions 4/4
100% Lines 25/25
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70            1x   2x 2x 2x   3x           3x 3x 3x   13308x 13308x   2x       13306x   13306x   35580x 35580x 35580x   20638x                   1x           2x 2x   18x   16x   18x   2x         20638x    
"use strict";
 
/**
 * Basic uninformed graph search.
 * @param {object} paramaters
 */
module.exports.graphSearch = function (paramaters)
{
  paramaters.generateResult = paramaters.generateResult || defaultGenerateResult;
  paramaters.stepCost = paramaters.stepCost || defaultStepCost;
  return async function (problem)
  {
    let frontier = paramaters.queueInsert({
      state: problem.state,
      stateSerialised: paramaters.stateSerialise(problem.state),
      parent: null,
      cost: 0,
    }, null);
    const explored = {};
    const goal = problem.goal || paramaters.goal;
    while (frontier.length > 0)
    {
      const leaf = paramaters.queuePop(frontier);
      if (paramaters.isGoalState(leaf.state, goal))
      {
        return paramaters.generateResult(leaf);
      }
      else
      {
        explored[leaf.stateSerialised] = true;
      }
      for (let action of paramaters.getActions(leaf.state))
      {
        const resultingState = paramaters.performAction(leaf.state, action);
        const stateSerialised = paramaters.stateSerialise(resultingState);
        if (explored[stateSerialised] === undefined)
        {
          frontier = paramaters.queueInsert({
            state: resultingState,
            action: action,
            stateSerialised: stateSerialised,
            parent: leaf,
            cost: leaf.cost + paramaters.stepCost(leaf.state, action)
          }, frontier);
        }
      }
    }
    return null;
  };
};
 
function defaultGenerateResult(leaf)
{
  let sequence = [];
  while (leaf)
  {
    if (leaf.action !== undefined)
    {
      sequence.unshift(leaf.action)
    }
    leaf = leaf.parent;
  }
  return sequence;
}
 
function defaultStepCost(state, action)
{
  return 1;
}