Sierpinski's triangle

Joined:
Sep 17, 2016
Posts:
26
Hi all,

A recent episode of Numberphile (www.youtube.com/watch?v=kbKtFN71Lfs), describes a really simple and unexpected way (to me in any case) of generating Sierpinski's triangle (or gasket): essentially you move from a random point half way towards one of three (noncollinear) points with one third probability each, draw another point and repeat. Quite amazingly this generates the famous fractal pattern. Thought people here might get a kick out of it.

edit: maybe I put this in the wrong forum, pls move if so.

Some (terrible) code below and examples:

Code:
```// Generate Sierpinski triangle - move some fraction of distance to one of 3 points according to
// randomly sampled integer from 1 to 3.

//room size 1920 x 1200

if keyboard_check_pressed(ord("R")) room_restart();

NumberOfPoints = 10000;

if can_choose = true
{
// triangle vertex coordinates and radius of circles drawn at those coordinates
vertex_x1 = 900;
vertex_y1 = 100;

vertex_x2 = 1700;
vertex_y2 = 1100;

vertex_x3 = 100;
vertex_y3 = 1100;

// Use these lines to randomize shape of starting triangle. No guarantee won't be colinear.
/*vertex_x1 = irandom_range(100,1800);
vertex_y1 = irandom_range(100,1100);

vertex_x2 = irandom_range(100,1800);
vertex_y2 = irandom_range(100,1100);

vertex_x3 = irandom_range(100,1800);
vertex_y3 = irandom_range(100,1100);

// fraction in original example was 0.5. Here mutiplied by separate scale for
// each of three vertexes
fraction = 0.5;

/*scale1x = 1;
scale2x = 1;
scale3x = 1;
scale1y = 1;
scale2y = 1;
scale3y = 1;*/

scale1x = random_range(0.5,1.5);
scale2x = random_range(0.5,1.5);
scale3x = random_range(0.5,1.5);
scale1y = random_range(0.5,1.5);
scale2y = random_range(0.5,1.5);
scale3y = random_range(0.5,1.5);

// starting position and radius of circle drawn at starting position
start_x = irandom_range(100,1800);
start_y = irandom_range(100,1100);

// generate array of random integers with values from 1 to 3
for (i=0; i<NumberOfPoints+1; i+=1)
{
direct[i] = choose(1,2,3);
}
}

// draw vertexes

// draw starting point

// state fraction*scales
draw_text_colour(100,150,fraction*scale1x,c_yellow,c_yellow,c_yellow,c_yellow,1);
draw_text_colour(100,200,fraction*scale2x,c_yellow,c_yellow,c_yellow,c_yellow,1);
draw_text_colour(100,250,fraction*scale3x,c_yellow,c_yellow,c_yellow,c_yellow,1);
draw_text_colour(100,300,fraction*scale1y,c_yellow,c_yellow,c_yellow,c_yellow,1);
draw_text_colour(100,350,fraction*scale2y,c_yellow,c_yellow,c_yellow,c_yellow,1);
draw_text_colour(100,400,fraction*scale3y,c_yellow,c_yellow,c_yellow,c_yellow,1);

// generate new point coordinates
current_x = start_x;
current_y = start_y;

for (i = 0; i < NumberOfPoints+1; i += 1)
{
if direct[i] == 1
{
current_x[i+1] = current_x[i] + sign(vertex_x1 - current_x[i])*fraction*scale1x*abs(vertex_x1 - current_x[i]);
current_y[i+1] = current_y[i] + sign(vertex_y1 - current_y[i])*fraction*scale1y*abs(vertex_y1 - current_y[i]);
}
if direct[i] == 2
{
current_x[i+1] = current_x[i] + sign(vertex_x2 - current_x[i])*fraction*scale2x*abs(vertex_x2 - current_x[i]);
current_y[i+1] = current_y[i] + sign(vertex_y2 - current_y[i])*fraction*scale2y*abs(vertex_y2 - current_y[i]);
}
if direct[i] == 3
{
current_x[i+1] = current_x[i] + sign(vertex_x3 - current_x[i])*fraction*scale3x*abs(vertex_x3 - current_x[i]);
current_y[i+1] = current_y[i] + sign(vertex_y3 - current_y[i])*fraction*scale3y*abs(vertex_y3 - current_y[i]);
}
}
// use these lines to draw all points simultaneously
for (i=1; i < NumberOfPoints+1; i += 1)
{
if i mod 2 = 0
if i mod 2 != 0
}

// use these lines to plot points one by one
// press space to plot points
/*if keyboard_check(vk_space)
{
for (m = 1; m < j+1; m += 1)
{
if m mod 2 = 0
if m mod 2 != 0
}
if (j < NumberOfPoints+1)
j += 1;
}
*/
can_choose = false;
```

