Genetic Algorithm — Evolving Cars

const POP = 8, NV = 6, TRIAL_T = 8, DT = 1 / 60, G = 900;
const TLEN = 6000, SEG = 30;
let terrain, cars, gen, history, allBest, camX, elapsed;

function groundY(x) {
  if (x <= 0) return terrain[0];
  const i = Math.floor(x / SEG);
  if (i >= terrain.length - 1) return terrain[terrain.length - 1];
  const t = (x - i * SEG) / SEG;
  return terrain[i] * (1 - t) + terrain[i + 1] * t;
}

function randGenome() {
  const v = [];
  for (let i = 0; i < NV; i++) v.push({ a: (i / NV) * Math.PI * 2, r: 14 + Math.random() * 22 });
  return { r1: 8 + Math.random() * 18, r2: 8 + Math.random() * 18, v };
}

function mutate(g) {
  const c = { r1: g.r1, r2: g.r2, v: g.v.map(p => ({ a: p.a, r: p.r })) };
  if (Math.random() < 0.5) c.r1 = Math.max(6, Math.min(28, c.r1 + (Math.random() - 0.5) * 6));
  if (Math.random() < 0.5) c.r2 = Math.max(6, Math.min(28, c.r2 + (Math.random() - 0.5) * 6));
  for (const p of c.v) if (Math.random() < 0.3) p.r = Math.max(8, Math.min(40, p.r + (Math.random() - 0.5) * 8));
  return c;
}

function crossover(a, b) {
  const c = { r1: Math.random() < 0.5 ? a.r1 : b.r1, r2: Math.random() < 0.5 ? a.r2 : b.r2, v: [] };
  const cut = Math.floor(Math.random() * NV);
  for (let i = 0; i < NV; i++) c.v.push({ a: a.v[i].a, r: i < cut ? a.v[i].r : b.v[i].r });
  return c;
}

function spawnCar(g) {
  return {
    g, x: 60, y: groundY(60) - 50, vx: 0, vy: 0, ang: 0, av: 0,
    w1: { ox: -18, oy: 18, x: 60 - 18, y: groundY(60) - 32, vx: 0, vy: 0 },
    w2: { ox: 18, oy: 18, x: 60 + 18, y: groundY(60) - 32, vx: 0, vy: 0 },
    fit: 0, maxX: 60, stuck: 0, alive: true, hue: Math.floor(Math.random() * 360),
  };
}

function initPop() {
  cars = [];
  for (let i = 0; i < POP; i++) cars.push(spawnCar(randGenome()));
  elapsed = 0;
}

function init() {
  const n = Math.ceil(TLEN / SEG) + 1;
  terrain = new Float32Array(n);
  let h = 360;
  for (let i = 0; i < n; i++) {
    terrain[i] = h;
    if (i < 6) h += (Math.random() - 0.5) * 4;
    else h += (Math.random() - 0.5) * 70 + Math.sin(i * 0.3) * 4;
    if (h < 200) h = 200; if (h > 480) h = 480;
  }
  gen = 1; history = []; allBest = null; camX = 0;
  initPop();
}

