Source: maze/longestPathFinder.js

/**
 * A module that helps with finding the longest path in a matrix maxe.
 * @module
 */
define([
  'lodash',
  'structs/PriorityQueue',
  './matrixMaze'
], function(_, PriorityQueue, matrixMaze) {
  'use strict';

  var exports = {};

  /**
   * Expand `path`'s end with one cell and put all those possible combinations
   * into `pathsQueue`.
   *
   * <p>The path can branch off into at maximum 4 new paths. When a new path is
   * created it's put into the paths queue where the priority is minus the
   * length of the path. `maze` is also updated for each visited cell with
   * `visited=true`. On the other hand, if `path` doesn't have any adjacent
   * unvisited floor cells nothing is done and the function returns `true`
   * which says that `path` has reached a dead end.</p>
   *
   * @private
   * @param {Array.<Array.<Object>>} maze A matrix that represents a maze.
   * @param maze.wall {boolean}
   * @param maze.visited {boolean}
   * @param {Array.<Object>} path The path that should be expanded.
   * @param path.y {number}
   * @param path.x {number}
   * @param {module:structs/PriorityQueue} pathsQueue Where the expanded paths
   *   should be put.
   * @returns {boolean} If the path has reached a dead end. In this case no new
   *   path is added to `pathsQueue`.
   */
  exports.__expandPath = function(maze, path, pathsQueue) {
    var lastPathCell = path[path.length - 1];
    var y = lastPathCell.y,
        x = lastPathCell.x;
    var neighborCells = matrixMaze.getCellNeighbors(maze, y, x);
    var unvisitedFloorNeighborCells = _.filter(neighborCells, function(cell) {
      // Mark the cell as visited in the maze
      var mazeCell = maze[cell.y][cell.x];
      return !mazeCell.visited && !mazeCell.wall;
    });
    switch (unvisitedFloorNeighborCells.length) {
      case 0:
        // Dead end
        return true;
      case 1:
      case 2:
      case 3:
      case 4:
        _.forEach(unvisitedFloorNeighborCells, function(cell) {
          maze[cell.y][cell.x].visited = true;
          // Clone the path
          var pathClone = _.clone(path, true);
          // Push the unvisited cell to the path
          pathClone.push(_.pick(cell, ['y', 'x']));
          // Add the path to the priority queue
          pathsQueue.enqueue(-pathClone.length, pathClone);
        });
        // No dead end
        return false;
    }
  };

  /**
   * Find the longest path in the maze.
   *
   * @param {Array.<Array.<Object>>} maze A matrix that represents a maze.
   * @param maze.wall {boolean} Whether it's a wall or a floor.
   * @param {Object} start The start of the path.
   * @param start.y {number} Y coordinate.
   * @param start.x {number} X coordinate.
   * @returns {Array.<Object>} An array of objects with x and y attributes.
   */
  exports.find = function(maze, start) {
    // Make a copy of the maze
    maze = _.clone(maze, true);
    // Add an attribute to each floor that saves if it has been visited
    _.forEach(maze, function(row) {
      _.forEach(row, function(cell) {
        if (!cell.wall) {
          cell.visited = false;
        }
      });
    });

    var paths = new PriorityQueue();
    paths.enqueue(-1, [start]);

    var longestPath;

    while(paths.size() > 0) {
      // Get the shortest path
      var path = paths.dequeue();
      var deadEnd = this.__expandPath(maze, path, paths);
      if (deadEnd) {
        longestPath = path;
      }
    }
    return longestPath;
  };

  return exports;
});