Chaos game: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Perl}}: there is no need to plot the initial points)
(Added Sidef)
Line 578: Line 578:
next
next
render #g</lang>
render #g</lang>

=={{header|Sidef}}==
<lang ruby>require('Imager')

var width = 600
var height = 600

var points = [
[width//2, 0],
[ 0, height-1],
[height-1, height-1],
]

var img = %s|Imager|.new(
xsize => width,
ysize => height,
)

var color = %s|Imager::Color|.new('#ff0000')
var r = [width.irand, height.irand]

30000.times {
var p = points.rand

r[] = (
(p[0] + r[0]) // 2,
(p[1] + r[1]) // 2,
)

img.setpixel(
x => r[0],
y => r[1],
color => color,
)
}

img.write(file => 'chaos_game.png')</lang>


=={{header|zkl}}==
=={{header|zkl}}==

Revision as of 04:25, 5 September 2016

Task
Chaos game
You are encouraged to solve this task according to the task description, using any language you may know.

The Chaos Game is a method of generating the attractor of an iterated function system (IFS). One of the best-known and simplest examples creates a fractal, using a polygon and an initial point selected at random.

Task

Play the Chaos Game using the corners of an equilateral triangle as the reference points. Add a starting point at random (preferably inside the triangle). Then add the next point halfway between the starting point and one of the reference points. This reference point is chosen at random.

After a sufficient number of iterations, the image of a Sierpinski Triangle should emerge.

See also



BASIC

This should require minimal adaptation to work with any of the older Microsoft-style BASICs (IBM PC, AppleSoft, Commodore, etc.). Users of other dialects will need to replace lines 10 and 150 with the appropriate statements to select a graphics output mode (if necessary) and to plot a pixel at x,y in colour v; they should also add LET throughout and 170 END if their dialects require those things. <lang basic>10 SCREEN 1 20 X = INT(RND(0) * 200) 30 Y = INT(RND(0) * 173) 40 FOR I=1 TO 20000 50 V = INT(RND(0) * 3) + 1 60 ON V GOTO 70,100,130 70 X = X/2 80 Y = Y/2 90 GOTO 150 100 X = 100 + (100-X)/2 110 Y = 173 - (173-Y)/2 120 GOTO 150 130 X = 200 - (200-X)/2 140 Y = Y/2 150 PSET X,Y,V 160 NEXT I</lang>

C++

This program will generate the Sierpinski Triangle and save it to your hard drive. <lang cpp>

  1. include <windows.h>
  2. include <ctime>
  3. include <string>
  4. include <iostream>

const int BMP_SIZE = 600;

class myBitmap { public: 

   myBitmap() : pen( NULL ), brush( NULL ), clr( 0 ), wid( 1 ) {}
   ~myBitmap() {
       DeleteObject( pen ); DeleteObject( brush );
       DeleteDC( hdc ); DeleteObject( bmp );
   }
   bool create( int w, int h ) {
       BITMAPINFO bi;
       ZeroMemory( &bi, sizeof( bi ) );
       bi.bmiHeader.biSize        = sizeof( bi.bmiHeader );
       bi.bmiHeader.biBitCount    = sizeof( DWORD ) * 8;
       bi.bmiHeader.biCompression = BI_RGB;
       bi.bmiHeader.biPlanes      = 1;
       bi.bmiHeader.biWidth       =  w;
       bi.bmiHeader.biHeight      = -h;

       HDC dc = GetDC( GetConsoleWindow() );
       bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 );
       if( !bmp ) return false;

       hdc = CreateCompatibleDC( dc );
       SelectObject( hdc, bmp );
       ReleaseDC( GetConsoleWindow(), dc );

       width = w; height = h;
       return true;
   }
   void clear( BYTE clr = 0 ) {
       memset( pBits, clr, width * height * sizeof( DWORD ) );
   }
   void setBrushColor( DWORD bClr ) {
       if( brush ) DeleteObject( brush );
       brush = CreateSolidBrush( bClr );
       SelectObject( hdc, brush );
   }
   void setPenColor( DWORD c ) {
       clr = c; createPen();
   }
   void setPenWidth( int w ) {
       wid = w; createPen();
   }
   void saveBitmap( std::string path ) {
       BITMAPFILEHEADER fileheader;
       BITMAPINFO       infoheader;
       BITMAP           bitmap;
       DWORD            wb;

       GetObject( bmp, sizeof( bitmap ), &bitmap );
       DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight];

       ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) );
       ZeroMemory( &infoheader, sizeof( BITMAPINFO ) );
       ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) );

       infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8;
       infoheader.bmiHeader.biCompression = BI_RGB;
       infoheader.bmiHeader.biPlanes = 1;
       infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader );
       infoheader.bmiHeader.biHeight = bitmap.bmHeight;
       infoheader.bmiHeader.biWidth = bitmap.bmWidth;
       infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD );

       fileheader.bfType    = 0x4D42;
       fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER );
       fileheader.bfSize    = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage;

       GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS );

       HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL );
       WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL );
       WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL );
       WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL );
       CloseHandle( file );

       delete [] dwpBits;
   }
   HDC getDC() const     { return hdc; }
   int getWidth() const  { return width; }
   int getHeight() const { return height; }

