Brownian tree

From Rosetta Code
Jump to: navigation, search
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.

Contents

[edit] AutoHotkey

Works with: AutoHotkey_L

Takes a little while to run, be patient. Requires the GDI+ Standard Library by Tic

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
}
Sample output file here

[edit] BBC BASIC

      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
 
 

Brownian BBC.gif

[edit] C

Library: FreeImage
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <FreeImage.h>
 
#define NUM_PARTICLES 1000
#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);
}

Bold text

[edit] Alternative Version

Translation of: D

This version writes the image as Portable Bit Map to stdout and doesn't move already set particles.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
 
#define SIDE 600
#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;
}

Run-time about 12.4 seconds with SIDE=600, NUM_PARTICLES=10000.

[edit] C++

BrownianTree cpp.png

For an animated version based on this same code see: Brownian tree/C++ animated

#include <windows.h>
#include <iostream>
#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;
}
//--------------------------------------------------------------------

[edit] C#

Works with: C# version 3.0
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");
}
}
}

[edit] D

Uses the module of the Grayscale Image task. Partial
Translation of: PureBasic
void main() {
import core.stdc.stdio, std.random, grayscale_image;
 
enum uint side = 600; // Square world side.
enum uint num_particles = 10_000;
static assert(side > 2 && num_particles < (side ^^ 2 * 0.7));
 
auto rng = unpredictableSeed.Xorshift;
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");
}

World side = 600, num_particles = 10_000, cropped (about 20 seconds run-time with dmd, about 4.3 seconds with ldc2):

Dla 10000 d.png

[edit] 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;

[edit] 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)
}
}
}
}
 

[edit] 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

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

[edit] 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:

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
}

Nearly the same, version below works with code from the bitmap task:

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
}

[edit] 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.

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

[edit] 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.

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

graphics.icn provides graphics printf.icn provides printf

[edit] 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
)

Example use:

   require'viewmat'
viewmat 480 640 brtr 30000

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

[edit] Java

Library: Swing
Library: AWT
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;
}
}
}

This is an alternate version which is a port of most of the code here. This code does not use a GUI and saves the output to image.png.

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
 
import javax.imageio.ImageIO;
 
public class BasicBrownianTree {
 
private int pixelsLost;
private Point p;
private Point nextP;
private int pixelCount;
private int width;
private int height;
private int color;
private BufferedImage img;
 
public BasicBrownianTree( int argb, int size, double density ) {
pixelsLost = 0;
p = new Point();
nextP = new Point();
width = size;
height = size;
color = argb;
pixelCount = (int) ( width * height * density );
img = new BufferedImage( width, height, BufferedImage.TYPE_INT_ARGB );
}
 
public void generate() {
// print text to the console
System.out.println( "Drawing " + pixelCount + " pixels" );
int background = img.getRGB( 0, 0 );
img.setRGB( width / 2, height / 2, color );
 
for( int i = 0; i < pixelCount; i++ ) {
p.x = (int) ( Math.random() * width );
p.y = (int) ( Math.random() * height );
 
while ( true ) {
int dx = (int) ( Math.random() * 3 ) - 1;
int dy = (int) ( Math.random() * 3 ) - 1;
nextP.setLocation( p.x + dx, p.y + dy );
// handle out-of-bounds
if ( nextP.x < 0 || nextP.x >= width || nextP.y < 0
|| nextP.y >= height ) {
// increment the number of pixels lost and escape the loop
pixelsLost++;
break;
}
if ( img.getRGB( nextP.x, nextP.y ) != background ) {
img.setRGB( p.x, p.y, color );
break;
}
p.setLocation( nextP );
}
// Print a message every 2%
if ( i % ( pixelCount / 50 ) == 0 ) {
System.out.println( "Done with " + i + " pixels" );
}
}
// We're done. Let the user know how many pixels were lost
System.out.println( "Finished. Pixels lost = " + pixelsLost );
}
 
public BufferedImage getImage() {
return img;
}
 
public int getWidth() {
return width;
}
 
public int getHeight() {
return height;
}
 
public static void main( String[] args ) {
// create the new generator
BasicBrownianTree generator = new BasicBrownianTree( 0x664444ff, 400, 0.4 );
// generate the image
generator.generate();
try {
// save the image to the file "image.png"
ImageIO.write( generator.getImage(), "png", new File( "image.png" ) );
} catch ( IOException e ) {
e.printStackTrace();
}
}
}

[edit] JavaScript + <canvas>

Live version

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);
 
}
<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>
<div id="message"></div>
</body>
</html>

[edit] Liberty BASIC

'[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

[edit] 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.

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

