ocadotechnology/rapid-router

View on GitHub
game/static/game/js/pathFinder.js

Summary

Maintainability
D
2 days
Test Coverage
'use strict';

var ocargo = ocargo || {};

ocargo.PathFinder = function(model) {
    this.van = model.van;
    this.nodes = model.map.nodes;
    this.destinations = model.map.destinations;

    this.pathScoreDisabled = DISABLE_ROUTE_SCORE;
    this.algorithmScoreDisabled = DISABLE_ALGORITHM_SCORE;
    this.modelSolution = MODEL_SOLUTION;

    const tooSimpleToGetAlgorithmScore = (LEVEL_ID < 13);

    if (!this.pathScoreDisabled) {
        if (tooSimpleToGetAlgorithmScore) {
            this.maxScoreForPathLength = 20;
        } else {
            this.maxScoreForPathLength = 10;
        }
    } else {
        this.maxScoreForPathLength = 0;
    }

    this.maxScoreForNumberOfInstructions = 0;

    if (!this.algorithmScoreDisabled) {
        this.maxScoreForNumberOfInstructions = 10;
    }

    this.maxScore = this.maxScoreForPathLength + this.maxScoreForNumberOfInstructions;
    this.optimalPath = getOptimalPath(this.nodes, this.destinations);
};

ocargo.PathFinder.prototype.getScore = function() {
    let routeCoins = {};
    let instrCoins = {};
    let performance= "";

    let pathLengthScore = 0;
    if (!this.pathScoreDisabled) {
        pathLengthScore = Math.max(0, this.getTravelledPathScore());
        routeCoins = this.getNumCoins(pathLengthScore, this.maxScoreForPathLength);
    }

    let totalScore = pathLengthScore;

    if (!this.algorithmScoreDisabled) {
        var initInstrScore = this.getScoreForNumberOfInstructions();
        var instrScore = Math.max(0, initInstrScore);

        if (initInstrScore >= 2 * this.maxScoreForNumberOfInstructions) {
            instrScore = 0;
        } else if (initInstrScore > this.maxScoreForNumberOfInstructions) {
            instrScore = this.maxScoreForNumberOfInstructions - initInstrScore % this.maxScoreForNumberOfInstructions;
        }
        instrScore = Math.max(0, instrScore);

        totalScore += instrScore;
        instrCoins = this.getNumCoins(instrScore, this.maxScoreForNumberOfInstructions);
    }

    if (pathLengthScore < this.maxScoreForPathLength) {
        performance = "pathLonger";
    }
    else if (initInstrScore > this.maxScoreForNumberOfInstructions) {
        performance = "algorithmShorter";
    }
    else if (initInstrScore < this.maxScoreForNumberOfInstructions) {
        performance = "algorithmLonger";
    }
    else if (totalScore === this.maxScore) {
        performance = "scorePerfect";
    }

    const endLevelMsg = function(performance) {
        switch (performance){
            case 'pathLonger':
                return gettext('Try finding a shorter route to the destination.');
            case 'algorithmLonger':
                return gettext('Try creating a simpler program.');
            case 'algorithmShorter':
                return gettext('That solution isn\'t quite right. Read the level instructions or click Help.');
            case 'scorePerfect':
                return gettext('Congratulations! You\'ve aced it.');
            default:
                return '';
        }
    };

    return {totalScore: totalScore,
            routeCoins: routeCoins,
            instrCoins: instrCoins,
            maxScore: this.maxScore,
            performance: performance,
            pathLengthScore: pathLengthScore,
            pathScoreDisabled: this.pathScoreDisabled,
            algorithmScoreDisabled: this.algorithmScoreDisabled,
            maxScoreForPathLength: this.maxScoreForPathLength,
            instrScore: instrScore,
            maxScoreForNumberOfInstructions: this.maxScoreForNumberOfInstructions,
            popupMessage: endLevelMsg(performance)};
};

/* Return number of coins for each type*/
ocargo.PathFinder.prototype.getNumCoins = function(score, maxScore) {
    return {whole: Math.floor(score), half: score - Math.floor(score) > 0 ? 1 : 0, zero: maxScore - Math.ceil(score)};
};

ocargo.PathFinder.prototype.getTravelledPathScore = function() {
    const travelled = this.van.getDistanceTravelled();
    const START_AND_END_BLOCKS = 2;
    return this.maxScoreForPathLength - (travelled + START_AND_END_BLOCKS - this.optimalPath.length);
};

ocargo.PathFinder.prototype.getScoreForNumberOfInstructions = function() {
    const blocksUsed = ocargo.utils.isIOSMode() ? ocargo.game.mobileBlocks : ocargo.blocklyControl.activeBlocksCount();
    let algorithmScore = 0;
    let difference = this.maxScoreForNumberOfInstructions;
    for (let i = 0; i < this.modelSolution.length; i++) {
        let currDifference = blocksUsed - this.modelSolution[i];
        if (Math.abs(currDifference) < difference) {
            difference = Math.abs(currDifference);
            algorithmScore = this.maxScoreForNumberOfInstructions - currDifference;
        }
    }
    return algorithmScore;
};

ocargo.PathFinder.prototype.getLength = function(stack) {
    let total = 0;
    if (!stack) {
        return total;
    }
    for (let i = 0; i < stack.length; i++) {
        if (stack[i].command === "While") {
            total += this.getLength(stack[i].block);
        }
        else if (stack[i].command === 'If') {
            total += this.getLength(stack[i].ifBlock);
            total += this.getLength(stack[i].elseBlock);
        }
        total++;
    }
    return total;
};

