Boids
A Boids algorithm simulates the flocking behavior of birds. This task requires the creation of a graphical or purely textual simulation of a flock of birds navigating the cave with obstacles depicted below.
Boids is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
.......###############............................................................... .......###############............................................................... ......#################.............................................................. O......###############............................................................... OO.....###############............................................................... OO.....###############....................#.........................#................ OO......#############...................#####...................#########............ OO......#############...................#####..................###########........... OO.......###########...................#######................#############.......... OO.........#######......................#####................###############......... OO............#.........................#####...............#################........ OO........................................#.................#################........ O...........................................................#################........ ............................................................#################........ ...........................................................###################....... ............................................................#################........
If you implement a purely textual simulation, this is a possible board representation, where "O" are the boids that should go toward the right, "#" are fixed walls that should be avoided by the boids, and "." is free space (using a space is also acceptable for free space, if you add some kind of frame around the board).
A simulation that doesn't contain obstacles but only shows flocking behavior is acceptable.
- See also
See Boids/C
ASCII mode
Const MAP_WIDTH = 86
Const MAP_HEIGHT = 20
Type Punto
As Integer x
As Integer y
End Type
Type Boid
As Punto posic
End Type
Type Environment
As Ubyte buffer(MAP_HEIGHT, MAP_WIDTH)
As Boid boids(17)
As Integer boidCnt
End Type
Dim Shared As Environment env
' Initialize map with walls and spaces
Sub initMap()
Dim As Integer x, y, posic = 1
' Add cave obstacles (hardcoded pattern)
Dim As String cave = _
" ############### " & Chr(10) & _
" ############### " & Chr(10) & _
" ################# " & Chr(10) & _
"O ############### " & Chr(10) & _
"OO ############### " & Chr(10) & _
"OO ############### # # " & Chr(10) & _
"OO ############# ##### ######### " & Chr(10) & _
"OO ############# ##### ########### " & Chr(10) & _
"OO ########### ####### ############# " & Chr(10) & _
"OO ####### ##### ############### " & Chr(10) & _
"OO # ##### ################# " & Chr(10) & _
"OO # ################# " & Chr(10) & _
"O ################# " & Chr(10) & _
" ################# " & Chr(10) & _
" ################### " & Chr(10) & _
" ################# "
' Process the map line by line
For y = 1 To 16
For x = 1 To 85
Select Case Mid(cave, posic, 1)
Case "#"
env.buffer(y, x) = Asc("#")
Case "O"
env.boids(env.boidCnt).posic.x = x
env.boids(env.boidCnt).posic.y = y
env.boidCnt += 1
env.buffer(y, x) = Asc(" ")
Case Else
env.buffer(y, x) = Asc(" ")
End Select
posic += 1
Next x
posic += 1 ' Skip Chr(10)
Next y
' Add frame
For x = 0 To MAP_WIDTH-1
env.buffer(0, x) = Asc("#")
env.buffer(MAP_HEIGHT-1, x) = Asc("#")
Next x
For y = 0 To MAP_HEIGHT-1
env.buffer(y, 0) = Asc("#")
env.buffer(y, MAP_WIDTH-1) = Asc("#")
Next y
'
End Sub
' Check if position is free
Function isFree(x As Integer, y As Integer) As Boolean
If env.buffer(y,x) = Asc(" ") Then
For i As Integer = 0 To env.boidCnt-1
If env.boids(i).posic.x = x Andalso env.boids(i).posic.y = y Then Return False
Next
Return True
End If
Return False
End Function
Sub moveBoids()
For i As Integer = 0 To env.boidCnt-1
Dim As Integer nx = env.boids(i).posic.x + 1
Dim As Integer ny = env.boids(i).posic.y
' Try to move right
If isFree(nx, ny) Then
env.boids(i).posic.x = nx
' If blocked, try up or down
Elseif isFree(env.boids(i).posic.x, ny-1) Then
env.boids(i).posic.y -= 1
Elseif isFree(env.boids(i).posic.x, ny+1) Then
env.boids(i).posic.y += 1
End If
Next
End Sub
Sub drawState()
Dim As Integer x, y, i
Cls
' Draw environment
For y = 0 To MAP_HEIGHT-1
For x = 0 To MAP_WIDTH-1
Draw String (x*8, y*16), Chr(env.buffer(y,x))
Next x
Next y
' Draw boids
For i = 0 To env.boidCnt-1
Draw String (env.boids(i).posic.x*8, env.boids(i).posic.y*16), "O"
Next
End Sub
' Main program
Screenres MAP_WIDTH*8, MAP_HEIGHT*16, 32
Windowtitle "Boids in FreeBASIC"
initMap()
Do
moveBoids()
drawState()
Sleep 100
Loop Until Multikey(&h01)
See Boids/Go
See Boids/Java
See Boids/Julia
See Boids/Nim
See Boids/Phix
Screenshot: http://phix.x10.mx/shots/boids.png
import math
import pygame
import random
WIDTH, HEIGHT = 1000, 800
def rotate_triangle(center: tuple[int, int], scale: int, angle: float):
v_center = pygame.math.Vector2(center)
points = [(-0.5, -0.866), (-0.5, 0.866), (2.0, 0.0)]
rotated_point = [pygame.math.Vector2(p).rotate(angle) for p in points]
triangle_points = [(v_center + p * scale) for p in rotated_point]
return triangle_points
class Boid:
def __init__(self, x: int, y: int, r: float, min_speed=5, max_speed=10):
self.x = x
self.y = y
self.min_speed = min_speed
self.speed = min_speed
self.max_speed = max_speed
self.r = r
self.turn_rate = 1
self.angle = random.randint(0, 360)
def draw(self, surface: pygame.Surface):
points = rotate_triangle((self.x, self.y), 10, self.angle)
pygame.draw.polygon(surface, (255, 255, 255), points)
def move(self):
angle_rad = math.radians(self.angle)
self.x = (self.x + math.cos(angle_rad) * self.speed) % WIDTH
self.y = (self.y + math.sin(angle_rad) * self.speed) % HEIGHT
def get_peripheral_rect(self):
w = h = self.r * 2
return pygame.Rect(self.x - w // 2, self.y - h // 2, w, h)
def is_neighbour(self, b: "Boid"):
return b.get_peripheral_rect().colliderect(self.get_peripheral_rect())
def calculate_steer(self, boids: list["Boid"]):
neighbours = [b for b in boids if b.is_neighbour(self)]
if len(neighbours) > 0:
sumation = 0
for n in neighbours:
sumation += n.angle
self.angle = sumation / len(neighbours)
center_y = sum(n.get_peripheral_rect().centerx for n in neighbours) / len(
neighbours
)
center_x = sum(n.get_peripheral_rect().centery for n in neighbours) / len(
neighbours
)
desired_angle = math.degrees(
math.atan2(center_y - self.y, center_x - self.x)
)
angle_diff = (desired_angle - self.angle + 180) % 360 - 180
if angle_diff <= 0:
self.angle += max(-self.turn_rate * 0.5, angle_diff)
else:
self.angle += min(angle_diff, self.turn_rate * 0.5)
self.speed = math.sqrt(self.x * self.x + self.y * self.y)
self.speed = max(self.speed % self.max_speed, self.min_speed)
def main():
pygame.init()
pygame.display.set_caption("Boids")
screen = pygame.display.set_mode((WIDTH, HEIGHT))
clock = pygame.time.Clock()
running = True
boids = [
Boid(random.randint(0, WIDTH), random.randint(0, HEIGHT), 15) for _ in range(15)
]
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
screen.fill((0, 0, 0))
for boid in boids:
boid.draw(screen)
boid.move()
boid.calculate_steer(boids)
pygame.display.flip()
clock.tick(60)
pygame.quit()
if __name__ == "__main__":
main()
- Output:
Rebol [
title: "Rosetta code: Boids"
file: %Boids.r3
url: https://rosettacode.org/wiki/Boids
note: "Translated from Red"
]
;=============================
; PARAMETERS
;=============================
W: 860
H: 160
N: 60 ; boids
random/seed now/time/precise ; randomize
; == FLOCKING BEHAVIOR ==
max-speed: 5.0
neighbor-radius: 80.0
separation-radius: 10.0
sep-weight: 1.8
ali-weight: 0.9
coh-weight: 0.15
;=============================
; VECTOR HELPERS (float)
;=============================
vmag: func [v][sqrt ((v/x * v/x) + (v/y * v/y))]
vnorm: func [v /local m][ m: vmag v either m > 0 [v * 1.0 / m][0x0] ]
vlimit: func [v m][ either m < vmag v [m * vnorm v][v] ]
vdist: func [a b][vmag a - b]
vdot: func [a b][(a/x * b/x) + (a/y * b/y)]
;=============================
; BOIDS
;=============================
boids: collect [
repeat i N [
keep make map! compose [
pos: (as-pair random 50 random H) ; started at left side
vel: (as-pair
random 1.0 ; heading to the right side
(1.0 - random 2.0) ; with some vertical variations
)
]
]
]
;== OBSTACLES DATA ===
obstacles: [
#[c: 160x20 r: 80]
#[c: 445x89 r: 30]
#[c: 700x140 r: 90]
]
;== SIMPLE OBSTACLE AVOIDANCE LOGIC ==
obstacle-avoidance: function [b][
force: 0x0
dir: vnorm b/vel
ahead: b/pos + (dir * (max-speed * 10))
foreach o obstacles [
d: vdist ahead o/c
if d < (o/r + 6.0) [
side: as-pair (negate dir/y) dir/x
to-c: o/c - b/pos
if ((to-c/x * side/x) + (to-c/y * side/y)) > 0 [
side: side * -1.0
]
force: force + side
]
]
if zero? vmag force [return 0x0]
1.8 * vnorm force ; instead of 2.5
]
resolve-obstacle-collision: function [b o][
dvec: b/pos - o/c
d: vmag dvec
if d < o/r [
; 1) push boid to surface
n: vnorm dvec
b/pos: o/c + (n * o/r)
; 2) remove inward velocity
vn: vdot b/vel n
if vn < 0.0 [
b/vel: b/vel - (n * vn)
]
]
]
;=============================
; UPDATE LOGIC
;=============================
flow: 0.05x0 ; right bias
update-boids: function [][
foreach b boids [
sep: ali: coh: 0x0
count: 0
foreach o boids [
if o <> b [
d: vdist b/pos o/pos
if d < neighbor-radius [
ali: ali + o/vel
coh: coh + o/pos
++ count
]
if d < separation-radius [
sep: sep + b/pos - o/pos
]
]
]
if count > 0 [
nc: 1.0 / count
ali: ali-weight * (vnorm ali * nc)
coh: coh-weight * (vnorm (coh * nc) - b/pos)
sep: sep-weight * (vnorm sep)
]
avoid: obstacle-avoidance b
acc: (((sep + ali) + coh) + avoid) + flow
b/vel: vlimit b/vel + acc max-speed
]
;== EDGE MECHANISM ==
foreach b boids [
b/pos: b/pos + b/vel
;== AVOID OBSTACLE COLLISION ==
foreach o obstacles [
resolve-obstacle-collision b o
]
;== BOUNDARY CHECK
if b/pos/x < 0 [b/pos/x: W]
if b/pos/x > W [b/pos/x: 0]
if b/pos/y < 20 [b/vel/y: b/vel/y + 1.9]
if b/pos/y > (H - 20) [b/vel/y: b/vel/y - 1.9]
]
]
;=============================
; DRAWING
;=============================
;; Prepare constant draw commands for the background.
background: [fill-all black fill-pen brown]
foreach o obstacles [
append background compose [circle (o/c) (o/r)]
]
;; Set the color for drawing boids.
append background [pen red]
draw-frame: function [][
blk: clear []
;== Prepare Background with obstacles
append blk background
;== Prepare Boids
update-boids
foreach b boids [
;; Using 3x append to avoid temporary block construction.
append append append blk
'line
b/pos
b/pos + b/vel
]
;== Draw the image.
draw img blk
]
;=============================
; START
;=============================
import blend2d
img: make image! as-pair W H
either function? :view [
;; Show animation when VIEW is available.
gob: make gob! [image: img]
win: view/no-wait gob
visible?: true
;; Register an event handler to detect closing the window.
handle-events [
name: 'view-boids
priority: 100
handler: func [event] [
if switch event/type [
close [true]
key [event/key = escape]
][
unhandle-events self
unview event/window
visible?: false
]
none
]
]
while [visible?][
draw-frame
show win
wait 0.01
]
][
;; Or simulate some number of frames...
loop 100 [draw-frame]
;; ...and save the image.
save %out.png img
]
Red [
Title: "Boids (Draft Task)"
Author: "hinjolicious"
Resources: "ChatGPT :)"
Purpose: "Implementing boid navigation through obstacles in graphical mode"
Needs: 'View
]
;=============================
; PARAMETERS
;=============================
W: 860
H: 160
N: 60 ; boids
random/seed now/time/precise ; randomize
; == FLOCKING BEHAVIOR ==
max-speed: 5.0
neighbor-radius: 80.0
separation-radius: 10.0
sep-weight: 1.8
ali-weight: 0.9
coh-weight: 0.15
;=============================
; VECTOR HELPERS (float)
;=============================
vec: func [xx yy][object [x: xx y: yy]]
vadd: func [a b][vec a/x + b/x a/y + b/y]
vsub: func [a b][vec a/x - b/x a/y - b/y]
vmul: func [a k][vec a/x * k a/y * k]
vmag: func [v][sqrt ((v/x * v/x) + (v/y * v/y))]
vnorm: func [v][ m: vmag v either m > 0.0 [vmul v 1.0 / m][vec 0.0 0.0] ]
vlimit: func [v m][ either (vmag v) > m [vmul (vnorm v) m][v] ]
vdist: func [a b][vmag vsub a b]
vdot: func [a b][(a/x * b/x) + (a/y * b/y)]
;=============================
; BOIDS
;=============================
boids: collect [
repeat i N [
keep object [
pos: vec random 50 random H ; started at left side
vel: vec
random 1.0 ; heading to the right side
(1.0 - random 2.0) ; with some vertical variations
]
]
]
;== OBSTACLES DATA ===
obstacles: reduce [
object [c: vec 160 20 r: 80]
object [c: vec 445 89 r: 30]
object [c: vec 700 140 r: 90]
]
;== SIMPLE OBSTACLE AVOIDANCE LOGIC ==
obstacle-avoidance: func [b][
force: vec 0.0 0.0
dir: vnorm b/vel
ahead: vadd b/pos (vmul dir (max-speed * 10)) ;30
foreach o obstacles [
d: vdist ahead o/c
if d < (o/r + 6.0) [
side: vec (negate dir/y) dir/x
to-c: vsub o/c b/pos
if ((to-c/x * side/x) + (to-c/y * side/y)) > 0 [
side: vmul side -1.0
]
force: vadd force side
]
]
if (vmag force) = 0.0 [return vec 0.0 0.0]
vmul (vnorm force) 1.8 ; instead of 2.5
]
resolve-obstacle-collision: function [b o][
dvec: vsub b/pos o/c
d: vmag dvec
if d < o/r [
; 1) push boid to surface
n: vnorm dvec
b/pos: vadd o/c (vmul n o/r)
; 2) remove inward velocity
vn: vdot b/vel n
if vn < 0.0 [
b/vel: vsub b/vel (vmul n vn)
]
]
]
;=============================
; UPDATE LOGIC
;=============================
flow: vec 0.05 0.0 ; right bias
update-boids: does [
foreach b boids [
sep: vec 0.0 0.0 ali: vec 0.0 0.0 coh: vec 0.0 0.0
count: 0
foreach o boids [
if o <> b [
d: vdist b/pos o/pos
if d < neighbor-radius [
ali: vadd ali o/vel
coh: vadd coh o/pos
count: count + 1
]
if d < separation-radius [
sep: vadd sep vsub b/pos o/pos
]
]
]
if count > 0 [
ali: vmul (vnorm vmul ali 1.0 / count) ali-weight
coh: vmul (vnorm vsub (vmul coh 1.0 / count) b/pos) coh-weight
sep: vmul (vnorm sep) sep-weight
]
avoid: obstacle-avoidance b
acc: vadd (vadd (vadd (vadd sep ali) coh) avoid) flow
b/vel: vlimit vadd b/vel acc max-speed
]
;== EDGE MECHANISM ==
foreach b boids [
b/pos: vadd b/pos b/vel
;== AVOID OBSTACLE COLLISION ==
foreach o obstacles [
resolve-obstacle-collision b o
]
;== BOUNDARY CHECK
if b/pos/x < 0 [b/pos/x: W]
if b/pos/x > W [b/pos/x: 0]
if b/pos/y < 20 [b/vel/y: b/vel/y + 1.9]
if b/pos/y > (H - 20) [b/vel/y: b/vel/y - 1.9]
]
]
;=============================
; DRAWING
;=============================
draw-boids: func [/local blk] [
blk: copy []
append blk [
;fill-pen white
pen white
]
foreach b boids [
append/only blk compose [
;circle (as-pair to-integer b/pos/x to-integer b/pos/y) 3
line (as-pair b/pos/x b/pos/y)
(as-pair (b/pos/x + b/vel/x) (b/pos/y + b/vel/y))
]
]
blk
]
;=============================
; START
;=============================
view/tight compose [
title "Boids - Rosetta Code"
base (as-pair (W) (H)) black draw [] rate 60 on-time [
blk: copy []
;== Draw Obstacles ==
append blk [fill-pen brown circle 160x20 80 circle 445x89 30 circle 700x140 90]
;== Draw Boids
update-boids
append blk draw-boids
;== Draw Animation Frame
face/draw: blk
]
]
See Boids/Wren