function stepCar(car) {
  if (!car.alive) return;
  const g = car.g, ca = Math.cos(car.ang), sa = Math.sin(car.ang);
  // Wheel spring constraint to body anchors
  for (const w of [car.w1, car.w2]) {
    const ax = car.x + ca * w.ox - sa * w.oy;
    const ay = car.y + sa * w.ox + ca * w.oy;
    const dx = ax - w.x, dy = ay - w.y;
    const fx = dx * 600 - w.vx * 14, fy = dy * 600 - w.vy * 14;
    w.vx += fx * DT; w.vy += fy * DT + G * DT;
    w.x += w.vx * DT; w.y += w.vy * DT;
    car.vx -= fx * DT * 0.18; car.vy -= fy * DT * 0.18;
  }
  // Wheel-ground + drive
  let grounded = 0;
  const wheels = [[car.w1, g.r1], [car.w2, g.r2]];
  for (const [w, r] of wheels) {
    const gy = groundY(w.x);
    if (w.y + r > gy) {
      w.y = gy - r;
      if (w.vy > 0) w.vy = -w.vy * 0.05;
      w.vx *= 0.92;
      car.vx += r * 9 * DT;
      grounded++;
    }
  }
  car.vy += G * DT;
  car.x += car.vx * DT; car.y += car.vy * DT;
  // Orient body to wheel-axle line
  const la = Math.atan2(car.w2.y - car.w1.y, car.w2.x - car.w1.x);
  let da = la - car.ang;
  while (da > Math.PI) da -= 2 * Math.PI;
  while (da < -Math.PI) da += 2 * Math.PI;
  car.av += da * 30 * DT - car.av * 4 * DT;
  car.ang += car.av * DT;
  // Body vertices vs ground
  for (const p of g.v) {
    const vx = car.x + Math.cos(p.a + car.ang) * p.r;
    const vy = car.y + Math.sin(p.a + car.ang) * p.r;
    const gy = groundY(vx);
    if (vy > gy) {
      car.y -= (vy - gy) * 0.5;
      if (car.vy > 0) car.vy *= -0.3;
      car.vx *= 0.85;
      car.av += (Math.random() - 0.5) * 4;
    }
  }
  if (car.x > car.maxX) { car.maxX = car.x; car.fit = car.x - 60; car.stuck = 0; }
  else car.stuck += DT;
  if (car.stuck > 1.5 || car.x > TLEN - 200) car.alive = false;
  if (grounded === 0 && car.y > 480) car.alive = false;
}

function nextGen() {
  cars.sort((a, b) => b.fit - a.fit);
  if (!allBest || cars[0].fit > allBest.fit) allBest = { fit: cars[0].fit, g: cars[0].g };
  history.push(cars[0].fit);
  if (history.length > 120) history.shift();
  const surv = cars.slice(0, POP / 2).map(c => c.g);
  const next = [surv[0]];
  while (next.length < POP) {
    const a = surv[Math.floor(Math.random() * surv.length)];
    const b = surv[Math.floor(Math.random() * surv.length)];
    next.push(mutate(crossover(a, b)));
  }
  cars = next.map(spawnCar);
  elapsed = 0; gen++;
}

function drawCar(ctx, c, alpha) {
  const g = c.g;
  ctx.globalAlpha = alpha;
  ctx.fillStyle = `hsl(${c.hue},70%,55%)`;
  ctx.strokeStyle = `hsl(${c.hue},70%,80%)`;
  ctx.lineWidth = 1.5;
  ctx.beginPath();
  for (let i = 0; i < g.v.length; i++) {
    const p = g.v[i], vx = c.x + Math.cos(p.a + c.ang) * p.r, vy = c.y + Math.sin(p.a + c.ang) * p.r;
    if (i === 0) ctx.moveTo(vx, vy); else ctx.lineTo(vx, vy);
  }
  ctx.closePath(); ctx.fill(); ctx.stroke();
  ctx.fillStyle = "#1a1a22";
  for (const [w, r] of [[c.w1, g.r1], [c.w2, g.r2]]) {
    ctx.beginPath(); ctx.arc(w.x, w.y, r, 0, Math.PI * 2); ctx.fill(); ctx.stroke();
    const spin = (w.x * 0.05) % (Math.PI * 2);
    ctx.beginPath(); ctx.moveTo(w.x, w.y); ctx.lineTo(w.x + Math.cos(spin) * r * 0.8, w.y + Math.sin(spin) * r * 0.8); ctx.stroke();
  }
  ctx.globalAlpha = 1;
}