function getOptimalPath(nodes, destinations) {
    // Brute force Travelling Salesman implementation, using A* to determine the connection lengths
    // If the map size increases or lots of destinations are required, it may need to be rethought
    let hash = {};
    function getPathBetweenNodes(node1, node2) {
        const key = '(' + node1.coordinate.x + ',' + node1.coordinate.y + '),(' + node2.coordinate.x +
                    ',' + node2.coordinate.y + ')';
        let solution;
        if (key in hash) {
            solution = hash[key];
        }
        else {
            solution = aStar(node1, node2, nodes);
            hash[key] = solution;
        }
        return solution;
    }

    function getPermutationPath(start, permutation) {
        let fragPath = [getPathBetweenNodes(start, permutation[0], nodes)];
        for (let i = 1; i < permutation.length; i++) {
            fragPath.push(getPathBetweenNodes(permutation[i-1], permutation[i], nodes));
        }

        let fullPath = [start];
        for (let i = 0; i < fragPath.length; i++) {
            if (!fragPath[i]) {
                return null;
            }
            else {
                fullPath = fullPath.concat(fragPath[i].slice(1));
            }
        }
        return fullPath;
    }

    let permutations = [];
    function permute(array, data) {
        let current;
        let currentPermutation = data || [];

        for (let i = 0; i < array.length; i++) {
            // Take node out
            current = array.splice(i, 1)[0];
            // Then the current permutation is complete so add it
            if (array.length === 0) {
                permutations.push(currentPermutation.concat([current]));
            }
            //Recurse over the remaining array
            permute(array.slice(), currentPermutation.concat([current]));
            // Add node back in
            array.splice(i, 0, current);
        }
    }

    let start = nodes[0];
    let bestScore = Number.POSITIVE_INFINITY;
    let bestPermutationPath = null;
    let destinationNodes = [];

    for (let i = 0; i < destinations.length; i++) {
        destinationNodes.push(destinations[i].node);
    }
    permute(destinationNodes);

    for (let i = 0; i < permutations.length; i++) {
        let permutation = permutations[i];
        const permutationPath = getPermutationPath(start, permutation, nodes);

        if (permutationPath && permutationPath.length < bestScore) {
            bestScore = permutationPath.length;
            bestPermutationPath = permutationPath;
        }
    }
    return bestPermutationPath;
}

function QueueLink(node, score) {
  this.node = node;
  this.score = score;
  this.next = null;
}

function PriorityQueue() {
  this.push = function(node, score) {
    if (this.head == null) {
      this.head = new QueueLink(node, score);
    } else if (this.head.score > score) {
      let tmp = this.head;
      this.head = new QueueLink(node, score);
      this.head.next = tmp;
    } else {
      let i = this.head;
      let found = false;
      while (i.next != null && !found) {
        if (i.next.score > score) {
          let tmp = i.next;
          i.next = new QueueLink(node, score);
          i.next.next = tmp;
          found = true;
        }
        i = i.next;
      }
      if (!found) {
        i.next = new QueueLink(node, score);
      }
    }
  };

  this.pop = function() {
    if (this.head == null) {
      return null;
    } else {
      const result = this.head.node;
      this.head = this.head.next;
      return result;
    }
  };

  this.isEmpty = function () {
    return this.head == null;
  }
}

function aStar(origin, destination, nodes) {
    const end = destination;          // Nodes already visited.
    let current;
    const start = origin;
    let closedSet = {};             // The neighbours yet to be evaluated.
    let openSet = new PriorityQueue();
    openSet.push(start, 0);

    initialiseParents(nodes);
    closedSet[start.id] = true;

    while (!openSet.isEmpty()) {
        current = openSet.pop();

        // End case.
        if (current === end) {
            return getNodeList(current);
        }
        for (let i = 0; i < current.connectedNodes.length; i++) {
            let neighbour = current.connectedNodes[i];
            if (Object.prototype.hasOwnProperty.call(closedSet, neighbour.id)) {
                continue;
            }
            closedSet[neighbour.id] = true;
            neighbour.parent = current;
            const score = distanceFromStart(neighbour) + heuristic(destination, neighbour);
            openSet.push(neighbour, score);
        }
    }
    // Failed to find a path
    return null;

    function heuristic(node1, node2) {
        const d1 = Math.abs(node2.coordinate.x - node1.coordinate.x);
        const d2 = Math.abs(node2.coordinate.y - node1.coordinate.y);
        return d1 + d2;
    }

    function initialiseParents(nodes) {
        for (let i = 0; i < nodes.length; i++) {
            nodes[i].parent = null;
            nodes[i].id = i;
        }
    }

    function distanceFromStart(current) {
      let count = 0;
      let i = current;
      while (i.parent != null) {
        count = count + 1;
        i = i.parent;
      }
      return count;
    }

    function getNodeList(current) {
        let curr = current;
        let ret = [];
        while (curr !== start && curr !== null) {
            ret.push(curr);
            curr = curr.parent;
        }
        ret.push(start);
        ret.reverse();
        return ret;
    }
}

function areDestinationsReachable(start, destinations, nodes) {
  for (let i = 0; i < destinations.length; i++) {
    if (aStar(start, destinations[i], nodes) == null) {
      return false;
    }
  }
  return true;
}