[edit] 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
canvasdim = 1000;
n = 0.35*canvasdim^2;
canvas = ConstantArray[0, {canvasdim, canvasdim}];
init = Floor@(0.5*{canvasdim, canvasdim}); (*RandomInteger[canvasdim,2]*)
canvas[[init[[1]], init[[2]]]] = 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[[particle[[1]], particle[[2]]]] = i;
Break[],
particle += ds
];
],
{i, n}],
{i, (particle + ds), MatrixPlot@canvas}
]
MatrixPlot[canvas,FrameTicks->None,ColorFunction->"DarkRainbow",ColorRules->{0 -> None}]

Result:

BrownianTree.png

[edit] OCaml

Translation of: D
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;
;;

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

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

[edit] Octave

Translation of: C
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

[edit] Perl

Brownian-00.png
Brownian-05.png
Brownian-11.png

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

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
 
# At each step, move this much towards center. Bigger numbers help the speed because
# particles are less likely to wander off, but greatly affects tree shape.
# 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;

[edit] Perl 6

Brownian tree perl6.png

This solution spawns new Particles at a growing square border and displays the Tree every 50 particles and at the end using unicode UPPER/LOWER HALF BLOCK and FULL BLOCK.

With the given size of 100 and particle count of 1000, this takes about 25 seconds with Niecza on my notebook.

constant size = 100;
constant particlenum = 1_000;
 
 
constant mid = size div 2;
 
my $spawnradius = 5;
my @map;
 
sub set($x, $y) {
@map[$x][$y] = True;
}
 
sub get($x, $y) {
return @map[$x][$y] || False;
}
 
set(mid, mid);
my @blocks = " ","\c[UPPER HALF BLOCK]", "\c[LOWER HALF BLOCK]","\c[FULL BLOCK]";
 
sub infix:<>($a, $b) {
@blocks[$a + 2 * $b]
}
 
sub display {
my $start = 0;
my $end = size;
say (for $start, $start + 2 ... $end -> $y {
(for $start..$end -> $x {
if abs(($x&$y) - mid) < $spawnradius {
get($x, $y) █ get($x, $y+1);
} else {
" "
}
}).join
}).join("\n")
}
 
for ^particlenum -> $progress {
my Int $x;
my Int $y;
my &reset = {
repeat {
($x, $y) = (mid - $spawnradius..mid + $spawnradius).pick, (mid - $spawnradius, mid + $spawnradius).pick;
($x, $y) = ($y, $x) if (True, False).pick();
} while get($x,$y);
}
reset;
 
while not get($x-1|$x|$x+1, $y-1|$y|$y+1) {
$x = ($x-1, $x, $x+1).pick;
$y = ($y-1, $y, $y+1).pick;
if (False xx 3, True).pick {
$x = $x >= mid ?? $x - 1 !! $x + 1;
$y = $y >= mid ?? $y - 1 !! $y + 1;
}
if abs(($x | $y) - mid) > $spawnradius {
reset;
}
}
set($x,$y);
display if $progress %% 50;
if $spawnradius < mid && abs(($x|$y) - mid) > $spawnradius - 5 {
$spawnradius = $spawnradius + 1;
}
}
 
say "";
display;
say "";
say "time elapsed: ", (now - BEGIN { now }).Num.fmt("%.2f"), " seconds";
say "";

[edit] 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) ) ) ) )

Use:

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

[edit] PureBasic

#Window1   = 0
#Image1 = 0
#ImgGadget = 0
 
#NUM_PARTICLES = 3000
#width = 200
#height = 200
#xmax = #width -3
#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
BrownianTree.pb.png


[edit] Python

Library: pygame
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()

[edit] Racket

#lang racket
(require 2htdp/image)
 
;; The unsafe fixnum ops are faster than the checked ones,
;; but if you get anything wrong with them, they'll bite.
;; If you experience any problems reactivate the
;; (require racket/fixnum) and instead of the unsafe requirement
;; below...
 
