app.js

var count = 10;
var numAnts = 3;
var randomAntIndex = [3, 6, 9];

var alpha = 1.0;
var beta = 5.0;
var Q = 100;
var V = 0.01;
var randomFactor = 0.07;

var cities = [];
var ants = [];
var edges = [];

var initialPheromoneLevel = 0.001;
var precision = 1;
var speedFactor = 10;

var enablePathDrawing = false;

var antMap = new Map();
var globalShortestDistance = 0.0;
var globalShortestPath = [];
var globalPheromones = [];

var simulationIteration = 0;

var animFinished = false;
var numFinishedAnts = 0;

class Edge {
  e;
  from;
  to;
  pheromone;
  constructor(e, from, to, pheromone) {
    this.e = e;
    this.from = from;
    this.to = to;
    this.pheromone = pheromone;
  }
}

class Node {
  p;
  index;
  symbol;
  constructor(index, p, symbol) {
    this.p = p;
    this.index = index;
    this.symbol = symbol;
  }
}

class Ant {
  startCity;
  goalCity;
  visualObject;
  travelledDistance;
  visitedCities;
  isFinished;
  pheromoneMap;

  constructor(startCity, visualObject) {
    this.startCity = startCity;
    this.visualObject = visualObject;

    this.visitedCities = [startCity];
    this.travelledDistance = 1.0;
    this.isFinished = false;

    this.goalCity = -1;

    this.pheromoneMap = [];
  }

  moveAnt() {
    if (this.isFinished) {
      return;
    }
    if (this.goalCity === undefined || this.goalCity < 0) {
      this.goalCity = this.getNextCity();
    }
    var goal = cities[this.goalCity];
    var isAtGoal = this.getDist(goal.p, this.visualObject.position);
    if (isAtGoal) {
      var from = this.visitedCities.at(-1);
      this.travelledDistance += this.getLength(cities[from].p.x, cities[from].p.y, 
        cities[this.goalCity].p.x, cities[this.goalCity].p.y);

      this.pheromoneMap.push(new Edge(null, from, this.goalCity, Q / this.travelledDistance));

      this.visitedCities.push(this.goalCity);
      if (this.visitedCities.length == count) {
        this.isFinished = true;
        return;
      }
      this.goalCity = this.getNextCity();
    } else {
      var direction = this.calculateDirectionVector(goal.p, this.visualObject.position);
      this.updateAntPosition(direction);
    }
  }

  getPheromoneUpdateAt(val) {
    return this.pheromoneMap[val];
  }

  updateAntPosition(newPos) {
    this.visualObject.position.x += newPos.x;
    this.visualObject.position.y += newPos.y;
  }

  getNextCity() {
    if (Math.random()  < randomFactor) {
      var randCity = this.pickRandomCity();
      return randCity.index;
    }
    var probs = this.calculateProbabilities();
    var maxProb = 0;
    var cityIndex = -1;
    for (var i = 0; i < count; i++) {
      var p = probs[i];
      if (maxProb <= p) {
        cityIndex = i;
        maxProb = p;
      }
    }
    return cityIndex;
  }

  pickRandomCity() {
    var citiesToChoose = [];
    for (var i = 0; i < count; i++) {
      if (this.visitedCities.includes(cities[i].index)) {
        continue;
      }
      citiesToChoose.push(cities[i]);
    }
    return citiesToChoose[Math.floor(Math.random() * citiesToChoose.length)];
  }

  calculateProbabilities() {
    var probs = [];
    var denom = 0.0;
    var currentCityIndex = this.startCity;
    for (var i = 0; i < count; i++) {
      if (this.visitedCities.includes(cities[i].index)) {
        continue;
      }
      denom += Math.pow(edges[currentCityIndex][i].pheromone, alpha) * Math.pow(1.0 / cities[currentCityIndex].symbol.position.getDistance(cities[i].p), beta);
    }
    if (denom > Number.MAX_VALUE) {
      denom = Number.MAX_VALUE;
    }
    for (var i = 0; i < count; i++) {
      if (this.visitedCities.includes(cities[i].index)) {
        probs[i] = 0.0;
        continue;
      }
      var num = Math.pow(edges[currentCityIndex][i].pheromone, alpha) * 
        Math.pow(1.0 / cities[currentCityIndex].symbol.position.getDistance(cities[i].p), beta);
      probs[i] = num / denom;
    }
    return probs;
  }

  calculateDirectionVector(p1, p2) {
    var a = new Point(p1.x, p1.y);
    var b = new Point(p2.x, p2.y);
    var rx = a.x - b.x;
    var ry = a.y - b.y;
    var p = new Point(rx, ry);
    p.x = p.x / p.length;
    p.y = p.y / p.length;
    return new Point(p.x, p.y);
  }

  getLength(x1, y1, x2, y2) {
    var a = x1 - y1;
    var b = x2 - y2;
    return Math.sqrt((a*a) + (b*b));
  }

  getDist(p1, p2) {
    return Math.abs(p1.x - p2.x) <= precision && Math.abs(p1.y - p2.y) <= precision;
  }
}

function createGraph() {
  var s = new Size(900, 750);
  for (var i = 0; i < count; i++) {
    var sr = Size.random();
    var sizeX = s.width * sr.width;
    var sizeY = s.height * sr.height;

    var tmpX = sizeX;
    var tmpY = sizeY;

    var p = new Point(tmpX, tmpY);
    var myCircle = new Path.Circle(p, 10);
    myCircle.fillColor = 'black';

    cities[i] = new Node(i, p, myCircle);
  }

  for (var i = 0; i < count; i++) {
    var start = cities[i];
    edges[i] = [];
    for (var j = 0; j < count; j++) {
      var end = cities[j];
      var path = new Path();
      path.add(start.p);
      path.add(end.p);
      if (enablePathDrawing) {
        path.strokeColor = 'black';
      }
      edges[i][j] = new Edge(path, i, j, initialPheromoneLevel);
    }
  }

  for (var i = 0; i < numAnts; i++) {
    var rndAnt = randomAntIndex[i];
    var antLocation = cities[rndAnt].p;

    var antPathObject = new Path.Circle(antLocation, 5);
    antPathObject.fillColor = 'red';

    var a = new Ant(rndAnt, antPathObject);
    ants[i] = a;
  }
}


function updatePheromones(shortestAnt) {
  for (var i = 0; i < count; i++) {
    for (var j = 0; j < count; j++) { 
      edges[i][j].pheromone *= (1.0 - V);
    }
  }
  for (var i = 0; i < ants.length; i++) {
    var ant = ants[i];
    for (const e of ant.pheromoneMap) {
      edges[e.from][e.to].pheromone += e.pheromone;
    }
  }
}

function findShortestAnt() {
  let maxPath = 0;
  let maxAnt = null;
  for (var i = 0; i < ants.length; i++) {
    var curAnt = ants[i];
    if (maxPath <= curAnt.travelledDistance) {
      maxAnt = curAnt;
      maxPath = curAnt.travelledDistance;
    }
  }
  return maxAnt;
  // this.pheromones[this.cityGoal] += (Q / this.traveledDistance);
}

function update(event) {
  if (numFinishedAnts == numAnts) {
    console.log("all ants finished");
    maxAnt = findShortestAnt();
    updatePheromones(maxAnt);
  }
  ants.forEach((a) => {
    if (a.isFinished) {
      numFinishedAnts++;
    } else {
      a.moveAnt();  
    }
  });
}

paper.install(window);

// Only executed our code once the DOM is ready.
window.onload = function() {
  var canvas = document.getElementById("myCanvas");
  paper.setup(canvas);

  createGraph();

  view.onFrame = update;
}