// traveling salesperson algorithm.

// This is extremely inefficient at finding a solution.

​

// 1. The distance between the cities is calculated and compared with

// the current shortest.

// 2. Two members of the array are swapped, and the process repeats.

​

// The green line is the best fit so far.

​

const cities = [],

  iPerFrame = 200;

cityCount = 10;

​

let best = Infinity,

  bestOrder = cities;

​

function setup() {

  createCanvas(innerWidth, innerHeight);

  for (let i = 0; i < cityCount; i++) {

    cities[i] = createVector(random(20, width-20), random(20, height-20));

  }

}

​

function draw() {

  background(10);

  noFill();

  beginShape();

  for (let i = 0; i < cities.length; i++) {

    vertex(cities[i].x, cities[i].y);

​

    if (i == 0) {

      strokeWeight(5);

      stroke(0, 0, 255);

    } else if (i == cities.length - 1) {

      strokeWeight(5);

      stroke(255, 0, 0);

    } else {

      strokeWeight(2);

      stroke(255);

    }

    ellipse(cities[i].x, cities[i].y, 8, 8);

  }

  stroke(70);

  strokeWeight(2);

  endShape();

​

  beginShape();

  stroke(0, 255, 0);

  strokeWeight(4);

  for (let i = 0; i < bestOrder.length; i++) {

    vertex(bestOrder[i].x, bestOrder[i].y);

  }

  endShape();

  noStroke();

  fill(255);

  textSize(18);

  text("shortest distance so far: " + best, 10, 20)

​

  for (let i = 0; i < iPerFrame; i++) {

    swap(

      cities,

      floor(random(1, cities.length - 1)),

      floor(random(1, cities.length - 1))

    );

​

    calcTotalDistance(cities);

  }

}

​

function swap(arr, idx1, idx2) {

  const temp = arr[idx1];

  arr[idx1] = arr[idx2];

  arr[idx2] = temp;

}

​

function calcTotalDistance(arr) {

  let d = 0;

  for (let i = 0; i < arr.length - 1; i++) {

    d += dist(arr[i].x, arr[i].y, arr[i + 1].x, arr[i + 1].y);

  }

  if (d < best) {

    best = d;

    bestOrder = cities.slice();

  }

  return d;

}

​