ErnieParke (talk | contribs) m (→Coding: Did a bit of touch of on a sentence.) |
(→Coding: Added a placeholder block.) |
||

(46 intermediate revisions by 24 users not shown) | |||

Line 1: | Line 1: | ||

[[File:Droste.jpg|thumb|125px|The [[wikipedia:Droste effect|droste effect]] is an example of '''Recursion'''.]] | [[File:Droste.jpg|thumb|125px|The [[wikipedia:Droste effect|droste effect]] is an example of '''Recursion'''.]] | ||

− | '''[[Recursion]]''' is the process of repeating items in a self-similar way. | + | '''[[Recursion]]''' is the process of repeating items in a self-similar way. It can be implemented in [[Scratch]] by making a [[My Blocks|Custom block]] that runs itself. This can be used to create '''{{wp|Fractals}}'''. |

+ | |||

+ | A fractal is pattern that produces a picture, which contains an infinite amount of copies of itself. Some well-known specimens are the [[wikipedia:Mandelbrot set|Mandelbrot set]], the [[wikipedia:Sierpinski triangle|Sierpinski Triangle]] (also, but less commonly known as the Sierpinski Gasket), and the [[wikipedia:Koch snowflake|Koch Snowflake]]. | ||

==Creating the Koch Curve== | ==Creating the Koch Curve== | ||

− | The Koch Curve is a fractal that can be created relatively easily in Scratch. | + | The Koch Curve is a fractal that can be created relatively easily in Scratch. It is a piece of the larger fractal, the [[wikipedia:Koch snowflake|Koch Snowflake]]. |

===Understanding Recursion in the Koch Curve=== | ===Understanding Recursion in the Koch Curve=== | ||

Line 9: | Line 11: | ||

The Koch Curve is made of four Koch Curves that are a third of the size of the original Koch Curve. They are they are arranged so that the first and fourth are flat and the middle two point up to make an equilateral that is triangle missing one side. | The Koch Curve is made of four Koch Curves that are a third of the size of the original Koch Curve. They are they are arranged so that the first and fourth are flat and the middle two point up to make an equilateral that is triangle missing one side. | ||

− | [[File:Recersion in Koch Curve.png| | + | [[File:Recersion in Koch Curve.png|750px]] |

To make it easier to draw, the Koch Curve can be broken down into iterations, each one more complicated than the last. The first iteration is made up of four straight lines. The second iteration contains four copies of the first iteration. The third iteration contains four copies of the second iteration or sixteen copies of the first iteration. As iterations are added it gets more complicated and looks more and more like the real Koch Curve. | To make it easier to draw, the Koch Curve can be broken down into iterations, each one more complicated than the last. The first iteration is made up of four straight lines. The second iteration contains four copies of the first iteration. The third iteration contains four copies of the second iteration or sixteen copies of the first iteration. As iterations are added it gets more complicated and looks more and more like the real Koch Curve. | ||

Line 15: | Line 17: | ||

[[File:Iterations of Koch Curve.png|500px]] | [[File:Iterations of Koch Curve.png|500px]] | ||

− | ===Implementation in Scratch=== | + | <!-- ===Implementation in Scratch=== |

− | + | To be based on this project: http://scratch.mit.edu/projects/10068174/--> | |

====Basic Pen Path without Recursion==== | ====Basic Pen Path without Recursion==== | ||

− | The triangle in the center is an equilateral triangle, therefore each of | + | The triangle in the center is an equilateral triangle, therefore each of its angles have a measure of 60°. |

[[File:Equilateral Triangle in Koch Curve.png|500px]] | [[File:Equilateral Triangle in Koch Curve.png|500px]] | ||

Line 31: | Line 33: | ||

<scratchblocks> | <scratchblocks> | ||

when gf clicked | when gf clicked | ||

− | point in direction (90) //make sure the sprite is pointed right | + | point in direction (90) // make sure the sprite is pointed right |

− | go to x: (-240) y: (-179) //put the sprite in the lower left corner | + | go to x: (-240) y: (-179) // put the sprite in the lower left corner |

− | + | erase all // clear graphics from previous runs | |

− | pen down //put the pen down for drawing | + | pen down // put the pen down for drawing |

make the first iteration of the Koch Curve with a length of (480) | make the first iteration of the Koch Curve with a length of (480) | ||

− | pen up //put the pen up so movement afterwards is not recorded | + | pen up // put the pen up so movement afterwards is not recorded |

define make the first iteration of the Koch Curve with a length of (length) | define make the first iteration of the Koch Curve with a length of (length) | ||

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

− | turn ccw (60) degrees //first turn | + | turn ccw (60) degrees // first turn |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

− | turn cw (120) degrees //second turn | + | turn cw (120) degrees // second turn |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

− | turn ccw (60) degrees //third turn | + | turn ccw (60) degrees // third turn |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

</scratchblocks> | </scratchblocks> | ||

Line 53: | Line 55: | ||

<scratchblocks> | <scratchblocks> | ||

when gf clicked | when gf clicked | ||

− | point in direction (90) //make sure the sprite is pointed right | + | point in direction (90) // make sure the sprite is pointed right |

− | go to x: (-240) y: (-179) //put the sprite in the lower left corner | + | go to x: (-240) y: (-179) // put the sprite in the lower left corner |

− | + | erase all // clear graphics from previous runs | |

− | pen down //put the pen down for drawing | + | pen down // put the pen down for drawing |

make the (5) iteration of the Koch Curve with a length of (480) | make the (5) iteration of the Koch Curve with a length of (480) | ||

− | pen up //put the pen up so movement afterwards is not recorded | + | pen up // put the pen up so movement afterwards is not recorded |

define make the (iteration) iteration of the Koch Curve with a length of (length) | define make the (iteration) iteration of the Koch Curve with a length of (length) | ||

− | if <(iteration) = [1]> then //is it the first iteration? | + | if <(iteration) = [1]> then // is it the first iteration? |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

else | else | ||

− | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) //make a smaller Koch | + | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve |

end | end | ||

− | turn ccw (60) degrees //first turn | + | turn ccw (60) degrees // first turn |

− | if <(iteration) = [1]> then //is it the first iteration? | + | if <(iteration) = [1]> then // is it the first iteration? |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

else | else | ||

− | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) //make a smaller Koch | + | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve |

