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; vertex_radius_1 = 10; vertex_radius_2 = 10; vertex_radius_3 = 10; vertex_radius_4 = 10; // 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_radius_1 = 10; vertex_x2 = irandom_range(100,1800); vertex_y2 = irandom_range(100,1100); vertex_radius_2 = 10; vertex_x3 = irandom_range(100,1800); vertex_y3 = irandom_range(100,1100); vertex_radius_3 = 10;*/ // 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); start_radius = 10; // 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_circle_colour(vertex_x1,vertex_y1,vertex_radius_1,c_red,c_red,false); draw_circle_colour(vertex_x2,vertex_y2,vertex_radius_2,c_red,c_red,false); draw_circle_colour(vertex_x3,vertex_y3,vertex_radius_3,c_red,c_red,false);*/ // draw starting point draw_circle_colour(start_x,start_y,start_radius,c_green,c_green,false); // 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[0] = start_x; current_y[0] = 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 draw_circle_colour(current_x[i],current_y[i],start_radius,c_yellow,c_black,false); if i mod 2 != 0 draw_circle_colour(current_x[i],current_y[i],start_radius,c_blue,c_black,false); } // 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 draw_circle_colour(current_x[m],current_y[m],start_radius,c_yellow,c_black,false); if m mod 2 != 0 draw_circle_colour(current_x[m],current_y[m],start_radius,c_blue,c_black,false); } 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:
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:
Thanks Chance! That's code from someone who actually knows what they're doing. Also I had no idea rooms could run that fast. Took your code and had some more fun. 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):
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();
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.
Very cool! I like how it progresses from noise to recognizable pattern repeatedly as the divisor increases. Also, sorry for delayed response - I have to wait for weekends.