foodmageddon/tests/marchingSquares.test.ts

import { describe, expect, it } from 'vitest';
import { CHUNK_SIZE } from '../src/shared/constants';
import { TerrainBitmap } from '../src/shared/terrain/bitmap';
import { extractContours, type Contour, type Point } from '../src/shared/terrain/marchingSquares';
import { simplifyContour, simplifyPolyline } from '../src/shared/terrain/simplify';
import { bitmapFrom } from './helpers';

const whole = (bm: TerrainBitmap): Contour[] => extractContours(bm, 0, 0, bm.width, bm.height);

/** Signed area (shoelace). With y down, solid-on-the-left loops have a consistent sign. */
function signedArea(points: Point[]): number {
  let a = 0;
  for (let i = 0; i < points.length; i++) {
    const p = points[i];
    const q = points[(i + 1) % points.length];
    a += p.x * q.y - q.x * p.y;
  }
  return a / 2;
}

describe('marching squares', () => {
  it('empty and full-interior regions produce no contour', () => {
    expect(whole(new TerrainBitmap(8, 8))).toEqual([]);
  });

  it('a single pixel yields a closed diamond around its center', () => {
    const contours = whole(bitmapFrom(['...', '.1.', '...']));
    expect(contours).toHaveLength(1);
    expect(contours[0].closed).toBe(true);
    expect(contours[0].points).toHaveLength(4);
    for (const p of contours[0].points) expect(Math.abs(p.x - 1.5) + Math.abs(p.y - 1.5)).toBeCloseTo(0.5);
  });

  it('a block yields one loop; a hole yields a second loop with opposite winding', () => {
    const solid = whole(bitmapFrom(['......', '.1111.', '.1111.', '.1111.', '......']));
    expect(solid).toHaveLength(1);
    const ring = whole(bitmapFrom(['.......', '.11111.', '.1...1.', '.1...1.', '.11111.', '.......']));
    expect(ring).toHaveLength(2);
    const areas = ring.map((c) => signedArea(c.points));
    expect(Math.sign(areas[0])).toBe(-Math.sign(areas[1]));
    expect(Math.sign(signedArea(solid[0].points))).toBe(Math.sign(Math.abs(areas[0]) > Math.abs(areas[1]) ? areas[0] : areas[1]));
  });

  it('solid touching the map border is closed by the border', () => {
    const contours = whole(bitmapFrom(['11', '11']));
    expect(contours).toHaveLength(1);
    expect(contours[0].closed).toBe(true);
  });

  it('diagonal pixels (saddle) stay disconnected, matching 4-connectivity', () => {
    const contours = whole(bitmapFrom(['....', '.1..', '..1.', '....']));
    expect(contours).toHaveLength(2);
  });

  it('chunk contours join exactly at chunk seams', () => {
    const w = CHUNK_SIZE * 2;
    const h = CHUNK_SIZE;
    const bm = new TerrainBitmap(w, h);
    for (let y = 20; y < 40; y++) for (let x = 40; x < 90; x++) bm.data[y * w + x] = 1;
    const left = extractContours(bm, 0, 0, CHUNK_SIZE, h);
    const right = extractContours(bm, CHUNK_SIZE, 0, w, h);
    expect(left.every((c) => !c.closed)).toBe(true);
    expect(right.every((c) => !c.closed)).toBe(true);
    const ends = (cs: Contour[]): string[] =>
      cs.flatMap((c) => [c.points[0], c.points[c.points.length - 1]]).map((p) => `${p.x},${p.y}`).sort();
    expect(ends(left)).toEqual(ends(right));
  });
});

describe('Douglas-Peucker', () => {
  it('collapses collinear points and keeps corners', () => {
    const line = Array.from({ length: 10 }, (_, i) => ({ x: i, y: 0 }));
    expect(simplifyPolyline(line, 0.5)).toEqual([line[0], line[9]]);
    const corner = [...line, { x: 9, y: 5 }];
    expect(simplifyPolyline(corner, 0.5)).toHaveLength(3);
  });

  it('simplifies a rectangle contour to its corners (plus the diagonal cut corners)', () => {
    const [loop] = whole(bitmapFrom(['..........', '.11111111.', '.11111111.', '.11111111.', '..........']));
    const simple = simplifyContour(loop, 0.8);
    expect(simple.closed).toBe(true);
    expect(simple.points.length).toBeLessThanOrEqual(8);
    expect(simple.points.length).toBeGreaterThanOrEqual(4);
  });
});