Brownian tree: Difference between revisions
(→Solutions: Added a Python solution) |
|||
Line 528: | Line 528: | ||
Until Event = #PB_Event_CloseWindow |
Until Event = #PB_Event_CloseWindow |
||
EndIf</lang>[[File:BrownianTree.pb.png]] |
EndIf</lang>[[File:BrownianTree.pb.png]] |
||
=={{header|Python}}== |
|||
{{libheader|pygame}} |
|||
<lang python>import pygame, sys, os |
|||
from pygame.locals import * |
|||
from random import randint |
|||
pygame.init() |
|||
MAXSPEED = 15 |
|||
SIZE = 3 |
|||
COLOR = (45, 90, 45) |
|||
WINDOWSIZE = 400 |
|||
TIMETICK = 1 |
|||
MAXPART = 50 |
|||
freeParticles = pygame.sprite.Group() |
|||
tree = pygame.sprite.Group() |
|||
window = pygame.display.set_mode((WINDOWSIZE, WINDOWSIZE)) |
|||
pygame.display.set_caption("Brownian Tree") |
|||
screen = pygame.display.get_surface() |
|||
class Particle(pygame.sprite.Sprite): |
|||
def __init__(self, vector, location, surface): |
|||
pygame.sprite.Sprite.__init__(self) |
|||
self.vector = vector |
|||
self.surface = surface |
|||
self.accelerate(vector) |
|||
self.add(freeParticles) |
|||
self.rect = pygame.Rect(location[0], location[1], SIZE, SIZE) |
|||
self.surface.fill(COLOR, self.rect) |
|||
def onEdge(self): |
|||
if self.rect.left <= 0: |
|||
self.vector = (abs(self.vector[0]), self.vector[1]) |
|||
elif self.rect.top <= 0: |
|||
self.vector = (self.vector[0], abs(self.vector[1])) |
|||
elif self.rect.right >= WINDOWSIZE: |
|||
self.vector = (-abs(self.vector[0]), self.vector[1]) |
|||
elif self.rect.bottom >= WINDOWSIZE: |
|||
self.vector = (self.vector[0], -abs(self.vector[1])) |
|||
def update(self): |
|||
if freeParticles in self.groups(): |
|||
self.surface.fill((0,0,0), self.rect) |
|||
self.remove(freeParticles) |
|||
if pygame.sprite.spritecollideany(self, freeParticles): |
|||
self.accelerate((randint(-MAXSPEED, MAXSPEED), |
|||
randint(-MAXSPEED, MAXSPEED))) |
|||
self.add(freeParticles) |
|||
elif pygame.sprite.spritecollideany(self, tree): |
|||
self.stop() |
|||
else: |
|||
self.add(freeParticles) |
|||
self.onEdge() |
|||
if (self.vector == (0,0)) and tree not in self.groups(): |
|||
self.accelerate((randint(-MAXSPEED, MAXSPEED), |
|||
randint(-MAXSPEED, MAXSPEED))) |
|||
self.rect.move_ip(self.vector[0], self.vector[1]) |
|||
self.surface.fill(COLOR, self.rect) |
|||
def stop(self): |
|||
self.vector = (0,0) |
|||
self.remove(freeParticles) |
|||
self.add(tree) |
|||
def accelerate(self, vector): |
|||
self.vector = vector |
|||
NEW = USEREVENT + 1 |
|||
TICK = USEREVENT + 2 |
|||
pygame.time.set_timer(NEW, 50) |
|||
pygame.time.set_timer(TICK, TIMETICK) |
|||
def input(events): |
|||
for event in events: |
|||
if event.type == QUIT: |
|||
sys.exit(0) |
|||
elif event.type == NEW and (len(freeParticles) < MAXPART): |
|||
Particle((randint(-MAXSPEED,MAXSPEED), |
|||
randint(-MAXSPEED,MAXSPEED)), |
|||
(randint(0, WINDOWSIZE), randint(0, WINDOWSIZE)), |
|||
screen) |
|||
elif event.type == TICK: |
|||
freeParticles.update() |
|||
half = WINDOWSIZE/2 |
|||
tenth = WINDOWSIZE/10 |
|||
root = Particle((0,0), |
|||
(randint(half-tenth, half+tenth), |
|||
randint(half-tenth, half+tenth)), screen) |
|||
root.stop() |
|||
while True: |
|||
input(pygame.event.get()) |
|||
pygame.display.flip()</lang> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
Revision as of 23:22, 13 May 2010
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) |
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.
- 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.
C
<lang 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);
}</lang>
D
D V.2, from the C version, writes a Portable Bit Map image to the stdout. <lang d>import std.c.stdlib: rand, srand; import std.c.time: time; import std.stdio: printf, putchar;
enum int WORLD_WIDTH = 800; enum int WORLD_HEIGHT = WORLD_WIDTH; enum int NUM_PARTICLES = 10_000;
static assert(NUM_PARTICLES > 0); static assert(WORLD_WIDTH * WORLD_HEIGHT > NUM_PARTICLES);
typedef ubyte[WORLD_WIDTH][WORLD_HEIGHT] TWorld;
void dla(ref TWorld world) {
int px, py; // particle values int dx, dy; // offsets
// put the tree seed world[WORLD_HEIGHT / 2][WORLD_WIDTH / 2] = 1;
foreach (_; 0 .. NUM_PARTICLES) { // set particle's initial position px = rand() % WORLD_WIDTH; py = rand() % WORLD_HEIGHT;
while (true) { // move particle // randomly choose a direction dx = rand() % 3 - 1; dy = rand() % 3 - 1;
if (dx + px < 0 || dx + px >= WORLD_WIDTH || dy + py < 0 || dy + py >= WORLD_HEIGHT) { // plop the particle into some other random location px = rand() % WORLD_WIDTH; py = rand() % WORLD_HEIGHT; } else if (world[py + dy][px + dx]) { // bumped into something, particle set world[py][px] = 1; break; } else { py += dy; px += dx; } } }
}
void toPBM(ref TWorld world) {
printf("P1\n"); // Type=Portable bitmap, Encoding=ASCII printf("%d %d\n", WORLD_WIDTH, WORLD_HEIGHT); foreach (ref line; world) { foreach (pixel; line) putchar(pixel ? '1' : '0'); putchar('\n'); }
}
void main() {
srand(cast(uint)time(null)); TWorld world; dla(world); toPBM(world);
}</lang>
Delphi
<lang delphi>const
SIZE = 256; NUM_PARTICLES = 1000;
procedure TForm1.Button1Click(Sender: TObject); type
TByteArray = array[0..0] of Byte; PByteArray = ^TByteArray;
var
B: TBitmap; I: Integer; P, D: TPoint;
begin
Randomize; B := TBitmap.Create; try B.Width := SIZE; B.Height := SIZE; B.PixelFormat := pf8bit;
B.Canvas.Brush.Color := clBlack; B.Canvas.FillRect(B.Canvas.ClipRect); B.Canvas.Pixels[Random(SIZE), Random(SIZE)] := clWhite;
For I := 0 to NUM_PARTICLES - 1 do Begin P.X := Random(SIZE); P.Y := Random(SIZE);
While true do Begin D.X := Random(3) - 1; D.Y := Random(3) - 1; Inc(P.X, D.X); Inc(P.Y, D.Y);
If ((P.X or P.Y) < 0) or (P.X >= SIZE) or (P.Y >= SIZE) Then Begin P.X := Random(SIZE); P.Y := Random(SIZE); end else if PByteArray(B.ScanLine[P.Y])^[P.X] <> 0 then begin PByteArray(B.ScanLine[P.Y-D.Y])^[P.X-D.X] := $FF; Break; end; end; end;
Canvas.Draw(0, 0, B); finally FreeAndNil(B); end;
end;</lang>
Fortran
For RCImageBasic and RCImageIO, see Basic bitmap storage/Fortran and Write ppm file#Fortran
<lang fortran>program BrownianTree
use RCImageBasic use RCImageIO
implicit none
integer, parameter :: num_particles = 1000 integer, parameter :: wsize = 800
integer, dimension(wsize, wsize) :: world type(rgbimage) :: gworld integer :: x, y
! init seed call init_random_seed world = 0 call draw_brownian_tree(world)
call alloc_img(gworld, wsize, wsize) call fill_img(gworld, rgb(0,0,0)) do y = 1, wsize do x = 1, wsize if ( world(x, y) /= 0 ) then call put_pixel(gworld, x, y, rgb(255, 255, 255)) end if end do end do
open(unit=10, file='browniantree.ppm', action='write') call output_ppm(10, gworld) close(10)
call free_img(gworld)
contains
! this code is taken from the GNU gfortran online doc subroutine init_random_seed integer :: i, n, clock integer, dimension(:), allocatable :: seed
call random_seed(size = n) allocate(seed(n)) call system_clock(count = clock) seed = clock + 37 * (/ ( i - 1, i = 1, n) /) call random_seed(put = seed) deallocate(seed) end subroutine init_random_seed
function randbetween(a, b) result(res) ! suppose a < b integer, intent(in) :: a, b integer :: res
real :: r
call random_number(r)
res = a + int((b-a)*r + 0.5)
end function randbetween
function bounded(v, ll, ul) result(res) integer, intent(in) :: v, ll, ul logical res
res = ( v >= ll ) .and. ( v <= ul ) end function bounded
subroutine draw_brownian_tree(w) integer, dimension(:,:), intent(inout) :: w
integer :: px, py, dx, dy, i integer :: xsize, ysize
xsize = size(w, 1) ysize = size(w, 2)
w(randbetween(1, xsize), randbetween(1, ysize)) = 1 do i = 1, num_particles px = randbetween(1, xsize) py = randbetween(1, ysize) do dx = randbetween(-1, 1) dy = randbetween(-1, 1) if ( .not. bounded(dx+px, 1, xsize) .or. .not. bounded(dy+py, 1, ysize) ) then px = randbetween(1, xsize) py = randbetween(1, ysize) else if ( w(px+dx, py+dy) /= 0 ) then w(px, py) = 1 exit else py = py + dy px = px + dx end if end do end do end subroutine draw_brownian_tree
end program</lang>
JavaScript + <canvas>
Live version <lang javascript>function brownian(canvasId, messageId) {
var canvas = document.getElementById(canvasId); var ctx = canvas.getContext("2d");
// Options var drawPos = true; var seedResolution = 50; var clearShade = 0; // 0..255 // Static state var width = canvas.width; var height = canvas.height; var cx = width/2; var cy = height/2; var clearStyle = "rgba("+clearShade+", "+clearShade+", "+clearShade+", 1)";
// Utilities function radius(x,y) { return Math.sqrt((x-cx)*(x-cy)+(y-cx)*(y-cy)); } function test(x, y) { if (x < 0 || y < 0 || x >= width || y >= height) return false; var data = ctx.getImageData(x, y, 1, 1).data; return data[0] != clearShade || data[1] != clearShade || data[2] != clearShade; } var shade = 120; function setc(x, y, c) { //var imgd = ctx.createImageData(1, 1); //var pix = imgd.data; //pix[0] = pix[1] = pix[2] = c == 255 ? 255 : shade; //pix[3] = 255; //shade = (shade + 1) % 254; //ctx.putImageData(imgd, x, y); //ctx.fillStyle = "rgba("+c+", "+c+", "+c+", 1)"; shade = (shade + 0.02) % 360; if (c) { ctx.fillStyle = "hsl("+shade+", 100%, 50%)"; } else { ctx.fillStyle = clearStyle; } ctx.fillRect (x, y, 1, 1); } function set(x,y) { setc(x,y,true); } function clear(x,y) { setc(x,y,false); }
// Initialize canvas to blank opaque ctx.fillStyle = clearStyle; ctx.fillRect (0, 0, width, height);
// Current position var x; var y;
// Farthest distance from center a particle has yet been placed. var closeRadius = 1;
// Place seed set(cx, cy);
// Choose a new random position for a particle (not necessarily unoccupied) function newpos() { // Wherever particles are injected, the tree will tend to grow faster // toward it. Ideally, particles wander in from infinity; the best we // could do is to have them wander in from the edge of the field. // But in order to have the rendering occur in a reasonable time when // the seed is small, without too much visible bias, we instead place // the particles in a coarse grid. The final tree will cover every // point on the grid. // // There's probably a better strategy than this. x = Math.floor(Math.random()*(width/seedResolution))*seedResolution; y = Math.floor(Math.random()*(height/seedResolution))*seedResolution; } newpos();
var animation; animation = window.setInterval(function () { if (drawPos) clear(x,y); for (var i = 0; i < 10000; i++) { var ox = x; var oy = y; // Changing this to use only the first four directions will result // in a denser tree. switch (Math.floor(Math.random()*8)) { case 0: x++; break; case 1: x--; break; case 2: y++; break; case 3: y--; break; case 4: x++; y++; break; case 5: x--; y++; break; case 6: x++; y--; break; case 7: x--; y--; break; } if (x < 0 || y < 0 || x >= width || y >= height || radius(x,y) > closeRadius+seedResolution+2) { // wandered out of bounds or out of interesting range of the // tree, so pick a new spot var progress = 1000; do { newpos(); progress--; } while ((test(x-1,y-1) || test(x,y-1) || test(x+1,y-1) || test(x-1,y ) || test(x,y ) || test(x+1,y ) || test(x-1,y+1) || test(x,y+1) || test(x+1,y+1)) && progress > 0); if (progress <= 0) { document.getElementById(messageId).appendChild(document.createTextNode("Stopped for lack of room.")); clearInterval(animation); break; } } if (test(x, y)) { // hit something, mark where we came from and pick a new spot set(ox,oy); closeRadius = Math.max(closeRadius, radius(ox,oy)); newpos(); } } if (drawPos) set(x,y); }, 1);
}</lang>
<lang html><html>
<head> <script src="brownian.js"></script> </head> <body onload="brownian('canvas', 'message')"> <canvas id="canvas" width="402" height="402" style="border: 2px inset;"></canvas>
</body>
</html></lang>
Octave
<lang octave>function r = browniantree(xsize, ysize = xsize, numparticle = 1000)
r = zeros(xsize, ysize, "uint8"); r(unidrnd(xsize), unidrnd(ysize)) = 1; for i = 1:numparticle px = unidrnd(xsize-1)+1; py = unidrnd(ysize-1)+1; while(1) dx = unidrnd(2) - 1; dy = unidrnd(2) - 1; if ( (dx+px < 1) || (dx+px > xsize) || (dy+py < 1) || (dy+py > ysize) )
px = unidrnd(xsize-1)+1; py = unidrnd(ysize-1)+1;
elseif ( r(px+dx, py+dy) != 0 )
r(px, py) = 1; break;
else
px += dx; py += dy;
endif endwhile endfor
endfunction
r = browniantree(200); r( r > 0 ) = 255; jpgwrite("browniantree.jpg", r, 100); % image package</lang>
PureBasic
<lang PureBasic>#Window1 = 0
- 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
Python
<lang python>import pygame, sys, os from pygame.locals import * from random import randint pygame.init()
MAXSPEED = 15 SIZE = 3 COLOR = (45, 90, 45) WINDOWSIZE = 400 TIMETICK = 1 MAXPART = 50
freeParticles = pygame.sprite.Group() tree = pygame.sprite.Group()
window = pygame.display.set_mode((WINDOWSIZE, WINDOWSIZE)) pygame.display.set_caption("Brownian Tree")
screen = pygame.display.get_surface()
class Particle(pygame.sprite.Sprite):
def __init__(self, vector, location, surface): pygame.sprite.Sprite.__init__(self) self.vector = vector self.surface = surface self.accelerate(vector) self.add(freeParticles) self.rect = pygame.Rect(location[0], location[1], SIZE, SIZE) self.surface.fill(COLOR, self.rect)
def onEdge(self): if self.rect.left <= 0: self.vector = (abs(self.vector[0]), self.vector[1]) elif self.rect.top <= 0: self.vector = (self.vector[0], abs(self.vector[1])) elif self.rect.right >= WINDOWSIZE: self.vector = (-abs(self.vector[0]), self.vector[1]) elif self.rect.bottom >= WINDOWSIZE: self.vector = (self.vector[0], -abs(self.vector[1]))
def update(self): if freeParticles in self.groups(): self.surface.fill((0,0,0), self.rect) self.remove(freeParticles) if pygame.sprite.spritecollideany(self, freeParticles): self.accelerate((randint(-MAXSPEED, MAXSPEED), randint(-MAXSPEED, MAXSPEED))) self.add(freeParticles) elif pygame.sprite.spritecollideany(self, tree): self.stop() else: self.add(freeParticles) self.onEdge()
if (self.vector == (0,0)) and tree not in self.groups(): self.accelerate((randint(-MAXSPEED, MAXSPEED), randint(-MAXSPEED, MAXSPEED))) self.rect.move_ip(self.vector[0], self.vector[1]) self.surface.fill(COLOR, self.rect)
def stop(self): self.vector = (0,0) self.remove(freeParticles) self.add(tree)
def accelerate(self, vector): self.vector = vector
NEW = USEREVENT + 1 TICK = USEREVENT + 2
pygame.time.set_timer(NEW, 50) pygame.time.set_timer(TICK, TIMETICK)
def input(events):
for event in events: if event.type == QUIT: sys.exit(0) elif event.type == NEW and (len(freeParticles) < MAXPART): Particle((randint(-MAXSPEED,MAXSPEED), randint(-MAXSPEED,MAXSPEED)), (randint(0, WINDOWSIZE), randint(0, WINDOWSIZE)), screen) elif event.type == TICK: freeParticles.update()
half = WINDOWSIZE/2
tenth = WINDOWSIZE/10
root = Particle((0,0),
(randint(half-tenth, half+tenth), randint(half-tenth, half+tenth)), screen)
root.stop()
while True:
input(pygame.event.get()) pygame.display.flip()</lang>
Ruby
<lang ruby>require 'rubygems' require 'RMagick'
NUM_PARTICLES = 1000 SIZE = 800
def draw_brownian_tree world
# set the seed world[rand SIZE][rand SIZE] = 1
NUM_PARTICLES.times do # set particle's position px = rand SIZE py = rand SIZE
loop do # randomly choose a direction dx = rand(3) - 1 dy = rand(3) - 1
if dx + px < 0 or dx + px >= SIZE or dy + py < 0 or dy + py >= SIZE # plop the particle into some other random location px = rand SIZE py = rand SIZE elsif world[py + dy][px + dx] != 0 # bumped into something world[py][px] = 1 break else py += dy px += dx end end end
end
world = Array.new(SIZE) { Array.new(SIZE, 0) } srand Time.now.to_i
draw_brownian_tree world
img = Magick::Image.new(SIZE, SIZE) do
self.background_color = "black"
end
draw = Magick::Draw.new draw.fill "white"
world.each_with_index do |row, y|
row.each_with_index do |colour, x| draw.point x, y if colour != 0 end
end
draw.draw img img.write "brownian_tree.bmp"</lang>
Tcl
<lang tcl>package require Tcl 8.5 package require Tk
set SIZE 300
image create photo brownianTree -width $SIZE -height $SIZE interp alias {} plot {} brownianTree put white -to brownianTree put black -to 0 0 [expr {$SIZE-1}] [expr {$SIZE-1}] proc rnd {range} {expr {int(rand() * $range)}}
proc makeBrownianTree count {
global SIZE # Set the seed plot [rnd $SIZE] [rnd $SIZE] for {set i 0} {$i<$count} {incr i} {
# Set a random particle's initial position set px [rnd $SIZE] set py [rnd $SIZE]
while 1 { # Randomly choose a direction set dx [expr {[rnd 3] - 1}] set dy [expr {[rnd 3] - 1}]
# If we are going out of bounds... if {$px+$dx < 0 || $px+$dx >= $SIZE || $py+$dy < 0 || $py+$dy>=$SIZE} { # Out of bounds, so move back in set dx [expr {[rnd 3] - 1}] set dy [expr {[rnd 3] - 1}] continue }
set ox $px set oy $py # Move/see if we would hit anything incr px $dx incr py $dy if {[lindex [brownianTree get $px $py] 0]} { # Hit something, so plot where we were plot $ox $oy break } } ## For display while things are processing, uncomment next line #update;puts -nonewline .;flush stdout
}
}
pack [label .l -image brownianTree] update makeBrownianTree 1000 brownianTree write tree.ppm</lang>