end | end | ||

− | turn cw (120) degrees //second turn | + | turn cw (120) degrees // second turn |

− | if <(iteration) = [1]> then //is it the first iteration? | + | if <(iteration) = [1]> then // is it the first iteration? |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

else | else | ||

− | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) //make a smaller Koch | + | make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve |

end | end | ||

− | turn ccw (60) degrees //third turn | + | turn ccw (60) degrees // third turn |

− | if <(iteration) = [1]> then //is it the first iteration? | + | if <(iteration) = [1]> then // is it the first iteration? |

− | move ((length) / (3)) steps //draw a line segment | + | move ((length) / (3)) steps // draw a line segment |

else | else | ||

− | + | ||

end | end | ||

</scratchblocks> | </scratchblocks> | ||

Line 88: | Line 90: | ||

==Creating the Mandelbrot Set== | ==Creating the Mandelbrot Set== | ||

[[File:Mandelbrot Set.gif|thumb|175px|An animation of zooming in on the Mandelbrot set.]] | [[File:Mandelbrot Set.gif|thumb|175px|An animation of zooming in on the Mandelbrot set.]] | ||

− | The Mandelbrot set is a mathematical fractal defined in the complex plane. It was named after its discoverer, Benoit Mandelbrot, and has many close relationships to the [[Wikipedia:Julia Sets|Julia Sets]]. | + | The Mandelbrot set is a mathematical fractal defined in the complex plane. It is completely self-similar, meaning that it repeats over and over as one zooms in. The Mandelbrot set was named after its discoverer, Benoit Mandelbrot, and has many close relationships to the [[Wikipedia:Julia Sets|Julia Sets]]. |

===Understanding the Definition=== | ===Understanding the Definition=== | ||

+ | In its definition, the Mandelbrot uses complex numbers. A complex number is the sum of a real number and an imaginary one, with an imaginary number simply being the square root of a negative number. Since that can not be taken, the square root of -1 is assigned the value i. For example, 3+3i is a complex number. | ||

+ | |||

The Mandelbrot set is defined as all c values in the complex plain which are bounded under iteration in the following equation: | The Mandelbrot set is defined as all c values in the complex plain which are bounded under iteration in the following equation: | ||

[[File:Mandelbrot Equation.png]] | [[File:Mandelbrot Equation.png]] | ||

