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

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>

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>

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

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

proc makeBrownianTree count { 

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

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

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 >= 800 || $py+$dy < 0 || $py+$dy>=800} { # 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>

Retrieved from "https://rosettacode.org/wiki/Brownian_tree?oldid=148045"