Coding Challenge #34: Diffusion-Limited Aggregation

Coding Challenge #34: Diffusion-Limited Aggregation



In this Coding Challenge, I explore the generative algorithm “Diffusion-Limited Aggregation.” The DLA visual pattern is generated from random walkers clustering around a seed (or set of seed) point(s).

Support this channel on Patreon:

Send me your questions and coding challenges!:

Contact:

Links discussed in this video:
Diffusion-Limited Aggregation Wikipedia:
Paul Bourke’s DLA reference:
Atom Live Server Package:

Source Code for the Video Lessons:

p5.js:
Processing:

For More Coding Challenges:

Help us caption & translate this video!

welcome to another coding challenge in this coding challenge I'm going to tackle diffusion limited aggregation so what is diffusion limited aggregation well I encourage you to take a look at two references there's always of course a Wikipedia page you can kind of find out a little bit out the history of this algorithm warehouse thought of what ifs applied to it what it kind of what is what it can be used for on the reference that I'm using here that I read right before making this video or actually earlier this morning a couple hours ago at this point is a page on the internet from June 1991 written by Paul Bork which describes the algorithm you can see that diffusion describes among other things the diffusion of the aggregation of zinc ions in an electrolytic solution that sounds kind of exciting but anyway the point of what we can do with this algorithm is to create certain kinds of fractal like tree like crystal like growth patterns and you can see there's a variety of possibilities and I there's one down here that I particularly like this one which I might try to recreate by the end of this video but let me I'm rather than read to you as much as you might enjoy me just reading that web page to you in this video what I described to you a little bit about how this algorithm works at least how I think it works and then the Internet can always correct me and while I start to write the code for it we'll see if I'm thinking about it correctly because honestly I don't know I should have practiced this in advance something is definitely gonna go wrong in this video okay so let's say we pick a point at the middle of the screen and then we just say oh hello oh we're saying hello too but there's this thing called a random Walker and the random Walker starts here just starts to randomly move around the screen and at some point it hits this point now obviously it's not going to take that exact path although it could randomly and once it hits an existing point it gets stuck and then we release a new random Walker and it starts to walk around and when it hits an existing point it also gets stuck and then we release another random Walker and it gets stuck and another one get stuck and another one gets stuck and another white gets stuck and as they get stuck we start to see this fanning out pattern so this is what I want to do now I think would be really interesting to actually animate the full process there's kind of a spectrum here we could write code animate the whole thing like we see these random walkers moving around the screen and getting stuck we could also not animate anything and just see the final image or we could do something in between I think I'm going to try to do point by point but not animate the random walk itself that's what I'm going to attempt so let's go back over and we need some code to start with which I have here no code I mean I have a p5.js sketch with a canvas and a background and if I go back to the browser I think I have it running here in the browser I can open up the console which I'm definitely gonna need for debugging and so let's first start what do I need I want I think I want to have an object no you know what let's just start right now first let's do this rather simply I'm going to say I'm going to call the thing that's finished the tree I don't know if that's a good name for it but all of the points that are in the pattern I'm going to call the tree I'm going to need a walker the thing the point that's moving around and that's just about it really and what I want to do is and I need a size like the size the radius for each one of these points which by the way you could do it on a per pixel basis so that always could be one but I'm going to try I'm going to try something like 16 just to have it be bigger to start with so um the first thing I'm going to do is I'm going to create I'm going to say tree index 0 equals create vector a point in the middle of the window and then what I'm going to do in draw is I'm going to say for all the points in the tree say stroke weight R and stroke 255 and I'm just going to draw a point tree index I X tree index I dot y so and let's not worry about this Walker for a second so I'm going to refresh it well ok but I don't need to refresh it it's life I'm using this atom package called live reload so there's the point ok so now what I want to do is I want to create something that I'm going to call a Walker and I'm gonna create I don't know if this is such a good idea but I'm just going to put it completely randomly anywhere in the in the sketch window it probably should start along the edge thing or actually if you read Paul Bork's page I remember now reading a point that you can make the algorithm more efficient by cleverly picking it close to where you think it might need to be but I'm just going to create a random Walker and I'm going to say I'm going to see if that Walker should be stuck so first thing I need to do is check again all of the points of the tree and I want to see I want to know the distance between that Walker and a particular point in the tree and if that distance is less than some threshold or I guess oh no are par times 2 right because I just want to know if those two circles are touching so if this circle if the two circles are touching the distance is less than twice their radii radius if distance is less than R then stuck equals true so I'm going to create a boolean variable assuming stuck is false and then I'm going to go through all of the points and if stuck is true I can say a break and now what do I do here I'm going to say and actually what I want to do is like keep going until you get stuck so as long as you're not stuck keep checking all the points and as soon as you get stuck so that's stuck equal to true and what happens if you get through this loop and you're still not stuck then Walker should it should randomly walk by some amount let's and you know I could probably be more thoughtful about this Walker dot X should change and walk or dot Y should change the other thing I really need to do is I should make sure it stays on the I don't want it to walk randomly far far away off the window so I should constrain it to two between 0 and the width of the window so let's see and now once it finds a part point when it's stuck then what do I do I say tree dot push Walker there we go and now let's see what happens here so I've got some infinite loop problem this always happens with live reload be like there we go oh look at that so I missed up something good is happening what boy did I mess something up this is interesting so I must have used an X in a Y ah okay that should help yeah so interestingly enough this doesn't look so totally crazy is this correct though very hard to tell so let's do a couple things one is the stroke weight should really be half the radius and then they should be right up against each other let's move them by let's move it by just one thing I want to do is create I'm going to I'm going to just make a random unit vector to be a little bit more controlled about how they're moving and then I'm just going to say Walker dot add that velocity so this is a little bit better just to make a random vector and add that to the Walker I got it I think this live reload thing doesn't work for me because because okay that's good and actually maybe I meant for this to be x – yeah there we go okay so this is definitely looking kind of right right now let's the basic idea let's make this much smaller yeah so you can see this is actually working although it's quite of the slow algorithm you can speed this up so I think I've got the basics of the algorithm correct actually it's just kind of slow to do this one point of time let's do it this way one thing I want to do wow this maybe this isn't as bad as I thought let's uh let's let's think about this let's do I think we could release a bunch of Walker's at a time so let's try let's try releasing ten Walker's at a time and just to see if we can kind of get this going a little bit faster oh you know what the walkers I think need to the start from an outside point right well let me let me do this though anyway and then we're going to pick out where the walkers start differently which is going to be much better I think so um so alright so I just want to see something if I I'm going to create a bunch of these walkers and then now actually I can just do this as a loop right while you're not stuck okay if I'm back and I thought of something which I think it might make a little bit more sense to be able to play with this a bit more by having the Walker itself be an object so I would like the instead of just being a vector I want it to be an object that can store both where it is on the screen its size you can call functions on it that's going to give us more ways of playing with this algorithm and make it perhaps a bit more efficient so let me go here and what I'm going to do is I'm going to create a new file and I'm going to call that file Walker j/s and I'm going to make a Walker object constructor function and I'm going to say I'm going to say this stop position equals create vector a random width random height so I just want to take a lot of this functionality and that I've written out here and I want to also whoops I want to create a variable called this dot stuck and I want that variable to be false when it starts I want to have a function that called walk so I want to I'm going to I want to have a function I want to have a function called walk where I implement this algorithm where I pick a random vector I add it to the walker so it moves somewhere on the screen I can strain where it is in the window and I want to have a function that says check what's a better name for that function like updates know a stick I can't think of a good name whatever check sticky check stuck whatever that's gonna be the name of the function check stuck and when that function what I'm going to do is I'm going to take this particular algorithm and I am going to I actually kind of want to see that walk but I think I have an I actually kind of want to do this without the while loop so what I want it for a second what I want to do is check all of the points on the tree and see if the distance between this walkers position right which is actually this dot paws now dot right the walkers no longer the walkers now an object with a position is near anything that's in the trees position because everything is in the tree our walkers that are stuck well you know what I didn't do is I'm not delete anyway so okay so and then if it's stuck I'm going to do something obviously okay so what I want to do here now is create an array of walkers and actually tree index 0 is going to be a new Walker that is in the middle of the window then and that is stuck so what I'm going to do in the object is I'm going to have some optional arguments I'm going to say X Y stuck and I'm going to say I'm going to say a X I'm going to say X or this is a way of doing optional arguments so if I pass in an X I'm going to create the vector at that X but if I don't X will be undefined then I'll get a random value Y or or random height okay and then a same thing here I'm going to say this stuck equals stuck in if it's undefined that's the same thing as saying false and then I need to say by the way this that stuck is true and this is this dot pause tree pause okay and I should really check against some other array like the others I'll call that which is called tree so what I want to do right now is I want to create one Walker in the tree and then I want to create in the walkers I want to put just a random Walker so I have tree and I have Walker's and I might as well do that the same way in index spot zero and then what I want to do is I want to see and you know what I should do is I should now I can also have a function which is called this dot show and I can actually take all this code I should have done this at the beginning I can take all this code and put it in the object so I can set a stroke weight set a stroke and this dot pause and draw the point at this dot paws dot Y and and I you know I could be a little smarter about this and actually just make this an ellipse so I could be more nice about the radius and I could say R times 2r times 2 which is a global variable at some point but I can have them be variable sizes at some point okay so now I have this object I have a walker object which can move it can check to see if it's sticking to anything else in some other array and it can also it can also a draw itself so what I want to do first is I just want to say let me display everything in the tree and let me display everything in the walkers array okay ready so if I if I reload this sketch Walker is not defined Oh sketch line seven it's not defined because I have to remember to add a reference to it in my JavaScript file – Walker Jas and missing Walker dot J's line 25 has an error so let me go down and see this dot ellipse this dot pause X this pause dot why I don't see any error here in line 525 oops I had a period there know how to comma there we go great so I should see here whoops I should see this is this and this is the Walker so let's now have let's just now in sketch let's also have Walker's index i dot update o update was not it walk so you can see there it is moving randomly it's going to take a while to randomly intersect that but it is walking randomly I could obviously make it walk faster so what I want to do now actually just as an experiment is I wanna is not at all I've gone off the beaten path here from the actual probably algorithm but I want to put 100 Walker's into the space right okay so they're all moving around randomly and what I want for them to do is if if Walker's index I check stuck others then walkers then I what I want to do is say walkers dot splice I want to take it out of there and I want to say tree dot push walkers index I so I want to whoops what I want to do is I want to anytime one of those walkers get stuck I want to put it in the tree and I want to take it out of the walkers all right because it's not something that's moving anymore so we let's check this dot stuck equals true so actually let's make a function is stuck actually so I don't need a I don't need this variable I can just say return true and if it kind of gets to the end return false so let's look at that and see what happens others is not defined a tree right have to pass in the tree there we go you can see them getting stuck gogo Walker's go go go go Walker's go so because yeah that takes a very long time I'm kind of curious to try a few things let's try a thousand walkers and I this isn't what Paul Bork describes what to do on the website at all but I kind of like it and so I kind of want to highlight them differently so I should actually by the way I should have that be a particular variable because what I would like to do when I draw them is if if this dots stuck want to give them a different color so let's so we can see which ones are stuck so now though I think better more than better than adding a ton so let's still at it let's actually do this particular algorithm multiple times for a frame like let's let it try to move all the walkers 100 times per frame oh why are they all clustering near each other am i oh I'm drawing them 100 times I don't want to I don't want to do this show so I just want to show them once there we go this is what I was sort of hoping to see so now they're finally okay so now we can kind of see the algorithm happening which i think is kind of interesting it's kind of happen very slow this is a complete and total brute-force method but I finally got something that I like here and because at least it sort of interesting to watch it is happening kind of slowly I want to try a few things to make it happen faster let's increase to 200 walkers and let's increase the number of times to 250 the framerate is a little bit slower now I kind of like to keep the framerate up so let's go down to 200 there we go so we could obviously um and the other thing I could do it's interesting oh it's slowing down over time so the reason why it's slowing down over time is there's more distance checking so one thing that I could do that would hopefully help this run a bit faster which normally I wouldn't care about but it is kind of bothering me how slow that it's running is let's see if we can eliminate the square root calculation and to see if that makes it run a lot faster so one thing that I'm doing here in the checks tuck function is using this distance function and I want to write my own distance function I'm going to call it distance square Euclidean distance and I want to take it I want it between two vectors a and B so what I want is the difference in X which is BX minus ax I want the difference in Y which is B y minus a dot Y and now normally if I were I would say return the square root of DX times DX plus dy times dy this would be regular old-fashioned Euclidean distance right a the square root of you know the hypotenuse of a triangle a squared plus B squared equals C squared or C equals the square root of a squared plus B squared so what I actually want to do here is just write this algorithm but take out the square root and then what I can do now is not use this but use my own distance squared function and then I can actually have that distance be R times R times 4 which is what I want now is for the distance to be did I mess something up here yeah I'm missing a parenthesis what I want is the distance to be instead of checking if the distance is less than R times R I want the distance R squared or R times 2 squared is R times R times 4 so this now a distance dist squared this should hopefully be a lot faster you know uh Wow good okay so boy just eliminating that square root you can see how much faster this is now okay now here's the other thing is every time I remove a walker this is kind of nice actually just to like let it grow with a fixed number of walkers I'm kind of enjoying that back there was a technical glitch there but hopefully you're still seeing me I seem to be I see myself again so you can see here that I have this kind of nice finished pattern which I really quite like actually so some other things that I can do here are one is whenever I remove a walker I could say like I always want to have two hundred walkers so I can all I can always say like while walkers dot length is is sorry is less than 200 walkers dot push walkers dot push new Walker so this is even when they get stuck I add new walkers so I never oh and by the way I started with so let's make a variable called max walkers equals a 200 200 and we're going to start with that's we're going to do it oh no no no that's a different value max Walker's it kind of means and then I'm going to make another variable which is iterations which I'm also going to make 200 let's make these variables I think is kind of nice right we can see how it behaves and we can see our base so now I'm always keeping up 200 Walker's so I would I want this really to happen pretty fast so let's see if I can up the iterations a bit and see if we can get this screen Aziz it is sort of slowing down so I think we're in we're in pretty good shape now here's the thing I think what's interesting oh you can see it really slowing down um so if I go back to oh and you know what there's also a problem here which is that I shouldn't be creating random Walker's anywhere in the window I should only be creating them around the edges so let's also make that improvement okay I think it's worth making that improvement so I'm going to make I'm going to go back into the Walker and instead of doing random with random height I need a function make R and let's do a random point and I'm going to give it that x and y right I want to have some separate function somewhere that's going to take care of this for me actually I'm going to say if X this dot pause equals create vector at that x and y so if you get an X and a y otherwise let's pick a random point now I'm sure there are lots of clever ways I could write a function to give me a random point along the edge but the way I'm going to do it as as follows I want four possibilities top right bottom or left so if if I'm picking something along the top I want a random X and I want to return create vector that random X comma 0 else if I equals 1 let's just say that's the bottom and again we could make this more efficient let's make that along the height else if I equals 2 I want a random Y and I'm going it along the left side and in all other cases I want two random point along the right-hand side so let's run this now you can see that I'm only picking random points that are coming from the edge which i think is also going to work a lot better because I don't want to pick random points kind of inside the thing that I've already created so here we have now diffusion limited aggregation go go go I wanted to finish so one thing that I kind of miss so this I got to come up with a clever solution to figure out when it's done because you can see it's kind of it's now like just infinitely picking points along the edge and it kind of went crazy a little bit when it kind of got to the edge so but I kind of liked the idea of actually just for right now never not adding not adding any more walkers and starting with a fixed number of points so I'm going to start with 1,000 points and yes it is running kind of slow but when those points are removed we got to get our first point to get stuck randomly there we go I think it's going to kind of speed up over time is my belief but and you know one thing I could probably do which might also help it run faster is draw less stuff or what might be better is to just add you know add one point at a time so I think really the way that you would do this is I might let's just do five but like have like a thousand iterations here's another way to doing it yeah I like this is nice I like looking at it this way too so there's so many different ways to can visualize this I'm kind of stuck on it and I encourage you to sort of enjoy coming up with ideas on your own but what I what I do want to do is what I do want to do is let's let's go back to this what I do want to do is kind of look at how how you can vary this algorithm to get different start different kinds of patterns so let's go back and look at the paul bork website and let's first sort of see a couple things one is hat right now this is essentially what I'm getting you know I could do a better job of kind of thinking about the layout of the space and making the algorithm more efficient or that you know letting it run for a long time and encourage you to do all that I'm going to release a processing version of this which maybe runs for a while like renders the final version to an image something to remind me in the comments if that doesn't exist so we can make a version that looks like this the browser it'll kinda I don't want to like shut down a browser window but let's at least first think let's try to see how it would create this pattern so this pattern it's all about the seed points what if I fill the tree with points along the bottom so let's let's fill in the beginning instead of having one point what if I say for VAR i equals I'm going to say power x equals zero X is less than with X plus equals R times two and what I want to do is say tree dot push new Walker at X comma height so I just want to create a whole bunch of points that I start with at the bottom and you can see what happens when I do that now what if I want I think I want all my Walker's actually just to start at the top so let's go now to the Walker file and what if I basically say at you know what let's just always have I'm going to comment all this out and let's always have all the Walker's start at the top so I just changed this function of all the walkers start at the top whoa what did I do wrong I'm back there was a major problem with my code which is right here I was saying I'm so clever and I can check to see if the user gives it an x and a y so if X and if there's an X and a y make a vector out of the X and the y otherwise make a random point well it turns out that if you give it the value 0 right 0 evaluates to false so when I say make a walker at 0 comma 0 for example or 0 comma height it's actually going to not make it at that point but give me a random point so what I actually need to do here is say as long as X is not undefined and I'm sure there's a more elegant way of doing this but I'm just going to fix it right now and saying and Y is not undefined do this and that should I think I have some sort of browser having crashed problem infinite loop problem and also I think I can do away with this third argument stuck and just say this dot you know it's if I'm making it at a particular point it's automatically stuck otherwise it's automatically not stuck just to be clear about that and now we should see ok so here we go now we have starting all the points at the top and they're going to go they're going to kind of get glued at the bottom so this we should see some kind of pattern as this runs for a little bit you know speed ahead in this video if you want you know listen to some music while you're waiting come on trees grow so so we should see a pattern that's coming much more like what we've got here in ups I'm in the wrong place what we've got here in this particular example so here's another so come up with your own scenario what if you start with points all along the edges what if you start with points along a radial path in a circle or have points moving back you have points starting around the edge of the circle and your random walkers all start in the center you get something like this now but I do want to add something else here which is look up too much music flag okay I do want to add something else here let's just see how it's going you can see it's moving along here we're growing our trees I want to go do I want to go back to Paul Bork site you can see something here which is interesting look at this particular image now as I scroll down look at this particular image and look at this particular image there's a kind of density or fuzziness or almost hairiness to it and you can what you can actually do is it's called stickiness you can have a probability you can think of when it touches something that's part of the part of this tree there's this diffusion limited aggregation thing that's growing you could have a probability that it gets stuck rather than automatically getting stuck so I think that's something interesting to add for example if it's within this threshold Joe don't just automatically have it get stuck but pick a random number between 0 and 1 and if that random number like I stickiness is now 10% then I could actually have it get stuck and unfortunately we didn't get to see how that was going let me see if I can make this run a little faster there's a couple things uh so I'm gonna I'm going to give it more iterations and more max random walkers um the other thing that I could do actually that I think would really help is I could have the walkers as they walk not just I could have them only ever walk down so I could actually say I'm just going to comment this out VAR velocity equals create vector some random amount between negative 1 and 1 and then some random amount between 0 and 1 so that these the the random Walker's only ever move down boy they move down much too fast I guess I should maybe I should wait it just a little bit something like that well ok hold on too many this was a nice idea that I had that doesn't seem to be working out very well there you can sort of see I don't know if this was a good idea or not but you can sort of see how if I have them randomly moving down why do they always go back up to the top am i oh I'm adding them back in again that's making it run slower so yes I wanted to take that out actually and you can sort of see anyway you can do that by varying lots of the algorithm I mean when I when I publish the code for this I'm going to make you a nice clean version that works really well because there's so many variables you could play with here okay I want to play with one last variable so look how slowly like come fall Walker's go to the bottom stick to the aggregation pattern oh okay so let's do one last thing what I'm going to do now which I think will be particularly interesting and is try to recreate this pattern notice how the walkers at the center are larger than the ones on the outside you can see this one as well I didn't get to do the the probably didn't get to see that the probability thing play out let me take that out for a second and so what I want to do now before I leave you if you're still watching is I don't want to have R as a global variable anymore I want to have each Walker have its own variable so I'm going to make our 32 and I need to look for anywhere that I reference it this dot our other dot R right now I'm also importantly checking my own radius against another radius or others index I dot R and then I also want to draw it with this dot R this dot R so one thing that I could do which is and then I want to go back to the center the version where it's all we're starting in the center which i think is a bit easier to kind of work with right now so I'm going to take out this tree that starts off the bottom let's just make sure this still works whoa look at these so if I make them really quite big that was kind of interesting let's make this eight okay so you can see what this looks like now and this is working again now with with with just sort of larger circles and I kind of would like to just also when I draw them I would like to give it a little bit of alpha here I think would be worth seeing let's just a little bit of Alpha okay so okay so now we have the basic core algorithm happening and you can see all of these Walker's getting stuck so what I want to do I think which I think would be interesting is I'm going to I'm going to make the maximum number of walkers just ten but I'm going to increase the iterations by ten to a thousand so these are the walkers now sticking one at a time now there are only ten of them so ten of them are going to get stuck that's all we're going to see but now what I'm going to do is I'm going to each time I delete one from the array I am going to add a new one with a smaller radius so what I want to do is let me get the ups let me get the radius of the last one in the array this might be eight and I'm going to make a new walker with oh boy I want to make a new Walker with up that that radius times 0.5 so half the size the problem is now I need to make the Walker be able to be created now with a radius but at a random point so I think one thing I need to do one thing I could do actually this is better is I could say if arguments.length equals two that means I've gotten two arguments in x and a y then create them then create a a walker with a radius of eight otherwise then create it with the radius and then otherwise if yeah otherwise create or the rocker with the radius of the first argument so if you have less than two argument so this is another way I could just check that arguments where I have a video tutorial about the Hat otherwise I can I can get it I can make one with us particularly Asst and so let's see let's see what happens here okay so where am I making Walkers ah so this is with I forgot no no no no so with way or else if arguments.length equals one else now with no arguments right then the position is random the radius is 8 and stuck is false so now the other what just happened here back I realize there's a problem here where I have actually I'm passing it three arguments because I had an extra straight true from before so let me take that out and you can see this is working now strangely enough though the the walkers are getting like really really really small really fast and I just realized that's because what I want to do is get that before I start adding a whole bunch of them I want to get the radius of the last one there because when I add one get the raised to the last one they're getting smaller is fine let's let's just make them go down by 75% so you can see here that the walkers are getting smaller as I added them back in and maybe that's like too much they just get smaller so quickly so let's see what this does and my yeah so you can see over time as I'm adding more and more walkers in they're getting smaller and smaller and smaller we could also do something now while we're here let that run for a little bit let's see if I give it 50 at a time well it kind of perform okay so one thing that I want to do is uh and I actually could just have every Walker in sequence be actually a little bit smaller than the previous one that might actually be a better way to do it because I could have like a radius counter and and that's kind of a yeah let's do it that way actually let's try this I want to have a radius of starting radius starting rate hike I should just say radius equals I can have a starting radius just for that Center one that's fine radius so I want to have a starting radius of eight and whenever I make a walker I say radius x equals 0.99 so shrink it a little bit shrink it a little bit and then there's another place where I make new ones which is here shrink it a little bit and then actually I can take out this idea of the argument because I just going to use a global variable I don't love this anymore I would just use a global variable radius that's always shrinking to go back and put that in here and have this always be radius radius so there is no there is only back now I've sort of simplified back to just two cases I either getting an X and a Y and this star is always just equal to that global variable rate I don't like now how I've done this but we're going to do it this way anyway so you can see every single one is like one percent smaller than the previous one which is kind of interesting because we're getting sort of they're actually not exactly in order so that's not what I intended to happen but we are seeing sort of an interesting result from this and they're getting smaller and smaller and smaller and then I could also say what I like about this is I could I now have sort of like a terminal point where I can say if the radius is less than one only whoops only bother to do this if radius is greater than two so now we actually like I don't want to have circles where the radius is less than one so now we actually have a terminal condition for this algorithm and I also now want to add one last thing which is coloring them so and you know I could actually so the other thing we could do is I could have I could map their hue I could map their hue so I could say I could say colormode HSB and in the Walker object itself I've got to add this in I could say fill I could I could say the hue is mapped to the radius which goes kind of between like zero and eight to between zero and 360 and I could give it that that color and I think I'm actually going to say no stroke and let's forget about the coloring it based on whether it's stuck or not and I have an error somewhere so we can see now I do not actually so I probably should order their color based on when they get stuck but this is kind of interesting nonetheless and you can see as they're getting smaller and bigger and you know I don't know what just why it just stopped right there oops but you can see I'm going to clean up this code and give you a working version I might change the order around the colors I'm going to a very good at crashing Chrome but you can see sort of the ideas behind this particular algorithm I don't really my time is up I think because this is going on for way too long I don't have a good perfect version of this to show you but I will I will include that in the the link from this video to the source code I'm going to make both a p5.js and a processing version of this so I can do kind of like a higher resolution one that kind of generates it just saves it to like a JPEG so you can see how that works maybe I'll come back and do another video follow-up about that but now you can see sort of the basic idea and the implementation behind this particular algorithm that's on Paul porks website okay thank you for watching and I'll see you in another coding challenge dude back for a quick addendum I actually I kind of cleaned up the code a little bit it's making it work a little better now I had two big things that I missed one is that it was good it was crashing the browser I think I need to point this out because I had this while loop that was always trying to fill it I was trying to fill it if it ever got less than a certain amount but I didn't allow myself to add any if radius was below a certain amount so it got stuck in that while loop so I fixed it to just say only do the while loop if radius is greater than one and the other thing that I did is I added a huge area below that each time it gets stuck I increase this sort of global huge area below you can see now the shoe is sort of assigned to the order in which it gets stuck so this isn't doesn't exactly match what you see on the these particular scenarios but I bet you with a little bit fiddling and tweaking of the algorithm you would get something like that so give that a try and if you could if you make more beautiful and interesting versions of this think about ways of optimizing it of where you start the walkers how many you use how you check to see if they're near something will come back and I'll make some improvements to this okay this is really the end now goodbye

