Brownian tree

From Rosetta Code
This page uses content from Wikipedia. The original article was at Brownian_tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)
Task
Brownian tree
You are encouraged to solve this task according to the task description, using any language you may know.
Generate and draw a Brownian Tree.

A Brownian Tree is generated as a result of an initial seed, followed by the interaction of two processes.

  1. The initial "seed" is placed somewhere within the field. Where is not particularly important; it could be randomized, or it could be a fixed point.
  2. Particles are injected into the field, and are individually given a (typically random) motion pattern.
  3. When a particle collides with the seed or tree, its position is fixed, and it's considered to be part of the tree.

Because of the lax rules governing the random nature of the particle's placement and motion, no two resulting trees are really expected to be the same, or even necessarily have the same general shape.

C

Library: FreeImage

<lang c>#include <string.h>

  1. include <stdlib.h>
  2. include <time.h>
  3. include <math.h>
  4. include <FreeImage.h>
  1. define NUM_PARTICLES 1000
  2. define SIZE 800

void draw_brownian_tree(int world[SIZE][SIZE]){

 int px, py; // particle values
 int dx, dy; // offsets
 int i;

 // set the seed
 world[rand() % SIZE][rand() % SIZE] = 1;
 for (i = 0; i < NUM_PARTICLES; i++){
   // set particle's initial position
   px = rand() % SIZE;
   py = rand() % SIZE;
   while (1){
     // randomly choose a direction
     dx = rand() % 3 - 1;
     dy = rand() % 3 - 1;
     if (dx + px < 0 || dx + px >= SIZE || dy + py < 0 || dy + py >= SIZE){
       // plop the particle into some other random location
       px = rand() % SIZE;
       py = rand() % SIZE;
     }else if (world[py + dy][px + dx] != 0){
       // bumped into something
       world[py][px] = 1;
       break;
     }else{
       py += dy;
       px += dx;
     }
   }
 }

}

int main(){

 int world[SIZE][SIZE];
 FIBITMAP * img;
 RGBQUAD rgb;
 int x, y;

 memset(world, 0, sizeof world);
 srand((unsigned)time(NULL));
 draw_brownian_tree(world);
 img = FreeImage_Allocate(SIZE, SIZE, 32, 0, 0, 0);
 for (y = 0; y < SIZE; y++){
   for (x = 0; x < SIZE; x++){
     rgb.rgbRed = rgb.rgbGreen = rgb.rgbBlue = (world[y][x] ? 255 : 0);
     FreeImage_SetPixelColor(img, x, y, &rgb);
   }
 }
 FreeImage_Save(FIF_BMP, img, "brownian_tree.bmp", 0);
 FreeImage_Unload(img);

}</lang>

D

D V.2, from the C version, writes a Portable Bit Map image to the stdout. <lang d>import std.c.stdlib: rand, srand; import std.c.time: time; import std.stdio: printf, putchar;

enum int WORLD_WIDTH = 800; enum int WORLD_HEIGHT = WORLD_WIDTH; enum int NUM_PARTICLES = 10_000;

static assert(NUM_PARTICLES > 0); static assert(WORLD_WIDTH * WORLD_HEIGHT > NUM_PARTICLES);

typedef ubyte[WORLD_WIDTH][WORLD_HEIGHT] TWorld;


void dla(ref TWorld world) {

   int px, py; // particle values
   int dx, dy; // offsets
   // put the tree seed
   world[WORLD_HEIGHT / 2][WORLD_WIDTH / 2] = 1;
   foreach (_; 0 .. NUM_PARTICLES) {
       // set particle's initial position
       px = rand() % WORLD_WIDTH;
       py = rand() % WORLD_HEIGHT;
       while (true) { // move particle
           // randomly choose a direction
           dx = rand() % 3 - 1;
           dy = rand() % 3 - 1;
           if (dx + px < 0 || dx + px >= WORLD_WIDTH ||
               dy + py < 0 || dy + py >= WORLD_HEIGHT) {
               // plop the particle into some other random location
               px = rand() % WORLD_WIDTH;
               py = rand() % WORLD_HEIGHT;
           } else if (world[py + dy][px + dx]) {
               // bumped into something, particle set
               world[py][px] = 1;
               break;
           } else {
               py += dy;
               px += dx;
           }
       }
   }

}