;; we have tested this...
#;(require racket/fixnum)
;; so we can use this...
(require racket/require
(only-in racket/fixnum make-fxvector in-fxvector)
(filtered-in
(? (name) (regexp-replace #rx"unsafe-" name ""))
racket/unsafe/ops))
 
;;; This implementation uses a 1d, mutable, fixnum vector
;;; there's a lot of work done making the tree, so this optimisation
;;; at the expense of clarity has been made. Sorry, guys!
(define (brownian-tree w h collisions n-particles seed-tree
generate-particle walk-particle)
(define w*h (fx* w h))
(define V (make-fxvector w*h))
(define (collision? x.y) (fx> (fxvector-ref V x.y) 0))
 
 ;; The main loop
(define (inner-b-t collisions particles)
(cond
[(fx= 0 collisions) V]
[else
(define-values (new-particles new-collisions)
(for/fold
((prtcls null)
(clsns 0))
((x.y particles)
#:break (fx= collisions clsns))
(define new-particle (walk-particle x.y w h w*h))
(cond
[(not new-particle) ; it died!
(values (cons (generate-particle V w h w*h) prtcls) clsns)]
[(collision? new-particle)
(fxvector-set! V x.y 1)
(values (cons (generate-particle V w h w*h) prtcls) (add1 clsns))]
[else
(values (cons new-particle prtcls) clsns)])))
(when (fx> new-collisions 0)
(define remain (fx- collisions new-collisions))
(unless (fx= (exact-floor (* 10 (log collisions)))
(exact-floor (* 10 (log (fxmax 1 remain)))))
(eprintf "~a (e^~a)~%" remain (log (fxmax 1 remain))))
(log-info "~a new collisions: ~a remain~%" new-collisions remain))
(inner-b-t (fxmax 0 (fx- collisions new-collisions)) new-particles)]))
 
 ;; Seed the tree
(seed-tree V w h)
(inner-b-t collisions
(build-list n-particles
(lambda (x) (generate-particle V w h w*h)))))
 
;; See below for why we do the (fxremainder ...) test
(define (uniform-particle-generator v w h w*h)
(define x.y (random w*h))
(define valid-x.y?
(and
(fx= (fxvector-ref v x.y) 0) ; start on empty cell
(fx> (fxremainder x.y w) 0))) ; not on left edge
 ; if it's valid take it otherwise regenerate
(if valid-x.y? x.y (uniform-particle-generator v w h w*h)))
 
;; The boundaries to the walker are to remain within the limits of
;; the vector... however, unless we stop particles going off the
;; east/west edges, the tree will be formed on a cylinder as the
;; particles wrap. So we kill particles that reach the left edge
;; either by decrement from the right or by incrementing and wrapping.
;; This is is tested with (= 0 (remainder x.y w)).
(define (brownian-particle-walker x.y w h w*h)
(define dx (fx- (random 3) 1))
(define dy (fx- (random 3) 1))
(define new-x.y (fx+ x.y (fx+ dx (fx* w dy))))
(and (fx> new-x.y 0) (fx< new-x.y w*h)
(fx> (fxremainder new-x.y w) 0)
new-x.y))
 
;; These seed functions modify v however you want!
(define (seed-middle v w h)
(fxvector-set! v (+ (quotient w 2) (* w (quotient h 2))) 1))
 
(define (seed-circle v w h)
(for ((a (in-range 0 360 120)))
(define x (exact-floor (* w 1/8 (+ 4 (sin (* pi 1/180 a))))))
(define y (exact-floor (* h 1/8 (+ 4 (cos (* pi 1/180 a))))))
(fxvector-set! v (+ x (* w y)) 1)))
 
;; SCALE is a general purpose knob for modifying the size of the problem
;; complexity increases with the sqaure of SCALE (at least)
(define SCALE 1)
(define tree-W (* SCALE 320))
(define tree-H (* SCALE 240))
(define tree-W.H (* tree-W tree-H))
;; play with tree-PARTICLES -- small values will lead to a smaller tree
;; as the tree moves towards the edges, more particles might affect its shape
(define tree-PARTICLES (quotient tree-W.H 4))
;; these are the particles that are bimbling around at any one time. If it's
;; too low, you might get bored waiting for a collision... if it's too high
;; you might get inappropriate collisions
(define working-PARTICLES (quotient tree-W.H 300))
 
(define b-t (time
(brownian-tree
tree-W tree-H tree-PARTICLES working-PARTICLES
seed-middle
uniform-particle-generator
brownian-particle-walker)))
 
(define (b-t-value->color c) (case c ((1) "black") (else "white")))
(define img (color-list->bitmap
(for*/list ((x (in-fxvector b-t)))
(b-t-value->color x))
tree-W tree-H))
 
img
(save-image img "brownian-tree.png")

[edit] 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 display snapshots of the field, either after so many cycles, and/or after some
elapsed time has elapsed (whole seconds only).   This makes for some fascinating observations.

Program note:   to keep things simple, the (system) command to clear the screen was hard-coded as   CLS.

/*REXX program shows  Brownian motion  of dust in a field with one seed.*/
parse arg height width motes randSeed . /*get args from the C.L. */
if height=='' | height==',' then height=0 /*None? Use the default*/
if width=='' | width==',' then width=0 /* " " " " */
if motes=='' | motes==',' then motes='10%' /*% dust motes in field, */
/* ··· otherwise just the number.*/
tree = '*' /*an affixed dust speck (tree). */
mote = '·' /*char for a loose mote (of dust)*/
hole = ' ' /*char for an empty spot in field*/
clearScr = 'CLS' /*(DOS?) command to clear screen.*/
eons = 1000000 /* # cycles for Brownian movement*/
snapshot = 0 /*every n winks, show snapshot.*/
snaptime = 1 /*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 a random placement. */
/*otherwise, place it at seedPos.*/
/*set RANDSEED for repeatability.*/
if datatype(randSeed,'W') then call random ,,randSeed /*if #, use it*/
/* [↑] set the 1st random number*/
if height==0 | width==0 then _=scrsize() /*not all REXXes have SCRSIZE.*/
if height==0 then height=word(_,1)-3 /*adjust for border.*/
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 . /*obtain X & Y seed coördinates*/
/* [↓] if right-most≡'%', use %.*/
if right(motes,1)=='%' then motes=height * width * strip(motes,,'%') %100
@.=hole /*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*/ /* [↑] place a mote at random. */
/*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 instead 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.*/
xb=x+random(1,3)-2 /* apply Brownian motion for X.*/
yb=y+random(1,3)-2 /* " " " " Y.*/
if @.xb.yb\==hole then iterate /*can mote actually move there ? */
@.x.y=hole /*empty out the old mote 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*/ /* [↑] limit the motes movement.*/
end /*x*/
call crop /*crops/truncates the mote field.*/
end /*winks*/
 
call show
exit /*stick a fork in it, we're done.*/
/*────────────────────────────────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==hole then iterate; @.xc.yc=hole
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==hole then iterate; @.xc.yc=hole
end /*yc*/
end /*xc*/
return
/*────────────────────────────────SHOW subroutine───────────────────────*/
show: clearScr /*not necessary, but speeds it up*/
do ys=height for height by -1; aRow=
do xs=1 for width; aRow=aRow || @.xs.ys
end /*xs*/
say aRow
end /*ys*/
return

This REXX program makes use of   SCRSIZE   REXX program (or BIF) which is used to determine the screen size of the terminal (console).
The   SCRSIZE.REX   REXX program is included here ──► SCRSIZE.REX.

output when using the default input

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

[edit] Ruby

Library: RMagick
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"

[edit] Run BASIC

BrownianTreeKokenge.png
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
#g "flush"

[edit] Scheme

Works with: Guile
; 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")

Scheme-guile-brownian-tree-large.png

[edit] Seed7

Simple brownian tree produced with Seed7 program

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

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

Original source: [1]

[edit] Tcl

Library: Tk
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

[edit] TI-83 BASIC

: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

[edit] Visual Basic .NET

Windows Forms Application.

 
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
 
Final output:

SH BrownianTree.jpg

[edit] XPL0

BrownXPL0.gif
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
];
]

[edit] zkl

This grows rather slowly, so I've added a circle for barnacles to attach to. It looks like tendrils growing from the center to the circle and vice versa. The tree type is similar to that shown in the XPLO and Visual Basic .NET solutions. Also, the image is written to disk as each particle attaches so EventViewer will auto update to show the progression.

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

w:=h:=400; numParticles:=20000;
bitmap:=PPM(w+2,h+2,0); // add borders as clip regions
 
bitmap[w/2,h/2]=0xff|ff|ff; // plant seed
bitmap.circle(w/2,h/2,h/2,0x0f|0f|0f); // plant seeds
 
fcn touching(x,y,bitmap){ // is (x,y) touching another pixel?
// (x,y) isn't on the border/edge of bitmap so no edge conditions
var [const] box=T(T(-1,-1),T(0,-1),T(1,-1),
T(-1, 0), T(1, 0),
T(-1, 1),T(0, 1),T(1, 1));
box.filter1('wrap([(a,b)]){ bitmap[a+x,b+y] }); //-->False: not touching, (a,b) if is
}
 
while(numParticles){
c:=(0x1|00|00).random(0x1|00|00|00) + (0x1|00).random(0x1|00|00) + (0x1).random(0x1|00);
reg x,y;
do{ x=(1).random(w); y=(1).random(h); }while(bitmap[x,y]); // find empty spot
while(1){ // stagger around until bump into a particle, then attach barnicle
if(touching(x,y,bitmap)){
bitmap[x,y]=c;
bitmap.write(f:=File("foo.ppm","wb")); // tell ImageViewer to update image
numParticles-=1;
break;
}
x+=(-1).random(2); y+=(-1).random(2); // [-1,0,1]
if( not ((0<x<w) and (0<y<h)) ){ // next to border --> color border
bitmap[x,y]=c;
break;
}
}
}
bitmap.write(File("foo.ppm","wb")); // the final image
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox