fi.sh - a Boids Clone in Bash

After squa.sh, I thought it was time for more abuse of the Bash shell. A few weeks ago I wrote fi.sh, a simulation of flocking behaviour, like migrating birds or a school of fish, written in pure Bash and with ascii-art graphics, of course.

Fi.sh is inspired by the classic Boids algorithm by Craig Reynolds. But since I wrote this in a week when I was in the middle of nowhere in Andalucia, without any means of connecting to the Internet it only uses two behaviours, instead of Reynolds’ three, still the results look pretty convincing.

Reynolds original Boids

Still screenshots don’t do fi.sh much justice, I’ll try to make a movie of it later, but below are two frames, a few timeslices apart, of fi.sh in action, to get an idea of the behaviour:

                                                6  

                                               7


              8 
                                        3
                                                                1
                                             5                    
                                                                   4

                                     0                                




                                                      2
            9                                           



                                            1                


                                              2                 

                                          6      4                

                    9 8                                             


                            5                       

                        3                           

                         7                            


                       0                                 

Isn’t it great how you can make screenshots of these programs by just copy-pasting from your terminal to preformatted text in HTML? :P

Each ‘agent’ in fi.sh has two behaviours:

  • flock(): move towards the average direction of peers
  • avoid(): when peers are within a certain range, move away from them

Each of these behaviours only considers ‘peers’ when they are visible for the current ‘agent’, that is, they are in a 180 degrees field of vision in the agent’s current direction.