function tick({ ctx, dt, width, height }) {
  if (dt > 0.05) dt = 0.05;
  for (const c of cars) stepCar(c);
  elapsed += DT;
  let lead = cars[0];
  for (const c of cars) if (c.x > lead.x) lead = c;
  camX += (Math.max(0, lead.x - width * 0.35) - camX) * 0.06;
  if (elapsed >= TRIAL_T || cars.every(c => !c.alive)) nextGen();

  const arenaH = height - 110;
  const grad = ctx.createLinearGradient(0, 0, 0, arenaH);
  grad.addColorStop(0, "#0a1226"); grad.addColorStop(1, "#1a2440");
  ctx.fillStyle = grad; ctx.fillRect(0, 0, width, arenaH);

  ctx.save();
  ctx.beginPath(); ctx.rect(0, 0, width, arenaH); ctx.clip();
  ctx.translate(-camX, 0);
  ctx.strokeStyle = "rgba(120,140,170,0.18)";
  ctx.fillStyle = "rgba(160,180,210,0.5)";
  ctx.font = "10px monospace";
  const xL = Math.max(0, camX - 40), xR = Math.min(TLEN, camX + width + 40);
  for (let x = Math.floor(xL / 200) * 200; x < xR; x += 200) {
    ctx.beginPath(); ctx.moveTo(x, 0); ctx.lineTo(x, arenaH); ctx.stroke();
    ctx.fillText(x + "", x + 3, 12);
  }
  ctx.beginPath();
  ctx.moveTo(xL, arenaH);
  for (let x = xL; x <= xR; x += SEG) ctx.lineTo(x, groundY(x));
  ctx.lineTo(xR, arenaH); ctx.closePath();
  ctx.fillStyle = "#2a3a28"; ctx.fill();
  ctx.strokeStyle = "#6ab06a"; ctx.lineWidth = 1.5;
  ctx.beginPath();
  for (let x = xL; x <= xR; x += SEG) { if (x === xL) ctx.moveTo(x, groundY(x)); else ctx.lineTo(x, groundY(x)); }
  ctx.stroke();
  if (camX + width > TLEN - 220) {
    const fx = TLEN - 200, fy = groundY(fx);
    ctx.strokeStyle = "#fff"; ctx.beginPath(); ctx.moveTo(fx, fy); ctx.lineTo(fx, fy - 60); ctx.stroke();
    ctx.fillStyle = "#ff5a4a"; ctx.fillRect(fx, fy - 60, 24, 16);
  }
  for (const c of cars) drawCar(ctx, c, c.alive ? 1 : 0.25);
  ctx.restore();

  ctx.fillStyle = "#cfd6e0"; ctx.font = "13px monospace";
  ctx.fillText("Genetic Algorithm — Cars", 12, 20);
  ctx.font = "11px monospace"; ctx.fillStyle = "#9aa6bc";
  ctx.fillText(`gen ${gen}   t ${elapsed.toFixed(1)}s / ${TRIAL_T}s   pop ${POP}`, 12, 36);
  let aliveN = 0; for (const c of cars) if (c.alive) aliveN++;
  ctx.fillText(`alive ${aliveN}   lead ${lead.fit.toFixed(0)}px   best ${allBest ? allBest.fit.toFixed(0) : "—"}px`, 12, 50);

  const CY = height - 95, CH = 80, CX = 12, CW = width - 24;
  ctx.fillStyle = "rgba(10,14,26,0.8)"; ctx.fillRect(CX, CY, CW, CH);
  ctx.strokeStyle = "#2a3344"; ctx.strokeRect(CX, CY, CW, CH);
  ctx.fillStyle = "#6a7388"; ctx.font = "10px monospace";
  ctx.fillText("best fitness per generation", CX + 6, CY + 12);
  if (history.length > 1) {
    let hMax = 1; for (const v of history) if (v > hMax) hMax = v;
    ctx.strokeStyle = "#ffe680"; ctx.lineWidth = 1.5; ctx.beginPath();
    for (let i = 0; i < history.length; i++) {
      const px = CX + (i / Math.max(1, history.length - 1)) * (CW - 4) + 2;
      const py = CY + CH - 6 - (history[i] / hMax) * (CH - 20);
      if (i === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
    }
    ctx.stroke();
    ctx.fillStyle = "#ffe680"; ctx.fillText("max " + hMax.toFixed(0) + "px", CX + CW - 90, CY + 12);
  } else {
    ctx.fillStyle = "#6a7388"; ctx.fillText("waiting for gen 1 to finish…", CX + 6, CY + 28);
  }
}