− | For example, | + | First, one starts with a z value of c (i.e. z<sub>1</sub> = c). Then, when one puts that z back into the equation, it becomes z^2+c. That z is then taken and put back through the equation over and over. This is called iteration. |

+ | |||

+ | For example, let c=1. The value z then becomes 1. Once 1 is put back into the equation, the equation becomes 1^2+1, which equals 2. Once 2 is put back in, it becomes 2^2+1, or 5. Once 5 is put back in, it becomes 26. That sequence escapes to infinity and therefore c=1 is not part of the Mandelbrot set. Meanwhile, the sequence c=-1 gives 0, -1, 0, -1, 0, ect..., is bounded and so belongs to the Mandelbrot set. | ||

− | + | It has been proven that if any sequence contains a complex value that is outside a distance of 2 from the origin, it will escape to infinity. | |

====Coloring==== | ====Coloring==== | ||

[[File:Mandelbrot Coloring.gif|thumb|150px|An animation of the Mandelbrot set under iteration.]] | [[File:Mandelbrot Coloring.gif|thumb|150px|An animation of the Mandelbrot set under iteration.]] | ||

− | In a basic Mandelbrot set, white is used for a c-values that | + | In a basic Mandelbrot set, white is used for a c-values that escape to infinity and black is used for all c-values that do not. This would be the actual Mandelbrot set. |

+ | |||

+ | In most Mandelbrot sets, though, colors are used to help depict the Mandelbrot set or make it more art-orientated. Colors are not defined through an equation, but rather through the last iteration before escaping a distance of two from the origin. The iteration is then assigned a color of the creator's preference. Color can also apply to the rate of the equation reaching infinity. | ||

− | + | <!-- ===Implementation in Scratch=== | |

+ | If needed, please use this project as a base: http://scratch.mit.edu/projects/12194871/#comments-14707164 ---> | ||

− | |||

− | |||

====Creating the Variables==== | ====Creating the Variables==== | ||

− | Due to the fact that Scratch does not directly support mathematics in the complex plain, a simple workaround has to be used. Each complex number will be defined as two | + | Due to the fact that Scratch does not directly support mathematics in the complex plain, a simple workaround has to be used. Each complex number will be defined as two [[variable]]s, the real part, and the complex part. And since there will be operations based on the complex numbers, two complex numbers will be needed, or four variables. For the tutorial, these names will be used: |

− | *Real 1 | + | * Real 1 |

− | *Real 2 | + | * Real 2 |

− | *Complex 1 | + | * Complex 1 |

− | *Complex 2 | + | * Complex 2 |

Along with that, a variable Best Fit will be used to figure out the color to be used when coloring a complex value: | Along with that, a variable Best Fit will be used to figure out the color to be used when coloring a complex value: | ||

− | *Best Fit | + | * Best Fit |

====Coding==== | ====Coding==== | ||

Line 124: | Line 131: | ||

<scratchblocks> | <scratchblocks> | ||

when gf clicked | when gf clicked | ||

− | hide//so that this sprite and its clones | + | hide // so that this sprite and its clones do not show |

set y to (180) | set y to (180) | ||

− | + | erase all // preparing the scene for the Mandelbrot set | |

repeat (12) | repeat (12) | ||

create clone of [myself v] | create clone of [myself v] | ||

− | change y by (-1)//this makes it so that clones | + | change y by (-1) // this makes it so that clones do not overlap |

end | end | ||

</scratchblocks> | </scratchblocks> | ||

Line 137: | Line 144: | ||

<scratchblocks> | <scratchblocks> | ||

when I start as a clone | when I start as a clone | ||

− | set pen size to (1.5)//any other size will appear transparent | + | set pen size to (1.5) // any other size will appear transparent |

− | set x to (-180)//the left hand side of the Mandelbrot set | + | set x to (-180) // the left hand side of the Mandelbrot set |

− | repeat ((360) / (12))//12 clones and each gets 30 rows on the screen to render | + | repeat ((360) / (12)) // 12 clones and each gets 30 rows on the screen to render |

− | repeat (360)//360 pixels will be the width of the Mandelbrot set once rendered | + | repeat (360) // 360 pixels will be the width of the Mandelbrot set once rendered |

− | //this is where | + | ... // this is where each point will be rendered |

end | end | ||

