<commit_before>const Direction = require('../models/direction');
const PathPlan = require('../models/pathPlan');

/**
 * Returns a PathPlan to get from the position after the current one
 * to the next goal
 * Returns an empty path if there is no path to the goal (about to die)
 */
export function planPathAStar(game) {
  // Need to start on the position *after* the current one because
  // at this point the snake is already moving there, there is nothing
  // to be gained by searching other directions from the current position
  game = game.update('snake', (snake) => snake.shift());

  const finish = game.goal;

  const open = [createAStarNode(game, null, null, finish)];
  const visited = new Set();

  while (open.length) {
    const current = open.splice(0, 1)[0];
    visited.add(current.id);

    const position = current.game.snake.head();

    if (position.equals(finish)) {
      return solutionPathFromAStar(current);
    }

    for (let {adjacent, direction} of availableAdjacents(current.game)) {
      if (visited.has(adjacent.hash())) {
        continue;
      }

      // Change directions AND shift so that the snake moves in this
      // direction
      const adjGame = current.game.update('snake',
        (snake) => snake.setDirection(direction).shift());
      const adjNode = createAStarNode(adjGame, current, direction, finish);

      // Skip a potential node with a lower cost
      var sameOpen = open.findIndex((n) => n.id === adjNode.id);
      if (sameOpen > -1) {
        if (open[sameOpen].cost < adjNode.cost) {
          continue;
        }
        else {
          // Remove sameOpen since its cost is higher than this path
          open.splice(sameOpen, 1);
        }
      }

      insertAStarNodeByCost(open, adjNode);
    }
  }
  
  // exhausted search
  console.debug('exhausted search for goal, giving up');
  return new PathPlan();
}

function createAStarNode(game, parent, direction, finish) {
  const position = game.snake.head();

  let total = 0;
  if (parent) {
    const parentPosition = parent.game.snake.head();
    total = parent.totalCost + parentPosition.squaredDistanceTo(position);
  }

  const estimate = position.squaredDistanceTo(finish);

  // Very basic heuristic for determining if this path will lead to a
  // dead end. A more advanced method would be to look ahead from the
  // finish and see if there are alternate paths afterwards
  // The advanced method should lookahead at least the number of spaces
  // the snake will grow to see if it hits something
  let extra = 0;
  if (position.equals(game.goal)) {
    const afterGoal = position.add(game.snake.direction);
    if (game.isSnake(afterGoal) || game.isOutOfBounds(afterGoal)) {
      // this extra cost will influence the snake to avoid these conditions
      // but also still not exhaust the search if this is the only option
      // Needs to be at least the square of the distance from corner to corner
      extra += 5000;
    }

    const twoAfterGoal = afterGoal.add(game.snake.direction);<commit_msg>Adding a heuristic to straighten the snake path<commit_after>const Direction = require('../models/direction');
const PathPlan = require('../models/pathPlan');

/**
 * Returns a PathPlan to get from the position after the current one
 * to the next goal
 * Returns an empty path if there is no path to the goal (about to die)
 */
export function planPathAStar(game) {
  // Need to start on the position *after* the current one because
  // at this point the snake is already moving there, there is nothing
  // to be gained by searching other directions from the current position
  game = game.update('snake', (snake) => snake.shift());

  const finish = game.goal;

  const open = [createAStarNode(game, null, null, finish)];
  const visited = new Set();

  while (open.length) {
    const current = open.splice(0, 1)[0];
    visited.add(current.id);

    const position = current.game.snake.head();

    if (position.equals(finish)) {
      return solutionPathFromAStar(current);
    }

    for (let {adjacent, direction} of availableAdjacents(current.game)) {
      if (visited.has(adjacent.hash())) {
        continue;
      }

      // Change directions AND shift so that the snake moves in this
      // direction
      const adjGame = current.game.update('snake',
        (snake) => snake.setDirection(direction).shift());
      const adjNode = createAStarNode(adjGame, current, direction, finish);

      // Skip a potential node with a lower cost
      var sameOpen = open.findIndex((n) => n.id === adjNode.id);
      if (sameOpen > -1) {
        if (open[sameOpen].cost < adjNode.cost) {
          continue;
        }
        else {
          // Remove sameOpen since its cost is higher than this path
          open.splice(sameOpen, 1);
        }
      }

      insertAStarNodeByCost(open, adjNode);
    }
  }
  
  // exhausted search
  console.debug('exhausted search for goal, giving up');
  return new PathPlan();
}

function createAStarNode(game, parent, direction, finish) {
  const position = game.snake.head();

  let extra = 0;

  let total = 0;
  if (parent) {
    const parentPosition = parent.game.snake.head();
    total = parent.totalCost + parentPosition.squaredDistanceTo(position);

    // An additional extra heuristic to favor straighter paths
    if (!game.snake.direction.equals(parent.game.snake.direction)) {
      // This weight will be the minimum number of steps the snake
      // will attempt to stay in a straight path for
      // It is usually safe to set this at the width or height of the
      // screen. Setting it too high (higher than other weights) will
      // result in those considerations being placed at a lower priority
      extra += 30;
    }
  }

  const estimate = position.squaredDistanceTo(finish);

  // Very basic heuristic for determining if this path will lead to a
  // dead end. A more advanced method would be to look ahead from the
  // finish and see if there are alternate paths afterwards
  // The advanced method should lookahead at least the number of spaces
  // the snake will grow to see if it hits something
  if (position.equals(game.goal)) {
    const afterGoal = position.add(game.snake.direction);
    if (game.isSnake(afterGoal) || game.isOutOfBounds(afterGoal)) {
      // this extra cost will influence the snake to avoid these conditions
      // but also still not exhaust the search if this is the only option
      // Needs to be at least the square of the distance from corner to corner
      extra += 5000;
    }

    const twoAfterGoal = afterGoal.add(game.snake.direction);
{'fraction_non_alphanumeric': 0.09918231374924288, 'fraction_numerical': 0.0036341611144760752, 'mean_word_length': 2.917556346381969, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2803792', 'n_tokens_mistral': 1883, 'n_tokens_neox': 1808, 'n_words': 700}