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.

AutoHotkey

Works with: AutoHotkey_L

Takes a little while to run, be patient. Requires the GDI+ Standard Library by Tic <lang AHK>SetBatchLines -1 Process, Priority,, high size := 400 D  := .08 num  := size * size * d field:= Object() field[size//2, size//2] := true ; set the seed lost := 0

Loop % num { x := Rnd(1, size), y := Rnd(1, size) Loop { oldX := X, oldY := Y x += Rnd(-1, 1), y += Rnd(1, -1) If ( field[x, y] ) { field[oldX, oldY] := true break } If ( X > Size ) or ( Y > Size) or ( X < 1 ) or ( Y < 1 ) { lost++ break } } }

pToken  := Gdip_startup() pBitmap := Gdip_CreateBitmap(size, size) loop %size% { x := A_index Loop %size% { If ( field[x, A_Index] ) { Gdip_SetPixel(pBitmap, x, A_Index, 0xFF0000FF) } } } Gdip_SaveBitmapToFile(pBitmap, "brownian.png") Gdip_DisposeImage(pBitmap) Gdip_Shutdown(pToken) Run brownian.png

MsgBox lost %lost%

Rnd(min, max){ Random, r, min, max return r }</lang>Sample output file here

BBC BASIC

<lang bbcbasic> SYS "SetWindowText", @hwnd%, "Brownian Tree"

     SIZE = 400
     
     VDU 23,22,SIZE;SIZE;8,16,16,0
     GCOL 10
     
     REM set the seed:
     PLOT SIZE, SIZE
     
     OFF
     REPEAT
       
       REM set particle's initial position:
       REPEAT
         X% = RND(SIZE)-1
         Y% = RND(SIZE)-1
       UNTIL POINT(2*X%,2*Y%) = 0
       
       REPEAT
         oldX% = X%
         oldY% = Y%
         X% += RND(3) - 2
         Y% += RND(3) - 2
       UNTIL POINT(2*X%,2*Y%)
       IF X%>=0 IF X%<SIZE IF Y%>=0 IF Y%<SIZE PLOT 2*oldX%,2*oldY%
       
     UNTIL FALSE
     

</lang>

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>

Bold text

Alternative Version

Translation of: D

This version writes the image as Portable Bit Map to stdout and doesn't move already set particles. <lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <time.h>
  3. include <stdbool.h>
  1. define SIDE 600
  2. define NUM_PARTICLES 10000

bool W[SIDE][SIDE];

int main() {

   srand((unsigned)time(NULL));
   W[SIDE / 2][SIDE / 2] = true;
   for (int i = 0; i < NUM_PARTICLES; i++) {
       unsigned int x, y;
       OVER: do {
           x = rand() % (SIDE - 2) + 1;
           y = rand() % (SIDE - 2) + 1;
       } while (W[y][x]);
       while (W[y-1][x-1] + W[y-1][x] + W[y-1][x+1] +
              W[y][x-1]               + W[y][x+1] +
              W[y+1][x-1] + W[y+1][x] + W[y+1][x+1] == 0) {
           unsigned int dxy = rand() % 8;
           if (dxy > 3) dxy++;
           x += (dxy % 3) - 1;
           y += (dxy / 3) - 1;
           if (x < 1 || x >= SIDE - 1 || y < 1 || y >= SIDE - 1)
               goto OVER;
       }
       W[y][x] = true;
   }
   printf("P1\n%d %d\n", SIDE, SIDE);
   for (int r = 0; r < SIDE; r++) {
       for (int c = 0; c < SIDE; c++)
           printf("%d ", W[r][c]);
       putchar('\n');
   }
   return 0;

}</lang> Run-time about 12.4 seconds with SIDE=600, NUM_PARTICLES=10000.

C++

For an animated version see: Brownian tree animated <lang cpp>

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

//-------------------------------------------------------------------------------------------------- using namespace std;

//-------------------------------------------------------------------------------------------------- enum states { SEED, GROWING, MOVING, REST }; enum treeStates { NONE, MOVER, TREE }; const int MAX_SIDE = 480, MAX_MOVERS = 511, MAX_CELLS = 15137;

//-------------------------------------------------------------------------------------------------- class point { public:

   point()                  { x = y = 0; }
   point( int a, int b )    { x = a; y = b; }
   void set( int a, int b ) { x = a; y = b; }
   int x, y;

}; //-------------------------------------------------------------------------------------------------- class movers { public:

   point pos;
   bool moving;
   movers() : moving( false ){}

}; //-------------------------------------------------------------------------------------------------- class myBitmap { public:

   myBitmap() : pen( NULL ) {}
   ~myBitmap()
   {

DeleteObject( pen ); 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()
   {

ZeroMemory( pBits, width * height * sizeof( DWORD ) );

   }
   void setPenColor( DWORD clr )
   {

if( pen ) DeleteObject( pen ); pen = CreatePen( PS_SOLID, 1, clr ); SelectObject( hdc, pen );

   }
   void saveBitmap( string path )
   {

BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; DWORD* dwpBits; DWORD wb; HANDLE file;

GetObject( bmp, sizeof( bitmap ), &bitmap );

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 );

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()     { return hdc; }
   int getWidth()  { return width; }
   int getHeight() { return height; }

private:

   HBITMAP bmp;
   HDC	    hdc;
   HPEN    pen;
   void    *pBits;
   int	    width, height;

}; //-------------------------------------------------------------------------------------------------- class brownianTree { public:

   brownianTree()         
   { 

_bmp.create( MAX_SIDE, MAX_SIDE ); init();

   }
   void init()
   {

_cellCount = 0; ZeroMemory( _grid, sizeof( _grid ) ); _bmp.clear(); _state = SEED;

   }

bool mainLoop()

   {

switch( _state ) { case REST: saveTree(); return false; case SEED: doSeed(); break; case GROWING: startMovers(); break; case MOVING: moveMovers(); } return true; }

   myBitmap* getBmp() { return &_bmp; }