void toPBM(ref TWorld world) {

   printf("P1\n"); // Type=Portable bitmap, Encoding=ASCII
   printf("%d %d\n", WORLD_WIDTH, WORLD_HEIGHT);
   foreach (ref line; world) {
       foreach (pixel; line)
           putchar(pixel ? '1' : '0');
       putchar('\n');
   }

}

void main() {

   srand(cast(uint)time(null));
   TWorld world;
   dla(world);
   toPBM(world);

}</lang>

Delphi

<lang delphi>const

   SIZE = 256;
   NUM_PARTICLES = 1000;

procedure TForm1.Button1Click(Sender: TObject); type

   TByteArray = array[0..0] of Byte;
   PByteArray = ^TByteArray;

var

   B: TBitmap;
   I: Integer;
   P, D: TPoint;

begin

   Randomize;
   B := TBitmap.Create;
   try
       B.Width := SIZE;
       B.Height := SIZE;
       B.PixelFormat := pf8bit;
       B.Canvas.Brush.Color := clBlack;
       B.Canvas.FillRect(B.Canvas.ClipRect);
       B.Canvas.Pixels[Random(SIZE), Random(SIZE)] := clWhite;
       For I := 0 to NUM_PARTICLES - 1 do
       Begin
           P.X := Random(SIZE);
           P.Y := Random(SIZE);
           While true do
           Begin
               D.X := Random(3) - 1;
               D.Y := Random(3) - 1;
               Inc(P.X, D.X);
               Inc(P.Y, D.Y);
               If ((P.X or P.Y) < 0) or (P.X >= SIZE) or (P.Y >= SIZE) Then
               Begin
                   P.X := Random(SIZE);
                   P.Y := Random(SIZE);
               end
               else if PByteArray(B.ScanLine[P.Y])^[P.X] <> 0 then
               begin
                   PByteArray(B.ScanLine[P.Y-D.Y])^[P.X-D.X] := $FF;
                   Break;
               end;
           end;
       end;
       Canvas.Draw(0, 0, B);
   finally
       FreeAndNil(B);
   end;

end;</lang>

Fortran

Works with: Fortran version 95 and later
Translation of: C

For RCImageBasic and RCImageIO, see Basic bitmap storage/Fortran and Write ppm file#Fortran

<lang fortran>program BrownianTree

 use RCImageBasic
 use RCImageIO
 implicit none
 integer, parameter :: num_particles = 1000
 integer, parameter :: wsize         = 800
 integer, dimension(wsize, wsize) :: world
 type(rgbimage) :: gworld
 integer :: x, y
 ! init seed
 call init_random_seed
 
 world = 0
 call draw_brownian_tree(world)
 call alloc_img(gworld, wsize, wsize)
 call fill_img(gworld, rgb(0,0,0))
 
 do y = 1, wsize
    do x = 1, wsize
       if ( world(x, y) /= 0 ) then
          call put_pixel(gworld, x, y, rgb(255, 255, 255))
       end if
    end do
 end do
 open(unit=10, file='browniantree.ppm', action='write')
 call output_ppm(10, gworld)
 close(10)
 call free_img(gworld)

contains

 ! this code is taken from the GNU gfortran online doc
 subroutine init_random_seed
   integer :: i, n, clock
   integer, dimension(:), allocatable :: seed
   call random_seed(size = n)
   allocate(seed(n))
   call system_clock(count = clock)
   seed = clock + 37 * (/ ( i - 1, i = 1, n) /)
   call random_seed(put = seed)
   deallocate(seed)
 end subroutine init_random_seed


 function randbetween(a, b) result(res) ! suppose a < b
   integer, intent(in) :: a, b
   integer :: res
   real :: r
   call random_number(r)
   res = a + int((b-a)*r + 0.5)
 end function randbetween
 function bounded(v, ll, ul) result(res)
   integer, intent(in) :: v, ll, ul
   logical res
   res = ( v >= ll ) .and. ( v <= ul )
 end function bounded


 subroutine draw_brownian_tree(w)
   integer, dimension(:,:), intent(inout) :: w
   integer :: px, py, dx, dy, i
   integer :: xsize, ysize
   xsize = size(w, 1)
   ysize = size(w, 2)
   w(randbetween(1, xsize), randbetween(1, ysize)) = 1
   
   do i = 1, num_particles
      px = randbetween(1, xsize)
      py = randbetween(1, ysize)
      
      do
         dx = randbetween(-1, 1)
         dy = randbetween(-1, 1)
         if ( .not. bounded(dx+px, 1, xsize) .or. .not. bounded(dy+py, 1, ysize) ) then
            px = randbetween(1, xsize)
            py = randbetween(1, ysize)
         else if ( w(px+dx, py+dy) /= 0 ) then
            w(px, py) = 1
            exit
         else
            py = py + dy
            px = px + dx
         end if
      end do
   end do
   
 end subroutine draw_brownian_tree

