A* algorithm returns heuristic value (JavaScript)

Question

I created a A* algorithm for JavaScript. The important thing is that it has to search for the longst path not the shortest. When the path finishes searching I just want to get the depth of the path / its length. The algorithm just returns a maximum length instead of the path.

When debugging the result I think this algorithm just returns the value of the heuristic.

I have stage objects with ids and activity objects which connect two stages by holding a fromId and a toId.

Example:

I have the ids of the status objects

1,
2,
3,
4,
5

and the activities

(1, 2),
(1, 3),
(2, 3),
(3, 5),
(5, 1)

I would expect this result:

distance stage 1: 0
distance stage 2: 1
distance stage 3: 2
distance stage 4: 0 (because there are no connections)
distance stage 5: 3

but the result I get is

result

Why do I think I can use the A* for the longest path?

Well the A* compares distances and takes the lower one. It should be possible to take the higher distance with higher cost by changing the compare statement.

I provide a working code example here

// #########################################
// My initializer script with some fake data
// #########################################

$(document).ready(() => {
  const path = new Path(activities, 1);

  for (let i = 0; i < stages.length; i++) {
    const currentStage = stages[i];
    const currentStageId = currentStage.id;
    const currentDistance = path.getMaximumDistance(currentStage);
    console.log(`id: ${currentStageId} distance: ${currentDistance}`);
  }
});

const stages = [
  new Stage(1),
  new Stage(2),
  new Stage(3),
  new Stage(4),
  new Stage(5)
];

function Stage(id) {
  this.id = id;
}

const activities = [
  new Activity(1, 2),
  new Activity(1, 3),
  new Activity(2, 3),
  new Activity(3, 5),
  new Activity(5, 1)
];

function Activity(fromId, toId) {
  this.fromId = fromId;
  this.toId = toId;
}

// #########################################
// The A* class
// #########################################

function Path(activities, initialId) {

  this.getMaximumDistance = (targetStage) => {
    var me = this;
    var targetId = targetStage.id;
    var openList = [];
    var closedList = [];

    this.addNodeToList(openList, this.createNode(initialId, this.activities));

    let maxDistance = 0;

    while (openList.length > 0) {
      var currentNode = openList[this.getHighestCostIndex(openList)];

      if (currentNode.id === targetId) {
        maxDistance = this.getPathLength(currentNode);
        break;
      }

      this.removeNodeFromList(openList, currentNode);
      this.addNodeToList(closedList, currentNode);

      currentNode.neighbourIds.forEach(id => {
        var neighbour = me.createNode(id, me.activities);

        let lookUpTableElement;
        if (!me.listContainsNode(closedList, neighbour)) {
          var tempIncrementalCost = currentNode.incrementalCost + 1;

          if (me.listContainsNode(openList, neighbour)) {
            if (tempIncrementalCost < neighbour.incrementalCost) {
              neighbour.changeIncrementalCost(tempIncrementalCost);
            }
          } else {
            neighbour.changeIncrementalCost(tempIncrementalCost);
            me.addNodeToList(openList, neighbour);
          }

          for (var i = 0; i < me.lookUpTable.length; i++) {
            var currentLookUpTableElement = me.lookUpTable[i];
            if (currentLookUpTableElement.id === neighbour.id) {
              lookUpTableElement = currentLookUpTableElement;
            }
          }

          var heuristic = lookUpTableElement ? lookUpTableElement.cost : 0;
          neighbour.changeHeuristic(heuristic);
          neighbour.setParent(currentNode);
        }
      });
    }

    return maxDistance;
  };

  this.createNode = (id, activities) => {
    return new PathNode(id, activities);
  };

  this.getHighestCostIndex = (openList) => {
    let highestCostIndex = 0;

    for (let i = 0; i < openList.length; i++) {
      if (openList[i].totalCost > openList[highestCostIndex].totalCost) {
        highestCostIndex = i;
      }
    }

    return highestCostIndex;
  };

  this.addNodeToList = (list, node) => {
    list.push(node);
  };

  this.listContainsNode = (list, node) => {
    return list.some(x => x.id === node.id);
  };

  this.removeNodeFromList = (list, node) => {
    var index = list.indexOf(node);
    list.splice(index, 1);
  };

  this.getPathLength = (node) => {
    let currentNode = node;
    let counter = 0;

    while (currentNode.parent) {
      currentNode = currentNode.parent;
      counter++;
    }

    return counter;
  };

  this.activities = activities;
  this.lookUpTable = new LookUpTable(this.activities, initialId).table;
}

// #########################################
// Node class for the A*
// #########################################

function PathNode(id, activities) {

  this.getNeighbourIds = (activities) => {
    return activities
      .filter(x => x.fromId === id)
      .map(x => x.toId);
  };

  this.setParent = (parentNode) => {
    this.parent = parentNode;
  };

  this.changeHeuristic = (heuristic) => {
    this.heuristic = heuristic;
    this.updateTotalCost();
  };

  this.changeIncrementalCost = (incrementalCost) => {
    this.incrementalCost = incrementalCost;
    this.updateTotalCost();
  };

  this.updateTotalCost = () => {
    this.totalCost = this.incrementalCost + this.heuristic;
  };

  this.id = id;
  this.heuristic = 0;
  this.incrementalCost = 0;
  this.totalCost = 0;
  this.parent = null;
  this.neighbourIds = this.getNeighbourIds(activities);
}

// #########################################
// The heuristic code
// #########################################

function LookUpTable(activities, originId) {
  this.getLookUpTable = (originId) => {
    const me = this;
    const lookUpTable = [];
    let currentLevel = 0;
    let openList = [];

    this.addStage(openList, originId, currentLevel);

    while (openList.length > 0) {
      var lookUpTableElements = openList.filter(openNode => openNode.cost <= currentLevel);

      lookUpTableElements.forEach(lookUpTableElement => {
        this.addStage(lookUpTable, lookUpTableElement.id, currentLevel);

        var neighbours = activities.filter(targetActivity => targetActivity.fromId === lookUpTableElement.id);

        neighbours.forEach(neighbour => {
          var neighbourId = neighbour.toId === lookUpTableElement.id ? neighbour.fromId : neighbour.toId;

          if (!lookUpTable.some(x => x.id === neighbourId) && !openList.some(x => x.id === neighbourId)) {
            me.addStage(openList, neighbourId, currentLevel + 1);
          }
        });
      });

      openList = openList.filter(x => x.cost !== currentLevel);
      currentLevel++;
    }

    return lookUpTable;
  };

  this.addStage = (array, stageId, level) => {
    array.push({
      id: stageId,
      cost: level
    });
  };

  this.activities = activities;
  this.table = this.getLookUpTable(originId);
}

What is wrong with my A* algorithm that it returns the correct heuristic value instead of the maximum distance?

Important note: If someone got a better idea for finding the maximum distance between these connections please let me know!

A* algorithm returns heuristic value (JavaScript)

Answers (1)

Related Questions