− | change y by (-12)//the clone finished a row and moves to another | + | change y by (-12) // the clone finished a row and moves to another |

set x to (-180) | set x to (-180) | ||

end | end | ||

</scratchblocks> | </scratchblocks> | ||

− | Although this is a functional script, it will take | + | Although this is a functional script, it will take a while to render. For speed preferences, a custom block will be inserted: |

<scratchblocks> | <scratchblocks> | ||

Line 156: | Line 163: | ||

repeat (30) | repeat (30) | ||

repeat (60) | repeat (60) | ||

− | forced iteration//renders 6 points without a screen refresh for speed benefits | + | forced iteration::custom // renders 6 points without a screen refresh for speed benefits |

end | end | ||

change y by (-12) | change y by (-12) | ||

Line 162: | Line 169: | ||

end | end | ||

− | define forced iteration//make sure this runs without screen refresh | + | define forced iteration |

− | repeat (6) | + | // make sure this runs without screen refresh |

− | //here is where we'll be rendering points now | + | repeat (6) // here is where we'll be rendering points now |

end | end | ||

</scratchblocks> | </scratchblocks> | ||

Line 170: | Line 177: | ||

As noted above, it is important that the custom block "forced iteration" runs without a screen refresh or else all the benefit of extra speed will be lost. | As noted above, it is important that the custom block "forced iteration" runs without a screen refresh or else all the benefit of extra speed will be lost. | ||

− | Anyway, now that that is coded, | + | Anyway, now that that is coded, a skeleton will be created for sampling a point and figuring out whether or not it is part of the Mandelbrot set: |

<scratchblocks> | <scratchblocks> | ||

define forced iteration | define forced iteration | ||

+ | // make sure it runs without screen refresh | ||

repeat (6) | repeat (6) | ||

− | set [Real 1 v] to ((x position) / (90))//90 pixels to the right is the equivalent of 1 | + | set [Real 1 v] to ((x position) / (90)) // 90 pixels to the right is the equivalent of 1 |

− | set [Imaginary 1 v] to ((y position) / (90))//90 pixels upwards is the equivalent of i | + | set [Imaginary 1 v] to ((y position) / (90)) // 90 pixels upwards is the equivalent of i |

if <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) < (2.15)> then | if <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) < (2.15)> then | ||

− | Test for Legibility at R: (Real 1) I: (Imaginary 1) | + | Test for Legibility at R: (Real 1) I: (Imaginary 1)::custom |

− | Set Pen Color | + | Set Pen Color::custom |

− | pen down//drawing the point | + | pen down // drawing the point |

pen up | pen up | ||

end | end | ||

− | change x by (1)//moving onto another point | + | change x by (1) // moving onto another point |

end | end | ||

− | define Test for Legibility at R: (Real) I: (Imaginary)//this is where | + | define Test for Legibility at R: (Real) I: (Imaginary) |

+ | // this is where a point will be tested if it is part of the Mandelbrot set or not | ||

− | define Set Pen Color//this is where | + | define Set Pen Color |

+ | // this is where the color will be picked depending on the variable 'Best Fit' | ||

</scratchblocks> | </scratchblocks> | ||

− | Now here is where the mathematics of the Mandelbrot set comes into play. In the Test for Legibility custom block, | + | Now here is where the mathematics of the Mandelbrot set comes into play. In the Test for Legibility custom block, someone has to take a complex number, apply the equation which defines the Mandelbrot set, and repeat if it is still within a distance of 2 from the origin: |

<scratchblocks> | <scratchblocks> | ||

Line 197: | Line 207: | ||

set [Best Fit v] to (-1) | set [Best Fit v] to (-1) | ||

repeat until <<(Best Fit) = (20)> or <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) > (2)>> | repeat until <<(Best Fit) = (20)> or <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) > (2)>> | ||

− | change [Best Fit v] by (1)//the complex number has survived one iteration | + | change [Best Fit v] by (1) // the complex number has survived one iteration |

set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) | set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) | ||

set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) | set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) | ||

− | set [Real 1 v] to (Real 2)//setting the scene for another iteration | + | set [Real 1 v] to (Real 2) // setting the scene for another iteration |