Both flock() and avoid() return a vector that represents the direction in which this behaviour wants to move. Fi.sh does not use true vector arithmetic to avoid the use of square roots in Bash’ integer-only arithmetic operators. Instead vectors are decomposed in separate x and y dimensions on wich all operations are done seperately. The vectors of flock() and avoid() are then weighted and added, avoid() is twice as ‘heavy’ as flock(). After adding the resulting vector is simplified to a unit step in both the x and y direction. In code, this looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
     
  # for each fish
        for ((fish = 0; fish < k_numfish; fish++))
        do
                # flocking behaviour
                flock_vector=$(flock ${fish})

                # avoidance behaviour
                avoid_vector=$(avoid ${fish})

                # flow vector (this should eventually be a food supply at some
                # position, implemented as another behaviour, like feed() or so.)
                flow_vector='0:0'
      
                # decompose vectors in x/y elements, integrate behaviours
                dx=$((${flow_vector/:*} + ${flock_vector/:*} + 2*${avoid_vector/:*}))
                dy=$((${flow_vector/*:} + ${flock_vector/*:} + 2*${avoid_vector/*:}))

                # redraw fish
              upd_pos ${fish}
  done

This is actually almost the exact core of fi.sh, pretty simple, eh?

Of course most of the complexity is in the flock() and avoid() functions, but in the end the whole algorithm is pretty simple. It never stops to amaze me how complexity arises from simple rules, and how you can capture quite fluid and natural behaviour in a few hunderd lines of Bash script!

Currently the fi.sh algorithm uses a torodial space: it wraps around the edges of the terminal. Especially on larger screens it might be more appropiate to make the screen edges repel the Boids instead. This is something that still needs to be implemented. Also, the different behaviours share a lot of common code, this should of course move to separate functions.

The latest version of fi.sh is included and available for download below:

(fi.sh) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
#!/bin/bash

# fi.sh - boids-like schools of fish in bash
# Hessel Schut, hessel@isquared.nl, 2010-01-25

###############################################################################

# fi.sh Is a boids-like program for glass-tty's written in Bash.
# I've tried to do as much processing in Bash as possible, the only
# extrernal programs that are called are 'tput', 'stty' and 'dd', all for
# terminal i/o. 'tput' is only used to set up to fill some variables once,
# 'dd' is called every iteration of main() and this is ugly, I would love to 
# see a better way of reading characters from stdin asynchronously. 
# My squa.sh program uses the same hack. 
# There is a config option to turn off keyboard commands, on my system I notice
# little change in execution speed when this is disabled.

# Distances are not calculated as a vector length, but as seperate x- and y-
# distances to avoid calculating square roots: Bash only has integer arithmetic.
# Not using vector math is lazy, faster and totally inaccurate, but works fine.

# The strength of attraction in flocking behaviour should be proportional by
# the size of the observed (cluster of) boid(s). In the current implementation
# size does not matter.

# Instead of a torodial space (screen wraparound) fi.sh should also feature 
# hard screen edges that repulse the boids and a parameter to choose between 
# these two modes.

# Boids only look in the direction of flight for both flocking and avoidance, 
# but the code for this should be moved to a seperate function handling all 
# 'visual' observations. Something like look() or so. Right now both flock() 
# and avoid() share a lot of code, which is hard to maintain and ugly.

# P A R A M E T E R S #########################################################

  k_numfish=10             # number of fish in simulation

  k_min_dist=2         # minimal separation between fish

  k_draw_trails=0          # leave trails

  k_draw_fishid=1          # draw fish as instance number

  k_fish_char="o"            # character to draw when not using
                  # fish instance number

  k_term_cleanup=1     # sanitize terminal on exit (disable to 
                  # keep standard-error barf)

  k_term_control=1     # use keyboard control commands

  k_reload_on_change=1     # reload on changes in population size

  k_record_fishfile=0      # keep track of all fish movements in
                  # ~/fishfile

###############################################################################

# terminal info
term_cols=$(tput cols)
term_rows=$(tput lines)

# terminal control
term_clear=$(tput clear)
term_bold=$(tput smso)
term_nobold=$(tput rmso)
term_cursor=$(tput cnorm)
term_nocursor=$(tput civis)

# keys
key_uparrow=$'\x1b[A'
key_downarrow=$'\x1b[B'
key_escape=$'\x1b'

# global variables (properties of fish instances)
declare -a fish_xpos[${k_numfish}]
declare -a fish_ypos[${k_numfish}]
declare -a fish_dx[${k_numfish}]
declare -a fish_dy[${k_numfish}]

((k_term_cleanup)) && trap cleanup EXIT TERM INT
cleanup() {
  # sanitize terminal settings
        echo ${term_nobold}${term_cursor}${term_clear}
  stty sane

        exit
}

abs() {
  # abs(value)
  value=${1}
  ((value < 0)) && value=$((-value))

  echo ${value}
}

wrap() {
  # wrap(value limit)
  value=${1}; limit=${2}

  if ((value > limit))
  then
      echo $((value - limit))
  elif ((value < 0))
  then
      echo $((limit - value))
  else
      echo ${value}
  fi
}

goto_xy() {
  # gotoxy(x y)
  # position cursor at row y, col x
  cursx=${1} cursy=${2}

  # bound coordinates
  ((cursx < 0)) && cursx=0
  ((cursx > term_cols)) && cursx=${term_cols}
  ((cursy < 0)) && cursy=0
  ((cursy > term_cols)) && cursy=${term_rows}

  # tput cup ${cursx} ${cursy}
  # fork()ing tput is too expensive, hardcoded cursor control:
  echo -n "[${cursy};${cursx}H"
}

init() {
  # setup terminal
  echo ${term_nocursor}${term_clear}
  stty -echo -icanon time 0 min 0

  # create fish instances
  for ((fish=0; fish < k_numfish; fish++))
  do
      # random fish positions, prevent overlapping fish
      overlap=1
      while ((overlap == 1))
      do  
          fish_ypos[${fish}]=$((${RANDOM} % (term_rows - 2) + 1))
          fish_xpos[${fish}]=$((${RANDOM} % (term_cols - 2) + 1))

          # check for overlaps
          overlap=0
          for ((check=0; check < fish; check++))
          do 
              if (( ${fish_ypos[${fish}]} == ${fish_ypos[${check}]} ))
              then
                  if (( ${fish_xpos[${fish}]} == ${fish_xpos[${check}]} ))
                  then
                      overlap=1
                  fi
              fi
          done
      done
  done
}


upd_pos() {
  # upd_pos(fish)
  # update position of fish-n

  fish=${1}
  
  # fish strings
  ((k_draw_trails)) && nofishstr="." || nofishstr=" "
  # pad string when drawing fish instance numbers
  if ((k_draw_fishid))
  then
      for ((space=1; space <= ${#fish} - 1; space++))
      do
          nofishstr=${nofishstr}" "
      done
  fi

  fishstr=${term_bold}
  ((k_draw_fishid)) && fishstr=${fish} || fishstr=${k_fish_char}
  fishstr=${fishstr}${term_nobold}
  
  # goto fish position and clear fish, optionally leave a trail
  goto_xy ${fish_xpos[${fish}]} ${fish_ypos[${fish}]}
  echo -n "${nofishstr}"

  # update fish position
  fish_xpos[${fish}]=$(
      wrap $((${fish_xpos[${fish}]} + ${fish_dx[${fish}]})) \
          ${term_cols}
  )
  fish_ypos[${fish}]=$(
      wrap $((${fish_ypos[${fish}]} + ${fish_dy[${fish}]})) \
          ${term_rows}
  )

  # goto fish position and set fish
  goto_xy ${fish_xpos[${fish}]} ${fish_ypos[${fish}]}
  echo -n "${fishstr}"
}

flock() {
  # flock(fish)
  # move to greatest density of peers 
  # (well, this isn't doing exactly that...)

  my_i=${1}
  my_x=${fish_xpos[${my_i}]}
  my_y=${fish_ypos[${my_i}]}
  my_dx=${fish_dx[${my_i}]}
  my_dy=${fish_dy[${my_i}]}

  # for each peer
  for ((i = 0; i < k_numfish; i++))
  do
      # skip myself
                ((i == my_i)) && continue

      # get peer coordinates
      peer_x=${fish_xpos[${i}]}
      peer_y=${fish_ypos[${i}]}
  
      # look only in flight direction (field of vision)
      peer_vdx=$((peer_x - my_x))
      peer_vdy=$((peer_y - my_y))
      if   ((peer_vdx > 0 && my_dx > 0)) || ((peer_vdx < 0 &&  my_dx < 0)) || \
          ((peer_vdy > 0 && my_dy > 0)) || ((peer_vdy < 0 &&  my_dy < 0)) || \
          ((my_dx == 0 || my_dy == 0)) # this line is a bit of a hack, due to not 
                          # using true vector arithmetic
      then
              # handle screen wrap-around, wrap for peers on 'opposite' screen half
              peer_xdist=$(abs ${peer_dx})
              peer_ydist=$(abs ${peer_dy})
              # using wrap() is a bit cumbersome here, this works too:
              ((2 * peer_xdist > term_cols)) && peer_x=$((term_cols - peer_x))
              ((2 * peer_ydist > term_rows)) && peer_y=$((term_rows - peer_y))
      
              # sum 'weights' per dimension, attraction fades with distance:
              # greater distances have less effect (peer_vd's reused here, to
              # save a few cycles, not as readable as recalculating.)
              ((peer_x < my_x)) && xw=$((xw - term_cols/(my_x - peer_x)))
              ((peer_x > my_x)) && xw=$((xw + term_cols/peer_vdx))
              ((peer_y < my_y)) && yw=$((yw - term_rows/(my_y - peer_y)))
              ((peer_y > my_y)) && yw=$((yw + term_rows/peer_vdy))
          fi
  done
  
  # return attraction vector
  echo "${xw}:${yw}"
}

avoid() {
  # avoid(fish)
  # avoid collisions with other fish

        my_i=${1}
        my_x=${fish_xpos[${1}]}
        my_y=${fish_ypos[${1}]}

  xw=0; yw=0
  # for each peer
        for ((i = 0; i < k_numfish; i++))
  do
      # skip myself
      ((i == my_i)) && continue

                # get peer coordinates
                peer_x=${fish_xpos[${i}]}
                peer_y=${fish_ypos[${i}]}
  
      # calculate x/y-distances
      peer_xdist=$((peer_x - my_x))
      peer_ydist=$((peer_y - my_y))
      
      # look only in flight direction
      if   ((peer_xdist > 0 && my_dx > 0)) || ((peer_xdist < 0 &&  my_dx < 0)) || \
          ((peer_ydist > 0 && my_dy > 0)) || ((peer_ydist < 0 &&  my_dy < 0)) || \
          ((my_dx == 0 || my_dy==0)) # blah, see flock()...
      then
          # don't move in a direction when neighbours are too close
          # smaller distances have greater effect
          if (($(abs ${peer_xdist}) <= k_min_dist))
          then
              # subtract from xw: moves away from other fish
              ((! peer_xdist)) && peer_xdist=1 # safeguard against division by 0
              xw=$((xw - term_cols / peer_xdist))
          fi
  
          if (($(abs ${peer_ydist}) <= k_min_dist))
          then
              # subtract from yw: moves away from other fish
              ((! peer_ydist)) && peer_ydist=1 # safeguard against division by 0
              yw=$((yw - term_rows / peer_ydist))
          fi
      fi
  done

  # return avoidance vector
  echo "${xw}:${yw}"
}

record() {
  for ((i=0; i < k_numfish; i++))
  do
      echo -n "(${fish_xpos[${i}]},${fish_ypos[${i}]}) "
  done
  echo
}

# initialize
init

# main loop
while (( 1 ))
do
  if ((k_term_control))
  then
      key=$(dd bs=3 count=1 2>/dev/null)
      case "${key}" in
          ${key_uparrow}|+)
              # increment number of fish
              ((k_numfish++))
              ((k_reload_on_change)) && init
          ;;
  
          ${key_downarrow}|-)    
              # decrement number of fish
              ((k_numfish--))
              ((k_reload_on_change)) && init
          ;;
  
          r)
              # reinitialize
              init
          ;;

          s)   # stop terminal control (no restart possible, yet)
              # not forking dd doesn't seem to speedup much, though
              k_term_control=0
          ;;
  
          t)
              # toggle drawing of trails
              k_draw_trails=$((!k_draw_trails))
          ;;

          w)
              # start recording fishfile
              k_record_fishfile=1
          ;;

          W)
              # stop recording fishfile
              k_record_fishfile=0
          ;;
  
          ${key_escape}|q)
              # quit
              cleanup
              exit
          ;;
      esac
  fi

  # for each fish
  for ((fish = 0; fish < k_numfish; fish++))
  do
      # flocking behaviour
      flock_vector=$(flock ${fish})

      # avoidance behaviour
      avoid_vector=$(avoid ${fish})

      # flow vector (this should eventually be a food supply at some
      # position, implemented as another behaviour, like feed() or so.)
      flow_vector='0:0'
      
      # decompose vectors in x/y elements, integrate behaviours
      dx=$((${flow_vector/:*} + ${flock_vector/:*} + 2*${avoid_vector/:*}))
      dy=$((${flow_vector/*:} + ${flock_vector/*:} + 2*${avoid_vector/*:}))
      
      # determine discrete deltas based upon element's sign
      # x
      if ((dx < 0))
      then
          fish_dx[${fish}]=-1
      elif ((dx > 0))
      then
          fish_dx[${fish}]=1
      else
          fish_dx[${fish}]=0
      fi
      
      # y
      if ((dy < 0))
      then
          fish_dy[${fish}]=-1
      elif ((dy > 0))
      then
          fish_dy[${fish}]=1
      else
          fish_dy[${fish}]=0
      fi
  
      # redraw fish
      upd_pos ${fish}

  done
  # optionally keep track of fish movement
  ((k_record_fishfile)) && record >> ~/fishfile
done

Comments