24 thoughts on “Coding Challenge #34: Diffusion-Limited Aggregation

  1. 36:30 You've fixed this in the GitHub version, but for those just watching the video checking if two circles of different radii overlap should've used

    sqrt((x1-x2)^2+(y1-y2)^2 < r1 + r2
    (x1+x2)^2+(y1-y2)^2 < (r1+r2)^2
    (x1+x2)^2+(y1-y2)^2 < r1^2 + 2 * r1 * r2 + r2^2

    Although, I believe my 2nd inequality here is is actually slightly more computationally efficient than the 3rd inequality (which is what was used in the GitHub version) as there are fewer multiplications and additions in it (replacing all occurrences of a^2 with a*a of course).

  2. 39:07 It is possible to pass "undefined" parameters.
    i.e. Walker(undefined, undefined, 10);
    The function definition may use Default parameters:
    Walker(x = random(1.0), y = random (1.0), r = 8) {…
    When 'undefined' is passed the default one is being used.
    Not sure if it was possible back in time video was made.

  3. 26:48 Simpler way to generate Walkers on the edges is:
    1) Generate random position in 0..1 range
    2) Round() X or Y (only one axis per walker, you could use random or toggle)
    3) Multiply on Width/Height

  4. It really surprised me how much time a square-root-calculation costs! I definitely try to avoid them in the future…

  5. The best way to move the particles randomly is by using direction as a reference and then choosing a point randomly between lets say 15 degrees to the left of current direction and 15 degrees to the right of current direction. This way the particles wont suddenly move backwards, instead they will have to follow a smooth path in order to change their directions. In simple words, you can restrict their motion beyond certain angles. I think it will help make diffusion limited aggregation faster.

  6. @22:39 You have just stumbled upon why Rational Trigonometry makes a ton of sense to program with. No square roots just quadrance as the measure of separation.
    You will also get notions of "space" and "time" for free as chromogeometry encompasses both of those types of geometry(red, and green geometry).
    Read a little/watch a little Norman Wildberger and it will change you Coding Challenges forever… (NJWILDBERGER)

  7. I nice idea would be to have the "walkers" also stick to each other. So whenever a particle hits anotherone it will stick. You could add types of particls (to simulate different atoms…). Very nice. What is really like is this spirit: change some here and there and experience what happens. A experimental approach to computer science.

  8. Have made it this way before in processing after watching your video then came back to the problem and realised its easier to use a boolean value that i called moveable, made it much faster and only required a single array of particles, also speeds up the more particles are not moving 😀 dont know where i should post the code if anyone wants to see

  9. All this talk of random walkers and I know it's a cellular automata, but I remember you did kinematics and I saw fish like 'swimming behavior'. Could you consider doing a simple walking figure animation

  10. I feel that checking the distance is making this algoritm so slow, if you make the size of the particles 1 pixel then you can make an array of stuck positions and if the particle get stuck you add to the array of stuck positions the neighbors positions of the particle. With this the algoritm will run faster when you have a big tree

  11. weird suggestion : for getting a random point on the edge, try using this: map(floor(random(0,2)),0,1,0,width) and same for height..

  12. I did these animations with JavaScript in 2015, also using Paul Bourke's "paper".
    * Builds from the center: http://codepen.io/DonKarlssonSan/details/EVZENz/
    * Builds from the sides: http://codepen.io/DonKarlssonSan/details/avwemr/
    * Builds from the sides, visualizing the walkers: http://codepen.io/DonKarlssonSan/details/MavaeJ/
    * Builds from the bottom of the screen: http://codepen.io/DonKarlssonSan/details/BopXpq/

    Instead of storing the stuck walkers in a flat list I use a 2d array to keep track of the stuck ones. The 2d array has the same size as the canvas, that way I don't need to loop through a flat list to check for stuck walkers – I can just index them directly like tree[x][y].

  13. I love this channel, and i find it amazing that it's grown so fast and to such a big size. I'd be interested to know the average level of expertise your audience has that are watching. I only ask because you go through some pretty intermediate/expert topics, and little for a beginner programmer to start to learn with. Just curious if the little explanations you give on why your doing certain things, is enough for a beginner to pick up on and understand the bigger picture.

  14. I think something that would give a good result is being able to change the radius of the walkers while they are moving, not just when they are created. You could also tie the radius to how many walkers have become stuck. (You might want to tie this to a logarithm so they scale a bit nicer.)

  15. Did my final year physics project on DLA… did it in python, first real program i've made , was replicating nanotubes undergoing DLA and trying to get some fractal dimension numbers/trends from different "nanotube" aspect ratios. it was an interesting projects, my results were fairly shit because i ran out of time but I might revisit it sometime.

Leave a Reply