Goals

• Space Filling
  • Concept
  • Steps
  • Result
• Smart Grids
  • Concept
  • Steps
  • Result

Resources

Procedural Space Filling
Procedural Smart Grids

Space Filling - Concept

Take a look at this image. Notice how each circle takes up space without overlapping? They also know who their closest neighbor is and draw a line to them.

The main idea here is to make "smart" decisions, before randomly placing objects on the screen. Let's take a look at how we do this:

Steps

First we need a plan to find out how this is going to work, so let's make some steps:

• Make a new Circle object
• Place it randomly with radius 1
• Check if it overlaps with any other
  • If it does we won't do anything
  • If it does not continue
• Find the closest neighbor to the new circle
• Keep setting the radius until we can't find a smaller one (best fit)
• Add the circle to the list

There are two important steps in this guide: detecting an intersection, and finding the closest neighbor.

Detecting an Intersection:

boolean hasIntersectionWith(Circle other) { float distance = dist(other.props.x, other.props.y, props.x, props.y); if (distance < (other.props.z + props.z)) { return true; } return false; }

Here it's a simple collision detection, is the distance between these two circle objects less than the sum of their radii?

Finding the Closest Neighbor:

void findClosestNeighbor(Circle other) { float distance = dist(other.props.x, other.props.y, props.x, props.y); if (props.z > distance - other.props.z) { props.z = distance - other.props.z; neighbor = other.id; } }

In this method, we're taking a look to see if the radius of our new circle it too big to fit next to the other circle we're currently checking. If it is, we will set the radius of the new circle to be exactly the distance between them minus the other circle's radius. We'll also update the neighbor field to the id of the other circle. This loop will keep going until the closest fit is found.

This is actually an example of a classic problem in programming, finding the minimum value that will work. Each step in the loop, the radius of the new circle might get smaller and smaller, until finally, after checking all the other circles, it can't possibly be any smaller, so it must be fitting perfectly to the last circle that it was checked with. This is now the new circle's neighbor.

Result

ArrayList<Circle> circles = new ArrayList<Circle>(); int mouseRect = 30; int maxRadius = 50; int minRadius = 4; void setup() { size(900, 600); smooth(); //add the first circle circles.add( new Circle( 0, 0, new PVector( random(width), random(height), random(20, 100) ) ) ); } void draw() { background(255); //random new position Circle newCircle = new Circle(circles.size(), circles.size(), new PVector( random(0+maxRadius, width-maxRadius), random(0+maxRadius, height-maxRadius), minRadius) ); //if the mouse is pressed put the new circle here if (mousePressed == true) { newCircle.props.x = random(mouseX-mouseRect/2, mouseX+mouseRect/2); newCircle.props.y = random(mouseY-mouseRect/2, mouseY+mouseRect/2); newCircle.props.z = 1; } //find out if new circle intersects with one of the others boolean intersection = false; for (int i=0; i < circles.size(); i++) { Circle current = circles.get(i); intersection = current.hasIntersectionWith( newCircle ); if (intersection) { break; //stop looping if we've already hit another circle } } //if there's no intersection, find the closest neighbor if (!intersection) { newCircle.props.z = width; for (int i=0; i < circles.size(); i++) { Circle current = circles.get(i); newCircle.findClosestNeighbor( current ); } //make sure we're not too big if (newCircle.props.z > maxRadius) newCircle.props.z = maxRadius; //add the new circle circles.add( newCircle ); } //draw circles for (int i=0; i < circles.size(); i++) { Circle current = circles.get(i); current.drawCircle(); } //draw lines for (int i=0; i < circles.size(); i++) { Circle current = circles.get(i); current.drawLine(); } } //a circle class to store our info class Circle { int id; int neighbor; PVector props; color c; Circle(int id, int neighbor, PVector props) { this.id = id; this.neighbor = neighbor; this. props = props; c = color(0, random(128), random(128, 255), 64); } //checks intersection returns true or false boolean hasIntersectionWith(Circle other) { float distance = dist(other.props.x, other.props.y, props.x, props.y); if (distance < (other.props.z + props.z)) { return true; } return false; } //finds the closest neighbor void findClosestNeighbor(Circle other) { float distance = dist(other.props.x, other.props.y, props.x, props.y); if (props.z > distance - other.props.z) { props.z = distance - other.props.z; neighbor = other.id; } } void drawCircle() { fill(c); noStroke(); pushMatrix(); translate(props.x, props.y); ellipse(0, 0, props.z * 2, props.z * 2); popMatrix(); } void drawLine() { strokeWeight(2); stroke(220); line(props.x, props.y, circles.get(neighbor).props.x, circles.get(neighbor).props.y); } }

Smart Grids - Concept

Take a look at this grid? There's a special relationship between each cell containing a shape. The relationship is calculated using a formula to decide which piece should be at which tile.

The formula is based on a binary number that is constructed from the east, south, west, and north neighbors of the current tile. If a neighbor is on, it has a value of '1', if it is off it has a value of '0'.

The binary number is laid out like this: north + west + south + east.

Which constructs a number something like 1101.

Converting this number to a decimal will give us the index of the shape in the list of grid shapes that we need for this specific tile.

So it's simply a clever way to encode and organize shapes based on the information of neighboring tiles. The formula can easily be constructed and the correct shape is always selected.

Steps

Let's take a look at the plan:

• Build a grid of objects
• Allow objects to be turned on (value = 1)
• Loop over entire grid and decide on shape:
  • Find east, south, west, north neighbor values
  • Put them in a string: north + west + south + east
  • Convert this number to a decimal number
  • Use number as shape index to select correct shape from shapes array
• Draw shapes

There is one crucial step here:

Calculating the formula:

void drawModules() { for (int gridY=1; gridY< gridResolutionY-1; gridY++) { for (int gridX=1; gridX< gridResolutionX-1; gridX++) { //get current tile Tile tile = tiles[gridX][gridY]; //use only active tiles if (tile.value == '1') { // check the four neighbours, each can be 0 or 1 String east = str(tiles[gridX+1][gridY].value); String south = str(tiles[gridX][gridY+1].value); String west = str(tiles[gridX-1][gridY].value); String north = str(tiles[gridX][gridY-1].value); // create a binary result out of it, eg. 1011 String binaryResult = north + west + south + east; //pass the result to the object to select and draw it's shape tile.drawModule(binaryResult); } } } }

The binaryResult is passed the the draw module method of the shape which handles converting it to a decimal. Once it's in decimal form, it's a number between 0 and 15 since it has 4 binary digits.

This is because, each digit represents a choice between 0 and 1, which is a bit of information.

Since we have 4 bits of information, we can make 4 choices of 0 and 1. (4 choices of 2 choices)

That means: 2 x 2 x 2 x 2 = 16, or 2^4, or 0-15 total possibilities.

Now we choose our shape from these shapes using the decimal number as an index into the array.

Shapes are 0-15 left to right, top to bottom.

Result