Chapter 41

ランダムパッキング

miku
miku
2021.11.15に更新

ある物体の中に別の物体をどれだけ詰め込めるかを考えるパズルのようなものをパッキングと呼ぶ。この章では画面内に円や矩形をランダムに詰めていくパッキングについて扱う。

円のランダムパッキング

const r = 50;
let circles;

function setup() {
  createCanvas(windowWidth, windowHeight);

  circles = [];
}

function draw() {
  let x, y;

  let i = 0;
  do {
    x = random(width);
    y = random(height);

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y));

  circle(x, y, r * 2);
  circles.push({ x, y });
}

function check(x, y) {
  let ok = true;
  circles.forEach((c) => {
    if (dist(x, y, c.x, c.y) < r * 2) {
      ok = false;
    }
  });

  return ok;
}

ランダムな座標に円を配置していく。ただしすでに配置したどれかの円と衝突するようなら座標を変える。ある程度時間が経つと配置できない可能性のほうが高くなるので、ループ回数の上限を決めておく。

大きさを変える

let circles;
const maxR = 50;

function setup() {
  createCanvas(windowWidth, windowHeight);

  circles = [];
}

function draw() {
  let x, y;
  let r = 1;

  let i = 0;
  do {
    x = random(width);
    y = random(height);

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y, r));

  while (r < maxR && check(x, y, r)) {
    r++;
  }
  r--;

  circle(x, y, r * 2);
  circles.push({ x, y, r });
}

function check(x, y, r) {
  let ok = true;
  circles.forEach((c) => {
    if (dist(x, y, c.x, c.y) < r + c.r) {
      ok = false;
    }
  });

  return ok;
}

先程の作例に加えて、見栄えのために円の大きさを変える作例。

大きさを変える その2

let circles;
const maxR = 50;

function setup() {
  createCanvas(windowWidth, windowHeight);

  const x = width / 2;
  const y = height / 2;
  const r = 100;
  circles = [{ x, y, r }];
}

function draw() {
  let x, y;
  let r = 1;

  let i = 0;
  do {
    x = random(width);
    y = random(height);

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y, r));

  while (r < maxR && check(x, y, r)) {
    r++;
  }
  r--;

  circle(x, y, r * 2);
  circles.push({ x, y, r });
}

function check(x, y, r) {
  let ok = true;
  circles.forEach((c) => {
    if (dist(x, y, c.x, c.y) < r + c.r) {
      ok = false;
    }
  });

  return ok;
}

更に手を加えて、あえて中央部分だけ円状の穴を空ける作例。

メリハリを付ける

let circles;
function setup() {
  createCanvas(windowWidth, windowHeight);
  noStroke();

  const x = width / 2;
  const y = height / 2;
  const r = 100;
  circle(x, y, r * 2);
  circles = [{ x, y, r }];
}

function draw() {
  let x, y;
  let r = 1;

  let i = 0;
  do {
    x = random(width);
    y = random(height);

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y, r));

  while (check(x, y, r)) {
    r++;
  }
  r--;

  circle(x, y, r * 2);
  circles.push({ x, y, r });
}

function check(x, y, r) {
  let ok = true;
  circles.forEach((c) => {
    if (dist(x, y, c.x, c.y) < r + c.r) {
      ok = false;
    }
  });

  return ok;
}

まず1つの円を中央に配置する。その後に配置する円のサイズは他の円と衝突するまで半径を大きくする。

影を付ける

let circles;
const maxR = 50;

function setup() {
  createCanvas(windowWidth, windowHeight);

  circles = [];
}

function draw() {
  let x, y;
  let r = 1;

  let i = 0;
  do {
    x = random(width);
    y = random(height);

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y, r));

  while (r < maxR && check(x, y, r)) {
    r++;
  }
  r--;

 // 影を付ける
  drawingContext.shadowOffsetX = 5;
  drawingContext.shadowOffsetY = -5;
  drawingContext.shadowBlur = 10;
  drawingContext.shadowColor = "black";

  circle(x, y, r * 2);
  circles.push({ x, y, r });
}

function check(x, y, r) {
  let ok = true;
  circles.forEach((c) => {
    if (dist(x, y, c.x, c.y) < r + c.r) {
      ok = false;
    }
  });

  return ok;
}

演出の一例として、配置する円に影をつける作例。

矩形のランダムパッキング

const maxSize = 50;
let rects;

function setup() {
  createCanvas(windowWidth, windowHeight);
  rects = [];

  drawingContext.shadowOffsetX = 5;
  drawingContext.shadowOffsetY = -5;
  drawingContext.shadowBlur = 10;
  drawingContext.shadowColor = "black";
}

function draw() {
  let x, y;
  let size = 1;

  let i = 0;
  do {
    x = floor(random(width));
    y = floor(random(height));

    i++;
    if (i > 1000) {
      return;
    }
  } while (!check(x, y, size, size));

  while (size < maxSize && check(x, y, size, size)) {
    size++;
  }
  if (size > 1) {
    size--;
  }

  rect(x, y, size, size);
  rects.push({ x, y, w: size, h: size });
}

function check(x, y, w, h) {
  let ret = true;

  for (const r of rects) {
    const a = x + w - 1 >= r.x;
    const b = x <= r.x + r.w - 1;
    const c = y + h - 1 >= r.y;
    const d = y <= r.y + r.h - 1;

    if (a && b && c && d) {
      ret = false;
      break;
    }
  }

  return ret;
}

矩形のランダムパッキングの場合は、描画を矩形に変えて、衝突判定を矩形と矩形で考えればいい。

過程を見せる

const maxSize = 50;
let rects, x, y, size, init;

function setup() {
  createCanvas(windowWidth, windowHeight);
  rects = [];
  init = true;

  drawingContext.shadowOffsetX = 5;
  drawingContext.shadowOffsetY = -5;
  drawingContext.shadowBlur = 10;
  drawingContext.shadowColor = "black";
}

function draw() {
  if (init) {
    size = 1;
    let i = 0;
    do {
      x = floor(random(width));
      y = floor(random(height));

      i++;
      if (i > 1000) {
        return;
      }
    } while (!check(x, y, size, size));

    init = false;
  }

  size++;

  if (size >= maxSize || !check(x, y, size, size)) {
    rects.push({ x, y, w: size, h: size });
    init = true;
    return;
  }

  clear();
  rect(x, y, size, size);
  for (const r of rects) {
    rect(r.x, r.y, r.w, r.h);
  }
}

function check(x, y, w, h) {
  let ret = true;

  for (const r of rects) {
    const a = x + w - 1 >= r.x;
    const b = x <= r.x + r.w - 1;
    const c = y + h - 1 >= r.y;
    const d = y <= r.y + r.h - 1;

    if (a && b && c && d) {
      ret = false;
      break;
    }
  }

  return ret;
}

衝突したら描画するのではなく、毎フレーム矩形が大きくなる過程を描画していく作例。