private:

   void saveTree()
   {

for( int y = 0; y < MAX_SIDE; y++ ) for( int x = 0; x < MAX_SIDE; x++ ) if( _grid[x][y] == TREE ) SetPixel( _bmp.getDC(), x, y, RGB( 255, 120, 0 ) );

       _bmp.saveBitmap( "f:\\rc\\tree.bmp" );
   }
   void doSeed()
   {

int x = MAX_SIDE - MAX_SIDE / 2, y = MAX_SIDE / 4; _grid[rand() % x + y][rand() % x + y] = TREE; _cellCount++; _state = GROWING;

   }
   void addMover( movers* m )
   {

m->moving = true; int x = MAX_SIDE - MAX_SIDE / 2, y = MAX_SIDE / 4, a, b; while( true ) { a = rand() % x + y; b = rand() % x + y; if( _grid[a][b] == NONE ) break; }

m->pos.set( a, b ); _grid[a][b] = MOVER;

   }
   void startMovers()
   {

movers* m; for( int c = 0; c < MAX_MOVERS; c++ ) { m = &_movers[c]; addMover( m ); } _state = MOVING;

   }
   void addToTree( movers* m )
   {

m->moving = false; _grid[m->pos.x][m->pos.y] = TREE; if( ++_cellCount >= MAX_CELLS ) _state = REST;

COORD c = { 0, 1 }; SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), c ); cout << "Cells added: " << _cellCount << " from " << MAX_CELLS << " => " << static_cast<float>( 100 * _cellCount ) / static_cast<float>( MAX_CELLS ) << "% ";

   }
   bool moveIt( movers* m )
   {

point f[8]; int ff = 0; for( int y = -1; y < 2; y++ ) { for( int x = -1; x < 2; x++ ) { if( !x && !y ) continue; int a = m->pos.x + x, b = m->pos.y + y; if( a < 0 || b < 0 || a >= MAX_SIDE || b >= MAX_SIDE ) { addToTree( m ); return true; } switch( _grid[a][b] ) { case TREE: addToTree( m ); return true; case NONE: f[ff++].set( a, b ); } }

       }

if( ff < 1 ) return false;

_grid[m->pos.x][m->pos.y] = NONE; m->pos = f[rand() % ff]; _grid[m->pos.x][m->pos.y] = MOVER;

return false;

   }
   void moveMovers()
   {

movers* mm; for( int m = 0; m < MAX_MOVERS; m++ ) { mm = &_movers[m]; if( !mm->moving ) continue; if( moveIt( mm ) && _cellCount < MAX_CELLS ) addMover( mm ); }

   }
   states   _state;
   BYTE     _grid[MAX_SIDE][MAX_SIDE];
   myBitmap _bmp;
   int      _cellCount;
   movers   _movers[MAX_MOVERS];

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

   ShowWindow( GetConsoleWindow(), SW_MAXIMIZE );
   srand( GetTickCount() );
   brownianTree tree;
   DWORD now = GetTickCount();
   while( tree.mainLoop() );
   now = GetTickCount() - now;
   cout << endl << endl << "It took " << now / 1000 << " seconds to complete the task!" << endl << endl;
   BitBlt( GetDC( GetConsoleWindow() ), 20, 90, MAX_SIDE, MAX_SIDE, tree.getBmp()->getDC(), 0, 0, SRCCOPY );
   system( "pause" );
   return 0;

} //-------------------------------------------------------------------------------------------------- </lang>

C#

Works with: C# version 3.0

<lang csharp>using System; using System.Drawing;

namespace BrownianTree {

   class Program
   {
       static Bitmap BrownianTree(int size, int numparticles)
       {
           Bitmap bmp = new Bitmap(size, size);
           Rectangle bounds = new Rectangle { X = 0, Y = 0, Size = bmp.Size };
           using (Graphics g = Graphics.FromImage(bmp))
           {
               g.Clear(Color.Black);
           }
           Random rnd = new Random();
           bmp.SetPixel(rnd.Next(size), rnd.Next(size), Color.White);
           Point pt = new Point(), newpt = new Point();
           for (int i = 0; i < numparticles; i++)
           {
               pt.X = rnd.Next(size);
               pt.Y = rnd.Next(size);
               do
               {
                   newpt.X = pt.X + rnd.Next(-1, 2);
                   newpt.Y = pt.Y + rnd.Next(-1, 2);
                   if (!bounds.Contains(newpt))
                   {
                       pt.X = rnd.Next(size);
                       pt.Y = rnd.Next(size);
                   }
                   else if (bmp.GetPixel(newpt.X, newpt.Y).R > 0)
                   {
                       bmp.SetPixel(pt.X, pt.Y, Color.White);
                       break;
                   }
                   else
                   {
                       pt = newpt;
                   }
               } while (true);
           }
           return bmp;
       }
       static void Main(string[] args)
       {
           BrownianTree(300, 3000).Save("browniantree.png");
       }
   }

}</lang>

D

Uses the module of the Grayscale Image task. Partial

Translation of: PureBasic

<lang d>import core.stdc.stdio, std.random, grayscale_image;

enum uint side = 600; // Square world side. enum uint num_particles = 1_000; static assert(side > 2 && num_particles < (side ^^ 2 * 0.7));

void main() {

   auto rng = Xorshift(unpredictableSeed);
   ubyte[side][side] W; // World.
   W[side / 2][side / 2] = 1; // Set tree root.
   foreach (immutable _; 0 .. num_particles) {
       // Random initial particle position.
       OVER: uint x, y;
       do {
           x = uniform(1, side - 1, rng);
           y = uniform(1, side - 1, rng);
       } while (W[y][x]); // Assure the chosen cell is empty.
       while (W[y-1][x-1] + W[y-1][x] + W[y-1][x+1] +
              W[y][x-1]               + W[y][x+1] +
              W[y+1][x-1] + W[y+1][x] + W[y+1][x+1] == 0) {
           // Randomly choose a direction (Moore neighborhood).
           uint dxy = uniform(0, 8, rng);
           if (dxy > 3) dxy++; // To avoid the center.
           x += (dxy % 3) - 1;
           y += (dxy / 3) - 1;
           if (x < 1 || x >= side - 1 || y < 1 || y >= side - 1)
               goto OVER;
       }
       W[y][x] = 1; // Touched, set the cell.
   }
   ubyte[] data = (&W[0][0])[0 .. side ^^ 2]; // Flat view.
   data[] += 255;
   Image!ubyte.fromData(data, side,side).savePGM("brownian_tree.pgm");

}</lang> World side = 600, num_particles = 10_000, cropped, about 20 seconds run-time:

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>

Fantom

<lang fantom> using fwt using gfx

class Main {

 public static Void main ()
 {
   particles := Particles (300, 200)
   1000.times { particles.addParticle } // add 1000 particles
   Window // open up a display for the final tree
   {
     title = "Brownian Tree"
     EdgePane
     {
       center = ScrollPane { content = ParticleCanvas(particles) }
     },
   }.open
 }

}

class Particles {

 Bool[][] image
 Int height
 Int width
 new make (Int height, Int width) 
 {
   this.height = height
   this.width = width
   // set up initial image as an array of booleans with one set cell 
   image = [,]
   width.times |w|
   {
     row := [,] 
     height.times { row.add (false) }
     image.add (row)
   }
   image[Int.random(0..<width)][Int.random(0..<height)] = true
 }
 Bool get (Int w, Int h) { return image[w][h] }
 Void addParticle ()
 { 
   x := Int.random(0..<width)
   y := Int.random(0..<height)
   Int dx := 0
   Int dy := 0 
   while (!image[x][y]) // loop until hit existing part of the tree
   {
     dx = [-1,0,1].random
     dy = [-1,0,1].random
     if ((0..<width).contains(x + dx))  
       x += dx
     else // did not change x, so set dx = 0
       dx = 0
     if ((0..<height).contains(y + dy)) 
       y += dy
     else
       dy = 0
   }
   // put x,y back to just before move onto existing part of tree
   x -= dx
   y -= dy
   image[x][y] = true
 }

}

