TSP: Nearest-Neighbor + 2-Opt

let cities;
let tour;
let tourLen;
let iter;
let lastSwap;
let W0, H0;

function rand(min, max) { return min + Math.random() * (max - min); }

function dist(a, b) {
  const dx = a.x - b.x, dy = a.y - b.y;
  return Math.sqrt(dx * dx + dy * dy);
}

function tourLength(t) {
  let s = 0;
  for (let i = 0; i < t.length; i++) {
    s += dist(cities[t[i]], cities[t[(i + 1) % t.length]]);
  }
  return s;
}

function nearestNeighbor() {
  const n = cities.length;
  const used = new Uint8Array(n);
  const t = new Array(n);
  t[0] = 0;
  used[0] = 1;
  for (let i = 1; i < n; i++) {
    const prev = cities[t[i - 1]];
    let best = -1, bestD = Infinity;
    for (let j = 0; j < n; j++) {
      if (used[j]) continue;
      const d = dist(prev, cities[j]);
      if (d < bestD) { bestD = d; best = j; }
    }
    t[i] = best;
    used[best] = 1;
  }
  return t;
}

function seedCities(W, H) {
  cities = [];
  const n = 16;
  for (let i = 0; i < n; i++) {
    cities.push({ x: rand(W * 0.08, W * 0.92), y: rand(H * 0.12, H * 0.92) });
  }
}

function rebuild() {
  tour = nearestNeighbor();
  tourLen = tourLength(tour);
  iter = 0;
  lastSwap = null;
}

function init({ width, height }) {
  W0 = width; H0 = height;
  seedCities(width, height);
  rebuild();
}

// Try one 2-opt swap per call; commit if it improves length.
function tryTwoOpt() {
  const n = tour.length;
  if (n < 4) return;
  // pick two non-adjacent edges
  let i = (Math.random() * n) | 0;
  let k = (Math.random() * n) | 0;
  if (i > k) { const t = i; i = k; k = t; }
  // ensure i < k and they don't share endpoints; need at least one node between
  if (k - i < 2) return;
  if (i === 0 && k === n - 1) return; // would reverse whole tour edge wrap
  const a = cities[tour[i]];
  const b = cities[tour[i + 1]];
  const c = cities[tour[k]];
  const d = cities[tour[(k + 1) % n]];
  const before = dist(a, b) + dist(c, d);
  const after = dist(a, c) + dist(b, d);
  iter++;
  if (after + 1e-9 < before) {
    // reverse segment tour[i+1..k]
    let lo = i + 1, hi = k;
    while (lo < hi) {
      const tmp = tour[lo]; tour[lo] = tour[hi]; tour[hi] = tmp;
      lo++; hi--;
    }
    tourLen += (after - before);
    lastSwap = { i, k, age: 0 };
  }
}

function addCity(x, y) {
  cities.push({ x, y });
  rebuild();
}

function tick({ ctx, width: W, height: H, input }) {
  // handle clicks: add a city
  for (const c of input.consumeClicks()) {
    if (c.x < 0 || c.y < 0 || c.x > W || c.y > H) continue;
    if (cities.length < 80) addCity(c.x, c.y);
  }

  // do several attempts per frame so improvement looks lively
  for (let s = 0; s < 8; s++) tryTwoOpt();

  // background with subtle trail fade
  ctx.fillStyle = "rgba(8,10,16,0.35)";
  ctx.fillRect(0, 0, W, H);

  const n = tour.length;

  // draw tour polyline (closed)
  ctx.lineWidth = 1.5;
  ctx.strokeStyle = "rgba(120,200,255,0.85)";
  ctx.beginPath();
  for (let i = 0; i < n; i++) {
    const p = cities[tour[i]];
    if (i === 0) ctx.moveTo(p.x, p.y); else ctx.lineTo(p.x, p.y);
  }
  ctx.closePath();
  ctx.stroke();

  // highlight latest swap edges (the two new edges after the reversal)
  if (lastSwap && lastSwap.age < 30) {
    const { i, k } = lastSwap;
    const a = cities[tour[i]];
    const b = cities[tour[i + 1]];
    const c = cities[tour[k]];
    const d = cities[tour[(k + 1) % n]];
    const alpha = 1 - lastSwap.age / 30;
    ctx.strokeStyle = `rgba(255,180,80,${alpha.toFixed(3)})`;
    ctx.lineWidth = 3;
    ctx.beginPath();
    ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y);
    ctx.moveTo(c.x, c.y); ctx.lineTo(d.x, d.y);
    ctx.stroke();
    lastSwap.age++;
  }

  // draw cities
  for (let i = 0; i < cities.length; i++) {
    const p = cities[i];
    ctx.fillStyle = "#0a0e16";
    ctx.beginPath(); ctx.arc(p.x, p.y, 5, 0, Math.PI * 2); ctx.fill();
    ctx.fillStyle = "#e8f0ff";
    ctx.beginPath(); ctx.arc(p.x, p.y, 3, 0, Math.PI * 2); ctx.fill();
  }

  // HUD
  ctx.fillStyle = "rgba(0,0,0,0.55)";
  ctx.fillRect(8, 8, 230, 60);
  ctx.fillStyle = "#fff";
  ctx.font = "13px monospace";
  ctx.fillText(`cities: ${cities.length}`, 16, 26);
  ctx.fillText(`tour length: ${tourLen.toFixed(1)}`, 16, 44);
  ctx.fillText(`2-opt iter: ${iter}`, 16, 62);

  ctx.fillStyle = "rgba(180,200,230,0.7)";
  ctx.font = "11px monospace";
  ctx.fillText("click to add a city", 16, H - 12);
}