private: 

   void createPen() {
       if( pen ) DeleteObject( pen );
       pen = CreatePen( PS_SOLID, wid, clr );
       SelectObject( hdc, pen );
   }
   HBITMAP bmp; HDC    hdc;
   HPEN    pen; HBRUSH brush;
   void    *pBits; int    width, height, wid;
   DWORD    clr;

}; class chaos { public: 

   void start() {
       POINT org;
       fillPts(); initialPoint( org ); initColors();
       int cnt = 0, i;
       bmp.create( BMP_SIZE, BMP_SIZE );
       bmp.clear( 255 );

       while( cnt++ < 1000000 ) {
           switch( rand() % 6 ) {
               case 0: case 3: i = 0; break;
               case 1: case 5: i = 1; break;
               case 2: case 4: i = 2;
           }
           setPoint( org, myPoints[i], i );
       }
       // --- edit this path --- //
       bmp.saveBitmap( "F:/st.bmp" );
   }

private: 

   void setPoint( POINT &o, POINT v, int i ) {
       POINT z;
       o.x = ( o.x + v.x ) >> 1; o.y = ( o.y + v.y ) >> 1;
       SetPixel( bmp.getDC(), o.x, o.y, colors[i] );
   }
   void fillPts() {
       int a = BMP_SIZE - 1;
       myPoints[0].x = BMP_SIZE >> 1; myPoints[0].y = 0;
       myPoints[1].x = 0; myPoints[1].y = myPoints[2].x = myPoints[2].y = a;
   }
   void initialPoint( POINT& p ) {
       p.x = ( BMP_SIZE >> 1 ) + rand() % 2 ? rand() % 30 + 10 : -( rand() % 30 + 10 );
       p.y = ( BMP_SIZE >> 1 ) + rand() % 2 ? rand() % 30 + 10 : -( rand() % 30 + 10 );
   }
   void initColors() {
       colors[0] = RGB( 255, 0, 0 );
       colors[1] = RGB( 0, 255, 0 );
       colors[2] = RGB( 0, 0, 255 );
   }
   
   myBitmap bmp;
   POINT myPoints[3];
   COLORREF colors[3];

}; int main( int argc, char* argv[] ) { 

   srand( ( unsigned )time( 0 ) );
   chaos c; c.start();
   return 0;

} </lang>

Haskell

<lang haskell>import Control.Monad (replicateM) import Control.Monad.Random (fromList)

type Point = (Float,Float) type Transformations = [(Point -> Point, Float)] -- weighted transformations

-- realization of the game for given transformations gameOfChaos :: MonadRandom m => Int -> Transformations -> Point -> m [Point] gameOfChaos n transformations x = iterateA (fromList transformations) x 

 where iterateA f x = scanr ($) x <$> replicateM n f</lang>

Some transformations:

