# Brownian tree

 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)
Brownian tree
You are encouraged to solve this task according to the task description, using any language you may know.
Generate and draw a Brownian Tree.

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

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

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

## C

Library: FreeImage

<lang c>#include <string.h>

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

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

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

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

}

int main(){

``` int world[SIZE][SIZE];
FIBITMAP * img;
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);
```

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

## JavaScript + <canvas>

<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;
```
``` // Utilities
return Math.sqrt((x-cx)*(x-cy)+(y-cx)*(y-cy));
}
function test(x, y) {
var data = ctx.getImageData(x, y, 1, 1).data;
}
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;
//ctx.putImageData(imgd, x, y);
//ctx.fillStyle = "rgba("+c+", "+c+", "+c+", 1)";
if (c) {
} 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 = 10;
var y = 10;
```
``` // Farthest distance from center a particle has yet been placed.
```
``` // 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 ||
// 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);
newpos();
}
}
if (drawPos) set(x,y);
}, 1);
```

}</lang>

<lang html><html>

```<head>
<script src="brownian.js"></script>
<canvas id="canvas" width="402" height="402" style="border: 2px inset;"></canvas>
```
```</body>
```

</html></lang>

## Octave

Translation of: C

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

``` r = zeros(xsize, ysize, "uint8");
r(unidrnd(xsize), unidrnd(ysize)) = 1;

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

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

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

r(px, py) = 1; break;

```     else
```

px += dx; py += dy;

```     endif
endwhile
endfor
```

endfunction

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

## PureBasic

<lang PureBasic>#Window1 = 0

1. Image1 = 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)
StartDrawing(ImageOutput(#Image1))
FrontColor(\$FFFFFF)
Plot( Random(#xmax) , Random(#ymax ))
StopDrawing()
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()
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

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>