Coding Challenge #16: L-System Fractal Trees

hello welcome to another coding challenge this is a coding challenge all about L systems I'm going to make this beautiful tree I think it's a little beautiful but you will hopefully make it even more beautiful one after watching this video but I'm going to make this tree up here in the browser using HTML using javascript and so what do I want to do here I want to define what an l-system is look at how the algorithm works and then build the code for rendering an l-system from scratch ok so what is an l-system L the L stands for Lindenmayer for Irish did Lindenmayer a hungarian botanist who developed this algorithm for modeling cellular growth so how what is what you can read more about L systems I've got the sort of Wikipedia page here as a reference but what I'm going to do is just kind of define for you the guts of it that's sort of like the actual terminology associated with an L system so an L system is actually all text-based we're going to use it to generate graphics but at its core it's just text-based and it involves a few things it involves an alphabet for example my alphabet might be the letters A or B these are also sometimes known as variables it involves an axiom meaning what is the beginning of our L system err else Testim begins with an axiom for example an axiom could be a and then it involves a set of rules meaning something like a becomes a B and B well hold on look I have actually the one that I want to start with which is sort of a becomes a b and b becomes a ok so look at that I just wanted to use since the up and B becomes a I don't know I don't the camera switch while I was doing that but so it has a set of rules so what does this mean so an l-system is a recursive way of generating sentences over and over again using string replacement so this is the set of elements in the L system and we start with the axiom a and this is generation 0 and in generation 1 we apply these rules to it becomes a be a becomes a beep and now we do this again I have generation to a be a becomes a B B becomes a and generation 3 Hey because I'll stop doing this eventually a becomes a B B becomes a and a becomes a B hopefully I did this right item manually as a human being kind of doing this string replacement I could easily get it wrong or contect me forever be very tedious this is the kind of thing a computer is perfectly beautifully well-suited to do and what what we have here is with this type of system these kind of recursive fractal like structures appear in the text the resulting text itself so it's up to you to say aha I have this system I've designed it I have an alphabet I have an axiom I have a set of rules I should write rules here and now I've generated these sentences what do I do with the sentence it could be read it as poetry a B a a B or perhaps you use it to be a song a B a a B or with rhythm or you tie it to graphics you know this means a dot this means a square and you draw a pattern on the screen so you could imagine there's a lot of ways you could interpret the L system and what I'm going to do is first program just this string replacement structure and then I'm going to show you how you can use a certain kind of alphabet to indicate things like draw a line forward turn right turn left and create all sorts of patterns in particular plant like patterns on the screen ok here we go coming back over here so we've got this down now and let's start writing the code for it so this is the what I want this is the one I want to do first and I called it variables here so I'm going to go to I've got a JavaScript I've got a JavaScript file here I'm working in the browser using the p5.js javascript framework and i'm going to just put this here at the top and comment it out so what do I want to do I want to start with and axiom and I'm going to say that axiom is a now I also need to have some rules so what would be a good way of creating a rule in JavaScript a way I could do that is I could make it a JavaScript object like I could say a whenever I see a it becomes a B and I could say that's rule one and then I could say rule 2 is B becomes a so now again this is a highly manual way of doing this and a and B are my own made-up things and oh you know it's a little bit confusing that I did that because the alphabet so maybe I should I just it's fine I'll use it once I get to the next example it'll be a little less weird-looking but the point is a becomes B so I'm looking for a and whenever I see a I substitute it with B so now let's just I'm going to write a function and call it generate and what I'm going to do is in a set up I'm going to say I'm going to say no canvas and I'm going to use the P Phi and I don't need draw right now I'm going to use the P Phi function called create P which creates a paragraph element in the page pause get it back okay so I'm using create P and I want to say create P axiom and I'm going to run this now in the browser over here and we can see there we go I have the letter A appearing so the first axiom has appeared so now what I need to do in generate is what I want to say is I need to look at every letter in the current sentence and use and substitute using the rules so I'm going to say for int I equals 0 I is less than axiom dot length I plus plus and you know what I want to have a new variable and I'm going to call it sentence and sentence is going to start with the axiom so I'm going to say sentence dot length I plus plus then I'm going to say the current current card character equals sentence car at I so what I'm doing is I'm looking at this is a something you do with strings in JavaScript I can look at each character one by one and pull it out and I can say here if current equals rule one dot a then and now what I also need I need next I need next sentence which is an empty string so what I need to do is build up the next sentence if current equals the a part of a rule then next sentence should get B so if it equals a substitute be in else if current equals rule one B next sentence plus equal rule sorry Rule two a so right if it matches a from rule one substitute in be from rule one if it matches a from rule to substitute in be from rule two otherwise just keep it so there are cases where you have a character and it doesn't match any of the rules in that case you just keep that same character so keep current in so if current is if current is a is rule one say put in rule ones B if current is rule tuesday put in rule 2's be if it's not any of the rules just keep current and then at the end of this the sentence should be now then the actual current sentence is now the next sentence so I'm going to I'm going to Sten I'm going to say create P sentence so now and then so when do i generate so let's make a button VAR button equals create button generate so create button is a function that's in the p5 Dom library and attach an event to it and that event is generate so I want whenever I press the mouse on that button I want to call that generate function so I want to go something or remove some of this unnecessary styling and now I'm going to refresh this page whoops so sketch is line 20 I have some sort of error oh I used int it should be var and I've got okay so now you can see here I have this generate button and I have the axiom there and I see a B a baa-baa B and you can see I hopefully this is right I'm going to generate a bunch of times and you can see I'm generating sentence after sentence here so so this is the idea so you know I could do this forever and ever and ever I'm sort of under I'm sure to curious why it's not like word wrapping but I'm sure that's just some sort of CSS styling that I could fix to make it a wrap to the next line or whatever anyway let's not worry about that so you see that this is the idea that works all I need to do is create an algorithm for generating a for starting with an axiom having a set of rules and iterating and doing string replacement now III did some kind of sloppy things with that just to sort of like make it work it would make much more sense for this to be an array and for me to say something like rules index zero equals this and rule in it and rules index one so it makes much more sense for me to have the rules be in an array because there's no reason for me to be checking both of those as separate else if statements when I could really just say for I equals zero I is less than rules length I plus plus and I can't use I because I already used I so this has to be J so what I want to do is instead of checking each rule individually because what if a else system I have eventually has like ten different rules this will become a mess so in that sense I can say if current equals which ever rules index J then next sentence should equal rules index J dot B and then what I can do is I can put a break here so I can once I can sort of get out of the loop as soon as if I because more than one rule can't be true so I can get out of that and then what I need to do though however is I need to figure out how way of adding if none of the rules if none of the rules are met are found then keep that current character so one way I can do that is I can say found is false and if I found one of the rules found is true and then at the end once I've gone through all the rules I can say if not found next sentence plus equals current so this would make sure so this should be identical to what I had before and if I run this we should see the same exact result now we aren't really sure one thing I should do to make sure this is really working is I should change this to have this actually become like ABC to make sure the C's continue through there at which they do so you can see this is still working so now I have a bit more of a flexible system by which I could just create an array of rules it doesn't matter how many rules it'll still work okay now we've got the basic mechanics of the L system down the next thing I need to do is do something more to draw from it so what I want to show you is I want to now use this particular L system so these are the letters of the alphabet for this L system F plus minus open bracket close bracket we start with F and this is the rule seems like a crazy rule but it's actually gonna do something quite interesting so what I want to do is here I want to start with F and actually I only have one rule so this is actually a much simpler scenario which F becomes this and now I should be able to run this start with F and you can see now it's now it's wrapping but you can see this is what I get even just in the third generation this is what I get so this looks totally insane but this is actually incredible these are entire instructions for growing this elaborately complex plant like shape you know and this is really magic and you can get the computational beauty of nature or algorithm beauty of plants there's all these books and research where you can find countless numbers of these kinds of L systems or you can invent your own to create these patterns but let's make this one happen so all that we've done so far is we've only made a program that renders the text to the screen now what I need to do is have a program that reads the text and draws to the window so how do I do that so I'm going to go back and I'm going to get rid of no canvas and I'm going to say create canvas 400 400 and I'm going to say background 51 so let's make sure there's now a canvas appearing great this is still working but now I want to see is every time I hit generate I want to read this text and draw to the drops of the screen based on it okay so so let's do that let's now write a function and I'm going to call this function turtle so I'm calling it turtle is because I'm going to interpret this particular text like a turtle graphics engine what is turtle graphics so the concept of a turtle comes from an old programming language called logo or you could write code to move a tribe to instruct a turtle how to move around the screen and as the turtle is moving around the screen the turtle is drawing lines so you could say things like f means move forward so move forward and draw a line plus means turn right - means turn left and what's especially sophisticated about the turtle graphics engine that we're about to implement is that these brackets mean save where you were so you could be a turtle moving around the screen at any point you could say save and you could keep moving and then you could um then you could say restore and go back to there and move from there and that's going to create a lot of sophisticated possibilities so what I need now is in the code is to write a loop and just go through every single character in that sentence and I'm going to say current again equals sentence car at AI so now what do I need to do if current equals F I need to draw a line zero zero zero negative length so this is somewhat arbitrary but I'm going to start with the default mechanic that I want to have this be my original position and I want to start drawing the line up so from 0 0 up to they are then I want to say else if current equals plus then I want to say rotate by I'm going to I'm going to try pi divided by 6 which I don't think is right but I'll just start with that else if current equals minus rotate pi divided by 6 on the negative direction else if current equals bracket open bracket push push is the function in p5 which is save the transformation state so I'm going to move around with translated rotate and push is going to be save else if current equals close bracket I'm going to say pop so now I'm going to pop so this is everything like this is the thing I don't even have to really like hit much about it like all the magic is happening in this L system itself I just have to write the instructions to know what to do but I didn't miss something so one of the things that I have to do is when I draw this line I then have to translate to move to the end of the line so in addition to drawing the line and we come back over here I need to say translate 0 negative length so I need to move to the end of the line so that I kind of draw the next line or rotate from there and that sort of thing so and then we need this to be a variable and say length equals 100 so what I want to do now is skewed let me find there's so much stuff going on here what I want to do is whenever I generate I want to call so call turtle so I'm going to call turtle once and set up just so the axiom is drawn and then whenever I after I finished generating I want to call turtle again okay so here we go so I know I don't see the line okay so let's let's see if we can figure this out turtle foot first of all draw let's draw the background again and then do stroke 255 oh I know why we don't see anything so where is the line being drawn it's being drawn from 0 0 up so I need to actually at the beginning make sure 0 0 is positioned at the bottom of the window so the very first thing I need to do in setup before any time before I call turtle is I need to say translate to the middle of the screen and the bottom of the screen and oh there we go so now you see F the sentence is currently only F so all I have is that one line now look at this let me do generate and now we have F F plus save plus F minus F minus F restore etc so let's look at this now it went crazily off the screen now why did that happen something weird is going on here so let's let's investigate this back after a technical problem I added in reset matrix in this turtle function because I'm not using the draw loop this guarantees that I'll always start my translations and rotations over again each time about to draw this else system does that fix this issue just with the way that I'm doing it right now so now you'll see if I hit refresh you can see that I'm drawing F when the sentence is only F I just draw one single line forward and now when the sentence is FF Plus save plus F then I'm saying go forward go forward TURN RIGHT save go go turn right again go forward turn left go forward turn left go forward then come back then turn left so you can see we could you this is a great exercise for you to do on a Saturday afternoon outside in the park you know copy down one of these sentences and like get out graph paper and try to be the L system but you can see here now I got to do is hit generate again and something much more complex is happening but I sort of have lost the picture I don't see what's going on so a couple things are missing one is I picked a random angle to rotate by pi divided by six which isn't actually the angle to be used with this particular L system so let me first fix that so I'm going to go into the code and I'm going to make a variable called angle and in in setup I'm just going to say angle equals radians 25 so 25 degrees I believe is the angle meant to be used with this and then here I could just say rotate instead of pi divide 6 by angle and negative angle so now I have a variable I could change so let's run this again I guess maybe PI divided by 2 by 2 625 and I'm losing mine looks the same I really losing my mind but regardless of that the issue I'm gonna have to check that in a second the issue is that with more and more generations I actually want to shrink the length that I'm drawing all this stuff so it would make sense here in the generate function to each time I generate I could say length x equals 0.5 so now you can see that's how I start then next ends next then type so I had it right maybe pi divided by 6 was right all along I'm gonna do one more generation and you can see how intricate this becomes and what you know what I might like to do is just give this a tiny bit of alpha so we can zoom in on it here and generate generate generate generate and so you know at a certain point it's so much for it to draw but you can see I've got this full structure beautiful structure now you just try to imagine drawing this through some of her mechanism so I encourage you to play around with this go investigate find other else systems plug them into this example see what kinds of patterns you get the other thing that you might think about is if you watched my one of my previous videos about how to turn a fractal tree into a whole set of branch objects that you could apply physics to you can also do the same thing with this particular example and if people are interested at some point I could release an example that does that or make another video that converts this into that so thanks for watching this L system video hope you go forth and make some L systems and let me know how it goes

Channel: The Coding Train

Views: 188,896

Rating: 4.9652777 out of 5

Keywords: fractal, coding, challenge, l-system, fractals, processing tutorial, nature of code, coding challenge, object oriented programming, creative coding, object oriented, l-systems, p5.js, tutorial, p5js, processing, p5.js tutorial, programming challenge, javascript (programming language), javascript, pvector, algorithmic botany, lindenmeyer system, lindenmeyer, lsystem, lsystem javascript, l-system javascript

Id: E1B4UoSQMFw

Length: 22min 2sec (1322 seconds)

Published: Tue May 31 2016