class ParticleCanvas : Canvas {

 Particles particles
 
 new make (Particles particles) { this.particles = particles }
 // provides canvas size for parent scrollpane 
 override Size prefSize(Hints hints := Hints.defVal)
 { 
   Size(particles.width, particles.height)
 }
 // repaint the display
 override Void onPaint (Graphics g)
 { 
   g.brush = Color.black
   g.fillRect(0, 0, size.w, size.h)
   g.brush = Color.green
   particles.width.times |w|
   {
     particles.height.times |h|
     { 
       if (particles.get(w, h)) // draw a 1x1 square for each set particle
         g.fillRect (w, h, 1, 1)
     }
   }
 }

} </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>

Go

Output png

The interpretation here of "collide" in the case of a new particle generated on top of a pixel of the existing tree is not to ignore the particle, but to find a place for it nearby. This properly increases the brightness of the area, reflecting that a particle was generated in the area. Visually, it appears to strengthen existing spines of the tree.

Using standard image library: <lang go>package main

import (

   "fmt"
   "image"
   "image/color"
   "image/png"
   "math/rand"
   "os"

)

const w = 400 // image width const h = 300 // image height const n = 15000 // number of particles to add const frost = 255 // white

var g *image.Gray

func main() {

   g = image.NewGray(image.Rectangle{image.Point{0, 0}, image.Point{w, h}})
   // off center seed position makes pleasingly asymetrical tree
   g.SetGray(w/3, h/3, color.Gray{frost})

generate:

   for a := 0; a < n; {
       // generate random position for new particle
       rp := image.Point{rand.Intn(w), rand.Intn(h)}
       if g.At(rp.X, rp.Y).(color.Gray).Y == frost {
           // position is already set.  find a nearby free position.
           for {
               rp.X += rand.Intn(3) - 1
               rp.Y += rand.Intn(3) - 1
               // execpt if we run out of bounds, consider the particle lost.
               if !rp.In(g.Rect) {
                   continue generate
               }
               if g.At(rp.X, rp.Y).(color.Gray).Y != frost {
                   break
               }
           }
       } else {
           // else particle is in free space.  let it wander
           // until it touches tree
           for !hasNeighbor(rp) {
               rp.X += rand.Intn(3) - 1
               rp.Y += rand.Intn(3) - 1
               // but again, if it wanders out of bounds consider it lost.
               if !rp.In(g.Rect) {
                   continue generate
               }
           }
       }
       // x, y now specify a free position toucing the tree.
       g.SetGray(rp.X, rp.Y, color.Gray{frost})
       a++
       // progress indicator
       if a%100 == 0 {
           fmt.Println(a, "of", n)
       }
   }
   f, err := os.Create("tree.png")
   if err != nil {
       fmt.Println(err)
       return
   }
   err = png.Encode(f, g)
   if err != nil {
       fmt.Println(err)
   }
   f.Close()

}

var n8 = []image.Point{

   {-1, -1}, {-1, 0}, {-1, 1},
   {0, -1}, {0, 1},
   {1, -1}, {1, 0}, {1, 1}}

func hasNeighbor(p image.Point) bool {

   for _, n := range n8 {
       o := p.Add(n)
       if o.In(g.Rect) && g.At(o.X, o.Y).(color.Gray).Y == frost {
           return true
       }
   }
   return false

}</lang> Nearly the same, version below works with code from the bitmap task: <lang go>package main

// Files required to build supporting package raster are found in: // * Bitmap // * Grayscale image // * Write a PPM file

import (

   "fmt"
   "math/rand"
   "raster"

)

const w = 400 // image width const h = 300 // image height const n = 15000 // number of particles to add const frost = 65535 // white

var g *raster.Grmap

func main() {

   g = raster.NewGrmap(w, h)
   // off center seed position makes pleasingly asymetrical tree
   g.SetPx(w/3, h/3, frost)
   var x, y int

generate:

   for a := 0; a < n; {
       // generate random position for new particle
       x, y = rand.Intn(w), rand.Intn(h)
       switch p, ok := g.GetPx(x, y); p {
       case frost:
           // position is already set.  find a nearby free position.
           for p == frost {
               x += rand.Intn(3) - 1
               y += rand.Intn(3) - 1
               p, ok = g.GetPx(x, y)
               // execpt if we run out of bounds, consider the particle lost.
               if !ok {
                   continue generate
               }
           }
       default:
           // else particle is in free space.  let it wander
           // until it touches tree
           for !hasNeighbor(x, y) {
               x += rand.Intn(3) - 1
               y += rand.Intn(3) - 1
               // but again, if it wanders out of bounds consider it lost.
               _, ok = g.GetPx(x, y)
               if !ok {
                   continue generate
               }
           }
       }
       // x, y now specify a free position toucing the tree.
       g.SetPx(x, y, frost)
       a++
       // progress indicator
       if a%100 == 0 {
           fmt.Println(a, "of", n)
       }
   }
   g.Bitmap().WritePpmFile("tree.ppm")

}

var n8 = [][]int{

   {-1, -1}, {-1, 0}, {-1, 1},
   { 0, -1},          { 0, 1},
   { 1, -1}, { 1, 0}, { 1, 1}}

func hasNeighbor(x, y int) bool {

   for _, n := range n8 {
       if p, ok := g.GetPx(x+n[0], y+n[1]); ok && p == frost {
           return true
       }
   }
   return false

}</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>

Icon and Unicon

400x400 PA=70% SA=50% D=8%

In this version the seed is randomly set within an inner area and particles are injected in an outer ring.

<lang Icon>link graphics,printf

procedure main() # brownian tree

Density  := .08 # % particles to area SeedArea := .5 # central area to confine seed ParticleArea := .7 # central area to exclude particles appearing Height := Width := 400 # canvas

Particles := Height * Width * Density Field := list(Height) every !Field := list(Width)

Size := sprintf("size=%d,%d",Width,Height) Fg  := sprintf("fg=%s",?["green","red","blue"]) Label := sprintf("label=Brownian Tree %dx%d PA=%d%% SA=%d%% D=%d%%",

        Width,Height,ParticleArea*100,SeedArea*100,Density*100)

WOpen(Label,Size,Fg,"bg=black") | stop("Unable to open Window")

sx := Height * SetInside(SeedArea) sy := Width * SetInside(SeedArea) Field[sx,sy] := 1 DrawPoint(sx,sy) # Seed the field

Lost := 0

