Space (and time) filling game-like sketch

While tinkering on another project, I was inspired by the circle-packing theorem to make this “puzzle-like” sketch. (generally: packing problems)

The goal is to cover as much suface as possible with the least number of circles.
There are no win/loss conditions, however.
It is theoretically possible to fill the entire window but there is no zoom feature… :stuck_out_tongue:

Instructions (also displayed)

  • Drag left mouse button to create a circle.
  • Right click a circle to remove it.
  • Press ‘a’ to toggle auto-size of created circles.
  • Press space bar twice to reset.


import java.util.HashMap;
import java.util.Set;

float DEFAULT_RADIUS = 10;
int BACKGROUND_COLOR = color(222);
int BALL_COLOR = color(255);

HashMap<Integer, Ball> hs = new HashMap<Integer, Ball>();

PGraphics mouseMap; // used for mouse "pointing"

boolean beginClear = false;
boolean autoSize = false;

boolean placement = false;
float startx = 0;
float starty = 0;
int idcounter = 1000;


void setup()
{
  size(1024,768);
  noSmooth();
  
  mouseMap = createGraphics(width,height);
  mouseMap.noStroke();
  mouseMap.beginDraw();
  mouseMap.background(255);
  mouseMap.endDraw();
  
  fill(240);
  noStroke();
  frameRate(30);
}


void mousePressed()
{
  if (LEFT == mouseButton)
  {
    placement = true;
    startx = mouseX;
    starty = mouseY;
  }
}


void mouseReleased()
{
  if (LEFT == mouseButton)
  {
    if (placement)
    {
      // Function checks radius against window bounds and other circles
      float checkdist = 100000000;
      Set<Integer> s = hs.keySet();
      for (Integer i : s)
      {
        Ball b = hs.get(i);
        if (placement)
        {
          float d = dist(startx,starty, b.x,b.y) - b.r;
          checkdist = min(checkdist, d);
        }
      }
    
      float tr = min(startx, width-startx);
      float r = tr;
      tr = min(starty, height-starty);
      r = min(r, tr);
      r = min(r, checkdist);
      
      if (!autoSize)
      {
        float dr = max(DEFAULT_RADIUS, dist(mouseX,mouseY, startx,starty));
        r = min(r,  dr);
      }
      
      int idx = idcounter++;
      hs.put(idx, new Ball(startx, starty, r, idx));
      placement = false;
    }
  }
  else if (RIGHT == mouseButton)
  {
    int idx = mouseMap.get(mouseX, mouseY) & 0xFFFFFF;
    hs.remove(idx);
  }
}


void keyReleased()
{
  if (' ' == key)
  {
    if (!beginClear)
    {
      beginClear = true;
    }
    else
    {
      hs.clear();
      beginClear = false;
    }
  }
  else if ('a' == key)
  {
    autoSize = !autoSize;
  }
}


void draw()
{
  background(BACKGROUND_COLOR);
  
  int tst = mouseMap.get(mouseX, mouseY) & 0xFFFFFF;
  float checkdist = 100000000;
  float surfaceArea = 0;
  
  mouseMap.beginDraw();
  mouseMap.background(255);
  Set<Integer> s = hs.keySet();
  for (Integer i : s)
  {
    Ball b = hs.get(i);
    surfaceArea += b.r*b.r*PI;
    
    if (placement)
    {
      float d = dist(startx,starty, b.x,b.y) - b.r;
      checkdist = min(checkdist, d);
    }
    
    if (tst == b.ID)
    {
      stroke(0,255,0);
    }
    else
    {
      noStroke();
    }
    
    fill(BALL_COLOR);
    ellipse(b.x,b.y, 2*b.r,2*b.r);
    
    mouseMap.fill(0xFF000000 | b.ID);
    mouseMap.ellipse(b.x,b.y, 2*b.r,2*b.r);
  }
  mouseMap.endDraw();
  
  if (placement)
  {
    stroke(0,0,255);
    float r = dist(mouseX,mouseY, startx,starty);
    
    float tr = min(startx, width-startx);
    r = min(r, tr);
    tr = min(starty, height-starty);
    r = min(r, tr);
    r = min(r, checkdist);
    
    fill(BALL_COLOR);
    ellipse(startx,starty, 2*r,2*r);
  }
  
  fill(0);
  float total = width*height;
  float covered = (100*surfaceArea/total);
  int n = hs.size();
  
  text("circle count (n): " + n + "\ncoverage: " + covered + " %\nauto size ('a' to toggle): " + autoSize, 40, 100);
  text("Drag left-mouse to add a circle\nRight-click to remove\nTap 'space bar' twice to reset", 40, 40);
}


class Ball
{
  float x=0, y=0, r=1;
  int ID = -1;
  
  Ball(float px, float py, float rad, int id)
  {
    x = px;
    y = py;
    r = rad;
    ID = id;
  }
}
4 Likes

Thanks so much for sharing this!

In theory it is not possible, right? Even an infinite number of circles will never fill a rectangle in theory… Could one turn every pixel white?

@jeremydouglass You are right, you could not really fill a given surface with a finite number of circles.
However, I only have so many pixels on my monitor. :grin:

True, “I couldn’t in theory but I DID in practice” is still quite an accomplishment!