A friend of mine was in town this week, and haven't had much spare time to play with my side projects. When I finally got down to it I was able to redo my boids simulation to use operator overloading, boundary rules, and improved some of the rendering. I based my implementation off of a couple of different sources: a pseudo-code explanation of the original boids paper, a Python implementation, and this Java implementation. There is one remaining problem that I have yet to figure out. I originally used the rules laid out in the Python implementation, but the animation was very jerky when rule 3 took affect, and once the dots swarmed together they just sit their stationary. Finding no difference between his implementation and my own I started looking around for other examples that might give me an insight. That is when I found the previously mentioned Java implementation which resulted in a much more smooth trajectory. Unfortunately it still did not fix the problem where after swarming together the boids don't go anywhere. I'm going to continue to work on it but wanted to post my results thus far.
open System;;
open System.Windows.Forms;;
open Microsoft.FSharp.Collections;;
let BOID_COUNT = 40;;
let HEIGHT = 700.;;
let WIDTH = 1000.;;
let WALL = 50.;;
let WALL_FORCE = 30.;;
let MAX_VEL = 800.;;
let R1_CONST = 0.2;;
let R2_CONST = 0.2;;
let R2_RANGE = 100.;;
let R3_CONST = 0.2;;
let FPS = 24;;
let RECT_HW = 3;;
type vector = {
x : double;
y : double;
} with
member v.mag() =
(v.x ** 2.0) + (v.y ** 2.0) |> Math.Sqrt;
static member ( + )(a:vector, b:vector) =
{x = a.x + b.x;
y = a.y + b.y};
static member ( - )(a:vector, b:vector) =
{x = a.x - b.x;
y = a.y - b.y};
[]
static member ( * ) (a:vector, b:int) =
let bd = Convert.ToDouble(b) in
{x = a.x * bd;
y = a.y * bd};
[]
static member ( * ) (a:vector, b:double) =
{x = a.x * b;
y = a.y * b};
[]
static member ( ** ) (a:vector, b:int) =
let bd = Convert.ToDouble(b) in
{x = a.x ** bd;
y = a.y ** bd};
[]
static member ( ** ) (a:vector, b:double) =
{x = a.x ** b;
y = a.y ** b};
[]
static member ( / ) (a:vector, b:int) =
let bd = Convert.ToDouble(b) in
{x = a.x / bd;
y = a.y / bd};
[]
static member ( / ) (a:vector, b:double) =
{x = a.x / b;
y = a.y / b};
static member ( > ) (a:vector, b:double) =
a.mag() > b;
static member ( < ) (a:vector, b:double) =
a.mag() < b;
end;;
type boid = {
pos : vector;
vel : vector;
} with
static member ( + )(a:boid, b:boid) =
{pos = a.pos + b.pos;
vel = a.vel + b.vel};
static member ( - )(a:boid, b:boid) =
{pos = a.pos - b.pos;
vel = a.vel - b.vel};
member b.distance b2 =
Math.Sqrt(Math.Abs(((b.pos.x - b2.pos.x) ** 2.0) - ((b.pos.y - b2.pos.y) ** 2.0)));
member b.update_pos() =
{b with
pos = b.pos + b.vel};
member b.neighbors(r, bl) =
[for n in bl ->
(b.distance(n), n)] |>
List.filter(fun (d:double, _) -> d < r) |>
List.sort(fun (d1:double, _) (d2:double, _) -> d1.CompareTo(d2)) |>
List.tl |>
List.unzip;
end;;
let rand = new Random();;
let rand_double(max:double) =
Convert.ToDouble(rand.Next(Convert.ToInt32(max) - 1)) + rand.NextDouble();;
let vector_init =
{x = 0.;
y = 0.};;
let boid_init =
{pos = vector_init;
vel = vector_init};;
let boid_sum_list bl =
List.fold_left(+) boid_init bl;;
let boid_adjust_v_to_fps b =
{ b with
vel = b.vel / (Convert.ToDouble(FPS))};;
let boid_limit_vel b =
let v = b.vel.mag() in
match v with
| _ when v > MAX_VEL ->
let vl = v / MAX_VEL in
{ b with
vel = b.vel / vl}
| _ -> b;;
let boid_check_x_bounds b =
match b with
| _ when b.pos.x < WALL ->
{b with
vel = {b.vel with
x = b.vel.x + WALL_FORCE}};
| _ when b.pos.x > (WIDTH - WALL) ->
{b with
vel = {b.vel with
x = b.vel.x - WALL_FORCE}};
| _ -> b;;
let boid_check_y_bounds b =
match b with
| _ when b.pos.y < WALL ->
{b with
vel = {b.vel with
y = b.vel.y + WALL_FORCE}};
| _ when b.pos.y > (WIDTH - WALL) ->
{b with
vel = {b.vel with
y = b.vel.y - WALL_FORCE}};
| _ -> b;;
let boid_rule1 b_sum count =
fun (b) ->
{b with
vel = b.vel + ((((b_sum.pos - b.pos) * (1. / (count - 1.))) - b.pos) * R1_CONST) };;
let boid_rule2 bl count =
fun (b:boid) ->
let (_, nbl) = b.neighbors(R2_RANGE, bl) in
let r2b = List.fold_left(fun b1 b2 -> b1 - (b2 - b)) boid_init nbl in
{ b with
vel = b.vel + ((r2b.pos * (1. / (count - 1.))) * R2_CONST) };;
let boid_rule3 b_sum count =
fun b ->
{b with
vel = b.vel + ((((b_sum.vel - b.vel) * (1. / (count - 1.))) - b.vel) * R3_CONST) };;
let boid_apply_rules b bl b_sum count =
b |> boid_check_y_bounds |> boid_check_x_bounds |> boid_rule1 b_sum count |> boid_rule2 bl count |>
boid_rule3 b_sum count |> boid_limit_vel |> boid_adjust_v_to_fps |> fun b -> b.update_pos();;
let get_wall() =
let height = Convert.ToInt32(HEIGHT) in
let width = Convert.ToInt32(WIDTH) in
let wl = Convert.ToInt32(WALL) in
[|new Drawing.Point(wl, wl);
new Drawing.Point(wl, height - wl);
new Drawing.Point(width - wl, height - wl);
new Drawing.Point(width - wl, wl)
|];;
type BoidControl = class
inherit UserControl as base
val mutable boidList:(boid list);
val brap:(Drawing.Point array);
val count:double;
val timer:Timer;
new(bl:(boid list)) as this = {
boidList = bl;
count = bl |> List.length |> Convert.ToDouble;
timer = new Timer();
brap = get_wall();
} then this.init();
member this.init() =
let height = Convert.ToInt32(HEIGHT) in
let width = Convert.ToInt32(WIDTH) in
let size = new Drawing.Size(width, height) in
base.Width <- width;
base.Height <- height;
base.MinimumSize <- size;
base.MaximumSize <- size;
base.BackColor <- Drawing.Color.White;
base.SetStyle (ControlStyles.UserPaint, true);
base.SetStyle (ControlStyles.DoubleBuffer, true);
base.SetStyle (ControlStyles.AllPaintingInWmPaint, true);
this.timer.Interval <- FPS;
this.timer.Tick.Add(fun _ ->
this.tick(););
this.timer.Start();
member this.boids_update() =
let b_sum = boid_sum_list this.boidList in
let al = [for b in this.boidList -> async { return boid_apply_rules b this.boidList b_sum this.count }] |> Async.Parallel in
this.boidList <- (Async.Run(al) |> Array.to_list);
();
override this.OnPaint e =
let g = e.Graphics in
List.iter(fun b ->
let x = Convert.ToInt32(b.pos.x) in
let y = Convert.ToInt32(b.pos.y) in
let bp1 = new Drawing.Point(x - RECT_HW, y - RECT_HW) in
let bp2 = new Drawing.Point(x - RECT_HW, y + RECT_HW) in
let bp3 = new Drawing.Point(x + RECT_HW, y + RECT_HW) in
let bp4 = new Drawing.Point(x + RECT_HW, y - RECT_HW) in
g.FillPolygon(Drawing.Brushes.Red, [|bp1; bp2; bp3; bp4|]);) this.boidList;
g.DrawPolygon(Drawing.Pens.Blue, this.brap);
member this.tick() =
this.boids_update();
this.Invalidate();
end;;
[]
do
let height = Convert.ToInt32(HEIGHT) in
let width = Convert.ToInt32(WIDTH) in
let size = new Drawing.Size(width, height) in
let bl = [for x in 1..BOID_COUNT -> {pos = {x = 50. + rand_double(WIDTH - 50.);
y = 50. + rand_double(HEIGHT - 50.)};
vel = vector_init }] in
let mw = new Form() in
let bc = new BoidControl(bl) in
mw.Controls.Add(bc);
mw.ClientSize <- size;
mw.MaximumSize <- mw.Size;
mw.MinimumSize <- mw.Size;
mw.Text <- "Boids";
mw.Show();
Application.Run(mw);;