every 1 to Particles do {

  repeat {
     px := Height * SetOutside(ParticleArea)
     py := Width  * SetOutside(ParticleArea)
     if /Field[px,py] then 
        break               # don't materialize in the tree
     }      
  repeat {
     dx := delta() 
     dy := delta()
     if not ( xy := Field[px+dx,py+dy] ) then {
        Lost +:= 1
        next                # lost try again
        }
     if \xy then
        break               # collision
   
     px +:= dx              # move to clear spot
     py +:= dy
     }
  Field[px,py] := 1
  DrawPoint(px,py)          # Stick the particle  
  }

printf("Brownian Tree Complete: Particles=%d Lost=%d.\n",Particles,Lost) WDone() end

procedure delta() #: return a random 1 pixel perturbation

  return integer(?0 * 3) - 1

end

procedure SetInside(core) #: set coord inside area

  return core * ?0 + (1-core)/2

end

procedure SetOutside(core) #: set coord outside area

  pt := ?0 * (1 - core)  
  pt +:= ( pt > (1-core)/2, core)
  return pt

end</lang>

graphics.icn provides graphics printf.icn provides printf

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>

Lua

The output is stored in as a ppm-image. The source code of these output-functions is located at Bitmap/Write a PPM file#Lua, Grayscale image#Lua, Basic bitmap storage#Lua. <lang lua>function SetSeed( f )

   for i = 1, #f[1] do         -- the whole boundary of the scene is used as the seed
       f[1][i]  = 1
       f[#f][i] = 1
   end
   for i = 1, #f do
       f[i][1]     = 1
       f[i][#f[1]] = 1
   end

end

function SetParticle( f )

   local pos_x, pos_y
   repeat
       pos_x = math.random( #f )
       pos_y = math.random( #f[1] )
   until f[pos_x][pos_y] == 0
   
   return pos_x, pos_y

end


function Iterate( f, num_particles )

   for i = 1, num_particles do
       local pos_x, pos_y = SetParticle( f )
       
       while true do
           local dx = math.random(5) - 3
           local dy = math.random(5) - 3
           if ( pos_x+dx >= 1 and pos_x+dx <= #f and pos_y+dy >= 1 and pos_y+dy <= #f[1] ) then
               if f[pos_x+dx][pos_y+dy] ~= 0 then
                   f[pos_x][pos_y] = 1
                   break
               else
                   pos_x = pos_x + dx
                   pos_y = pos_y + dy
               end            
           end
       end
   end

end


size_x, size_y = 400, 400 -- size of the scene num_particles = 16000

math.randomseed( os.time() )

f = {} for i = 1, size_x do

   f[i] = {}
   for j = 1, size_y do
       f[i][j] = 0
   end

end

SetSeed( f ) Iterate( f, num_particles )

-- prepare the data for writing into a ppm-image file for i = 1, size_x do

   for j = 1, size_y do
       if f[i][j] == 1 then f[i][j] = 255 end
   end

end Write_PPM( "brownian_tree.ppm", ConvertToColorImage(f) )</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.35*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 = 400 let world_height = 400 let num_particles = 20_000

let () =

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

let dla ~world =

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

 for i = 1 to num_particles do
   (* looping helper function *)
   let rec aux px py =
     (* 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
       (* plop the particle into some other random location *)
       aux (Random.int world_width) (Random.int world_height)
     else if world.(py + dy).(px + dx) <> 0 then
       (* bumped into something, particle set *)
       world.(py).(px) <- 1
     else
       aux (px + dx) (py + dy)
   in
   (* set particle's initial position *)
   aux (Random.int world_width) (Random.int world_height)
 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 print_int 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>

better to compile to native code to get a faster program:

$ ocamlopt -o brownian_tree.opt brownian_tree.ml
$ ./brownian_tree.opt | display -

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>

Perl

Simulation code. Tremendously slow, partly because it doesn't use a grid-based collision checking. Showing three sample images with different STEP and ATTRACT parameters, to demonstrate how sensitive the result is to them.

Code runs until the tree reached specified radius. Output is written to "test.eps" of wherever the current directory is. The 0-0 sample took maybe 3 hours (I don't really know, I went for dinner.) <lang perl>sub PI() { atan2(1,1) * 4 } # The, er, pi sub STEP() { .5 } # How far does the particle move each step. Affects

                               #       both speed and accuracy greatly

sub STOP_RADIUS() { 100 } # When the tree reaches this far from center, end

  1. At each step, move this much towards center. Bigger numbers help the speed because
  2. particles are less likely to wander off, but greatly affects tree shape.
  3. Should be between 0 and 1 ish. Set to 0 for pain.

sub ATTRACT() { .2 }

my @particles = map([ map([], 0 .. 2 * STOP_RADIUS) ], 0 .. 2 * STOP_RADIUS); push @{ $particles[STOP_RADIUS][STOP_RADIUS] }, [0, 0];

my $r_start = 3; my $max_dist = 0;

sub dist2 {

       my ($dx, $dy) = ($_[0][0] - $_[1][0], $_[0][1] - $_[1][1]);
       $dx * $dx + $dy * $dy

}

sub move {

       my $p = shift;
       # moved too far, kill particle
       # return if dist2($p, [0, 0]) > 2 * $r_start * $r_start;
       $p->[0] += 2 * $r_start while $p->[0] < -$r_start;
       $p->[0] -= 2 * $r_start while $p->[0] >  $r_start;
       $p->[1] += 2 * $r_start while $p->[1] < -$r_start;
       $p->[1] -= 2 * $r_start while $p->[1] >  $r_start;
       my ($ix, $iy) = (int($p->[0]), int($p->[1]));
       my $dist = 2 * $r_start * $r_start;
       my $nearest;
       # see if the particle is close enough to stick to an exist one
       for ($ix - 1 .. $ix + 1) {
               my $idx = STOP_RADIUS + $_;
               next if $idx > 2 * STOP_RADIUS || $idx < 0;
               my $xs = $particles[ $idx ];
               for ($iy - 1 .. $iy + 1) {
                       my $idx = STOP_RADIUS + $_;
                       next if $idx > 2 * STOP_RADIUS || $idx < 0;
                       for (@{ $xs->[ $idx ] }) {
                               my $d = dist2($p, $_);
                               next if $d > 2;
                               next if $d > $dist;
                               $dist = $d;
                               $nearest = $_;
                       }
               }
       }
       # yes, found one
       if ($nearest) {
               my $displace = [ $p->[0] - $nearest->[0],
                                $p->[1] - $nearest->[1] ];
               my $angle = atan2($displace->[1], $displace->[0]);
               $p->[0] = $nearest->[0] + cos($angle);
               $p->[1] = $nearest->[1] + sin($angle);
               push @{$particles[$ix + STOP_RADIUS][$iy + STOP_RADIUS]}, [ @$p ];
               $dist = sqrt dist2($p);
               if ($dist + 10 > $r_start && $r_start < STOP_RADIUS + 10) {
                       $r_start = $dist + 10
               }
               if (int($dist + 1) > $max_dist) {
                       $max_dist = int($dist + 1);
                       # write_eps();
                       # system('pstopnm -portrait -xborder 0 -yborder 0 test.eps 2> /dev/null');
                       # system('pnmtopng test.eps001.ppm 2>/dev/null > test.png');
                       return 3 if $max_dist >= STOP_RADIUS;
               }
               return 2;
       }
       # random walk
       my $angle = rand(2 * PI);
       $p->[0] += STEP * cos($angle);
       $p->[1] += STEP * sin($angle);
       # drag particle towards center by some distance
       my $nudge;
       if (sqrt(dist2($p, [0, 0])) > STOP_RADIUS + 1) {
               $nudge = 1;
       } else {
               $nudge = STEP * ATTRACT;
       }
       if ($nudge) {
               $angle = atan2($p->[1], $p->[0]);
               $p->[0] -= $nudge * cos($angle);
               $p->[1] -= $nudge * sin($angle);
       }
       return 1;

}

my $count; PARTICLE: while (1) {

       my $a = rand(2 * PI);
       my $p = [ $r_start * cos($a), $r_start * sin($a) ];
       while ($_ = move($p)) {
               given ($_) {
                       when (1) { next }
                       when (2) { $count++; last; }
                       when (3) { last PARTICLE }
                       default  { last }
               }
       }
       print STDERR "$count $max_dist/@{[int($r_start)]}/@{[STOP_RADIUS]}\r" unless $count% 7;

}

sub write_eps {

       my $size = 128;
       my $p = $size / (STOP_RADIUS * 1.05);
       my $b = STOP_RADIUS * $p;
       if ($p < 1) {
               $size = STOP_RADIUS * 1.05;
               $b = STOP_RADIUS;
               $p = 1;
       }
       my $hp = $p / 2;
       open OUT, ">", "test.eps";
       # print EPS to standard out
       print OUT <<"HEAD";

%!PS-Adobe-3.0 EPSF-3.0 %%BoundingBox: 0 0 @{[$size*2, $size*2]} $size $size translate /l{ rlineto }def /c{ $hp 0 360 arc fill }def -$size -$size moveto $size 2 mul 0 l 0 $size 2 mul l -$size 2 mul 0 l closepath 0 setgray fill 0 setlinewidth .1 setgray 0 0 $b 0 360 arc stroke .8 setgray /TimesRoman findfont 16 scalefont setfont -$size 10 add $size -16 add moveto (Step = @{[STEP]} Attract = @{[ATTRACT]}) show 0 1 0 setrgbcolor newpath HEAD

       for (@particles) {
               for (@$_) {
                       printf OUT "%.3g %.3g c ", map { $_ * $p } @$_ for @$_;
               }
       }
       print OUT "\n%%EOF";
       close OUT;

}

write_eps;</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>

REXX

A large part of the REXX program's prologue was to handle the various options.

With a little more REXX code, a petri dish option could be added, that is, when a particle hits the
edge, it "bounces" back. Also, the field could then be displayed as a round area (a petri dish).

REXX code was added to do snapshots of the field, either after so many cycles, and/or after some elapsed
time has elasped (whole seconds only). This makes for some facinating observations.

Program note: to keep things simple, the (system) command to clear the screen was hardcoded as CLS. <lang rexx>/*REXX program shows brownian motion of dust in a field with one seed. */ parse arg height width motes . if height== | height==',' then height=0 if width== | width==',' then width=0 if motes== then motes='10%' /*nn% Calculate # of dust motes.*/

                                      /* ... otherwise just the number.*/

tree ='*' /*an affixed dust speck (tree). */ mote ='fa'x /*char for a loose mote (of dust)*/ empty=' ' /*char for an empty spot in field*/ clearScr='CLS' /*(DOS?) command to clear screen.*/ eons=1000000 /*time limit for browian movement*/ snapshot=0 /*every n winks, show snapshot.*/ snaptime=2 /*every n secs, show snapshot.*/ seedPos=30 45 /*place seed in this field pos. */ seedPos=0 /*if =0, use middle of the field.*/

                                      /*if -1, use random placement.   */
                                      /*otherwise, place it at seedPos.*/

randseed=0 /*set RANDSEED for repeatability.*/ if randseed\==0 then call random ,,randseed /*set the 1st random num.*/

if height==0 | width==0 then _=scrsize() /*not all REXXes have SCRSIZE.*/ if height==0 then height=word(_,1)-3 if width==0 then width=word(_,2)-1

                   seedAt=seedPos

if seedPos== 0 then seedAt=width%2 height%2 if seedPos==-1 then seedAt=random(1,width) random(1,height) parse var seedAt xs ys .

if right(motes,1)=='%' then motes=height*width*strip(motes,,'%')%100 @.=empty /*create the field, all empty. */

 do j=1  for motes                    /*sprinkle dust motes randomly.  */
 rx=random(1, width);   ry=random(1,height);   @.rx.ry=mote
 end   /*j*/
                                      /*plant the seed from which the  */
                                      /*tree will grow from dust motes */

@.xs.ys=tree /*that affixed themselves. */ call show /*show field before we mess it up*/ tim=0 /*the time (in secs) of last show*/ loX=1; hiX= width /*used to optimize mote searching*/ loY=1; hiY=height /* " " " " " */

         /*═════════════════════════════soooo, this is brownian motion.*/
 do winks=1  for eons  until \motion  /*EONs is used just in case of ∞.*/
 motion=0                             /*turn off brownian motion flag. */
 if snapshot \== 0  then  if winks//snapshot==0       then call show
 if snaptime \== 0  then  do;  t=time('S')
                          if t\==tim & t//snaptime==0 then do
                                                           tim=time('s')
                                                           call show
                                                           end
                          end
 minX=loX;    maxX=hiX                /*as the tree grows, the search  */
 minY=loY;    maxY=hiY                /*   for dust motes gets faster. */
 loX= width;  hiX=1                   /*used to limit mote searching.  */
 loY=height;  hiY=1                   /*  "   "   "     "      "       */
   do x  =minX  to maxX;    xm=x-1;  xp=x+1
     do y=minY  to maxY;    if @.x.y\==mote  then iterate
     if x<loX then loX=x;   if x>hiX  then hiX=x   /*is faster than: hiX=max(X hiX) */
     if y<loY then loY=y;   if y>hiY  then hiY=y   /*is faster than: hiY=max(y hiY) */
     if @.xm.y ==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     if @.xp.y ==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     ym=y-1
     if @.x.ym ==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     if @.xm.ym==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     if @.xp.ym==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     yp=y+1
     if @.x.yp ==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     if @.xm.yp==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     if @.xp.yp==tree  then do;  @.x.y=tree; iterate; end   /*neighbor?*/
     motion=1                         /*brownian motion is coming up.  */
     xb=x+random(1,3)-2               /*apply brownian motion for  X.  */
     yb=y+random(1,3)-2               /*apply brownian motion for  Y.  */
     if @.xb.yb\==empty  then iterate /*can the mote move there ?      */
     @.x.y=empty                      /*"blank" out the old position.  */
     @.xb.yb=mote                     /*move the mote (or possibly not)*/
     if xb<loX  then loX=max(1,xb);   if xb>hiX  then hiX=min( width,xb)
     if yb<loY  then loY=max(1,yb);   if yb>hiY  then hiY=min(height,yb)
     end   /*y*/
   end     /*x*/
 call crop
 end       /*winks*/

call show exit /*stick a fork in it, we're done.*/ /*────────────────────────────────SHOW subroutine───────────────────────*/ show: clearScr /*not necessary, but speeds it up*/

                do ys=height by -1 for height;  aRow=
                          do xs=1 for width;  aRow=aRow||@.xs.ys
                          end   /*xs*/
                say aRow
                end             /*ys*/

return /*────────────────────────────────CROP subroutine───────────────────────*/ crop: if loX>1 & hiX<width & loY>1 & hiY<height then return /*cropping?*/

 do yc=-1 to height+1 by height+2     /*delete motes (moved off field).*/
     do xc=-1 to width+1;   if @.xc.yc==empty then iterate; @.xc.yc=empty
     end   /*xc*/
 end       /*yc*/
 do xc=-1 to width+1 by width+2       /*delete motes (moved off field).*/
     do yc=-1 to height+1;  if @.xc.yc==empty then iterate; @.xc.yc=empty
     end   /*yc*/
 end       /*xc*/

return</lang> output when using the default input

                                                                                                                         *  *
                                                                                                                          **
                                                             *                                                             *
                                                              *                                             *             * ****
                                                               ***                                           *           * * * *
                                                               *  *                                    * *  *            *      **
                                                                 **                                    **    *           **      *
                                                                   *                                     ** *      *   **
                                                                    **                                     *     **   *  *
                                                                  **  *                                  **     * *  *    *
                                                                       *                                   *   * *   **
                                                                      * *           **                **    * *   ***  *
                                                                         *           *                *      *          *
                                                            *             *      *   *               * *    * *         *
                                                           **            * **     * *                   ** *   **
                                                             * *    *     *      * *                   ** * *
                                                              * ** * *  **     * *                        *
                                                                 * *  * **      * **                      *
                                                                * * *  *  *        *                     *
                                                                     * * *        *                    ** * *   *
                                                                      *   ***    * * *                     * ** *     **
                            *                                        ***    *    ** *                       **  * * ** **                                  * *
                           **                                         *      *  *                          *  ** * *        *                               *
                             *                                            *  * *                  *      **    *    *     ***                                *
                             **                                            ** * *                 * * * *  **        **  *    *         *                   * **
                               * *                                         *  *  **                * * * *             ** ** *         *                    *
                                *                                                *           *       *                      *         *                  * * *
                                *                                                * **        *      **                               *   *                *   **
                               *                                                  *          *** * ****                               *   *       *       *     *
                           *    ****                                              *             * *   *                              *    ****     *      **     *
                           *   *                                       *          *             *      ***                         * *    **        **   **
                        *  *   *                                       *         * *          ** *                                  * *  *          *** *  ***
                         ** *  * *                                      **       *         *  *                                  ** *  **         **   *
                             ** *                                         *     * *  *      **    **                               *             * *  **
                            *    *                                  * *    * *    *   *       ** ** *                            **              **
                                 *          *                      * **     *    *   *    *  *  *                                 *  *       **** *
                                  *     *   *                     *    *  ** * ** * *      ***                                    * *       *    * **
                                  **     ** **                         * **  **  * * *       *                                     *      **      *
                                  *        *                            *      **   *       * *                              *      *    *  *
                                 *        * **                         *            *     * *  ** *                         *    *  * * *   *
                         *    *  *       *    *                      **              *     *     * *                        *     ** * *     *
                         *   **  *           * *                    *             *   *** *                      *           ** **
                   *    * *  * * *          *                                      * **  * *                  * *           * ** *
                * *       * *   **     *   **     *                               * *     * *                 **           *    * *
             *** *       * *      *    *     *   * *                               *     *   *                 *          *        *  * *
        *  * * ** * *  *        *  *  * **  * * *                                  *      *   * *  ***       * ***       * *       ** * *     *
         **   *  *  *   *        *  ** *  **   **                                **        *   * **   *   * ***       * **        *  * * *    **   * *
          *     * * *  * *       * *       *    *                                 *       *      *    *    *   **      *         *    *     **  * **  *
    *    * * *  * ** ** ******    *       *      **                          *    **     *      *      **  * *   * *  * *         *    **  *  *  *  ** *
   * * **   * **     *   *    * **       **      ** *                      **    **     * * *            *  *     *  *   *        *   *  ** * **    *
      **    *  *        *      *                *  * * *             *  *    *   * *     * *            * **     * * *           *     * *     *    *
   * ***     *  *    * *        *               * * * **             ** * *   * *         * *            * ***      *           *         *        *** *
 *  *       *   *     * *      * *                 * *  *              * **  * * *      **   *          * *   **     *         *          **       *  * *
  **                  * **    * *                     *           **       **  *         *    *        *  **   *   ** *                   * *     * *
  *                   * *     * *                      *            ** *****   *        *     **           *  *       *  **               *          *
  *                  *  *   **  *           * **        *         *   *        *        * *     **           * *       ** *                **       * **   *
                        *      * *           *  *        *         * *        *        * *      * *         *   *         *                *          * ** *
                              *             *    *      **         * *        *        *        **         *   *          ****            **         *  * *
                                          **    * *      **   *    ** *      *         *       *          *   *          * *  **        **           *  *  *
                                         *        **    *  * * *  *  *     **         * *       * *        *   *           *  *           *            *
                                        *      * * *****  ***   **    *   *          ** *   ** * ***       *    ** *         * **         **            *
                                      **        *        *      * *    *            **        * *             **  *            *          * *            *
                                      * *      *        *      *  *    *           *           *              *  * *  *        *         *  * *
                                               *      **    ***  * *    *          *          *                  *  **        * *         *  ***
                                                       *      *  *                *          *                    *  **       *  *        *    *
                                                     **      *   *               * *        * *                       *        *         * *    *
                                                      *        ** *             ** *     ** *  ** *                    *      *         * *    *
                                 *                  **          *              *        *  *   * **  *                       *         *  *     *
                                  *                * *         * **           *           * *   * * *                                    * *     *
                                   *              *   *       *  *            **        **  *   *  *                                              * *
                                    *   *  *     **    *     *    *           *           *      *                                                 *
                                     ** ***       *     *    *               **                 * *
                                  ***  *   *   * * *        **              ** *                 * **
                                   *  *   *** * *             *                                  *   **
                                      *  *   * * *                                               *
                                              **                                                *
                                              * *                                                *
                                             *                                                    *
                                            *                                                     ***
                                           * *                                                   *
                                            *                                                   * **
                                         * *                                                   *
                                          *

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>

Run BASIC

<lang runbasic>numParticles = 3000 dim canvas(201,201) canvas(rnd(1) * 100 , rnd(1) * 200) = 1 'start point for i = 1 To numParticles

   x = (rnd(1) * 199) + 1 
   y = (rnd(1) * 199) + 1
   while canvas(x+1, y+1) + canvas(x, y+1)+canvas(x+1, y)+canvas(x-1, y-1)+canvas(x-1, y)+canvas(x, y-1) = 0
       x = x + (rnd(1)* 2) + 1 
       y = y + (rnd(1)* 2) + 1 
       If x < 1 Or x > 200 Or y < 1 Or y > 200 then
           x = (rnd(1) * 199) + 1 
           y = (rnd(1) * 199) + 1
       end if   
   wend
  canvas(x,y) = 1

next i

graphic #g, 200,200 for x = 1 to 200

 for y = 1 to 200
    if canvas(x,y) = 1 then  #g "color green ; set "; x; " "; y else #g "color blue ; set "; x; " "; y
 next y

next x render #g

  1. g "flush"</lang>

Scheme

Works with: Guile

<lang scheme>; Save bitmap to external file (define (save-pbm bitmap filename) (define f (open-output-file filename)) (simple-format f "P1\n~A ~A\n" (list-ref (array-dimensions bitmap) 0) (list-ref (array-dimensions bitmap) 1)) (do ((c 0 (+ c 1))) ((eqv? c (list-ref (array-dimensions bitmap) 1))) (do ((r 0 (+ r 1))) ((eqv? r (list-ref (array-dimensions bitmap) 0))) (display (array-ref bitmap r c) f)) (newline f)) (close-output-port f) )

Return a random coordinate in the bitmap that isn't filled yet along with a direction

(define (new-particle bitmap) (define x (random (list-ref (array-dimensions bitmap) 0))) (define y (random (list-ref (array-dimensions bitmap) 1))) (define dx (- (random 3) 1)) (define dy (- (random 3) 1)) ;Repeat until we find an unused location (if (> (array-ref bitmap x y) 0) (new-particle bitmap) (list (list x y) (list dx dy))))

Check neighboring coordinates to see if a collision occured

(define (collision-check bitmap p) (define c #f) (define oob #f) (define x (list-ref (car p) 0)) (define y (list-ref (car p) 1)) (define dx (list-ref (cadr p) 0)) (define dy (list-ref (cadr p) 1)) (define w (list-ref (array-dimensions bitmap) 0)) (define h (list-ref (array-dimensions bitmap) 1))

; If the particle hasn't gone out of bounds keep checking for a collision (if (or (> 0 x) (> 0 y) (<= w x) (<= h y)) (set! oob #t) (do ((x (- (list-ref (car p) 0) 1) (+ x 1))) ((eqv? x (+ (list-ref (car p) 0) 2))) (do ((y (- (list-ref (car p) 1) 1) (+ y 1))) ((eqv? y (+ (list-ref (car p) 1) 2))) ; Check existing neighbors for collisions (if (and (<= 0 x) (<= 0 y) (> w x) (> h y)) (if (not (zero? (array-ref bitmap x y))) (set! c #t)))))) (if oob #f ; Return false if out of bounds (if c p ; Return the point of collision if a collision occured (if (and (zero? dx) (zero? dy)) #f ; Return false if particle is motionless with no collision (collision-check bitmap (particle-move p))))))

Plot a particle on the bitmap

(define (particle-plot! bitmap p) (array-set! bitmap 1 (list-ref (car p) 0) (list-ref (car p) 1)))

Move a particle along its slope

(define (particle-move p) (list (list (+ (list-ref (car p) 0) (list-ref (cadr p) 0)) (+ (list-ref (car p) 1) (list-ref (cadr p) 1))) (cadr p)))

Grow a brownian tree

(define (grow-brownian-tree! bitmap collisions) (define w (list-ref (array-dimensions bitmap) 0)) (define h (list-ref (array-dimensions bitmap) 1))

; Generate a new particle at a random location (define p (new-particle bitmap))

; Find a collision or lack of one and plot it on the bitmap (set! p (collision-check bitmap p)) (if p (begin ; Display collision number and the place it happened (display collisions)(display ": ")(display (car p))(newline) (set! collisions (- collisions 1)) ; Plot the point (particle-plot! bitmap p)))

; If we're done say so (if (zero? collisions) (display "Done\n"))

; Keep going until we have enough collisions ; or have filled the bitmap (if (and (< 0 collisions) (memq 0 (array->list (array-contents bitmap)))) (grow-brownian-tree! bitmap collisions)))

Plot a random point to seed the brownian tree

(define (seed-brownian-tree! bitmap) (define p (new-particle bitmap)) (particle-plot! bitmap p))

Example usage ;;;
Seed the random number generator

(let ((time (gettimeofday))) (set! *random-state* (seed->random-state (+ (car time) (cdr time)))))

Generate a tree with 320*240 collisions on a bitmap of the size 640x480
The bitmap is zeroed to start and written with a one where a collision occurs

(define bitmap (make-array 0 640 480)) (seed-brownian-tree! bitmap) (grow-brownian-tree! bitmap (* 320 240))

Save to a portable bitmap file

(save-pbm bitmap "brownian-tree.pbm")</lang>

Seed7

Simple brownian tree produced with Seed7 program

The program below generates a small brownian tree. You can watch how it grows.

<lang seed7>$ include "seed7_05.s7i";

 include "draw.s7i";
 include "keybd.s7i";

const integer: SIZE is 300; const integer: SCALE is 1;

const proc: genBrownianTree (in integer: fieldSize, in integer: numParticles) is func

 local
   var array array integer: world is 0 times 0 times 0;
   var integer: px is 0;
   var integer: py is 0;
   var integer: dx is 0;
   var integer: dy is 0;
   var integer: i is 0;
   var boolean: bumped is FALSE;
 begin
   world := fieldSize times fieldSize times 0;
   world[rand(1, fieldSize)][rand(1, fieldSize)] := 1;  # Set the seed
   for i range 1 to numParticles do
     # Set particle's initial position
     px := rand(1, fieldSize);
     py := rand(1, fieldSize);
     bumped := FALSE;
     repeat
       # Randomly choose a direction
       dx := rand(-1, 1);
       dy := rand(-1, 1);
       if dx + px < 1 or dx + px > fieldSize or dy + py < 1 or dy + py > fieldSize then
         # Plop the particle into some other random location
         px := rand(1, fieldSize);
         py := rand(1, fieldSize);
       elsif world[py + dy][px + dx] <> 0 then
         # Bumped into something
         world[py][px] := 1;
         rect(SCALE * pred(px), SCALE * pred(py), SCALE, SCALE, white);
         DRAW_FLUSH;
         bumped := TRUE;
       else
         py +:= dy;
         px +:= dx;
       end if;
     until bumped;
   end for;
 end func;

const proc: main is func

 begin
   screen(SIZE * SCALE, SIZE * SCALE);
   KEYBOARD := GRAPH_KEYBOARD;
   genBrownianTree(SIZE, 20000);
   readln(KEYBOARD);
 end func;</lang>

Original source: [1]

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>

TI-83 BASIC

<lang ti83b>:StoreGDB 0

ClrDraw
FnOff
AxesOff
Pxl-On(31,47)
For(I,1,50)
randInt(1,93)→X
randInt(1,61)→Y
1→A
While A
randInt(1,4)→D
Pxl-Off(Y,X)
If D=1 and Y≥2
Y-1→Y
If D=2 and X≤92
X+1→X
If D=3 and Y≤60
Y+1→Y
If D=4 and X≥2
X-1→X
Pxl-On(Y,X)
If pxl-Test(Y+1,X) or pxl-Test(Y+1,X+1) or pxl-Test(Y+1,X-1) or pxl-Test(Y,X+1) or pxl-Test(Y,X-1) or pxl-Test(Y-1,X) or pxl-Test(Y-1,X-1) or pxl-Test(Y-1,X+1)
0→A
End
End
Pause
RecallGDB 0</lang>

Visual Basic .NET

Windows Forms Application.

<lang vbnet> Imports System.Drawing.Imaging

Public Class Form1

 ReadOnly iCanvasColor As Integer = Color.Black.ToArgb
 ReadOnly iSeedColor As Integer = Color.White.ToArgb
 Dim iCanvasWidth As Integer = 0
 Dim iCanvasHeight As Integer = 0
 Dim iPixels() As Integer = Nothing
 Private Sub BrownianTree()
   Dim oCanvas As Bitmap = Nothing
   Dim oRandom As New Random(Now.Millisecond)
   Dim oXY As Point = Nothing
   Dim iParticleCount As Integer = 0
   iCanvasWidth = ClientSize.Width
   iCanvasHeight = ClientSize.Height
   oCanvas = New Bitmap(iCanvasWidth, iCanvasHeight, Imaging.PixelFormat.Format24bppRgb)
   Graphics.FromImage(oCanvas).Clear(Color.FromArgb(iCanvasColor))
   iPixels = GetData(oCanvas)
   ' We'll use about 10% of the total number of pixels in the canvas for the particle count.
   iParticleCount = CInt(iPixels.Length * 0.1)
   ' Set the seed to a random location on the canvas.
   iPixels(oRandom.Next(iPixels.Length)) = iSeedColor
   ' Run through the particles.
   For i As Integer = 0 To iParticleCount
     Do
       ' Find an open pixel.
       oXY = New Point(oRandom.Next(oCanvas.Width), oRandom.Next(oCanvas.Height))
     Loop While iPixels(oXY.Y * oCanvas.Width + oXY.X) = iSeedColor
     ' Jitter until the pixel bumps another.
     While Not CheckAdjacency(oXY)
       oXY.X += oRandom.Next(-1, 2)
       oXY.Y += oRandom.Next(-1, 2)
       ' Make sure we don't jitter ourselves out of bounds.
       If oXY.X < 0 Then oXY.X = 0 Else If oXY.X >= oCanvas.Width Then oXY.X = oCanvas.Width - 1
       If oXY.Y < 0 Then oXY.Y = 0 Else If oXY.Y >= oCanvas.Height Then oXY.Y = oCanvas.Height - 1
     End While
     iPixels(oXY.Y * oCanvas.Width + oXY.X) = iSeedColor
     ' If you'd like to see updates as each particle collides and becomes
     ' part of the tree, uncomment the next 4 lines (it does slow it down slightly).
     ' SetData(oCanvas, iPixels)
     ' BackgroundImage = oCanvas
     ' Invalidate()
     ' Application.DoEvents()
   Next
   oCanvas.Save("BrownianTree.bmp")
   BackgroundImage = oCanvas
 End Sub
 ' Check adjacent pixels for an illuminated pixel.
 Private Function CheckAdjacency(ByVal XY As Point) As Boolean
   Dim n As Integer = 0
   For y As Integer = -1 To 1
     ' Make sure not to drop off the top or bottom of the image.
     If (XY.Y + y < 0) OrElse (XY.Y + y >= iCanvasHeight) Then Continue For
     For x As Integer = -1 To 1
       ' Make sure not to drop off the left or right of the image.
       If (XY.X + x < 0) OrElse (XY.X + x >= iCanvasWidth) Then Continue For
       ' Don't run the test on the calling pixel.
       If y <> 0 AndAlso x <> 0 Then
         n = (XY.Y + y) * iCanvasWidth + (XY.X + x)
         If iPixels(n) = iSeedColor Then Return True
       End If
     Next
   Next
   Return False
 End Function
 Private Function GetData(ByVal Map As Bitmap) As Integer()
   Dim oBMPData As BitmapData = Nothing
   Dim oData() As Integer = Nothing
   oBMPData = Map.LockBits(New Rectangle(0, 0, Map.Width, Map.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb)
   Array.Resize(oData, Map.Width * Map.Height)
   Runtime.InteropServices.Marshal.Copy(oBMPData.Scan0, oData, 0, oData.Length)
   Map.UnlockBits(oBMPData)
   Return oData
 End Function
 Private Sub SetData(ByVal Map As Bitmap, ByVal Data As Integer())
   Dim oBMPData As BitmapData = Nothing
   oBMPData = Map.LockBits(New Rectangle(0, 0, Map.Width, Map.Height), ImageLockMode.WriteOnly, PixelFormat.Format32bppArgb)
   Runtime.InteropServices.Marshal.Copy(Data, 0, oBMPData.Scan0, Data.Length)
   Map.UnlockBits(oBMPData)
 End Sub
 Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
   DoubleBuffered = True
   BackgroundImageLayout = ImageLayout.Center
   Show()
   Activate()
   Application.DoEvents()
   BrownianTree()
 End Sub

End Class </lang>

Final output:

XPL0

<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations def W=128, H=W; \width and height of field int X, Y; [SetVid($13); \set 320x200 graphic video mode Point(W/2, H/2, 6\brown\); \place seed in center of field loop [repeat X:= Ran(W); Y:= Ran(H); \inject particle

       until   ReadPix(X,Y) = 0;        \ in an empty location
       loop    [Point(X, Y, 6\brown\);  \show particle
               if ReadPix(X-1,Y) or ReadPix(X+1,Y) or \particle collided
                  ReadPix(X,Y-1) or ReadPix(X,Y+1) then quit;
               Point(X, Y, 0\black\);   \erase particle
               X:= X + Ran(3)-1;        \(Brownian) move particle
               Y:= Y + Ran(3)-1;
               if X<0 or X>=W or Y<0 or Y>=H then quit; \out of bounds
               ];
       if KeyHit then [SetVid(3);  quit]; \restore text mode
       ];

]</lang>