− | set [Imaginary | + | set [Imaginary 1 v] to (Imaginary 2) |

end | end | ||

</scratchblocks> | </scratchblocks> | ||

− | Up above, it may be noticed that the repeat continues until the complex number is found to | + | Up above, it may be noticed that the repeat continues until the complex number is found not to be part of the Mandelbrot set, or until it has iterated 20 times. That 20 can be changed to whatever one wants, with higher numbers producing higher quality; though the higher the number, the more lag will be caused. |

To complete the Mandelbrot set, colors need to be implemented: | To complete the Mandelbrot set, colors need to be implemented: | ||

Line 212: | Line 222: | ||

define Set Pen Color | define Set Pen Color | ||

if <(Best Fit) = (-1)> then | if <(Best Fit) = (-1)> then | ||

− | set pen color to [#000]//this point is already outside a distance of 2 from the origin | + | set pen color to [#000] // this point is already outside a distance of 2 from the origin |

else | else | ||

if <(Best Fit) = (20)> then | if <(Best Fit) = (20)> then | ||

− | set pen color to [#FFF]//this point is a solution to the Mandelbrot set | + | set pen color to [#FFF] // this point is a solution to the Mandelbrot set |

− | else | + | else |

− | set pen color to (50)//this complex number is not a solution, but survives several iterations | + | set pen color to (50) // this complex number is not a solution, but survives several iterations |

set pen shade to (((0) - (Best Fit)) * (5)) | set pen shade to (((0) - (Best Fit)) * (5)) | ||

end | end | ||

Line 223: | Line 233: | ||

</scratchblocks> | </scratchblocks> | ||

− | + | Those colors may be changed to one's wishes. | |

====Final Product==== | ====Final Product==== | ||

Line 233: | Line 243: | ||

hide | hide | ||

set y to (180) | set y to (180) | ||

− | + | erase all | |

repeat (12) | repeat (12) | ||

create clone of [myself v] | create clone of [myself v] | ||

− | change y by (-1)//so that clones | + | change y by (-1) // this makes it so that clones do not overlap |

end | end | ||

Line 244: | Line 254: | ||

repeat (30) | repeat (30) | ||

repeat (60) | repeat (60) | ||

− | forced iteration | + | forced iteration::custom |

end | end | ||

change y by (-12) | change y by (-12) | ||

Line 250: | Line 260: | ||

end | end | ||

− | define forced iteration//remember, run this without screen refresh! | + | define forced iteration |

+ | // remember, run this without screen refresh! | ||

repeat (6) | repeat (6) | ||

set [Real 1 v] to ((x position) / (90)) | set [Real 1 v] to ((x position) / (90)) | ||

Line 257: | Line 268: | ||

Test for Legibility at R: (Real 1) I: (Imaginary 1) | Test for Legibility at R: (Real 1) I: (Imaginary 1) | ||

Set Pen Color | Set Pen Color | ||

− | pen down//drawing the point | + | pen down // drawing the point |

pen up | pen up | ||

end | end | ||

− | change x by (1)//moving onto another point | + | change x by (1) // moving onto another point |

end | end | ||

Line 266: | Line 277: | ||

set [Best Fit v] to (-1) | set [Best Fit v] to (-1) | ||

repeat until <<(Best Fit) = (20)> or <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) > (2)>> | |||

− | change [Best Fit v] by (1)//the complex number has survived one iteration | + | change [Best Fit v] by (1) // the complex number has survived one iteration |

set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) | set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) | ||

set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) | set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) | ||

set [Real 1 v] to (Real 2) | set [Real 1 v] to (Real 2) | ||