Here's an example of the classic triangle with scale factors equal to 0.5. The green circle is the starting point: I then played around with distorting the scale factors:  Last edited: Apr 30, 2017
renex, Wraithious, hippyman and 6 others like this.
2. chancepredictably randomForum StaffModerator

Joined:
Apr 22, 2016
Posts:
774
That's an interesting algorithm. I've always used cellular automata algorithms to draw these, one line at a time. This sub-division approach is one I haven't seen. Although reading about it, I guess it's fairly common. Not immediately intuitive, though.

Fun to watch this evolve step-by-step. Just takes a few lines in DRAW:

Code:
```var old_x = new_x; // swap point
var old_y = new_y;

var index = choose(0,1,2); // draw new point
new_x = old_x + (vert_x[index] - old_x)/2;
new_y = old_y + (vert_y[index] - old_y)/2;

surface_set_target(surf); // update surface
draw_point(new_x,new_y);
surface_reset_target();

draw_surface(surf,0,0); // draw the surface
```
The surface is initialized in the Create event, of course. Along with the three vertices and starting values for new_x/y. With room_speed at 9999, it takes <10 sec to get a detailed gasket: renex, Adiabat, joqlepecheur and 3 others like this.

Joined:
Sep 17, 2016
Posts:
26
Thanks Chance! That's code from someone who actually knows what they're doing. Also I had no idea rooms could run that fast.

Two triangles: Letting scaling factor vary in one triangle: Regular hexagon, scale = 0.7 (instead of 0.5): Regular hexagon, scale = 0.6 (less than that, starts to look like noise): Rivo likes this.

Joined:
Sep 17, 2016
Posts:
26
I thought the Barnsley fern they mentioned looked great so I did that too, plus the variation described in the corresponding Wikipedia article. Classic on left, variation on right: Here's the code (modified version of chance's code):

Code:
```// Barnsley fern and variation

var old_x = new_x; // swap points
var old_y = new_y;

var old_x2 = new_x2;
var old_y2 = new_y2;

// classic fern
part = irandom_range(1,100)

if (part == 1)
{
new_x = 0;
new_y = 0.16*old_y;
}
if (part <= 86) and (part != 1)
{
new_x = 0.85*old_x + 0.04*old_y;
new_y = -0.04*old_x + 0.85*old_y + 1.6;
}
if (part >= 87) and (part <= 93)
{
new_x = 0.2*old_x - 0.26*old_y;
new_y = 0.23*old_x + 0.22*old_y + 1.6;
}
if (part >= 94)
{
new_x = -0.15*old_x + 0.28*old_y;
new_y = 0.26*old_x + 0.24*old_y + 0.44;
}

// variation
part2 = irandom_range(1,100);

if (part2 == 1) or (part2 == 2)
{
new_x2 = 0;
new_y2 = 0.25*old_y2 - 0.4;
}
if (part2 <= 86) and (part2 >= 3)
{
new_x2 = 0.95*old_x2 + 0.005*old_y2 - 0.002;
new_y2 = -0.005*old_x2 + 0.93*old_y2 + 0.5;
}
if (part2 >= 87) and (part2 <= 93)
{
new_x2 = 0.035*old_x2 - 0.20*old_y2 - 0.09;
new_y2 = 0.16*old_x2 + 0.04*old_y2 + 0.02;
}
if (part2 >= 94)
{
new_x2 = -0.04*old_x2 + 0.20*old_y2 + 0.083;
new_y2 = 0.16*old_x2 + 0.04*old_y2 + 0.12;
}

surface_set_target(surf); // update surface
draw_set_colour(c_green);
draw_point(new_x*100+500,1100-new_y*100);
draw_set_colour(c_lime);
draw_point(1500-new_x2*150,1100-new_y2*150);

surface_reset_target();

draw_surface(surf,0,0); // draw the surface

if keyboard_check_pressed(ord("R")) room_restart();```

Last edited: May 1, 2017
Snayff, Kenjiro, Simon Gust and 9 others like this.
5. chancepredictably randomForum StaffModerator

Joined:
Apr 22, 2016
Posts:
774
Very nice. I love to see iteration used to create fractal organic shapes. Reminds me of the earliest programs I ever wrote.

Your other examples with Sierpinski triangles using different divisors got me thinking. So I made an animation to see it "evolve" as the divisor was varied over time.

Here's an HTML5 example. It uses two surfaces: one to display the last result, while the other surface is being updated. Then they get swapped every step. Even with 20,000 iterations per step, it still runs quickly since the calculation is very simple.

Just click to play in browser:
http://dotcom-games.com/sierpinski/

Interesting "fireball" effect at the end. With the divisor very large, the points just dance around a central location after the first update.

Bentley, Dragon47, renex and 2 others like this.