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) |
Generate and draw a Brownian Tree.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
A Brownian Tree is generated as a result of an initial seed, followed by the interaction of two processes.
- 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.
- Particles are injected into the field, and are individually given a (typically random) motion pattern.
- 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.
Action!
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
BYTE FUNC CheckNeighbors(CARD x BYTE y)
IF Locate(x-1,y-1)=1 THEN RETURN (1) FI
IF Locate(x,y-1)=1 THEN RETURN (1) FI
IF Locate(x+1,y-1)=1 THEN RETURN (1) FI
IF Locate(x-1,y)=1 THEN RETURN (1) FI
IF Locate(x+1,y)=1 THEN RETURN (1) FI
IF Locate(x-1,y+1)=1 THEN RETURN (1) FI
IF Locate(x,y+1)=1 THEN RETURN (1) FI
IF Locate(x+1,y+1)=1 THEN RETURN (1) FI
RETURN (0)
PROC DrawTree()
DEFINE MAXW="255"
DEFINE MINX="1"
DEFINE MAXX="318"
DEFINE MINY="1"
DEFINE MAXY="190"
BYTE CH=$02FC
CARD x,l,r
BYTE y,t,b,w,h,dx,dy,m=[20]
x=160 y=96
Plot(x,y)
l=x-m r=x+m
t=y-m b=y+m
w=r-l+1 h=b-t+1
DO
DO
x=Rand(w)+l y=Rand(h)+t
UNTIL Locate(x,y)=0
OD
WHILE CheckNeighbors(x,y)=0
DO
DO
dx=Rand(3) dy=Rand(3)
UNTIL dx#2 OR dy#2
OD
IF dx=0 THEN
IF x>l THEN x==-1
ELSE x=r-1
FI
ELSEIF dx=1 THEN
IF x<r THEN x==+1
ELSE x=l+1
FI
FI
IF dy=0 THEN
IF y>t THEN y==-1
ELSE y=b-1
FI
ELSEIF dy=1 THEN
IF y<b THEN y==+1
ELSE y=t+1
FI
FI
OD
Plot(x,y)
IF l>MINX AND l+m>x AND w<MAXW THEN
l==-1 w==+1
FI
IF r<MAXX AND r-m<x AND w<MAXW THEN
r==+1 w==+1
FI
IF t>MINY AND t+m>y THEN
t==-1 h==+1
FI
IF b<MAXY AND b-m<y THEN
b==+1 h==+1
FI
Poke(77,0) ;turn off the attract mode
UNTIL CH#$FF ;until key pressed
OD
CH=$FF
RETURN
PROC Main()
BYTE COLOR1=$02C5,COLOR2=$02C6
Graphics(8+16)
Color=1
COLOR1=$0E
COLOR2=$02
DrawTree()
RETURN- Output:
Ada
with Ada.Numerics.Discrete_Random;
with SDL.Video.Windows.Makers;
with SDL.Video.Renderers.Makers;
with SDL.Events.Events;
procedure Brownian_Tree is
Width : constant := 800;
Height : constant := 600;
Points : constant := 50_000;
subtype Width_Range is Integer range 1 .. Width;
subtype Height_Range is Integer range 1 .. Height;
type Direction is (N, NE, E, SE, S, SW, W, NW);
package Random_Width is new Ada.Numerics.Discrete_Random (Width_Range);
package Random_Height is new Ada.Numerics.Discrete_Random (Height_Range);
package Random_Direc is new Ada.Numerics.Discrete_Random (Direction);
Window : SDL.Video.Windows.Window;
Renderer : SDL.Video.Renderers.Renderer;
Event : SDL.Events.Events.Events;
Width_Gen : Random_Width.Generator;
Height_Gen : Random_Height.Generator;
Direc_Gen : Random_Direc.Generator;
function Poll_Quit return Boolean is
use type SDL.Events.Event_Types;
begin
while SDL.Events.Events.Poll (Event) loop
if Event.Common.Event_Type = SDL.Events.Quit then
return True;
end if;
end loop;
return False;
end Poll_Quit;
procedure Draw_Brownian_Tree is
Field : array (Width_Range, Height_Range) of Boolean := (others => (others => False));
X : Width_Range;
Y : Height_Range;
Direc : Direction;
procedure Random_Free (X : out Width_Range; Y : out Height_Range) is
begin
-- Find free random spot
loop
X := Random_Width.Random (Width_Gen);
Y := Random_Height.Random (Height_Gen);
exit when Field (X, Y) = False;
end loop;
end Random_Free;
begin
-- Seed
Field (Random_Width.Random (Width_Gen),
Random_Height.Random (Height_Gen)) := True;
for I in 0 .. Points loop
Random_Free (X, Y);
loop
-- If collide with wall then new random start
while
X = Width_Range'First or X = Width_Range'Last or
Y = Height_Range'First or Y = Height_Range'Last
loop
Random_Free (X, Y);
end loop;
exit when Field (X - 1, Y - 1) or Field (X, Y - 1) or Field (X + 1, Y - 1);
exit when Field (X - 1, Y) or Field (X + 1, Y);
exit when Field (X - 1, Y + 1) or Field (X, Y + 1) or Field (X + 1, Y + 1);
Direc := Random_Direc.Random (Direc_Gen);
case Direc is
when NW | N | NE => Y := Y - 1;
when SW | S | SE => Y := Y + 1;
when others => null;
end case;
case Direc is
when NW | W | SW => X := X - 1;
when SE | E | NE => X := X + 1;
when others => null;
end case;
end loop;
Field (X, Y) := True;
Renderer.Draw (Point => (SDL.C.int (X), SDL.C.int (Y)));
if I mod 100 = 0 then
if Poll_Quit then
return;
end if;
Window.Update_Surface;
end if;
end loop;
end Draw_Brownian_Tree;
begin
Random_Width.Reset (Width_Gen);
Random_Height.Reset (Height_Gen);
Random_Direc.Reset (Direc_Gen);
if not SDL.Initialise (Flags => SDL.Enable_Screen) then
return;
end if;
SDL.Video.Windows.Makers.Create (Win => Window,
Title => "Brownian tree",
Position => SDL.Natural_Coordinates'(X => 10, Y => 10),
Size => SDL.Positive_Sizes'(Width, Height),
Flags => 0);
SDL.Video.Renderers.Makers.Create (Renderer, Window.Get_Surface);
Renderer.Set_Draw_Colour ((0, 0, 0, 255));
Renderer.Fill (Rectangle => (0, 0, Width, Height));
Renderer.Set_Draw_Colour ((200, 200, 200, 255));
Draw_Brownian_Tree;
Window.Update_Surface;
loop
exit when Poll_Quit;
delay 0.050;
end loop;
Window.Finalize;
SDL.Finalise;
end Brownian_Tree;
Applesoft BASIC
Uses XDRAW to plot to Hi-res GRaphics, in fullscreen [POKE 49234,0] 280 x 192, effectively 140 x 192 because colors stretch over two pixels, using a single pixel shape. The POKEs create one shape in a shape table starting at address 768 and point addresses 232 and 233 to this address. Address 234 is the collision counter which is used to detect if the randomly placed seed has hit anything and if the moving seed has collided with the tree. Plotting the seed creates an animation effect of the seed moving around in it's Brownian way.
0GOSUB2:FORQ=0TOTSTEP0:X=A:Y=B:FORO=0TOTSTEP0:XDRAWTATX,Y:X=INT(RND(T)*J)*Z:Y=INT(RND(T)*H):XDRAWTATX,Y:O=PEEK(C)>0:NEXTO:FORP=0TOTSTEP0:A=X:B=Y:R=INT(RND(T)*E):X=X+X(R):Y=Y+Y(R):IFX<0ORX>MORY<0ORY>NTHENNEXTQ
1 XDRAW T AT X,Y:P = NOT PEEK (C): XDRAW T AT A,B: NEXT P: XDRAW T AT X,Y:Q = A = 0 OR A = M OR B = 0 OR B = N: NEXT Q: END
2 T = 1:Z = 2:E = 8:C = 234
3 W = 280:A = W / 2:J = A
4 H = 192:B = H / 2:M = W - 2
5 N = H - 1:U = - 1:V = - 2
6 Y(0) = U:X(0) = V:Y(1) = U
7 Y(2) = U:X(2) = 2:X(3) = 2
8 Y(4) = 1:X(4) = 2:Y(5) = 1
9 X(6) = V:Y(6) = 1:X(7) = V
10 POKE 768,1: POKE 769,0
11 POKE 770,4: POKE 771,0
12 POKE 772,5: POKE 773,0
13 POKE 232,0: POKE 233,3
14 HGR : POKE 49234,0
15 ROT= 0: SCALE= 1: RETURNAutoHotkey
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
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
C
#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
Alternative Version
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.
C#
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");
}
}
}
C++
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;
}
//--------------------------------------------------------------------
Common Lisp
When the random walk lands on a set pixel it sets the pixel at the previous position. An alternate method sets a pixel if the current position is vacant and at least one neighbour is set. The former produces denser trees than the latter. If compiled with SBCL, providing a command line argument will invoke the latter method. Requires Quicklisp library manager and the CL-GD package for producing PNG images.
;;; brownian.lisp
;;; sbcl compile: first load and then (sb-ext:save-lisp-and-die "brownian" :executable t :toplevel #'brownian::main)
(ql:quickload "cl-gd")
(defpackage #:brownian
(:use #:cl #:cl-gd))
(in-package #:brownian)
(defvar *size* 512)
(defparameter bitmap (make-array *size*))
(dotimes (i *size*)
(setf (svref bitmap i) (make-array *size* :element-type 'bit)))
;;; is pixel at coord set? returns coord if so otherwise nil if not set or invalid
;;; type:pair->pair|nil
(defun set-p (coord)
(and coord (= (sbit (svref bitmap (car coord)) (cdr coord)) 1) coord))
;;; valid coord predicate, return its arg if valid or nil otherwise
;;; type:pair->pair|nil
(defun coord-p (coord)
(and ((lambda (v hi) (and (>= v 0) (< v hi))) (car coord) *size*)
((lambda (v hi) (and (>= v 0) (< v hi))) (cdr coord) *size*)
coord))
;;; valid coord predicate for the ith neighbour, return its arg if valid or nil otherwise
;;; type:pair->pair|nil
(defun coordi-p (coord i)
(coord-p (cons (+ (car coord) (nth i '(-1 -1 -1 0 0 1 1 1)))
(+ (cdr coord) (nth i '(-1 0 1 -1 1 -1 0 1))))))
;;; random walk until out of bounds or hit occupied pixel
;;; assumes start is valid vacant coord, return start or nil if off-grid
;;; type:pair->pair|nil
(defun random-walk (start)
(let ((next (coordi-p start (random 8))))
(if (set-p next) start
(and next (random-walk next)))))
;;; random walk until out of bounds or or adjacent to occupied pixel
;;; assumes start is valid vacant coord, return start or nil if off-grid
;;; type:pair->pair|nil
(defun random-walk2 (start)
(if (some #'set-p
(remove-if #'null (mapcar (lambda (i) (coordi-p start i)) '(0 1 2 3 4 5 6 7))))
start
(let ((next (coordi-p start (random 8))))
(and next (random-walk2 next)))))
(defparameter use-walk2 nil)
(defun main ()
(setf *random-state* (make-random-state t)) ;; randomize
(when (cdr sb-ext:*posix-argv*) (setf use-walk2 t)) ;; any cmd line arg -> use alt walk algorithm
(with-image* (*size* *size*)
(allocate-color 0 0 0) ; background color
;;; set the desired number of pixels in image as a pct (10%) of total
(let ((target (truncate (* 0.10 (* *size* *size*))))
(green (allocate-color 104 156 84)))
(defun write-pixel (coord)
(set-pixel (car coord) (cdr coord) :color green)
(setf (sbit (svref bitmap (car coord)) (cdr coord)) 1)
coord)
;; initial point set
(write-pixel (cons (truncate (/ *size* 2)) (truncate (/ *size* 2))))
;; iterate until target # of pixels are set
(do ((i 0 i)
(seed (cons (random *size*) (random *size*)) (cons (random *size*) (random *size*))))
((= i target) )
(let ((newcoord (and (not (set-p seed)) (if use-walk2 (random-walk2 seed) (random-walk seed)))))
(when newcoord
(write-pixel newcoord)
(incf i)
;; report every 5% of progress
(when (zerop (rem i (round (* target 0.05))))
(format t "~A% done.~%" (round (/ i target 0.01))))))))
(write-image-to-file "brownian.png"
:compression-level 6 :if-exists :supersede)))
D
Uses the module of the Grayscale Image task. Partial
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):
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;
EasyLang
color3 0 1 1
len f[] 200 * 200
move 50 50
rect 0.5 0.5
f[100 * 200 + 100] = 1
n = 9000
while i < n
repeat
x = random 200
y = random 200
until f[y * 200 + x] <> 1
.
while 1 = 1
xo = x
yo = y
x += random 3 - 1
y += random 3 - 1
if x < 0 or y < 0 or x >= 200 or y >= 200
break 1
.
if f[y * 200 + x] = 1
move xo / 2 yo / 2
rect 0.5 0.5
f[yo * 200 + xo] = 1
i += 1
if i mod 16 = 0
color3 0.2 + i / n 1 1
sleep 0
.
break 1
.
.
.
Factor
This example sets four spawn points, one in each corner of the image, giving the result a vague x-shaped appearance. For visual reasons, movement is restricted to diagonals. So be careful if you change the seed or spawns — they should all fall on the same diagonal.
USING: accessors images images.loader kernel literals math
math.vectors random sets ;
FROM: sets => in? ;
EXCLUDE: sequences => move ;
IN: rosetta-code.brownian-tree
CONSTANT: size 512
CONSTANT: num-particles 30000
CONSTANT: seed { 256 256 }
CONSTANT: spawns { { 10 10 } { 502 10 } { 10 502 } { 502 502 } }
CONSTANT: bg-color B{ 0 0 0 255 }
CONSTANT: fg-color B{ 255 255 255 255 }
: in-bounds? ( loc -- ? )
dup { 0 0 } ${ size 1 - dup } vclamp = ;
: move ( loc -- loc' )
dup 2 [ { 1 -1 } random ] replicate v+ dup in-bounds?
[ nip ] [ drop ] if ;
: grow ( particles -- particles' )
spawns random dup
[ 2over swap in? ] [ drop dup move swap ] until nip
swap [ adjoin ] keep ;
: brownian-data ( -- seq )
HS{ $ seed } clone num-particles 1 - [ grow ] times { }
set-like ;
: blank-bitmap ( -- bitmap )
size sq [ bg-color ] replicate B{ } concat-as ;
: init-img ( -- img )
<image>
${ size size } >>dim
BGRA >>component-order
ubyte-components >>component-type
blank-bitmap >>bitmap ;
: brownian-img ( -- img )
init-img dup brownian-data
[ swap [ fg-color swap first2 ] dip set-pixel-at ] with each
;
: save-brownian-tree-image ( -- )
brownian-img "brownian.png" save-graphic-image ;
MAIN: save-brownian-tree-image
- Output:
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)
}
}
}
}Fortran
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
FreeBASIC
' version 16-03-2017
' compile with: fbc -s gui
Const As ULong w = 400
Const As ULong w1 = w -1
Dim As Long x, y, lastx, lasty
Dim As Long count, max = w * w \ 4
ScreenRes w, w, 8 ' windowsize 400 * 400, 8bit
' hit any key to stop or mouseclick on close window [X]
WindowTitle "hit any key to stop and close the window"
Palette 0, 0 ' black
Palette 1, RGB( 1, 1, 1) ' almost black
Palette 2, RGB(255, 255, 255) ' white
Palette 3, RGB( 0, 255, 0) ' green
Line (0, 0) - (w1, w1), 0, BF ' make field black
Line (0, 0) - (w1, w1), 1, B ' draw border in almost black color
Randomize Timer
x = Int(Rnd * 11) - 5
y = Int(Rnd * 11) - 5
PSet(w \ 2 + x, w \ 2 + y), 3 ' place seed near center
Do
Do ' create new particle
x = Int(Rnd * w1) + 1
y = Int(Rnd * w1) + 1
Loop Until Point(x, y) = 0 ' black
PSet(x, y), 2
Do
lastx = x
lasty = y
Do
x = lastx + Int(Rnd * 3) -1
y = lasty + Int(Rnd * 3) -1
Loop Until Point(x, y) <> 1
If Point(x, y) = 3 Then
PSet(lastx, lasty), 3
Exit Do ' exit do loop and create new particle
End If
PSet(lastx, lasty), 0
PSet(x,y), 2
If Inkey <> "" Or Inkey = Chr(255) + "k" Then
End
End If
Loop
count += 1
Loop Until count > max
Beep : Sleep 5000
EndGnuplot
Plotting helper file for load command
plotff.gp - Plotting from any data-file with 2 columns (space delimited), and writing to png-file.
Especially useful to plot colored fractals using points.
## plotff.gp 11/27/16 aev
## Plotting from any data-file with 2 columns (space delimited), and writing to png-file.
## Especially useful to plot colored fractals using points.
## Note: assign variables: clr, filename and ttl (before using load command).
reset
set terminal png font arial 12 size 640,640
ofn=filename.".png"
set output ofn
unset border; unset xtics; unset ytics; unset key;
set size square
dfn=filename.".dat"
set title ttl font "Arial:Bold,12"
plot dfn using 1:2 with points pt 7 ps 0.5 lc @clr
set output
Versions #1 - #4. Plotting from PARI/GP generated dat-files
Note: dat-files are [PARI/GP] generated output files.
## BTff.gp 11/27/16 aev
## Plotting 6 Brownian tree pictures.
## dat-files are PARI/GP generated output files:
## http://rosettacode.org/wiki/Brownian_tree#PARI.2FGP
#cd 'C:\gnupData'
##BT1
clr = '"dark-green"'
filename = "BTAH1"
ttl = "Brownian Tree v.#1"
load "plotff.gp"
##BT2
clr = '"brown"'
filename = "BTOC1"
ttl = "Brownian Tree v.#2"
load "plotff.gp"
##BT3
clr = '"navy"'
filename = "BTSE1"
ttl = "Brownian Tree v.#3"
load "plotff.gp"
##BT41
clr = '"red"'
filename = "BTPB1"
ttl = "Brownian Tree v.#4-1"
load "plotff.gp"
##BT42
clr = '"red"'
filename = "BTPB2"
ttl = "Brownian Tree v.#4-2"
load "plotff.gp"
##BT43
clr = '"red"'
filename = "BTPB3"
ttl = "Brownian Tree v.#4-3"
load "plotff.gp"
- Output:
1. All BTff.gp commands. 2. All plotted png-files: BT1gp.png, BT2gp.png, BT3gp.png, BT41gp.png, BT43gp.png, BT43gp.png.
Go
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: <syntaxhighlight lang="go">package main
import (
"fmt" "image" "image/color" "image/png" "math/rand" "os"
)
const w = 400 // image width const h = 300 // image height const n = 15000 // number of particles to add const frost = 255 // white
var g *image.Gray
func main() {
g = image.NewGray(image.Rectangle{image.Point{0, 0}, image.Point{w, h}})
// off center seed position makes pleasingly asymetrical tree
g.SetGray(w/3, h/3, color.Gray{frost})
generate:
for a := 0; a < n; {
// generate random position for new particle
rp := image.Point{rand.Intn(w), rand.Intn(h)}
if g.At(rp.X, rp.Y).(color.Gray).Y == frost {
// position is already set. find a nearby free position.
for {
rp.X += rand.Intn(3) - 1
rp.Y += rand.Intn(3) - 1
// execpt if we run out of bounds, consider the particle lost.
if !rp.In(g.Rect) {
continue generate
}
if g.At(rp.X, rp.Y).(color.Gray).Y != frost {
break
}
}
} else {
// else particle is in free space. let it wander
// until it touches tree
for !hasNeighbor(rp) {
rp.X += rand.Intn(3) - 1
rp.Y += rand.Intn(3) - 1
// but again, if it wanders out of bounds consider it lost.
if !rp.In(g.Rect) {
continue generate
}
}
}
// x, y now specify a free position toucing the tree.
g.SetGray(rp.X, rp.Y, color.Gray{frost})
a++
// progress indicator
if a%100 == 0 {
fmt.Println(a, "of", n)
}
}
f, err := os.Create("tree.png")
if err != nil {
fmt.Println(err)
return
}
err = png.Encode(f, g)
if err != nil {
fmt.Println(err)