[Unity] Procedural Object Placement (E01: poisson disc sampling)
In this video we look at implementing poisson disc sampling, an algorithm for generating tightly-packed points which are all some minimum distance from one another. This implementation is based on the paper here: www.cs.ubc.ca/~rbridson/docs/...
Source code: github.com/SebLague/Poisson-D...
Support the creation of more tutorials and get early access to new videos: / sebastianlague
Пікірлер: 274
Your tutorials are incredible, Sebastian. Always very informative, well explained and about topics you don't often find in KZread. Thank you for your work, I learned a lot from you and I hope to learn even more.
I am glad to find out how people managed to place objects procedurally. For some reason, I could not find out how games like Minecraft know how to place trees, et cetera. Thank you for the knowledge!
@powerus1179
5 жыл бұрын
Would just like to note that minecraft doesn't use this system to place trees, it simply uses random positions within chunks
@caspera3193
5 жыл бұрын
Yeah, you are right.
@frocket5861
4 ай бұрын
There are many scientific papers regarding this topic. Many of them are also not too hard to understand
I will always thank you so much, all of your tutorials are the best! I had a lot of trouble getting on the right way of programming for Unity and getting the right "inspiration" for studying it. You helped me a lot with all of this. Sorry if my English is not the best, I am from Colombia. Keep on the good and great work you do with all of this, and thank you, so much.
Hey Sebastian, awesome tutorial! Please, continue with this series of Poisson Disk Sampling and procedural placement it is really interesting and I saw in the comments a lot of people are freaking interested on that as well. So please continue! Thanks a lot!
Ok just like, Thank you so much, Been fiddling around making custom terrain and got some parts down but never really understood how to make things look awesome and run well until I found your videos. Thank you so much for sharing this with us.
Such a well done tutorial. I love procedural generation; you making it look so easy. I hope to see more on this topic. Looking forward to see your next tutorial. Keep up the excellent work!
Easily one of the best Devs for teaching on youtube, learned so much!
Hey Sebastian! Thank you for this! I’m laborating with spawning junk in space in clumps, and the way to set this up to run in the editor instead of play mode is an excellent idea! I’m considering using Poisson disc sampling to create the clumps, by creating a bunch, then removing 90% of them, then use the same algorithm withing each disc to create items that do not overlap. Looking forward to check the next part of this :)
I too would be very interested in seeing episode two!
Your videos are so great. I really feel connected to the problems that you explore
I can't even begin to comprehend the math as math and I agreed long ago to disagree but this is really cool. Seems the proper way to distribute items across through out a level. Thank you for making all the videos you have made, they are always really good.
This is just what I needed, and as usual a great tutorial.
Hey there. You are so polite and a nice teacher for me, most of the people don't understand you. Don't mind any bad comments. Keep doing what you are doing because you are doing it so well. Cheers!
NIce, been looking for one tutorial in this case. thanks, mate.
Thank you for another fantastic tutorial, Seb.
Looking forward to another of your awesome series :) Keep up the good work. You are awesome!
It's like you're reading my mind, I was making procedurally generated stars and I couldn't figure it out how to make some of them not spawn on each other. Great stuff as always!
@hogoromootsutsuki4079
2 жыл бұрын
I came up with something like that, it was for a galaxy generator I was making for a star trek game. what I did was spawn in a star, and after that, create points, and then I would measure distance from point to any and all spawned in stars, if the point was a specific distance away and within a specific distance, I used that point to spawn in the star, and then I would repeat the process till all the stars had been spawned
Please do continue this series, love your videos!
Very strong programmer, I'm porting some of these tutorials to godot as git modules. Thanks for the techniques.
I'm working on a node-based map like "Slay the Spire," and this is a fantastic starting point. Thanks!
I don't even know how to use Unity or C#, but I still watch.
you are like coding train just for unity and c# I love it
Really nice tutorial! I expanded this to sample a 3D space. You can really start to see the difference as you increase the k (rejection threshold). The edges of the 3D space began to have less points than the one in middle of the space. I assume because the initial spawnpoint was at the center. Anyway, great tutorial never knew this algorithm like this existed :)
Yeah episode 2 would be appreciated
For anyone wondering about alternatives, I don't know how efficient it is, it takes a bit of loading time, but an alternative to the first thing you talked about, where you check distances between each point, is spawn a sphere(or circle) collider at the point you would like to spawn, if it collides with more than two(if you are including the ground), check for another point. Of course, poisson disc sampling is a more efficient way of spawning, and with my method, you would definitely have to have a "check limit" to prevent a stack overflow if there's absolutely nowhere to spawn, but I used this for a game I'm making, and it works just fine. Spawned 1000 enemies on a giant plane, and it only takes a couple seconds to spawn.
@alex197
4 ай бұрын
I thought I was the only one
I just wanna give this man a hug
Yo could you please do the next ep on this? I really like your stuff.
@suncrafterspielt9479
4 жыл бұрын
Yessss
@Kasslim11
4 жыл бұрын
I was looking for the next episode too, I wonder if he forgot about this series
@connorconnor2421
4 жыл бұрын
I think he did
@darkstar9942
2 жыл бұрын
he forgor ;(
Thank you, this is exactly what I needed. Also, thank you for the previous procedural planet video. I altered the algorithm a bit and used it to procedurally generate caves (by flipping the triangles to have their showing faces inward instead of outward).
@burgerlx8871
5 жыл бұрын
How did you add caves to the planet? Can you send me a link?
@Truji851
5 жыл бұрын
@@burgerlx8871 Seconded.
@vancuongo3316
5 жыл бұрын
can you give me how to do and send me the link please !
Your tutorial always teach me something awasome and new, that you cant find anywhere else. Thank you for making these tutorials
Pleease continue this series. No tutorials out there for multi-class poisson disc sampling
Juste perfect, continue like this !
Aww... he never did a follow-up video for this. 😥
i love that theme i have it already 4 months its epic
Excellent video. The only thing I'd like to say is that in a square (all sides equally long) the diagonal "r" would be equal to one side "s" time the root of 2. So: r=s•√2 and you get to s=r/√2 much quicker. But your calcualtion process also works with rectangles which would probably be very handy in certain situations.
Amazing video! I hope you'll get around to making more videos on poisson disc samplng.
I would really love to see more about it
Hi, you can try similar result by creating a perlin noise and instancing meshes only on one color, for example white. you can make differents layers and using as masks, for example for instancing grass or trees on a mountain type mesh, you dont want to populate too much certain areas. Always its a pleasure to watch yours tutoriales
Really love your tutorial bro. :)
Would be interrested in the next episode as well. Dont know how much you planned, but maybe finish it off by actually adding trees and grass (for different disc sizes) to a terrain mesh. That would be cool :)
would love to see more episodes on Procedural Object Placement and Procedural Landmass Generation :)
This is extremely helpful
I finally got sampling disks of multiple sizes to work on my own, thanks hugely to your first video on the topic! Please do the second part still, though, so I can replace this god-awful pile of spaghetti with something better!
PLZ continue this series!
Great tutorial. I wonder if you are going to cover voronoi cells in the future. It could possibly work well together with this procedural point placement.
At 7:00 I think you put sin and cos backwards on line 22. To convert from polar coordinates to Cartesian coordinates its actually x,y = cos(angle), sin(angle), but you put sin(angle), cos(angle). Still, great video! It's really useful in a project I'm working on. Thanks!
@scokerra2
2 жыл бұрын
Unity has 0 at the top of the unit sphere rotating clockwise, instead of to the left rotating anticlockwise. Converting between the two is done by subtracting the traditional one from 90 (unity = 90 - traditional), and since sin(90-x) = cos(x), swapping them around is a shorthand way of doing this transposition.
Спасибо Себастьян за твои туториалы
What keyboard shortcut are you using to jump to the function parameters and back at 6:00?
I'm quite interested in points of different sizes and point density. Will you be returning to this series this year?
@Sabastian Lague do you know how to implement this with your procedural terrain generation because this is great but im not sure how to do it in 3d map generation on the series u did ages ago
The border regions will have fewer points because IsValid filters with RegionSize, which makes it eaiser to reach numSamplesBeforeRejection.
Looking forward to the next episode on this series. Any ideas on when you will be releasing it?
@rulyhyperion8277
3 жыл бұрын
I've got some bad news for you
PLEASE add more to this!
Amazing Tutorial as always Seb, when are doing different radius video?
Is the planet series finished? Or are you just starting this series along side of it?
Nice tutorial overall, but there is a slight issue with the code, IMO. At around 3:50, you compute the grid count using the ceiling of "region size / cell size". By using the ceiling, your grids basically become smaller than they were supposed to be. This could lead to points being generated that are closer together than they should be. Furthermore, at around 08:50 and around 11:00, you compute the grid indices of the candidate point using a potentially different grid cell size than the actual grid would use. Yes, these issues would be very, very rare, but they could occur. Here's an example: Let's say the region is 1x1 and your initial cell size based on the radius is just below 1/3 (for example 0.332). That results in 4 cells on each axis (1 / 0.332 = 3.01... => ceiling is 4). Now, each cell in your grid is actually 0.25 on each axis (1 / 4), which is considerably smaller than they should be. However, you still use 0.332 for your computations. Therefore, a point at 0.76 / 0.8 will return grid coordinates of 2/2, while it should really be in 3/3. With these wrong grid coordinates, IsValid can yield wrong results because it didn't consider a point it really should have considered. To fix this, I'd suggest using the floor instead of the ceiling for the initial guess of the cell size. This would lead to grid cells that are always slightly larger than they need to be, ensuring the minimum distance condition you rely on in IsValid. After initialising the grid to its final size, recompute the actual grid's cell sizes on each axis and use those in the rest of the code to get the proper grid cell indices. Other than that, there are a few possible optimizations and I would prefer putting this into a non-static class that separates the grid computation from the actual sampling, reducing the number of parameters you have to pass around, but I don't think that's an issue for a tutorial.
@3snoW_
3 жыл бұрын
I realize this is a year old, but I don't believe it's right. The grid is used to store up to 1 point per (x, y) pair, so that when placing a new one you check the surrounding points on the grid to see if it's valid, rather than all of them. So you want the grid size to round up, to make sure that whatever coordinates inside the sample region will be translated into integer grid coordinates. So you use ceil to round up the grid size. Further ahead while validating, before anything else he checks that the coordinates are in the sample region, then when converting region points to grid points he rounds to the nearest integer rather than rounding up, making sure that the points are inside the grid for sure since the grid size is rounded up. So the problem you described could never happen.
Hi. First amazing video and great explanation. Question : could we use this technique to generate non overlaping position over time ?
That was a great video. :)
Thank you for the great tutorial. What would be the best way to change the seed and scatter on other type of objects like circle or sphere?
Hello Sebastian, i love your tutorials and i am very grateful for the quailty and level of depth in your work, i am wondering if you are going to continue your 2D Platformer series in the future? Many thanks, Will
Can't wait for more!! ~_~
Please continue :)
I know I am very late and this isn’t related to the tutorial at all however I can’t help but notice how beautiful your VS Code is set up, hence I want to ask what theme are you using? Thanks, Calcopod
Is this serie going to continue? It's truly interesting!
@nates9778
4 жыл бұрын
Presumably not :"(
@cazhalsey8877
3 жыл бұрын
:(
@reyariass
3 жыл бұрын
I still have hope after all these years :/
@legohexman2858
3 жыл бұрын
@@reyariass your hope seems to be misplaced
@reyariass
2 жыл бұрын
@@legohexman2858 I still have hope
How did you set up VS code for unity? what is the font and the theme that you are using, Sebastian?
Nice video. I was wondering if you are still gonna make the video on neural net backpropagation?
How do you use this to angle this down onto a plane and summon obstacles? I would like to use this to create a random temple run esque game but I'm not sure how to put this onto the z plane and turn the sphere's into one of my prefabs
Where’s the variable size video? :/
how do you find these mathematical concepts and know to use them for procedural generated animations? Poisson disc sampling is not in my daily vocabulary and even if it was, i would never have thought about using it for creating tree locations or grass stems (the examples you used in the beginning of the video). Is there a field in math or game dev for this? Trying to figure out what to google lol
would really like more tutorials
Sorry for the noob question, but how would we go about changing the position and the rotation of the points using the GameObjects transform? I can do the actual transformation, but Ive found moving the transform gizmo doesn't actually trigger on validate, so I have to manually change something on the component to get it to work update. Any way to get around this?
Which extension do you use for C# unity code?? I mean codelens like "Vector2" or "Mathf.sqrt()"
Where is the next video? This theme is so interesting! Love your videos
Le Poisson, Le Poisson, HOW I LOVE Le Poisson!!
Great content. Latest Unity does not like bigger regionsizes. Anything above 5x5 and I get a "Hold on" that does not stop.
This is a obvious deadend
Awesome! :)
Awesome tutorial! Small note - I've checked out Bridson's original algorithm, and you deviate from it in that your distribution of the points in the ring is not uniform. It's an easy fix though - just replace Random.Range(radius, 2 * radius) with radius * Mathf.Sqrt(Random.Range(1, 4)).
@projectafterworld2557
2 жыл бұрын
I believe this was intentional to avoid having any equations involving square roots in the algorithm, as they're very expensive calculations. The loss in uniformity is a sacrifice in order to allow this implementation to run at high volume, or alternatively, many parallel instances at small volumes, which is what a procedural game with dynamic generation would require. Though yes, if you have a use case that requires uniformity, and can sacrifice performance to get it, this should work.
@ZeroPlayerGame
2 жыл бұрын
@@projectafterworld2557 you can probably get away with a couple of iterations of x = (x + x0/x)/2 and get much better accuracy though
@klhjglkjhlkjhlkjhlkjh
Жыл бұрын
@@projectafterworld2557 square roots are not that bad, modern CPUs have dedicated instructions and even something like @alex S suggested would probably be slower.
Is there a second part video and I just can't find it?
would love to see how this could be implemented together with your procedural terrain series
@envymak2254
Жыл бұрын
Literally the only thing I came here for....
@Arelias95
Жыл бұрын
@@envymak2254 Not that hard if it comes to just making points at given coords, instead of vector2 just pass float for size of the chunk (keep in mind scale number as well). Code I changed in validation: static bool IsValid(Vector2 candidate, Vector3 center, float sampleRegionSize, float cellSize, float radius, List points, int[,] grid) { if (candidate.x >= center.x - (sampleRegionSize / 2) && candidate.x = center.z - (sampleRegionSize / 2) && candidate.y int cellX = (int)(((candidate.x - center.x) + sampleRegionSize / 2) / cellSize); int cellY = (int)(((candidate.y - center.z) + sampleRegionSize / 2) / cellSize); //Works fine, grid operates on 0 to n values int searchStartX = Mathf.Max(0, cellX - 2); int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1); int searchStartY = Mathf.Max(0, cellY - 2); int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1); for (int x = searchStartX; x
NEAT!
Which program are you using for drawing animations?
what is the program with a c logo on your task bar?
Is there any befit to using boxes with a diagonal of length r and checking a 5 by 5 area compared to using boxes with a side length of r and checking a 3 by 3 area? Wouldn’t using boxes with a side length of r reduce the area to check for points, thus speeding the algorithm up or am I missing something?
@vivid4259
2 жыл бұрын
If the box' side length is r it no longer guarantees that there's at most only one point within given box, since you could, for example, fit two points near the diagonally opposite corners of the box that would be over r distance apart.
@ehnehm
2 жыл бұрын
@@vivid4259 Ah, right. Thank you. :)
me: I dont understand ASMR Also me: This video
@chriskeddy1975
3 жыл бұрын
Yep. I had to max youtube/computer/speakers to hear this.
Would it be any faster to use 1.41421356237 in place of mathf.sqrt(2) in the GeneratePoints function?
aww man what a cliffhanger! don't tell me you're Fireflying us?
Thats gold
Great tutorial. I was wondering wouldn't it be possible to first generate random points within each square, and then filter out those that are offending (too close to neighbors)? This would allow you to have points everywhere, and the algorithm would not stop abruptly when you decrease the k.
@SeungHuLee
5 жыл бұрын
Did you find the answer to your question? Guess I'm having exact same situation here.
Hey man thank you so much for this. Any chance you could show us how to do points with different radius?
How I can apply this on each region of the procedural map generation series to generate trees? Ty for this incredible tutorial!
@ujustinree2987
5 жыл бұрын
Step 1. Poisson Disc Sampler for each chunk to get a bunch of points. Step 2. For each point raycast down to the terrain to get the height. Step 3. Instantiate a tree at the raycast hit point. You can also check the height with the terrain to have trees only spawn at a certain altitude.
Nice, exactly what I was about to implement! It would be awesome if you cover how to make forests of different density and plains with lone trees with this technique.
You are the god
Does anyone else catches Index Out Of Range Exception on the line 27? It seems in my case it is always goes out of bounds, don't know why tho. Would much appreciate help, thanks!
When producing polar coordinates to determine a random point inside a circle/annulus, using uniformly random values for a polar coordinate's theta & radius values will favor areas of the circle/annulus that are closer to the center/smaller edge. My guess is that it's affect is negligible in the examples shown in this video. But it's worth noting if anyone chooses to modify or expand upon the algorithm. More can be seen about this problem in the video: The Best Way to Find a Random Point in a Circle by nubDotDev ( kzread.info/dash/bejne/Zq2T0M-pppCfnKw.html )
Can you recommend a book on math for programming?
watching this, I understand everything and it looks really really easy. But once I open the code editor, well sh*t
Why does he use sine for the x value and cosine for the y? I don't think it really makes a difference as long as they're different from each other, but doesn't cosine of an angle technically give you the x, and sine for y? Thanks, hope someone can help.
@joshstubblefield9093
4 жыл бұрын
Yes I think you are correct.
IsValid should use early exits to reduce nesting. you could do: (new Rect(Vector2.zero, sampleRegionSize)).contains(candidate) to make it a bit more readable. the for loop for the samplepoints could be extracted in its own private method, returning an boolean and using ref parameters for the lists/grid. (you'd get rid of the boolean "accepted" and the initial code would look smoother) the amount of parameters you need to carry around makes me wonder if wouldn't be better to not make everything static, but instead have a generator object that takes the needed parameters in the constructor.
Hello and Greeting, I'm trying to recreate with z-axis instated y, but I'm having trouble implanting it, I kept getting stuck in an endless loop, it seems it at all the points get accept regardless of check
How do I do different sized radius's in my program?