− | set [Imaginary | + | set [Imaginary 1 v] to (Imaginary 2) |

end | end | ||

define Set Pen Color | define Set Pen Color | ||

if <(Best Fit) = (-1)> then | if <(Best Fit) = (-1)> then | ||

− | set pen color to [#000]//this point is already outside a distance of 2 from the origin | + | set pen color to [#000] // this point is already outside a distance of 2 from the origin |

else | else | ||

if <(Best Fit) = (20)> then | if <(Best Fit) = (20)> then | ||

− | set pen color to [#FFF]//this point is a solution to the Mandelbrot set | + | set pen color to [#FFF] // this point is a solution to the Mandelbrot set |

− | else | + | else |

− | set pen color to (50)//this complex number is not a solution, but survives several iterations | + | set pen color to (50) // this complex number is not a solution, but survives several iterations |

set pen shade to (((0) - (Best Fit)) * (5)) | set pen shade to (((0) - (Best Fit)) * (5)) | ||

end | end | ||

Line 291: | Line 302: | ||

[[File:Julia Set Equation.png]] | [[File:Julia Set Equation.png]] | ||

− | The only difference in | + | The only difference in its definition from the Mandelbrot set is that c is no longer a point in the complex plane, but rather a complex parameter, which is consistent whichever point you pick. Also, z1 is defined as being the point you pick in the complex plane. The technique above for rendering the Mandelbrot set may be used here again, with the required changes. |

Here is a gallery of images on the Julia set: | Here is a gallery of images on the Julia set: | ||

Line 302: | Line 313: | ||

==See Also== | ==See Also== | ||

− | *[http://scratch.mit.edu/projects/10068174/ Example of Koch Curve] | + | * [http://scratch.mit.edu/projects/10068174/ Example of Koch Curve] |

− | *[http://scratch.mit.edu/projects/12194871/ | + | * [http://scratch.mit.edu/projects/12194871/ Example of Mandelbrot Set and Julia Set] |

− | *[[Recursion]] | + | * [[Recursion]] |

− | [[Category: Scripting Tutorials]] | + | [[Category:Scripting Tutorials]] |

− | [[Category: | + | [[Category:Computer Science]] |

+ | [[de:Fraktale]][[hu:Fraktálok]] |

## Latest revision as of 14:03, 20 March 2020

**Recursion** is the process of repeating items in a self-similar way. It can be implemented in Scratch by making a Custom block that runs itself. This can be used to create **Fractals**.

A fractal is pattern that produces a picture, which contains an infinite amount of copies of itself. Some well-known specimens are the Mandelbrot set, the Sierpinski Triangle (also, but less commonly known as the Sierpinski Gasket), and the Koch Snowflake.

## Contents

## Creating the Koch Curve

The Koch Curve is a fractal that can be created relatively easily in Scratch. It is a piece of the larger fractal, the Koch Snowflake.

### Understanding Recursion in the Koch Curve

The Koch Curve is made of four Koch Curves that are a third of the size of the original Koch Curve. They are they are arranged so that the first and fourth are flat and the middle two point up to make an equilateral that is triangle missing one side.

To make it easier to draw, the Koch Curve can be broken down into iterations, each one more complicated than the last. The first iteration is made up of four straight lines. The second iteration contains four copies of the first iteration. The third iteration contains four copies of the second iteration or sixteen copies of the first iteration. As iterations are added it gets more complicated and looks more and more like the real Koch Curve.

#### Basic Pen Path without Recursion

The triangle in the center is an equilateral triangle, therefore each of its angles have a measure of 60°.

Using basic geometry the angles of the rotations the sprite must make can be found.

Using this these angles, a script can be created that draws the first iteration of Koch Curve. Since each line segment is 1/3 the total length of the Koch Curve, the sprite should move 1/3 of the length given each time.

when gf clicked point in direction (90) // make sure the sprite is pointed right go to x: (-240) y: (-179) // put the sprite in the lower left corner erase all // clear graphics from previous runs pen down // put the pen down for drawing make the first iteration of the Koch Curve with a length of (480) pen up // put the pen up so movement afterwards is not recorded define make the first iteration of the Koch Curve with a length of (length) move ((length) / (3)) steps // draw a line segment turn ccw (60) degrees // first turn move ((length) / (3)) steps // draw a line segment turn cw (120) degrees // second turn move ((length) / (3)) steps // draw a line segment turn ccw (60) degrees // third turn move ((length) / (3)) steps // draw a line segment

#### Adding Recursion

To add recursion, instead of drawing a line, a smaller Koch Curve can be drawn. When each iteration above one is drawn, it contains four smaller Koch Curves that are one iteration less than it self. For example, when drawing the second iteration you must draw four copies that are 1/3 the size of the first iteration. When the program gets to the first iteration it must draw straight lines. The following code will make the fifth iteration of the Koch Curve

when gf clicked point in direction (90) // make sure the sprite is pointed right go to x: (-240) y: (-179) // put the sprite in the lower left corner erase all // clear graphics from previous runs pen down // put the pen down for drawing make the (5) iteration of the Koch Curve with a length of (480) pen up // put the pen up so movement afterwards is not recorded define make the (iteration) iteration of the Koch Curve with a length of (length) if <(iteration) = [1]> then // is it the first iteration? move ((length) / (3)) steps // draw a line segment else make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve end turn ccw (60) degrees // first turn if <(iteration) = [1]> then // is it the first iteration? move ((length) / (3)) steps // draw a line segment else make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve end turn cw (120) degrees // second turn if <(iteration) = [1]> then // is it the first iteration? move ((length) / (3)) steps // draw a line segment else make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve end turn ccw (60) degrees // third turn if <(iteration) = [1]> then // is it the first iteration? move ((length) / (3)) steps // draw a line segment else make the ((iteration) - (1)) iteration of the Koch Curve with a length of ((length) / (3)) // make a smaller Koch Curve end

## Creating the Mandelbrot Set

The Mandelbrot set is a mathematical fractal defined in the complex plane. It is completely self-similar, meaning that it repeats over and over as one zooms in. The Mandelbrot set was named after its discoverer, Benoit Mandelbrot, and has many close relationships to the Julia Sets.

### Understanding the Definition

In its definition, the Mandelbrot uses complex numbers. A complex number is the sum of a real number and an imaginary one, with an imaginary number simply being the square root of a negative number. Since that can not be taken, the square root of -1 is assigned the value i. For example, 3+3i is a complex number.

The Mandelbrot set is defined as all c values in the complex plain which are bounded under iteration in the following equation:

First, one starts with a z value of c (i.e. z_{1} = c). Then, when one puts that z back into the equation, it becomes z^2+c. That z is then taken and put back through the equation over and over. This is called iteration.

For example, let c=1. The value z then becomes 1. Once 1 is put back into the equation, the equation becomes 1^2+1, which equals 2. Once 2 is put back in, it becomes 2^2+1, or 5. Once 5 is put back in, it becomes 26. That sequence escapes to infinity and therefore c=1 is not part of the Mandelbrot set. Meanwhile, the sequence c=-1 gives 0, -1, 0, -1, 0, ect..., is bounded and so belongs to the Mandelbrot set.

It has been proven that if any sequence contains a complex value that is outside a distance of 2 from the origin, it will escape to infinity.

#### Coloring

In a basic Mandelbrot set, white is used for a c-values that escape to infinity and black is used for all c-values that do not. This would be the actual Mandelbrot set.

In most Mandelbrot sets, though, colors are used to help depict the Mandelbrot set or make it more art-orientated. Colors are not defined through an equation, but rather through the last iteration before escaping a distance of two from the origin. The iteration is then assigned a color of the creator's preference. Color can also apply to the rate of the equation reaching infinity.

#### Creating the Variables

Due to the fact that Scratch does not directly support mathematics in the complex plain, a simple workaround has to be used. Each complex number will be defined as two variables, the real part, and the complex part. And since there will be operations based on the complex numbers, two complex numbers will be needed, or four variables. For the tutorial, these names will be used:

- Real 1
- Real 2
- Complex 1
- Complex 2

Along with that, a variable Best Fit will be used to figure out the color to be used when coloring a complex value:

- Best Fit

#### Coding

To start, a base of clones is needed to render a full screen due to the computing power needed to render the Mandelbrot set:

when gf clicked hide // so that this sprite and its clones do not show set y to (180) erase all // preparing the scene for the Mandelbrot set repeat (12) create clone of [myself v] change y by (-1) // this makes it so that clones do not overlap end

Next, it is important to give the clones a skeleton:

when I start as a clone set pen size to (1.5) // any other size will appear transparent set x to (-180) // the left hand side of the Mandelbrot set repeat ((360) / (12)) // 12 clones and each gets 30 rows on the screen to render repeat (360) // 360 pixels will be the width of the Mandelbrot set once rendered ... // this is where each point will be rendered end change y by (-12) // the clone finished a row and moves to another set x to (-180) end

Although this is a functional script, it will take a while to render. For speed preferences, a custom block will be inserted:

when I start as a clone set pen size to (1.5) set x to (-180) repeat (30) repeat (60) forced iteration::custom // renders 6 points without a screen refresh for speed benefits end change y by (-12) set x to (-180) end define forced iteration // make sure this runs without screen refresh repeat (6) // here is where we'll be rendering points now end

As noted above, it is important that the custom block "forced iteration" runs without a screen refresh or else all the benefit of extra speed will be lost.

Anyway, now that that is coded, a skeleton will be created for sampling a point and figuring out whether or not it is part of the Mandelbrot set:

define forced iteration // make sure it runs without screen refresh repeat (6) set [Real 1 v] to ((x position) / (90)) // 90 pixels to the right is the equivalent of 1 set [Imaginary 1 v] to ((y position) / (90)) // 90 pixels upwards is the equivalent of i if <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) < (2.15)> then Test for Legibility at R: (Real 1) I: (Imaginary 1)::custom Set Pen Color::custom pen down // drawing the point pen up end change x by (1) // moving onto another point end define Test for Legibility at R: (Real) I: (Imaginary) // this is where a point will be tested if it is part of the Mandelbrot set or not define Set Pen Color // this is where the color will be picked depending on the variable 'Best Fit'

Now here is where the mathematics of the Mandelbrot set comes into play. In the Test for Legibility custom block, someone has to take a complex number, apply the equation which defines the Mandelbrot set, and repeat if it is still within a distance of 2 from the origin:

define Test for Legibility at R: (Real) I: (Imaginary) set [Best Fit v] to (-1) repeat until <<(Best Fit) = (20)> or <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) > (2)>> change [Best Fit v] by (1) // the complex number has survived one iteration set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) set [Real 1 v] to (Real 2) // setting the scene for another iteration set [Imaginary 1 v] to (Imaginary 2) end

Up above, it may be noticed that the repeat continues until the complex number is found not to be part of the Mandelbrot set, or until it has iterated 20 times. That 20 can be changed to whatever one wants, with higher numbers producing higher quality; though the higher the number, the more lag will be caused.

To complete the Mandelbrot set, colors need to be implemented:

define Set Pen Color if <(Best Fit) = (-1)> then set pen color to [#000] // this point is already outside a distance of 2 from the origin else if <(Best Fit) = (20)> then set pen color to [#FFF] // this point is a solution to the Mandelbrot set else set pen color to (50) // this complex number is not a solution, but survives several iterations set pen shade to (((0) - (Best Fit)) * (5)) end end

Those colors may be changed to one's wishes.

#### Final Product

In the end, this is all the code used to draw the Mandelbrot set (scroll to see all of the code):

when gf clicked hide set y to (180) erase all repeat (12) create clone of [myself v] change y by (-1) // this makes it so that clones do not overlap end when I start as a clone set pen size to (1.5) set x to (-180) repeat (30) repeat (60) forced iteration::custom end change y by (-12) set x to (-180) end define forced iteration // remember, run this without screen refresh! repeat (6) set [Real 1 v] to ((x position) / (90)) set [Imaginary 1 v] to ((y position) / (90)) if <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) < (2.15)> then Test for Legibility at R: (Real 1) I: (Imaginary 1) Set Pen Color pen down // drawing the point pen up end change x by (1) // moving onto another point end define Test for Legibility at R: (Real) I: (Imaginary) set [Best Fit v] to (-1) repeat until <<(Best Fit) = (20)> or <([sqrt v] of (((Real 1) * (Real 1)) + ((Imaginary 1) * (Imaginary 1)))) > (2)>> change [Best Fit v] by (1) // the complex number has survived one iteration set [Real 2 v] to ((((Real 1) * (Real 1)) - ((Imaginary 1) * (Imaginary 1))) + (Real)) set [Imaginary 2 v] to (((2) * ((Real 1) * (Imaginary 1))) + (Imaginary)) set [Real 1 v] to (Real 2) set [Imaginary 1 v] to (Imaginary 2) end define Set Pen Color if <(Best Fit) = (-1)> then set pen color to [#000] // this point is already outside a distance of 2 from the origin else if <(Best Fit) = (20)> then set pen color to [#FFF] // this point is a solution to the Mandelbrot set else set pen color to (50) // this complex number is not a solution, but survives several iterations set pen shade to (((0) - (Best Fit)) * (5)) end end

## Julia Set

The Julia set is a series of equations that are mathematical fractals, and that is defined very similarly to the Mandelbrot set. The official equation is:

The only difference in its definition from the Mandelbrot set is that c is no longer a point in the complex plane, but rather a complex parameter, which is consistent whichever point you pick. Also, z1 is defined as being the point you pick in the complex plane. The technique above for rendering the Mandelbrot set may be used here again, with the required changes.

Here is a gallery of images on the Julia set: