Genuary 2025 day 21

// By Roni Kaufman

// https://ronikaufman.github.io

​

// Made for Genuary 2025

// Day 21: Create a collision detection system (no libraries allowed).

​

let margin = 3;

let N = 22;

let maxSize = 5;

let u, gap = 0;

​

let rectangles = [];

​

let randInt = (a, b) => (floor(random(a, b))); 

​

function setup() {

  createCanvas(600, 600);

  pixelDensity(2);

  strokeWeight(2);

  noLoop();

  u = width/N;

  createComposition();

  createConnections();

  DSatur("col", ["#2b67af", "#f9d531", "#ef562f", "#29ac9f", "#f589a3"], true);

}

​

function draw() {

  background(5);

  noStroke();

  for (let recta of rectangles) {

    drawRectangle(recta);

  }

  stroke("#fffbe6");

  for (let recta of rectangles) {

    drawConnections(recta);

  }

}

​

// creating the composition

​

function createComposition() {

  let nRects = 1000;

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

    let newRecta = generateRectangle(rectangles);

    if (newRecta.si > 1 || newRecta.sj > 1) {

      rectangles.push(newRecta);

    }

  }

  // fill the gaps with 1x1 rectangles

  for (let i = margin; i < N-margin; i++) {

    for (let j = margin; j < N-margin; j++) {

      let newRecta = {

        i: i,

        j: j,

        si: 1,

        sj: 1

      }

      let canAdd = true;

      for (let recta of rectangles) {

        if (rectanglesIntersect(newRecta, recta)) {

          canAdd = false;

          break;

        }

      }

      if (canAdd) {

        rectangles.push(newRecta);

      }

    }

  }

}

​

function rectanglesIntersect(recta1, recta2) {

  return ((recta1.i <= recta2.i && recta1.i+recta1.si > recta2.i) || (recta2.i <= recta1.i && recta2.i+recta2.si > recta1.i)) && ((recta1.j <= recta2.j && recta1.j+recta1.sj > recta2.j) || (recta2.j <= recta1.j && recta2.j+recta2.sj > recta1.j));

}

​

function generateRectangle(rectangles) {

  let i = randInt(margin, N-margin);

  let j = randInt(margin, N-margin);

  // determine biggest possible size

  let s = 0;

  if (rectangles.length == 0) {

    s = min(maxSize, N-i-margin-1, N-j-margin-1);

  } else {

    let intersects = false;

    while (!intersects) {

      s++;

      for (let recta of rectangles) {

        if (i+s > N-margin || j+s > N-margin || s > maxSize || rectanglesIntersect({i: i, j: j, si: s, sj: s}, recta)) {

          intersects = true;

          break;

        }

      }

    }

    s--;

  }

  let si = s, sj = s;

  let recta = {

    i: i,

    j: j,

    si: si,

    sj: sj

  };

  return recta;

}

​

// creating the graph

​

function createConnections() {

  let l = rectangles.length;

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

    let recta1 = rectangles[i];

    if (!recta1.neighbors) recta1.neighbors = [];

    for (let j = 0; j < l; j++) {

      let recta2 = rectangles[j];

      if (!recta2.neighbors) recta2.neighbors = [];

      if (i != j && rectanglesTouch(recta1, recta2)) {

        recta1.neighbors.push(recta2);

        //recta2.neighbors.push(recta1);

      }

    }

  }

}

​

function rectanglesTouch(recta1, recta2) {

  if (((recta1.i <= recta2.i && recta1.i+recta1.si == recta2.i) || (recta2.i <= recta1.i && recta2.i+recta2.si == recta1.i)) && ((recta1.j <= recta2.j && recta1.j+recta1.sj > recta2.j) || (recta2.j <= recta1.j && recta2.j+recta2.sj > recta1.j)))

    return true;

  if (((recta1.i <= recta2.i && recta1.i+recta1.si > recta2.i) || (recta2.i <= recta1.i && recta2.i+recta2.si > recta1.i)) && ((recta1.j <= recta2.j && recta1.j+recta1.sj == recta2.j) || (recta2.j <= recta1.j && recta2.j+recta2.sj == recta1.j)))

    return true;

  return false;

}

​

// coloring the graph

​

function DSatur(el, elements, shuffleIt) {

  // from https://en.wikipedia.org/wiki/DSatur

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

    // step 1

    let v, vSat = -1, vElementsUsed;

    for (let recta of rectangles) {

      if (!recta[el]) {

        let elementsUsed = elementsUsedByNeighbors(recta, el);

        let sat = elementsUsed.length;

        if (sat > vSat) {

          v = recta;

          vSat = sat;

          vElementsUsed = elementsUsed;

        } else if (sat == vSat) {

          if (largestDegreeInTheSubgraphInducedByTheUncoloredVertices(recta, el) > largestDegreeInTheSubgraphInducedByTheUncoloredVertices(v, el)) {

            v = recta;

            vSat = sat;

            vElementsUsed = elementsUsed;

          }

        }

      }

    }

​

    // step2

    shuffle(elements, shuffleIt);

    for (let element of elements) {

      if (vElementsUsed.indexOf(element) == -1) {

        v[el] = element;

        break;

      }

    }

  }

}

​

function elementsUsedByNeighbors(v, el) {

  let elementsUsed = [];

  for (let neigh of v.neighbors) {

    if (neigh[el]) elementsUsed.push(neigh[el]);

  }

  return [...new Set(elementsUsed)];

}

​

function largestDegreeInTheSubgraphInducedByTheUncoloredVertices(v, el) {

  let largestDegree = -1;

  for (let neigh of v.neighbors) {

    if (!neigh[el]) {

      let sat = elementsUsedByNeighbors(neigh, el);

      if (sat > largestDegree) largestDegree = sat;

    }

  }

  return largestDegree;

}

​

// drawing

​

function drawRectangle(recta) {

  let x = recta.i*u + gap/2, y = recta.j*u + gap/2;

  let w = recta.si*u - gap, h = recta.sj*u - gap;

  fill(recta.col);

  circle(x+w/2, y+h/2, w);

}

​

function drawConnections(recta1) {

  let x1 = recta1.i*u + recta1.si*u/2, y1 = recta1.j*u + recta1.sj*u/2;

  for (let recta2 of recta1.neighbors) {

    let x2 = recta2.i*u + recta2.si*u/2, y2 = recta2.j*u + recta2.sj*u/2;

    line(x1, y1, x2, y2);

  }

}