9.8: Random Circles with No Overlap - p5.js Tutorial
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2024
- This video demonstrates a "circle packing"-like algorithm. Circles are placed randomly in the canvas, but only if they are not overlapping with any previous circles. This is referred to as "uniform random sampling." The p5.js dist() function is demonstrated.
Source-code: github.com/Cod...
Contact: / shiffman
All JavaScript/p5.js videos: www.youtube.co...
Help us caption & translate this video!
amara.org/v/Qbt2/
📄 Code of Conduct: github.com/Cod...
I'm glad I found your channel, as an amateur noob coder, this helps me see more ways to solve things, and evolve a much more flexible logic. Thanks!
"Who's watching this still?!"
Me! Don't stop! :D
Seriously, don't ever change, you are incredibly fun to watch, and you really make this fun to learn :)
Thanks for the nice feedback!
what if i wanted specifically sized circles to randomly be arranged and not touch?
Just set r to the specific circle size you want, instead of random. He does that all the way through the video with r: 32 until 18:03 where he changes the radius from specific size to random size.
Why not changing circle radius? You already iterate through all the circles, so if you find overlapping, just change the radius so it won't :)
*facepalm*
before I saw this vid, I checked if 2 circles are overlapping by comparing EACH circle on a seperate line...
dist circle 1 with 2
dist circle 1 with 3
dist circle 1 with 4
...
dist circle 2 with 3
dist circle 2 with 4 ...and so on :D
if you want to be absolutely sure that it does what you want, why not xD
You are amazing at teaching, seriously one of the best on this platform.
He has a lecture, so he is probably not only a good teach on this platform but also in the classroom.
Also he is really good to motivate, I always left his videos wanting to code something myself
6 years later comment still is valid. I’ve found this channel like last week and I’ve been binge watching it like it’s Breaking Bad
"Is anyone even watching this?"
73,380 views...
Yet another good tutorial.
P.S... please don't abandon Processing
+Robert Coyle never!
Daniel Shiffman Can you please make more videos on Processing...
This is cool - it teaches the basic and necassary stuff in programming, but with an interesting problem.
So glad to hear!
I thought it was funny how you didn't show yourself correcting the accidental "i" in --> for( var j = 0; j < circles.length; *i*++) ;)
I used this tutorial in a game where I needed to randomly place planets without them overlapping :D
***** I dont worry about optimizing it, becouse it only happens once when you load the game
I learned to think like that the hard way. I've wasted so much time trying to optimize code that isn't a bottleneck.
That is indeed a very important aspect of programming ^^
"Who's still watching this??" me):
and me :p
Jarmahent me too!
I am also on the "me-train"
and me
Daniel, these videos are absolutely amazing and sadly underated. You deserve WAY more views.
I enjoy every one you upload, and thoroughly thank you! Keep it up! :)
Wouldn't it be better to start with a certain radius. Place as many circles as possible, and when you cant place any anymore decrease the radius by 1, and repeat the process, until the radius is 0, then stop the loop. That would give you as much circles with the biggest size as possibly fit on the screen,right?
YourNightmar3 this is still a brute force approach. After how many iterations are you determining you can't fit anymore circles on the screen? It may just be that there is a spot to fill with that radius length, but the computer hasn't found it yet. Although an interesting proposal, I think random radius lengths from the get-go would still be faster
Daniel Alarcon it'll be faster but it definitely will not fill every spot on the screen.
Ah, well if that's your goal then you have a brilliant proposal. It would be cool if you updated Daniel Schiffman's code with your idea!
Yep, that would slightly optimize the program.
Daniel Alarcon Haha i can't code javascript :D
It's very inefficient. For n circles the complexity of your algorithm will be n^2. Soo bad. Dividing area into a grid of width 'maxradius' and storing only info about circles that overlapse each field of this grid would give you compexity of n.
The idea is simple: create an array[width/maxradius][height/maxradius]. For each circle store its position in those cells of array that this circle is overlapping (you can store it as a linked list). When searching for collisions you have to check no more than 9 cells (9 lists). For example: maxradius=10, Width=1000, Height=1000. You will get an array[100][100]. For circle at (252,503), radius=7 you store it's position in cells: [24][49], [25][49], [24][50], [25][50] since it it stretched from (245,496)* to (259,510)*
*actually a little bit less, but it doesn't matter.
I used the idea and made a water droplet filter. Thanks for the inspiration
oh, would love to see!
I am blind or is this video's source code missing on github?
you are not blind! I need to re-organize anad make things easier to find github.com/CodingTrain/website/tree/master/Tutorials/P5JS/p5.js/09
wow. i love this!
i don't understand it all, but that's ok.
or if circles are overlapping you can just write "i--;" !
This is unbelievably smart, thank you!
write it where?
In the first if of the second for loop if i remember correctly , it was 2 years ago ^^
@@alvan5416 oh didnt realise lol ty for the reply
I do watch your videos sir.
I'm a new subscriber btw and I really enjoy your videos!
Keep it up! ;)
+3mroos4 thank you!!
could you please give the proper link to this source code??
I played around with this idea in C# a bit. I started with a canvas size of 1280 x 720, a radius of 32 and a maximum of 500 attempts to draw a circle not overlapping another one. After I'd tried that 500 times, I started over, doubling the number of attempts and halving the radius, so radius 16, 1000 attempts. I continue this until I have a radius of 2 and I'm attempting to place 8000 circles. In the end I managed to get around 2500 circles to draw of varying radii, none of which overlap any other circles. Takes about 1.3 seconds to calculate and draw. The way I implemented it is not very optimized though. It only uses around 6mb of RAM, but nearly 50% of my CPU. For the last attempt of the radius 2 circles, it's done a total of 15449 distance calculations (I don't bother checking the first one of radius 32).
Hi Daniel, I already used this method to generate non-overlapping circles for my project. Thanks for this awesome video though. It would be really helpful for others. I have a question. Its not efficient way of doing it. What is the optimized approach to solve this problem? Thanks.
Look for more fancier solutions here: en.wikipedia.org/wiki/Circle_packing I will do some videos on this sometime.
for (var j = 0; j < circles.length; j++) {
var other = circles[j];
var d = dist(circle.x, circle.y, other.x, other.y);
if (d < other.r){ // if center is in the other // maby make "circle" move in de direction of the (circle.x, circle.y, other.x, other.y) to make it fitt more
overlapping = true;
}else{
while (d < circle.r + other.r) {
circle.r--;
}
}
}
Remember doing a similar tutorial back in the 1980s on my 8bit BBC Micro, took a lot longer to run.
I was on an Apple II+ back then!
@@TheCodingTrain did take longer to run back then :)
I thought I've watched every single video on this channel. And yet I'm still finding some that I've missed.
would love to Learn more efficient ways of doing this. hope you do a follow up with one way
+eye beholderz yes I would like to!
I'm getting more excited when we are approaching CS algorithm lessons, by peeking at 9.9 Minimum Spanning Tree (Prim's Algorithm).
This is off topic and kind of random, but I really like the color choices for your UI. Is it custom or can I download it somewhere?
Create this code, but make circles have a random color, and make the radius fixed, and every time it can't find a spot to place a circle, reduce the radius by 1 pixel and retry. Stop when the radius is 0.
Was a fine video. Well, could you have done this similar type of algorithm for random shapes (random polygons) instead of circles? In that case, what would be the limiting criteria for not overlapping of shapes?
A related Q&A about overlaping: gamedev.stackexchange.com/questions/136885/keep-balls-in-the-box-and-prevent-intersection
what a legend this guy even videos from 8 years ago are still helping people
proud 2024 watcher
Same!
@the coding train Can you do one with rectangles? Whole different ball park!
I came here to try and find this formula.
This one was very interesting tutorial.
By the way, comparing this, with your recent videos, the quality of everything (lighting, video, audio, the way you explain things) got improved to a very high degree. An already great channel getting better everyday.
It is inspiring to see how much you've come and realize how to improve along the way. As a recovering perfectionist, it explains me how it should be done. Thank you.
Here's one simple next optimization step: instead of checking if the circles overlap, make that loop calculate distance to the closest circle, let's call it "minDist". Let's also replace the magic numbers 6 and 36 with the variables "minRadius" and "maxRadius". Then add:
if (minDist > minRadius) { circle.r = random(minRadius, min(minDistance - gap, maxRadius)); } // where "gap" is a variable for the number of pixels you want between circles
Using this approach, the small gaps in the image will get filled much quicker (also, compared to before the distribution of circle sizes will be skewed to smaller circles, but that's not really important).
edit: clarity
+Job van der Zwan thanks for this great suggestion!
I dont even know the problem
i tried running the same program
and maybe I am missing something.
but it is just a blank screen :(
Dear Daniel. I"m learning processing through your video's and I gotta thank you big time. I will have a test in three weeks about arays, return, if / else, loops etc. with these video's im bound to pass the test. thankyou so much
+Philip Helbach so glad to hear!
You should do a video about Reciprocal Velocity Obstacles, that would be awesome. I tried to read one of the papers on the subject but I have a hard time turning it into code.
This video made me think. I'd forget the array, unless you want the circles to interact later in the program. Otherwise, I immediately thought of a different way to do it by picking a point of test coordinates and checking if it touches a circle's color. If it doesn't touch a circle's color, check the perimeter of a circle with radius n at the test coordinates (where n = 1 to the maximum circle size). A routine could select points around an imaginary circle and test each point for a circle's color (kind of like looking around a point in a spiral to see if there is any circles nearby). If it doesn't touch a circle, the imaginary circle grows until it reaches the maximum size or hits a circle's color, at which point, a circle with radius n-1 would be drawn and the program repeats. This continues until the circles get smaller and smaller, filling in all the space. If you want to array the successful circles, this method would still allow for that. If I could program in p5.js, I'd give it a try, but I'm really, really old school. I still program in BASIC. I'm trying to learn from your videos, but I appreciate the logic structure more than the actual code.
Could you instead write:
if (overlapping == true ){
i--;
}
so it would try again until you actually get your amount of circles?
Because that second loop is outside the first loop, decreasing i does nothing. If you nest all of those loops inside of each other (probably a bad idea unless you use functions to make the code easier on the eyes), then yes, appending that to the end of your loop would work.
"overlapping == true" doesn't really make any sense. You might as well just write "overlapping".
it makes sense, but, yeah, just `if(overlapping)` works too and it a little better
yes, I did the same and it works ;)
The entire time I was like you need to i--. Then he did the while loop and I was like....Well then, that's the same result.
Thank youuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu!!!
:)
Fab - many thanks for sharing!
Coding challenge : piano in c++
At first glance this video seems pointless and silly. But for someone like me this is incredible. Thank you for all your amazing content. Please keep it coming! Also, I need a whiteboard! Hah
thanks for the nice words!
I just coded this with you step by step and learned a ton about brackets and how to read java script. You are awesome. Thanks.
Daniel, nice! I enjoy tutorial videos that show one way to tackle an algorithm 👍
+endofmysteries thanks! glad to hear it!
This Kind of video for P5.js and it works
I'm not event sure I understood, but you rock!!
I'm trying to modify this code so that it produces circles only if they are bordering another circle, but I can't seem to get it right. It either produces circles overlapping or exclusively not overlapping.
Hi, I change the code to extend automatically the canvas width if protection is reached. Then you can show all the bubbles. I have also added the condition at the end of this message to ensure all the circles will be shown completely.
function setup() {
var circles = [],
circle = {},
overlapping = false,
NumCircles = 30,
protection = 100000,
counter = 0,
canvasWidth = window.innerWidth,
canvasHeight = window.innerHeight;
widthDefined = window.innerWidth;
heightDefined = window.innerHeight;
// populate circles array
// brute force method continues until # of circles target is reached
// or until the protection value is reached
while (circles.length < NumCircles &&
counter < protection) {
if(counter==protection-1)
{
counter = 0;
widthDefined = widthDefined + 100;
}
circle = {
x: random(widthDefined),
y: random(heightDefined),
r: random(50, 100)
};
overlapping = false;
// check that it is not overlapping with any existing circle
// another brute force approach
for (var i = 0; i < circles.length; i++) {
var existing = circles[i];
var d = dist(circle.x, circle.y, existing.x, existing.y)
if (d < circle.r + existing.r) {
// They are overlapping
overlapping = true;
// do not add to array
break;
}
}
// add valid circles to array
if (!overlapping) {
circles.push(circle);
}
counter++;
}
createCanvas(widthDefined, heightDefined);
// circles array is complete
// draw canvas once
background("#233")
fill("#2AC1A6");
noStroke();
for (var i = 0; i < circles.length; i++) {
ellipse(circles[i].x, circles[i].y,
circles[i].r*2, circles[i].r*2);
}
}
And if you want to ensure all the full circles are visible change this line:
if (!overlapping && circle.x-circle.r>0 && circle.y-circle.r>0 && circle.x+circle.r
Did you ever do that force-directed graph video? I needed to do something along those lines for a project at work. I'm brand new to JS and have never touched P5 but I've been watching your videos for years just for the algorithmic interest (I've been programmin in C/C++/C# for decades). Any way, when I had to tackle this I thought I'd come back and see if you have anything I could draw from but I couldn't find a video on self organising graphs (maybe I'd have more success now that I know the correct term - "force-directed graphs").
Anyway, here's what I was able to slap together. I'm super impressed with how easy it was to write my first P5.js code. This is literally the first sketch that I've written in P5. But thanks to all your videos it made getting into it a walk in the park. You may even recognise some terminology that was taken straight from your tutorials, like "Bubbles". Sorry, I coudn't find an intuitive place to bring in Unicorns or Kittens ;-)
editor.p5js.org/deefstes/sketches/MYMhdhD5C
Sir Would Java be of no use because of PYTHON web dev , data science, ML, AI and KOTLIN, DART flutter in ANDROID side
If not so please explain.
wow p5 looks a bit easier than regular javascript.
eg instead of var x = Math.random()*width;
you do var x = random(width);
and ellipse is better than arc
man I was stuck on this problem and was frustrated. Thank you very much for this video. It saved me
Any idea on how to calculate the distance between the two circles using the Pythagorean theorem? I'm using plain JS which doesn't have the distance function.
Hi have a challenge for you! :D
The circles should move at different speeds and directions and still cannot overlapping. Too much physics?! Yes, it smells like collisions :D
Are you able to write this type of code but with the same concept as the maze generator? That is, a single object moving around the screen looking for places to add the circles? (I know nothing about programming) Perhaps a new challenge?
I just started your video with a speed of 1.25 because I needed it before and was very surprised why you are so in hurry. :D
couldn't you just used the circle() instead of the ellipse() ? circle() only uses x,y,and radius.
Haven't watched yet but I would probably create an array of 500 randomly placed circles then run through the array with hit detection between each circle and delete a circle if they overlap. Or maybe create a smaller 50 circle array and keep randomizing a circles size and position if it overlaps something else until it doesn't.
An alternative without random run time would be when using squares.
You would split the canvas into an grid in an array and then just shuffle the array once.
And then you would just go through the array.
wonderful video, I would like to follow you
Hey, this is a great video, thank you for posting it. You said that this algorithm was not the most efficient, right? What more efficient methods exist, say for even more circles?
Hey Daniel, just a suggestion. I came to this video of yours after watching a couple of your latest videos and I could see this one has a far better sense of explanation. You even assumed that viewer might not know what a radius. I think if you can inculcate and carry on same style in your future videos it will be very helpful, especially to someone who is just starting to learn how to think a puzzle in a programmer's perspective
What kind of weird ass IDE hangs when the application doesn't terminate?
Could you have the circles set to decrease size when they run out of available space? Like when they run out of space to fit the largest circles, the size decreases to accommodate the next smallest ones, etc... with the radius continually shrinking until you reach the smallest radius that you want
+Daniel Shiffman Were you transmit live videos?, I'll like to see your lives..
this was useful for a whole other problem I'm working on, random placement of random triangular terrain tiles and subdivision into polygons made of triangles. I can splat some triangles into a rectangular map and build triangles between the side and two corners of one triangle and a corner of a nearby triangle. I need to make sure my initial triangles don't overlap and any new triangles I build off the sides of a terrain tile connect to a corner of a nearby triangle rather than overlap...
I really hope that makes sense.
It would be cool if you do a challenge about creating the shape siri has in iOS 10, kinda like a bunch of colorful sin and cos shapes together.
One query here ... Circles are going out of window and getting cut off randomly on the edges. Can all the random circles be set in the available area only and does not cut off
Challenge 2.0 make video showing efficient algorithm
i have made a code i put "draw" in "function draw()" and mouse poss makse a cirel that fits in if ouside all circels center is the mouseXandY
but i want it to fit grow move xy untill it get suck between 3 "other" i made so it calculete the outer border if inside where can i post this code
i feel it seaser to show thatn to explain
How do I draw random circles that when collide with each other and walls of canvas move in opposite directions and burst when clicked by a mouse
how to create this on processing in as easy and basic manner . the one on you put for processing in GitHub is very complex for me to understand.
Just wondering if i wanted to optimize the positioning such that as much randomly sized circle could fit the canvas.
Let's say there's a minimum area allowed for each circle.
Great vid as always tho :)
Hi Daniel, I like your videos.
There are several opportunities to improve the algorithm.
First we can add a buffer which stores unsuitable positions to place the circle. This will avoid repetition calculating distances between points.
Second we can divide the region into chunks and calculate only the distance to the circles from nearest chunks.
This will improve speed and increase the density of circles.
My implementation:
github.com/roocster/p5.js-no-overlap-circles
Thank you! I would love to cover this in a future episode!
github.com/CodingRainbow/Rainbow-Topics/issues/147
It's a simple idea, but I'll be happy if it helps someone
What a great idea!! This is a really cool idea, but unfortunately it does not improve performance, it on the other hand decreases performance really really badly. Do you really understand what will be the size of this buffer?? Around screenWidth*screenHeight or 200000, and every time you are going to check if the circle is in this buffer?? Isnt it better to check previous circles (around 200) as he did? Y u so dumb?
You were doing so well with your comment, right up until the end there. There is no need to call someone dumb when you're offering constructive feedback.
30svich reading in a buffer (if its a hasmap) of 200000 elements or more is O(1) vs looking for all n circles with distance calculation is O(n). I dont know why you call him dumb when he's proposing a very smart optimization. Next time test your theory before it backfire on you.
Bibibiboobooboob! Stunning!
How can you replicate this code using only javascript and not p5?
To protect your loop, you could have summerize pushed circle areas and compare it to the actual area of the canvas.
Is it possible to solve this problem in O(n) instead of 0(n^2)?
I can't thank you enough, Daniel! I was looking for a solution for this exact problem for over a week and found this today, I love you!!
oyg, it's full of DOTS :D big dot, small dot, this dot, that dot xD
Does anyone know a good video that demonstrates a force directed layout
You are amazing. Everytime when I watch your videos, I learning a lot. and you really make this fun to learn :) Thank you.
I cant access the code links. Does anyone have the refreshed one or the code themselves?
Your videos are really fun and interesting.
I would like to learn and do some JavaScript as a hobby.
So far tutorials I've tried are try and dull.
Is starting out supposed to be like that or is there a fun way to learn?
Thanks
him: draws circle
him 2 seconds later : oh see we got lucky they dont overlap
tks teach so much. love u
Thankyou for the video. Can you please do a tutorial on packing random shapes (polygons for example) without them overlapping please? Cheers
Keep more coming =)
I absolutely love your stuff. Thanks for sharing. I hope you see this.
The logic is greater than the result for us
even though most time i have no idea what you are doing, i still like to watch your vids, you are sooo relaxing and make it look so easy. just great
I love your videos man! I made it thought the holidays watching them! :P
What if we add similar size images in place of circles?
genius
This was great!!! This helps with a generative art project I'm working on. You're an excellent teacher 🙌🏽
Is it just me or is he not in love with the case tructure?
Hi Daniel, This is awesome, I am using this in my iOS app. I wanted to modify this a bit. How would you go about placing Circles (with predefined fixed radius) in a view such that they are closely packed with each other?
I did try using a Gaussian distribution so placing the circles around the center has a higher probability, but not getting the expected result.