Mazes on Voronoi tessellations / Mark Seemann / Observable

// One iteration of the recursive backtracker algorithm

function recursiveBacktrack(grid, stack) {

  const current = stack[stack.length - 1];

  const neighbors = current.neighbors.filter(n => n.isUnlinked && sharedSideIsWideEnough(n, current, grid.voronoi));

  if (neighbors.length === 0) {

    stack.pop();

  } else {

    const neighbor = sample(neighbors);

    current.link(neighbor);

    stack.push(neighbor);

  }

}

xxxxxxxxxx

function sharedSideIsWideEnough(cell1, cell2, voronoi) {

  const poly1 = cell1.polygon(voronoi);

  const poly2 = cell2.polygon(voronoi);

  const sharedSide = commonPoints(poly1, poly2);

  const sideLength = lineLength(sharedSide);

  return minimumWidth <= sideLength;

}

xxxxxxxxxx

class Grid {

  constructor(points) {

    this.voronoi = new d3.Delaunay(points).voronoi([0, 0, width, height]);

    this.cells = Array.from({length: points.length / 2}, (_, i) => new Cell(i));

    for (const cell of this.cells) {

      const neighborIndices = this.voronoi.neighbors(cell.index);

      for (const idx of neighborIndices) {

        const neighbor = this.cells[idx];

        cell.neighbors.push(neighbor);

      }

    }

  }

}

xxxxxxxxxx

class Cell {

  constructor(index) {

    this.index = index;

    this.neighbors = [];

    this.links = [];

  }

  link(other) {

    this.links.push(other);

    other.links.push(this);

  }

  get isUnlinked() {

    return this.links.length === 0;

  }

  isLinkedTo(other) {

    return this.links.includes(other);

  }

  polygon(voronoi) {

    return voronoi.cellPolygon(this.index);

  }

}