(bell rings)
- Yes! It's another snowflake coding challenge.
This is my third holiday snowflake challenge,
and in this one I'm going to, once again,
make an algorithmic snowflake and I'm going to
render in processing of the Koch snowflake,
otherwise known as the Koch curve, Koch star, Koch island.
It's a mathematical curve and one of the earliest
fractal curves to have been described.
I'm just reading the Wikipedia page
by this Swedish mathematician Helge von Koch.
And I think I'm pronouncing that correctly.
All right, so how does it work?
I'm going to just show you over on the white board.
So the idea of the Koch snowflake,
and this is a recursive pattern that we're going to apply
over and over again on a line,
and actually there's something really kind of
crazy about this that I do want to talk about,
maybe towards the end, the property of this curve is insane.
So if I have any line, right,
the rule that I'm going to do is I'm going to take this line
and divide it into thirds, okay?
So I take the line and I divide it into thirds.
Then the idea is to erase the middle section
and, as if there were an equilateral triangle here,
render these two sides of the equilateral triangle.
And you get this, the idea being that
we've gone from this line to this,
which we would then go to, we would do that again
to each of these line segments
and again and again and again.
So this is will be like a Koch line or curve.
But if we start with this pattern
that you might want to, after watching this video,
make your own version and try starting
with different patterns, and there's all sorts
of variations on this that you can do,
we'll end up with something that has
a quality like a snowflake, yay!
Okay, so let's get started.
And you can see this described right here.
And in theory, if we do this correctly,
we're going to end up with something that looks like this.
All right, so I'm going to use processing.
I will also create a JavaScript with p5.js version of this.
The code for both of those should be
in this video description linked
whenever you're watching this.
But right you'll have to (mumbles)
I made an example for this many, many years ago.
I'm sort of figuring it out.
So I think what I want to is I think I want a class,
and I want to call the class a Segment.
And I'm definitely going to make heavy use here
of I think of the PVector object in processing.
It's all called p5.vector in p5.
It's an object that holds an x and a y value,
also a z value and a lot of mathematical operations
that you might typically do with vectors,
and you can find in my other videos
about what is a vector if you're so interested.
Okay, so in the segment constructor,
I'm going to give it a start and an end.
I think I want to call these a and b.
So it's going to have a PVector a and PVector b.
Who's to say what's the start and the end of a line?
Is this the start, this the end;
or this start or is this end?
So really a and b, and I'm just going to use
as the arguments a_ in b_ as what gets passed in.
I don't know if that makes sense.
I'm also going to be very careful and make sure
I copy the object because I think
that might become necessary.
So basically the segment is just this thing.
So what I need to do then, if I have a line segment,
I need a function that takes one segment
and makes it into four.
So I don't know what to call that.
Generate maybe?
Let's call this generate,
and it's going to generate an array of segments.
So this is now a function that returns in theory,
I'm just going to put return null at the end
so it doesn't give me an error,
this function should return an array.
I'll call those the children segments.
I don't know if that makes sense, but generated or new.
Let's just call it Segments.
Let's call it children as a new array
with four spots in it.
Right? So the idea here is that
each one, a segment has a starting point
and an end point, and then it should generate four sub ones.
So let's go to the main program for a second.
And what are we doing?
I guess I could make a snowflake class,
but ultimately what I want is an array list of segments.
Segments equals a new ArrayList full of segments.
And then I'm going to say background zero, stroke 255,
and I'm just going to draw them all.
So for every Segment s in segments, say s.show.
And this is the really easy part
because if I have a function called show, oops,
to show a segment is just to draw a line
from a.x, a.y to b.x, b.y, okay?
So this is the idea.
A segment is two end points of a line.
It could draw that line, and then somehow I'm going to have
to generate the sub lines that I haven't figured out yet.
So now if we do this, oh, well let's add a segment.
So I can call this like, I can say segments push,
and I'm going to say...
No, not push.
Push is the name for adding something
to an array in JavaScript.
I'm getting very confused.
Add, so let's make two PVectors,
and I'll make them somewhat arbitrary.
So I'm going to say like zero comma 300
and PVector b is a new PVector that's at a 300 comma,
oh no, 600 comma 300.
So if I create a new segment between a and b,
then I should see it.
There we go!
So there's my segment.
So now what I should do is I need to somehow,
let's actually put this in a...
Let's put this in a variable called start
because I'm curious.
What I want to do is I want to just test out my algorithm.
So I'm going to say segment children equals start.generate.
So I just want to test out my algorithm once.
So I make that starting segment,
I add it to the array list and now I just want to
generate before child.
It's a little bit silly to call them children.
It's kind of like a parent-child relationship
in the sense that the segment gives birth
to four new segments.
So okay, so now I can start doing this work.
So I really just need to figure out the math
for like if I label these,
if I label these like A, B, C and D.
Let's do A and D first.
That must be the easiest, right?
So let's do segment A.
So one thing I could do is I could represent
this line segment as a vector.
So as a vector that points from A from B.
Because if I do that, I could divide the magnitude
of the vector by three and then move that distance
from A and move that distance from B,
and now I have, I should label these like one, sorry, two.
And I probably should have counted from zero
to three and four, right?
This is A and this is B starting out, right?
So if I can get that vector, shrink it
and then move from here, that gives me a new segment
between this A and this new point,
and I can also take it this point to the end.
So that's going to be easy.
So first what I want to do is I want to make a vector,
which is the difference between b and a.
Then what I want to do is divide that vector by three.
So I want to just shrink that.
I could divide it by three.
And then for segment one, I need a new point,
a new point like so, b1 I'll just call it.
The naming here, I've really got to think about that.
And obviously... ♪ I will refactor this later ♪
♪ You know I will refactor this later ♪
Is...
♪ I will refactor this later ♪ adding to a that v.
And then children zero is a new segment
that goes between a and b1, right?
Again, this is really weird what I'm doing here,
but I'm calling this point now b1, okay?
And maybe this point is now going to be a1,
because I'm going to use it to make a line segment to this.
By the way, you might not realize watching this,
but I've been live streaming for well over three hours
and things aren't making as much sense to me
as they typically look.
So now let me do segment number four,
which is really taking b and subtracting v, right?
Subtract v from b.
B minus v, I think that's right.
And I'll call this A1,
and this should really be segment zero and segment three,
because I'm putting it in this array
so let's remember those.
So now I want to make a segment between a1 and b.
So again, this is zero, one, two and three.
And I've called this b1, called this A1,
let's just call this, let's call this c.
Okay, so now what I need to do is figure out that point
and then I'm done.
That shouldn't be too hard, right?
So how do I figure out c?
So c is actually, ah, I got an idea.
We can rotate, right?
What is this?
An equilateral triangle.
This angle is 60 degrees or pi over, pi is 180.
So that's like 1/3.
Pi divided by three, is that right?
That's 60 degrees. (chuckles)
Sorry.
Yes, okay.
So this is 60 degrees.
So if I can take this vector, which is doing this,
rotate it 60 degrees, add it to b1, I'll have c.
So I should be able to say v rotate pi divided by three.
And I might have to do negative
because the whole coordinate system is flipped
in computer graphics.
And then I'm going to say PVector c equals PVector add.
What did I call that, b1, b1 plus v.
So now, segment two is,
children two is a new segment
that goes between b1 and c,
and then I need one that goes between c and a1.
That goes between b1, b1 and c.
And segment three goes between c and A1.
And again, I might want to rethink the naming here.
And maybe some of you have good suggestions for that
and then I can say return children.
Okay, so first let's just see if this doesn't
give me any errors.
Let's just see if like I run this
and I'm going to just say like println and children.
It's not going to show me anything here because...
But okay, so that's good, I didn't get any errors
and I'm getting this sort of console log.
So this is a nice place of using JavaScript.
Ooh, why did I get null there?
So one of them was null.
I got to check that.
But this is the nice thing about using JavaScript,
is if I console log that array,
I'd be able to actually look at the object
and see what all the properties are.
It's a little trickier to do that in Java,
but why was one of them null?
Children zero, children three.
Oh, this is one.
Sorry, this should be one.
Okay, so now if I do that again,
we can see there's four segments.
I got to say perfect.
Now what I want to do is I'm not going to add
the start just to see, I'm going to say segments,
I think add all allows me to add an array
to an array list.
It's giving me an error here though.
(bell rings) All right, so I looked around
on the Java docs page for a little while.
I didn't see anything that would really work for me.
I'm sure somebody in the comments will give me
a good suggestion, but I'm actually just going
to write my own function.
I'm going to say addAll.
I'm going to get an array,
and I'm going to add it to,
I'm going to add it to an array list of segments.
I wonder if I typed the array somehow.
Oh no, I did type the array.
And then I'm just going to do a for loop.
For every segment s in array, list.add s.
So this is my own function to add everything from an array
into an array list.
So I will now call addAll all the children to the segments.
And now let's see.
Ooh, yay, that worked.
It's upside down, I had a feeling that was going to happen.
So that's an easy fix.
I can just rotate by negative pi over three,
and there we go. (bell rings)
This is the building block.
Now I just need to do this generation
after generation after generation.
So let's think about how I want to do this now.
So let's say what I want to do is
let me click the mouse and get a new generation each time.
So I'm going to do this,
and I'm going to take this,
and I'm going to make a mousePressed function.
And what I'm going to do in mousePressed
is I'm going to make a blank array list.
I'm going to make a new one.
I'm going to call it nextGeneration
is a new ArrayList of segments, okay?
So I'm making, oops, I'm making a new
array list of segments.
Oh no, this is fine.
And what I'm going to do is for all this current segments
in the array, I am going to,
I should just make this.
This would be so much easier
if I just made this return.
So this I could refactor, have this return an array list.
This was silly to make this an array
because then those could get added together.
Should I do that?
Eh, it's fine, I already have it.
But that's something you could do
to improve this code if you want.
Segment children equals s dot,
what did I call it, generate?
Then I want to say addAll the children
to the next generation.
And then I want to say segments equals next generation, right?
So basically, oh that's not a function, right?
I need to pick a new array because the old segments
don't get kept.
Each one just makes a bunch of new ones and gets added.
So what this should do now, click, click, click,
click, click, there we go.
Look at that, there's that Koch curve, all right?
And some people in the chat are giving me
some good suggestions.
All right, so we need to turn this into a snowflake.
But first I want to talk to you about something crazy.
Please, please humor me for a second.
This is called the monster curve for a reason.
And why, why?
This is one of those mathematics things
that really excites me.
And let's see if I can explain this.
Let's say this line segment has a length of one.
Think about for a second what is the length now
of this, this the Koch curve, it has length one.
At generation zero, it has length one.
At generation one, what is its length?
Well, if this is 1/3, each one of these is length 1/3.
So it's length is 4/3.
Now what is its length?
Oh my god, this is going to be so hard to figure out.
But if this was 1/3 then this is 1/9,
so this is 4/9 times three,
the length would be 12/9.
Is that right?
No, no, that couldn't possibly be right, right?
This is one, this is 1/3.
This is 1/9.
And then we have, no, no, no, no, 16/9, right?
So right, that was right there.
This part is 4/9, but there are now three things
that are all 4/9.
Four things are all 4/9.
So we get 16/9.
This number, actually if we keep doing this
over and over again and we could probably create
an equation to do this pretty easily,
somebody else on some other YouTube channel will do that,
this goes to infinity.
I'm not going to prove that to you right now,
I'm going to let you try to figure that out on your own.
What's crazy about that?
So as you do this over and over again,
how much paint, if you could draw the Koch curve
to the infinite generation, it would fit.
It would fit here.
It's never going to not fit here.
But how much ink would I need?
I would need an infinite amount of ink.
So that's the kind of mathematical paradox.
How could we have a curve that infinitely long
fit into a finite space?
Think about that.
Now we don't have to worry about that.
That problem is irrelevant for us
because we have pixel limitations, right?
I mean, at a certain point, I can keep clicking
but I'm not going to get any more resolution out of this
because I have a limited number of pixels.
But that's an interesting.
And it's also going to get really, really slow,
one thing you could do is you could think about,
this could be a challenge for you
after you watch this, is could you make
an infinitely zoomable ones?
This is, by the way, four divided by three
to the zero power, generation zero.
This is four divided by three to the oneth power,
four divided by three; and this is four
divided by three squared, 16, nine, nine.
You can now imagine what the next generation would be.
Four divided by three cubed.
So this is actually the equation
for expanding out the Koch curve.
Okay, so now what do I want to do?
Ah, what I want to do is make a triangle.
So I'm going to make a triangle.
So let's think about this.
This shouldn't be too hard.
The first segment would be, so let's do a
is going to be at like zero comma 100.
B is going to be at width comma like 100, yeah.
And then all I need is c.
This should be an equilateral
triangle though probably, right?
Let's just do this first.
Let's do this at like 300 comma 600.
(chuckles)
Segment one.
Segment two, segment three, a to b,
b to c and c to a.
And I want to add segment one,
segment two, segment three.
Huh, did I like get that right?
Here we go, there it is!
(whistle blows)
The Koch snowflake.
I should give myself some more space.
Oh no.
I'm so brain dead right now.
I'm going to translate down by a hundred.
There we go, there we go.
I'm sure somebody could come up with a nicer way.
So there's so many possibilities here.
These are all individual objects in a big array.
So you know what, I could actually move them all around.
I could have them all fall
and I could animate them back into place.
There's so many possibilities there.
I could color them.
There's a lot of variations on how,
I'm going to go to here and I'm going to show you,
there's actually an interesting post here
which links to this page which shows
a bunch of ways you can,
variations on how you can draw this.
So this is something you could attempt
after watching this video.
So think about color, think about animation,
think about making many of them, but this is
(whistle blows) the Koch
Koch, Koch
(whistle blows) snowflake in processing.
And oh, so when you make a variation of this,
check the video description,
go to the link to the codingarray.com,
there are some instructions for how you can
submit your variation of them.
And then after the new year on a live stream,
I will share a whole bunch of all these
different kind of snowflakes that people have made, okay?
Thank you very much for watching,
and I'll see you next time.
And yet, there is more, an addendum here
which is that if you have an equilateral triangle,
if the height of an equilateral triangle
is the square root of three divided by two
times the length of the base.
So actually, I very quickly added that to the code.
Thank you to Simon who reminded me of this fact.
And you can see here, I am now setting
the last point c as the length of the base,
which I know by the way is 600.
So I could just said 600 here.
But I'm getting that distance just to be sure.
The length of the base times the square root of three
divided by two, and that's where I'm setting that point c.
So now here is finally the Koch curve
with an actual equilateral triangle.
(majestic music)
(upbeat music)