end program</lang>

Haskell

The modules Bitmap, Bitmap.Netpbm, and Bitmap.BW are on Rosetta Code. The commented-out type signatures require scoped type variables in order to function.

<lang haskell>import Control.Monad import Control.Monad.ST import Data.STRef import Data.Array.ST import System.Random import Bitmap import Bitmap.BW import Bitmap.Netpbm

main = do

   g <- getStdGen
   (t, _) <- stToIO $ drawTree (50, 50) (25, 25) 300 g
   writeNetpbm "/tmp/tree.pbm" t

drawTree :: (Int, Int) -> (Int, Int) -> Int -> StdGen -> ST s (Image s BW, StdGen) drawTree (width, height) start steps stdgen = do

   img <- image width height off
   setPix img (Pixel start) on
   gen <- newSTRef stdgen
   let -- randomElem :: [a] -> ST s a
       randomElem l = do
           stdgen <- readSTRef gen
           let (i, stdgen') = randomR (0, length l - 1) stdgen
           writeSTRef gen stdgen'
           return $ l !! i
       -- newPoint :: ST s (Int, Int)
       newPoint = do
           p <- randomElem border
           c <- getPix img $ Pixel p
           if c == off then return p else newPoint
       -- wander :: (Int, Int) -> ST s ()
       wander p = do
           next <- randomElem $ filter (inRange pointRange) $ adjacent p
           c <- getPix img $ Pixel next
           if c == on then setPix img (Pixel p) on else wander next
   replicateM_ steps $ newPoint >>= wander
   stdgen <- readSTRef gen
   return (img, stdgen)
 where pointRange = ((0, 0), (width - 1, height - 1))
       adjacent (x, y) = [(x - 1, y - 1), (x, y - 1), (x + 1, y - 1),
                          (x - 1, y),                 (x + 1, y),
                          (x - 1, y + 1), (x, y + 1), (x + 1, y + 1)]
       border = liftM2 (,) [0, width - 1] [0 .. height - 1] ++
                liftM2 (,) [1 .. width - 2] [0, height - 1]
       off = black
       on = white</lang>

J

<lang j>brtr=:4 :0

 seed=. ?x
 clip=. 0 >. (<:x) <."1 ]
 near=. [: clip +"1/&(,"0/~i:1)
 p=.i.0 2
 mask=. 1 (<"1 near seed)} x$0
 field=.1 (<seed)} x$0
 for.i.y do.
   p=. clip (p +"1 <:?3$~$p),?x
   b=.(<"1 p) { mask
   fix=. b#p
   if.#fix do. NB. if. works around j602 bug: 0(0#a:)}i.0 0
     p=. (-.b)# p
     mask=. 1 (<"1 near fix)} mask
     field=. 1 (<"1 fix)} field
   end.
 end.
 field

)</lang>

Example use:

<lang j> require'viewmat'

  viewmat 480 640 brtr 30000</lang>

Note that building a brownian tree like this takes a while and would be more interesting if this were animated.

Java

Library: Swing
Library: AWT

<lang java>import java.awt.Graphics; import java.awt.image.BufferedImage; import java.util.*; import javax.swing.JFrame;

public class BrownianTree extends JFrame implements Runnable {

   BufferedImage I;
   private List<Particle> particles;
   static Random rand = new Random();
   public BrownianTree() {
       super("Brownian Tree");
       setBounds(100, 100, 400, 300);
       setDefaultCloseOperation(EXIT_ON_CLOSE);
       I = new BufferedImage(getWidth(), getHeight(), BufferedImage.TYPE_INT_RGB);
       I.setRGB(I.getWidth() / 2, I.getHeight() / 2, 0xff00);
       particles = new LinkedList<Particle>();
   }
   @Override
   public void paint(Graphics g) {
       g.drawImage(I, 0, 0, this);
   }
   public void run() {
       for (int i = 0; i < 20000; i++) {
           particles.add(new Particle());
       }
       while (!particles.isEmpty()) {
           for (Iterator<Particle> it = particles.iterator(); it.hasNext();) {
               if (it.next().move()) {
                   it.remove();
               }
           }
           repaint();
       }
   }
   public static void main(String[] args) {
       BrownianTree b = new BrownianTree();
       b.setVisible(true);
       new Thread(b).start();
   }
   private class Particle {
       private int x, y;
       private Particle() {
           x = rand.nextInt(I.getWidth());
           y = rand.nextInt(I.getHeight());
       }
       /* returns true if either out of bounds or collided with tree */
       private boolean move() {
           int dx = rand.nextInt(3) - 1;
           int dy = rand.nextInt(3) - 1;
           if ((x + dx < 0) || (y + dy < 0)
                   || (y + dy >= I.getHeight()) || (x + dx >= I.getWidth())) {
               return true;
           }
           x += dx;
           y += dy;
           if ((I.getRGB(x, y) & 0xff00) == 0xff00) {
               I.setRGB(x - dx, y - dy, 0xff00);
               return true;
           }
           return false;
       }
   }

}</lang>

JavaScript + <canvas>

Live version <lang javascript>function brownian(canvasId, messageId) {

 var canvas = document.getElementById(canvasId);
 var ctx = canvas.getContext("2d");
 // Options
 var drawPos = true;
 var seedResolution = 50;
 var clearShade = 0; // 0..255
 
 // Static state
 var width = canvas.width;
 var height = canvas.height;
 var cx = width/2;
 var cy = height/2;
 var clearStyle = "rgba("+clearShade+", "+clearShade+", "+clearShade+", 1)";
 // Utilities
 function radius(x,y) {
   return Math.sqrt((x-cx)*(x-cy)+(y-cx)*(y-cy));
 }
 function test(x, y) {
   if (x < 0 || y < 0 || x >= width || y >= height)
     return false;
   var data = ctx.getImageData(x, y, 1, 1).data;
   return data[0] != clearShade || data[1] != clearShade || data[2] != clearShade;
 }
 var shade = 120;
 function setc(x, y, c) {
   //var imgd = ctx.createImageData(1, 1);
   //var pix = imgd.data;
   //pix[0] = pix[1] = pix[2] = c == 255 ? 255 : shade;
   //pix[3] = 255;
   //shade = (shade + 1) % 254;
   //ctx.putImageData(imgd, x, y);
   //ctx.fillStyle = "rgba("+c+", "+c+", "+c+", 1)";
   shade = (shade + 0.02) % 360;
   if (c) {
     ctx.fillStyle = "hsl("+shade+", 100%, 50%)";
   } else {
     ctx.fillStyle = clearStyle;
   }
   ctx.fillRect (x, y, 1, 1);
 }
 function set(x,y) {
   setc(x,y,true);
 }
 function clear(x,y) {
   setc(x,y,false);
 }
 // Initialize canvas to blank opaque
 ctx.fillStyle = clearStyle;
 ctx.fillRect (0, 0, width, height);
 // Current position
 var x;
 var y;
 // Farthest distance from center a particle has yet been placed.
 var closeRadius = 1;
 // Place seed
 set(cx, cy);
 // Choose a new random position for a particle (not necessarily unoccupied)
 function newpos() {
   // Wherever particles are injected, the tree will tend to grow faster 
   // toward it. Ideally, particles wander in from infinity; the best we
   // could do is to have them wander in from the edge of the field.
   // But in order to have the rendering occur in a reasonable time when
   // the seed is small, without too much visible bias, we instead place 
   // the particles in a coarse grid. The final tree will cover every
   // point on the grid.
   //
   // There's probably a better strategy than this.
   x = Math.floor(Math.random()*(width/seedResolution))*seedResolution;
   y = Math.floor(Math.random()*(height/seedResolution))*seedResolution;
 }
 newpos();
 var animation;
 animation = window.setInterval(function () {
   if (drawPos) clear(x,y);
   for (var i = 0; i < 10000; i++) {
     var ox = x;
     var oy = y;
     
     // Changing this to use only the first four directions will result
     // in a denser tree.
     switch (Math.floor(Math.random()*8)) {
       case 0: x++; break;
       case 1: x--; break;
       case 2: y++; break;
       case 3: y--; break;
       case 4: x++; y++; break;
       case 5: x--; y++; break;
       case 6: x++; y--; break;
       case 7: x--; y--; break;
     }
     if (x < 0 || y < 0 ||
         x >= width || y >= height ||
         radius(x,y) > closeRadius+seedResolution+2) {
       // wandered out of bounds or out of interesting range of the
       // tree, so pick a new spot
       var progress = 1000;
       do {
         newpos();
         progress--;
       } while ((test(x-1,y-1) || test(x,y-1) || test(x+1,y-1) ||
                 test(x-1,y  ) || test(x,y  ) || test(x+1,y  ) ||
                 test(x-1,y+1) || test(x,y+1) || test(x+1,y+1)) && progress > 0);
       if (progress <= 0) {
         document.getElementById(messageId).appendChild(document.createTextNode("Stopped for lack of room."));
         clearInterval(animation);
         break;
       }
     }
     if (test(x, y)) {
       // hit something, mark where we came from and pick a new spot
       set(ox,oy);
       closeRadius = Math.max(closeRadius, radius(ox,oy));
       newpos();
     }
  }
  if (drawPos) set(x,y);
 }, 1);

}</lang>

<lang html><html>

<head>
 <script src="brownian.js"></script>
</head>
<body onload="brownian('canvas', 'message')">
  <canvas id="canvas" width="402" height="402" style="border: 2px inset;"></canvas>
</body>

</html></lang>

Liberty BASIC

<lang lb>'[RC]Brownian motion tree

   nomainwin
   dim screen(600,600)
   WindowWidth = 600
   WindowHeight = 600
   open "Brownian" for graphics_nsb_nf as #1
   #1 "trapclose [quit]"
   #1 "down ; fill blue"
   rad=57.29577951
   particles=500
   'draw starting circle and mid point
   for n= 1 to 360
           x=300-(200*sin(n/rad))
           y=300-(200*cos(n/rad))
           #1, "color white ; set ";x;" ";y
           screen(x,y)=1
   next n
   #1, "color white ; set 300 300"
   screen(300,300)=1
   'set up initial particles
   dim particle(particles,9)'x y deltax deltay rotx roty
   for n = 1 to particles
       gosub [randomparticle]
   next
   'start timed drawing loop
   timer 17, [draw]
   wait


   [draw]
   #1 "discard"
   scan
   for n = 1 to particles
       oldx=particle(n,1)
       oldy=particle(n,2)
       'erase particle
       if not(screen(oldx,oldy)) then
           #1 "color blue ; set ";oldx;" ";oldy
       end if
       'move particle x
       particle(n,1)=particle(n,1)+int((sin(particle(n,6)/rad)*10)+particle(n,3))
       particle(n,5)=particle(n,5)+6 mod 360
       if particle(n,1)>599 or particle(n,1)<1 then gosub [randomparticle]
       'move particle y
       particle(n,2)=particle(n,2)+int((sin(particle(n,5)/rad)*10)+particle(n,4))
       particle(n,6)=particle(n,6)+6 mod 360
       if particle(n,2)>599 or particle(n,2)<1 then gosub [randomparticle]
       'checkhit
       x=particle(n,1)
       y=particle(n,2)
       if screen(x-1,y-1) or screen(x-1,y) or screen(x-1,y+1)_
       or screen(x,y-1) or screen(x,y) or screen(x,y+1)_
       or screen(x+1,y-1) or screen(x+1,y) or screen(x+1,y+1) then
           #1 "color white ; set ";particle(n,1);" ";particle(n,2)
           screen(particle(n,1),particle(n,2))=1
       else
           #1 "color red ; set ";particle(n,1);" ";particle(n,2)
       end if
   next
   wait


   [randomparticle]
   particle(n,1)=int(rnd(0)*599)+1
   particle(n,2)=int(rnd(0)*599)+1
   particle(n,3)=int(2-rnd(0)*4)
   particle(n,4)=int(2-rnd(0)*4)
   particle(n,5)=int(rnd(0)*360)
   particle(n,6)=int(rnd(0)*360)
   return
   [quit]
   timer 0
   close #1
   end</lang>

Mathematica

There is a prettier version at the Mathematica demo site. Its source code is also available there but it is not mine.

Loose
Translation of: D

<lang Mathematica>canvasdim = 1000; n = 0.5*canvasdim^2; canvas = ConstantArray[0, {canvasdim, canvasdim}]; init = Floor@(0.5*{canvasdim,

    canvasdim});(*RandomInteger[canvasdim,2]*)

canvas[[init1, init2]] = 1; (*1st particle initialized to midpoint*)

Monitor[(*Provides real-time intermediate result monitoring*)

Do[
 particle = RandomInteger[canvasdim, 2];
 While[True,
  ds = RandomInteger[{-1, 1}, 2];
  While[(*New Particle Domain Limit Section*)
   !And @@ (0 < (particle + ds)# <= canvasdim & /@ {1, 2}),
   particle = RandomInteger[canvasdim, 2];
   ];
  (* Particle Aggregation Section *)
  If[canvas[[(particle + ds)1, (particle + ds)2]] > 0,
   canvas[[particle1, particle2]] = i;
   Break[],
   particle += ds
   ];
  ],
 {i, n}],
{i, (particle + ds), MatrixPlot@canvas}
]

MatrixPlot[canvas,FrameTicks->None,ColorFunction->"DarkRainbow",ColorRules->{0 -> None}]</lang>

Result:

OCaml

Translation of: D

<lang ocaml>let world_width = 800 let world_height = 800 let num_particles = 10_000

let () =

 assert(num_particles > 0);
 assert(world_width * world_height > num_particles);

let dla ~world =

 (* particle values *)
 let px = ref 0
 and py = ref 0 in

 (* put the tree seed *)
 world.(world_height / 2).(world_width / 2) <- 1;

 for i = 1 to num_particles do
   (* set particle's initial position *)
   px := Random.int world_width;
   py := Random.int world_height;

   try
     while (true) do  (* move particle *)
       (* randomly choose a direction *)
       let dx = (Random.int 3) - 1  (* offsets *)
       and dy = (Random.int 3) - 1 in

       if (dx + !px < 0 || dx + !px >= world_width ||
           dy + !py < 0 || dy + !py >= world_height) then begin
         (* plop the particle into some other random location *)
         px := Random.int world_width;
         py := Random.int world_height;
       end
       else if (world.(!py + dy).(!px + dx) <> 0) then begin
         (* bumped into something, particle set *)
         world.(!py).(!px) <- 1;
         raise Exit;
       end
       else begin
         py := !py + dy;
         px := !px + dx;
       end
     done
   with Exit -> ()
 done

let to_pbm ~world =

 print_endline "P1";  (* Type=Portable bitmap, Encoding=ASCII *)
 Printf.printf "%d %d\n" world_width world_height;
 Array.iter (fun line ->
   Array.iter (fun pixel -> print_int pixel) line;
   print_newline()
 ) world

let () =

 Random.self_init();
 let world = Array.make_matrix world_width world_height 0 in
 dla ~world;
 to_pbm ~world;
</lang>

Octave

Translation of: C

<lang octave>function r = browniantree(xsize, ysize = xsize, numparticle = 1000)

 r = zeros(xsize, ysize, "uint8");
 r(unidrnd(xsize), unidrnd(ysize)) = 1;
 
 for i = 1:numparticle
   px = unidrnd(xsize-1)+1;
   py = unidrnd(ysize-1)+1;
   while(1)
     dx = unidrnd(2) - 1;
     dy = unidrnd(2) - 1;
     if ( (dx+px < 1) || (dx+px > xsize) || (dy+py < 1) || (dy+py > ysize) )

px = unidrnd(xsize-1)+1; py = unidrnd(ysize-1)+1;

     elseif ( r(px+dx, py+dy) != 0 )

r(px, py) = 1; break;

     else

px += dx; py += dy;

     endif
   endwhile
 endfor

endfunction

r = browniantree(200); r( r > 0 ) = 255; jpgwrite("browniantree.jpg", r, 100); % image package</lang>

PicoLisp

<lang PicoLisp>(load "@lib/simul.l")

(de brownianTree (File Size Cnt)

  (let Img (grid Size Size)
     (put Img (/ Size 2) (/ Size 2) 'pix T)
     (use (P Q)
        (do Cnt
           (setq P (get Img (rand 1 Size) (rand 1 Size)))
           (loop
              (setq Q ((if2 (rand T) (rand T) north east south west) P))
              (T (; Q pix) (put P 'pix T))
              (setq P (or Q (get Img (rand 1 Size) (rand 1 Size)))) ) ) )
     (out "img.pbm"
        (prinl "P1")
        (prinl Size " " Size)
        (for L Img
           (for This L
              (prin (if (: pix) 1 0)) )
           (prinl) ) ) ) )</lang>

Use:

(brownianTree "img.pbm" 300 9000)
(call 'display "img.pbm")

PureBasic

<lang PureBasic>#Window1 = 0

  1. Image1 = 0
  2. ImgGadget = 0
  1. NUM_PARTICLES = 3000
  2. width = 200
  3. height = 200
  4. xmax = #width -3
  5. ymax = #height -3

Define.i Event ,i ,x,y

If OpenWindow(#Window1, 0, 0, #width, #height, "Brownian Tree PureBasic Example", #PB_Window_SystemMenu )

  If CreateImage(#Image1, #width, #height)
     ImageGadget(#ImgGadget, 0, 0, #width, #height, ImageID(#Image1))
     StartDrawing(ImageOutput(#Image1))
     FrontColor($FFFFFF)
     Plot( Random(#xmax) , Random(#ymax ))
     StopDrawing()
     SetGadgetState(#ImgGadget, ImageID(#Image1))
     For i = 1 To #NUM_PARTICLES
         x = Random(#xmax)+1 : y = Random (#ymax)+1
         StartDrawing(ImageOutput(#Image1))
         While Point(x+1, y+1) + Point(x, y+1)+Point(x+1, y)+Point(x-1, y-1)+Point(x-1, y)+Point(x, y-1) = 0
             x = x + (Random(2)-1) : y = y + (Random(2)-1) 
             If x < 1 Or x > #xmax Or y < 1 Or y > #ymax
                 x = Random(#xmax)+1 : y = Random (#ymax)+1
             EndIf   
         Wend
         Plot(x,y) 
         StopDrawing()
         SetGadgetState(#ImgGadget, ImageID(#Image1))          
     Next
     
  EndIf
   Repeat
     Event = WaitWindowEvent()
   Until Event = #PB_Event_CloseWindow

EndIf</lang>


Python

Library: pygame

<lang python>import pygame, sys, os from pygame.locals import * from random import randint pygame.init()

MAXSPEED = 15 SIZE = 3 COLOR = (45, 90, 45) WINDOWSIZE = 400 TIMETICK = 1 MAXPART = 50

freeParticles = pygame.sprite.Group() tree = pygame.sprite.Group()

window = pygame.display.set_mode((WINDOWSIZE, WINDOWSIZE)) pygame.display.set_caption("Brownian Tree")

screen = pygame.display.get_surface()


class Particle(pygame.sprite.Sprite):

   def __init__(self, vector, location, surface):
       pygame.sprite.Sprite.__init__(self)
       self.vector = vector
       self.surface = surface
       self.accelerate(vector)
       self.add(freeParticles)
       self.rect = pygame.Rect(location[0], location[1], SIZE, SIZE)
       self.surface.fill(COLOR, self.rect)
   def onEdge(self):
       if self.rect.left <= 0:
           self.vector = (abs(self.vector[0]), self.vector[1])
       elif self.rect.top <= 0:
           self.vector = (self.vector[0], abs(self.vector[1]))
       elif self.rect.right >= WINDOWSIZE:
           self.vector = (-abs(self.vector[0]), self.vector[1])
       elif self.rect.bottom >= WINDOWSIZE:
           self.vector = (self.vector[0], -abs(self.vector[1]))
   def update(self):
       if freeParticles in self.groups():
           self.surface.fill((0,0,0), self.rect)
           self.remove(freeParticles)
           if pygame.sprite.spritecollideany(self, freeParticles):
               self.accelerate((randint(-MAXSPEED, MAXSPEED), 
                                randint(-MAXSPEED, MAXSPEED)))
               self.add(freeParticles)
           elif pygame.sprite.spritecollideany(self, tree):
               self.stop()
           else:
               self.add(freeParticles)
               
           self.onEdge()
           if (self.vector == (0,0)) and tree not in self.groups():
               self.accelerate((randint(-MAXSPEED, MAXSPEED), 
                                randint(-MAXSPEED, MAXSPEED)))
           self.rect.move_ip(self.vector[0], self.vector[1])
       self.surface.fill(COLOR, self.rect)
   def stop(self):
       self.vector = (0,0)
       self.remove(freeParticles)
       self.add(tree)
   def accelerate(self, vector):
       self.vector = vector

NEW = USEREVENT + 1 TICK = USEREVENT + 2

pygame.time.set_timer(NEW, 50) pygame.time.set_timer(TICK, TIMETICK)


def input(events):

   for event in events:
       if event.type == QUIT:
           sys.exit(0)
       elif event.type == NEW and (len(freeParticles) < MAXPART):
           Particle((randint(-MAXSPEED,MAXSPEED),
                     randint(-MAXSPEED,MAXSPEED)),
                    (randint(0, WINDOWSIZE), randint(0, WINDOWSIZE)), 
                    screen)
       elif event.type == TICK:
           freeParticles.update()


half = WINDOWSIZE/2 tenth = WINDOWSIZE/10

root = Particle((0,0),

               (randint(half-tenth, half+tenth), 
                randint(half-tenth, half+tenth)), screen)

root.stop()

while True:

   input(pygame.event.get())
   pygame.display.flip()</lang>

Ruby

Library: RMagick

<lang ruby>require 'rubygems' require 'RMagick'

NUM_PARTICLES = 1000 SIZE = 800

def draw_brownian_tree world

 # set the seed
 world[rand SIZE][rand SIZE] = 1
 NUM_PARTICLES.times do
   # set particle's position
   px = rand SIZE
   py = rand SIZE
   loop do
     # randomly choose a direction
     dx = rand(3) - 1
     dy = rand(3) - 1
     if dx + px < 0 or dx + px >= SIZE or dy + py < 0 or dy + py >= SIZE
       # plop the particle into some other random location
       px = rand SIZE
       py = rand SIZE
     elsif world[py + dy][px + dx] != 0
       # bumped into something
       world[py][px] = 1
       break
     else
       py += dy
       px += dx
     end
   end
 end

end

world = Array.new(SIZE) { Array.new(SIZE, 0) } srand Time.now.to_i

draw_brownian_tree world

img = Magick::Image.new(SIZE, SIZE) do

 self.background_color = "black"

end

draw = Magick::Draw.new draw.fill "white"

world.each_with_index do |row, y|

 row.each_with_index do |colour, x|
   draw.point x, y if colour != 0
 end

end

draw.draw img img.write "brownian_tree.bmp"</lang>

Tcl

Library: Tk

<lang tcl>package require Tcl 8.5 package require Tk

set SIZE 300

image create photo brownianTree -width $SIZE -height $SIZE interp alias {} plot {} brownianTree put white -to brownianTree put black -to 0 0 [expr {$SIZE-1}] [expr {$SIZE-1}] proc rnd {range} {expr {int(rand() * $range)}}

proc makeBrownianTree count {

   global SIZE
   # Set the seed
   plot [rnd $SIZE] [rnd $SIZE]
   for {set i 0} {$i<$count} {incr i} {

# Set a random particle's initial position set px [rnd $SIZE] set py [rnd $SIZE]

while 1 { # Randomly choose a direction set dx [expr {[rnd 3] - 1}] set dy [expr {[rnd 3] - 1}]

# If we are going out of bounds... if {$px+$dx < 0 || $px+$dx >= $SIZE || $py+$dy < 0 || $py+$dy>=$SIZE} { # Out of bounds, so move back in set dx [expr {[rnd 3] - 1}] set dy [expr {[rnd 3] - 1}] continue }

set ox $px set oy $py # Move/see if we would hit anything incr px $dx incr py $dy if {[lindex [brownianTree get $px $py] 0]} { # Hit something, so plot where we were plot $ox $oy break } } ## For display while things are processing, uncomment next line #update;puts -nonewline .;flush stdout

   }

}

pack [label .l -image brownianTree] update makeBrownianTree 1000 brownianTree write tree.ppm</lang>