Heuristic algorithm for playing snake

snake.hogg.io

/**
 * @param {Array[Number]} cell Coordinates of the cell to return a value for
 * @param {Number} xMax The number of cells across the x axis
 * @param {Number} yMax The number of cells across the y axis
 * @param {Array[Array[Number]} snake Coordinates of the position of the snake from head to tail. E.g. [[4, 1], [3, 1]]
 * @param {Array[Number]} point Coorodinates of the point.
 */
function heuristic(cell, xMax, yMax, snake, point) {

  let snakeHead = snake[0];
  if( !snakeHead.neighbors().containsCords(cell) ) return 0;

  let pathToPoint = shortestPath(cell, point, snake);

  if( pathToPoint ) {
    let snakeWhenAtPoint = snake.progressCords(pathToPoint);
    let pathToTail = shortestPath(snakeWhenAtPoint[0], snakeWhenAtPoint.tail(), snakeWhenAtPoint);
    if( pathToTail && pathToTail.length > 3 ) {
      return pathToPoint.length;
    }
  } 
  

  // fallback follow the tail.
  let pathToTail2 = shortestPath(cell, snake.tail(), snake);
  if( pathToTail2 ) return 200 - pathToTail2.length;

  // expensive search for tail
  let pathToTail3 = expensivePathToTail(cell, snake);
  if( pathToTail3 ) return 300 - pathToTail3.length;

  return  888;
}


function shortestPath(start, end, obstacles=[]){

  obstacles = obstacles.removeCords([end]);
  let frontier = [start];
  let cameFrom = {};
  cameFrom[start.key()] = null;

  while( frontier.length ) {
    let current = frontier.shift();

    if( current.is(end) ) break;
    for( let next of current.neighbors().removeCords(obstacles) ) {
      if(!(next.key() in cameFrom)) {
        frontier.push(next)
        cameFrom[next.key()] = current
      }
    }
  }

  // return path
  current = end;
  path = [end];
  while( !current.is(start) ) {
    current = cameFrom[current.key()]
    if( !current ) return null; //there is no path
    path.push(current);
  }

  return path;
}

function expensivePathToTail(cell, snake) {
  let frontier = [cell];
  let paths = {};
  let throttle = 10;

  while( frontier.length ) {
    if( !throttle-- ) return null;
    let current = frontier.shift();
    let pathSoFar = paths[current.key()] || [cell];
    let newSnake = snake.progressCords(pathSoFar);

    let path = shortestPath(current, newSnake.tail(), newSnake);
    if( path ) {
      // warning: repeated cord at join
      return path.concat(pathSoFar);
    }

    for( let next of current.neighbors().removeCords(newSnake) ) {
      if(!(next.key() in paths)) {
        frontier.push(next)
        paths[next.key()] = pathSoFar.concat([next])
      }
    }
  }

  return null;
}


//cords
Array.prototype.neighbors = Array.prototype.neighbors || function() {
  return [
    [this[0],this[1]-1],
    [this[0]+1,this[1]],
    [this[0],this[1]+1],
    [this[0]-1,this[1]]
  ].filter( c => c[0]>=0 && c[1]>=0 && c[0]<=14 && c[1]<=14)
}

Array.prototype.is = Array.prototype.is || function(cords) {
  return this[0]==cords[0] && this[1]==cords[1];
}

Array.prototype.key = Array.prototype.toString

//cords Array
Array.prototype.containsCords = Array.prototype.containsCords || function(cords) {
  return !!this.find( c => c.is(cords) )
}

Array.prototype.removeCords = Array.prototype.removeCords || function(cordsArray) {
  return this.filter( c => !cordsArray.containsCords(c) )
}

Array.prototype.tail = Array.prototype.tail || function() {
  return this[this.length-1]
}

Array.prototype.progressCords = Array.prototype.progressCords || function(cordsArray) {
  let newSnake = cordsArray.concat(this);
  newSnake.splice(0-cordsArray.length);
  return newSnake;
}