In my
previous post
, we came up with a program to generate a single 8-armed component of the aah tangle. In this post, we’ll figure out how to spread them randomly around the canvas, as in the image at the top of the post. We’ll use the program from the last post as a starting point.
As a first try, let’s just generate a draw 20 aah images randomly on the canvas. Our draw() function looks like this:
function draw() {
for (i=0; i<20; ++i) {
const aah = newAah(sizeAah, [random(0, width), random(0, height)]);
drawAah(aah);
}
noLoop();
}
Not shown above, we also change the value of sizeAah from 400 to 100 so that more would fit on the canvas. This is the result:
As you can see, we didn’t get very good coverage of the canvas, and many of the aah images overlap. We don’t necessarily want perfect coverage of the canvas, but better would be nice, and we definitely don’t want any aah touching its neighbors. How do we fix this? The answer is collision detection.
Collision detection is a complicated subject, fully understandable only by people better at math than I. If you’d like to dive down the rabbit hole, Jeffrey Thompson has written up an excellent explanation of the subject with examples of how to figure out things like whether a point is on a line, whether a line crosses a circle (or a triangle or a rectangle), etc. There are examples in a programming language called Processing . If you want to learn more, this is definitely the place to start.
We aren’t using Processing; we are using Javascript, along with the p5.js library which provides many of Processing’s capabilities. Happily, Ben Moran has painstakingly gone through that documentation, converting all the Processing examples into Javascript. The result is the p5.collide2d library , which we will use in this project.
If you are following along running this program as we modify it, you will need to include this library. You do this not by changing the Javascript file, but by changing the index.html file that loads the javascript into your browser. You need to add the line <script src="https://cdn.jsdelivr.net/npm/p5.collide2d"></script>. The index.html file should look something like this:
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.10.2/p5.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.10.2/addons/p5.sound.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/p5.collide2d"></script>
<link rel="stylesheet" type="text/css" href="style.css">
<meta charset="utf-8" />
</head>
<body>
<script src="sketch.js"></script>
</body>
</html>
So how do we use this library to find out whether two aah images touch? There is a function, collidePolyPoly(), which tests whether two polygons have collided. To use it, we just have to draw a polygon around each aah image, and compare each to the others using collidePolyPoly(). To do this, we’ll first modify newAah() to define an enclosing polygon.
function newAah(size, [x, y]) {
if (x === undefined) x = 0;
if (y === undefined) y = 0;
if (size === undefined) size = 100;
let aah = {
length: size/2, // Expected length of each arfterm in pixels
lengthSD: 0, // Standard deviation of arm length
thetaSD: 2, // Standard deviation of arm angle
arms: [], // Array of arms
poly: [], // Enclosing polygon
};
aah.lengthSD = (0.05 + 0.05 * random()) * aah.length;
const rotation = random(0, 45);
for (let angle=0; angle<360; angle+=45) {
const theta = randomGaussian(angle+rotation, aah.thetaSD);
const r = randomGaussian(aah.length, aah.lengthSD);
const gap = (0.05 + 0.05 * random()) * aah.length;
let arm = {
start: [], // Draw line from here...
stop: [], // ...to here
tipDiameter: gap, // The tip diameter is the same as the gap for each line
};
arm.start = toCartesian(gap, theta, [x, y]);
arm.stop = toCartesian(r, theta, [x, y]);
aah.arms.push(arm);
let vert = toCartesian(r + 5*gap, theta, [x, y]); // Put a vertex out beyond the tip of the arm
aah.poly.push(createVector(vert[0], vert[1]));
}
return aah;
}
The change here is that we have defined a new component of the aah data structure called poly, which is a list of vertices for the enclosing polygon. Then, after we create each arm of the aah, we also create a new vertex. We’ll create the vertex a bit further out than the end of the arm; here we are using 5 times the gap size. Changing this distance will vary how close two aah images can get.
Normally we won’t actually draw this polygon on the canvas, but it’s useful to do so while we are working on this so we can see what is happening. To do so, we can add this code the end of the drawAah() function:
fill(128,0,0,128);
beginShape();
for(i=0; i < aah.poly.length; i++){
vertex(aah.poly[i].x, aah.poly[i].y);
}
endShape(CLOSE);
This will draw the polygon in red over the aah image. Since we make it partially transparent (the 4th parameter to the fill() function), we can still see the aah underneath it.
Going back to the original draw() function that only draws one aah, we get this:
That’s all well and fine, but while we don’t want two aah images to get too close, we don’t mind if the arm of one goes between the arms of another. So we can modify our polygon from an octogon to an 8-pointed star. Whenever we create a vertex for the polygon, we create another that is 22 degrees further ahead (about halfway to the next arm) and is roughly 60% as far from the center at the arm is long. As with many of our decisions, these exact values are completely arbitrary and are chosen for pleasing results. Feel free to modify them to see what happens.
This is the change needed to add the 2nd vertex. Put this at the bottom of the loop in newAah():
vert = toCartesian(0.6*r, theta+22, [x, y]); // Put a 2nd vertex about halfway to the next arm
aah.poly.push(createVector(vert[0], vert[1]));
Now our polygon looks like this:
We will allow another aah image anywhere on the canvas as long as it’s polygon doesn’t touch this image’s polygon. And a third is long as it’s polygon doesn’t touch the polygons of the first two, etc. We can create new aah images with newAah() and check for collisions before we draw them with drawAah().
Now we have another issue. If we specify a number of aah images to put on the canvas, we may not get that many because of collisions, even though there may be room for them. On the other hand, if we specify more than could fit on the page, we have to be careful of an infinite loop when the program keeps trying to add aah images to the canvas forever even though no more will fit.
We can deal with this by keeping track of how many images we have drawn, and also how many we have failed to draw. We can stop drawing when we reach the number we asked for or if the number of failures exceed a certain threshold. Then we can safely ask for a number somewhat above what will fit to try to get as many on the page as possible. To do this we’ll create a drawAahs() to cover an area with aah images.
function drawAahs(n, size, box) {
const margin = sizeAah/6;
let polys = [];
let drawCount = 0;
let failCount = 0;
while(drawCount < n) {
const x = random(margin, box.width-margin); // Random (x,y) for our aah, within margins
const y = random(margin, box.height-margin);
const sizeSD = 0.15 * size;
const aah = newAah(randomGaussian(size, sizeSD), [x, y]);
let conflict = false;
for (let i=0; i<polys.length; ++i) {
if(collidePolyPoly(aah.poly, polys[i], true)) {
conflict = true;
break;
}
}
if(conflict) {
++failCount;
if(failCount > n*3) {
break;
}
} else {
polys.push(aah.poly);
drawAah(aah);
++drawCount;
}
}
return drawCount;
}
This function accepts three parameters:
n– The desired number ofaahimagessize– the approximate size of eachaahimagebox– The area where these should be drawn. This is itself an object with four components:x,y,widthandheight, which define an area on the canvas on which to draw.
Inside the function, we’ll set a margin. While we don’t mind if an aah extends past the box, we don’t want the center of the aah to be too close to the boundary. Here we set the margin to a sixth of the size of the aah.
We declare a polys variable to hold polygons of any aah images we actually draw. We’ll use this list to compare against new aah candidates. Then we declare drawCount and failCount variables to keep track of how many images we have added, and how many we have failed to add.
The loop is where all the interesting stuff happens. There we randomly select an (x,y) point, then create a new aah at that location with a slight random size variation. We then loop through all the polygons in the poly array to see if our new aah infringes on any existing ones. If there is a conflict, we up the failCount, and if there have been more failures than three times the requested number of aah images, we assume we can’t fit any more and exit the loop entirely. If we didn’t get a conflict, we draw the aah, up the drawCount and go back to the top of the loop to try to add another, assuming we don’t already have as many as we want.
We call drawAahs() from the draw() function. Now we get something that looks like this:
Removing the code from drawAah() which displays the polygon, we get our final result:
This is the complete final program:
// Canvas size
const height = 600;
const width = 600;
const sizeAah = 100; // Approximate size of each AAH
function setup() {
createCanvas(width, height);
background(240);
}
function draw() {
drawAahs(100, sizeAah, {x: 0, y: 0, width: width, height: height});
noLoop();
}
function toCartesian(r, theta, [x, y]) {
angleMode(DEGREES);
p = [r * cos(theta), r * sin(theta)];
if (x != undefined) p[0] += x;
if (y != undefined) p[1] += y;
return p
}
function newAah(size, [x, y]) {
if (x === undefined) x = 0;
if (y === undefined) y = 0;
if (size === undefined) size = 100;
let aah = {
length: size/2, // Expected length of each arm in pixels
lengthSD: 0, // Standard deviation of arm length
thetaSD: 2, // Standard deviation of arm angle
arms: [], // Array of arms
poly: [], // Enclosing polygon
};
aah.lengthSD = (0.05 + 0.05 * random()) * aah.length;
const rotation = random(0, 45);
for (let angle=0; angle<360; angle+=45) {
const theta = randomGaussian(angle+rotation, aah.thetaSD);
const r = randomGaussian(aah.length, aah.lengthSD);
const gap = (0.05 + 0.05 * random()) * aah.length;
let arm = {
start: [], // Draw line from here...
stop: [], // ...to here
tipDiameter: gap, // The tip diameter is the same as the gap for each line
};
arm.start = toCartesian(gap, theta, [x, y]);
arm.stop = toCartesian(r, theta, [x, y]);
aah.arms.push(arm);
let vert = toCartesian(r + 5*gap, theta, [x, y]); // Put a vertex out beyond the tip of the arm
aah.poly.push(createVector(vert[0], vert[1]));
vert = toCartesian(0.6*r, theta+22, [x, y]); // Put a 2nd vertex about halfway to the next arm
aah.poly.push(createVector(vert[0], vert[1]));
}
return aah;
}
function drawAah(aah) {
fill(0, 0, 0);
stroke(0, 0, 0);
aah.arms.forEach(arm => {
line(arm.start[0], arm.start[1], arm.stop[0], arm.stop[1]);
circle(arm.stop[0], arm.stop[1], arm.tipDiameter);
});
}
function drawAahs(n, size, box) {
const margin = sizeAah/6;
let polys = [];
let drawCount = 0;
let failCount = 0;
while(drawCount < n) {
const x = random(margin, box.width-margin); // Random (x,y) for our aah, within margins
const y = random(margin, box.height-margin);
const sizeSD = 0.15 * size;
const aah = newAah(randomGaussian(size, sizeSD), [x, y]);
let conflict = false;
for (let i=0; i<polys.length; ++i) {
if(collidePolyPoly(aah.poly, polys[i], true)) {
conflict = true;
break;
}
}
if(conflict) {
++failCount;
if(failCount > n*3) {
break;
}
} else {
polys.push(aah.poly);
drawAah(aah);
++drawCount;
}
}
return drawCount;
}
Tandika’s aah step-out shows there should also be some small circles in the spaces between the aah images. See figures 3 and 4 of the step-out.
We’ll save that for some future post. For now, have fun playing with this program! Feel free to make some changes to see what happens.