<lang haskell>-- the Sierpinsky`s triangle triangle :: Transformations triangle = [ (mid (0, 0), 1) 

          , (mid (1, 0), 1)
          , (mid (0.5, 0.86), 1) ]
 where mid (a,b) (x,y) = ((a+x)/2, (b+y)/2)

-- the Barnsley's fern fern :: Transformations fern = [(f1, 1), (f2, 85), (f3, 7), (f4, 7)] 

 where f1 (x,y) = (0, 0.16*y)
       f2 (x,y) = (0.85*x + 0.04*y, -0.04*x + 0.85*y + 1.6)
       f3 (x,y) = (0.2*x - 0.26*y, 0.23*x + 0.22*y + 1.6)
       f4 (x,y) = (-0.15*x + 0.28*y, 0.26*x + 0.24*y + 0.44)</lang>

Drawing the result: <lang haskell>import Control.Monad.Random (getRandomR) import Graphics.Gloss

main = do x <- getRandomR (0,1) 

         y <- getRandomR (0,1)
         pts <- gameOfChaos 500000 triangle (x,y)
         display window white $ foldMap point pts
           where window = InWindow "Game of Chaos" (400,400) (0,0)
                 point (x,y) = translate (100*x) (100*y) $ circle 0.02 </lang>

J

<lang j> Note 'plan, Working in complex plane' 

 Make an equilateral triangle.
 Make a list of N targets
 Starting with a random point near the triangle,
   iteratively generate new points.
 plot the new points.

 j has a particularly rich notation for numbers.

   1ad_90 specifies a complex number with radius 1
   at an angle of negative 90 degrees.

   2p1 is 2 times (pi raised to the first power).

)

N=: 3000

require'plot' TAU=: 2p1 NB. tauday.com mean=: +/ % #

NB. equilateral triangle with vertices on unit circle NB. rotated for fun. TRIANGLE=: *(j./2 1 o.(TAU%6)*?0)*1ad_90 1ad150 1ad30

TARGETS=: (N ?@:# 3) { TRIANGLE

NB. start on unit circle START=: j./2 1 o.TAU*?0

NEW_POINTS=: (mean@:(, {.) , ])/ TARGETS , START

'marker'plot NEW_POINTS </lang>

Java

Works with: Java version 8

<lang java>import java.awt.*; import java.awt.event.*; import java.util.*; import javax.swing.*; import javax.swing.Timer;

public class ChaosGame extends JPanel { 

   class ColoredPoint extends Point {
       int colorIndex;

       ColoredPoint(int x, int y, int idx) {
           super(x, y);
           colorIndex = idx;
       }
   }

   Stack<ColoredPoint> stack = new Stack<>();
   Point[] points = new Point[3];
   Color[] colors = {Color.red, Color.green, Color.blue};
   Random r = new Random();

   public ChaosGame() {
       Dimension dim = new Dimension(640, 640);
       setPreferredSize(dim);
       setBackground(Color.white);

       int margin = 60;
       int size = dim.width - 2 * margin;

       points[0] = new Point(dim.width / 2, margin);
       points[1] = new Point(margin, size);
       points[2] = new Point(margin + size, size);

       stack.push(new ColoredPoint(-1, -1, 0));

       new Timer(10, (ActionEvent e) -> {
           if (stack.size() < 50_000) {
               for (int i = 0; i < 1000; i++)
                   addPoint();
               repaint();
           }
       }).start();
   }

   private void addPoint() {
       try {
           int colorIndex = r.nextInt(3);
           Point p1 = stack.peek();
           Point p2 = points[colorIndex];
           stack.add(halfwayPoint(p1, p2, colorIndex));
       } catch (EmptyStackException e) {
           System.out.println(e);
       }
   }

   void drawPoints(Graphics2D g) {
       for (ColoredPoint p : stack) {
           g.setColor(colors[p.colorIndex]);
           g.fillOval(p.x, p.y, 1, 1);
       }
   }

   ColoredPoint halfwayPoint(Point a, Point b, int idx) {
       return new ColoredPoint((a.x + b.x) / 2, (a.y + b.y) / 2, idx);
   }

   @Override
   public void paintComponent(Graphics gg) {
       super.paintComponent(gg);
       Graphics2D g = (Graphics2D) gg;
       g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
               RenderingHints.VALUE_ANTIALIAS_ON);

       drawPoints(g);
   }

   public static void main(String[] args) {
       SwingUtilities.invokeLater(() -> {
           JFrame f = new JFrame();
           f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
           f.setTitle("Chaos Game");
           f.setResizable(false);
           f.add(new ChaosGame(), BorderLayout.CENTER);
           f.pack();
           f.setLocationRelativeTo(null);
           f.setVisible(true);
       });
   }

}</lang>

JavaScript

Plots the fractal on an HTML canvas element. <lang javascript><html>

<head>

<meta charset="UTF-8">

<title>Chaos Game</title>

</head>

<body>

<canvas id="sierpinski" width=400 height=346></canvas>

<button onclick="chaosGame()">Click here to see a Sierpiński triangle</button>

<script>

function chaosGame() { 

   var canv = document.getElementById('sierpinski').getContext('2d');
   var x = Math.random() * 400;
   var y = Math.random() * 346;
   for (var i=0; i<30000; i++) {
       var vertex = Math.floor(Math.random() * 3);
       switch(vertex) {
           case 0:
               x = x / 2;
               y = y / 2;
               canv.fillStyle = 'green';
               break;
           case 1:
               x = 200 + (200 - x) / 2
               y = 346 - (346 - y) / 2
               canv.fillStyle = 'red';
               break;
           case 2:
               x = 400 - (400 - x) / 2
               y = y / 2;
               canv.fillStyle = 'blue';
       }
       canv.fillRect(x,y, 1,1);
   }

}

</script>

</body>

</html></lang>

<lang logo>to chaosgame :sidelength :iterations 

   make "width :sidelength
   make "height (:sidelength/2 * sqrt 3)
   make "x (random :width)
   make "y (random :height)
   repeat :iterations [
       make "vertex (random 3)
       if :vertex = 0 [
           make "x (:x / 2)
           make "y (:y / 2)
           setpencolor "green
       ]
       if :vertex = 1 [
           make "x (:width / 2 + ((:width / 2 - :x) / 2))
           make "y (:height - ((:height - :y) / 2))
           setpencolor "red
       ]
       if :vertex = 2 [
           make "x (:width - ((:width - :x) / 2))
           make "y (:y / 2)
           setpencolor "blue
       ]
       penup
       setxy (:x - :width / 2) (:y - :height / 2)
       pendown
       forward 1
   ]
   hideturtle

end</lang>

Maple

<lang maple>chaosGame := proc(numPoints) local points, i; randomize(); use geometry in RegularPolygon(triSideways, 3, point(cent, [0, 0]), 1); rotation(tri, triSideways, Pi/2, counterclockwise); randpoint(currentP, -1/2*sqrt(3)..1/2*sqrt(3), -1/2..1/2); points := [coordinates(currentP)]; for i to numPoints do midpoint(mid, currentP, parse(cat("rotate_triSideways_", rand(1..3)(), "_tri"))); points := [op(points), coordinates(mid)]; point(currentP, coordinates(mid)); end do: end use; use plottools in plots:-display( seq([plots:-display([seq(point(points[i]), i = 1..j)])], j = 1..numelems(points) ), insequence=true); end use; end proc:</lang>

Perl

<lang perl>use Imager;

my $width = 1000; my $height = 1000;

my @points = ( 

   [ $width/2,         0],
   [        0, $height-1],
   [$height-1, $height-1],

);

my $img = Imager->new( 

                     xsize    => $width,
                     ysize    => $height,
                     channels => 3,
                    );

my $color = Imager::Color->new('#ff0000'); my $r = [int(rand($width)), int(rand($height))];

foreach my $i (1 .. 100000) { 

   my $p = $points[rand @points];

   my $h = [
       int(($p->[0] + $r->[0]) / 2),
       int(($p->[1] + $r->[1]) / 2),
   ];

   $img->setpixel(
       x     => $h->[0],
       y     => $h->[1],
       color => $color,
   );

   $r = $h;

}

$img->write(file => 'chaos_game_triangle.png');</lang>

Perl 6

Works with: Rakudo version 2016.05

<lang perl6>use Image::PNG::Portable;

my ($w, $h) = (640, 640);

my $png = Image::PNG::Portable.new: :width($w), :height($h);

my @vertex = [0, 0], [$w, 0], [$w/2, $h];

my ($x, $y) = (0, 0);

for ^1e5 { 

   ($x, $y) = do given @vertex[3.rand] -> @v { ((($x, $y) »+« @v) »/» 2)».Int };
   $png.set: $x, $y, 0, 255, 0;

}

$png.write: 'Chaos-game-perl6.png';</lang>

Processing

<lang java>size(300,260);

background(#ffffff); // white

int x = Math.floor(Math.random() * 300); int y = Math.floor(Math.random() * 260);

int colour;

for (int i=0; i<30000; i++) { 

  int v = Math.floor(Math.random() * 3);
  switch (v) {
     case 0:
     x = x / 2;
     y = y / 2;
     colour = #00ff00; // green
     break;
     case 1:
     x = 150 + (150 - x)/2;
     y = 260 - (260 - y)/2;
     colour = #ff0000; // red
     break;
     case 2:
     x = 300 - (300 - x)/2;
     y = y / 2;
     colour = #0000ff; // blue
  }
  set(x,y, colour);

}</lang>

Run BASIC

<lang runbasic>x = int(rnd(0) * 200) y = int(rnd(0) * 173) graphic #g, 200,200

  1. g color("green")

for i =1 TO 20000 v = int(rnd(0) * 3) + 1 if v = 1 then x = x/2 y = y/2 end if if v = 2 then x = 100 + (100-x)/2 y = 173 - (173-y)/2 end if if v = 3 then x = 200 - (200-x)/2 y = y/2 end if #g set(x,y) next render #g</lang>

Sidef

<lang ruby>require('Imager')

var width = 600 var height = 600

var points = [ 

   [width//2,        0],
   [       0, height-1],
   [height-1, height-1],

]

var img = %s|Imager|.new( 

                     xsize => width,
                     ysize => height,
                    )

var color = %s|Imager::Color|.new('#ff0000') var r = [width.irand, height.irand]

30000.times { 

   var p = points.rand

   r[] = (
       (p[0] + r[0]) // 2,
       (p[1] + r[1]) // 2,
   )

   img.setpixel(
       x     => r[0],
       y     => r[1],
       color => color,
   )

}

img.write(file => 'chaos_game.png')</lang>

zkl

This is a half assed animated process - a bunch of pixels are drawn every couple of seconds and the pixmap written [to the file system]. So, if you open the output file ("chaosGame.jpg") it will [auto] update and show the progression of the image.

Uses the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl

Translation of: Java

<lang zkl>w,h:=640,640; bitmap:=PPM(w,h,0xFF|FF|FF); // White background colors:=T(0xFF|00|00,0x00|FF|00,0x00|00|FF); // red,green,blue

margin,size:=60, w - 2*margin; points:=T(T(w/2, margin), T(margin,size), T(margin + size,size) ); N,done:=Atomic.Int(0),Atomic.Bool(False);

Thread.HeartBeat('wrap(hb){ // a thread 

  var a=List(-1,-1);

  if(N.inc()<50){
     do(500){

colorIndex:=(0).random(3); // (0..2) b,p:=points[colorIndex], halfwayPoint(a,b); x,y:=p; bitmap[x,y]=colors[colorIndex]; a=p; 

     }
     bitmap.writeJPGFile("chaosGame.jpg",True);
  }
  else{ hb.cancel(); done.set(); }  // stop thread and signal done

},2).go(); // run every 2 seconds, starting now

fcn halfwayPoint([(ax,ay)], [(bx,by)]){ T((ax + bx)/2, (ay + by)/2) }

done.wait(); // don't exit until thread is done println("Done");</lang>

Retrieved from "https://rosettacode.org/wiki/Chaos_game?oldid=264959"