Flocking by Ian Rae & Irene Shei

NOTE: If the game doesn't run and you have Firefox 3.6 and Firebug 1.5, you're the victim of a strange bug. See the “known issues” section for details.

Main Control Box

Framerate: ??

Ship
All Boids
Neutral Boids
Homing Boids

Welcome to our Flocking demo project!

Instructions

Use the W, A, S, and D keys to maneuver your ship and spacebar to fire your gun. Avoid colliding with the boids and watch out—red boids will try to ram your ship!

Destroy all of the boids to win.

Known Issues

The R-Tree library doesn't play well with Firebug 1.5 and Firefox 3.6. If you get a JavaScript error like “b is undefined,” you've encountered the problem. Everything runs fine if you have Firebug enabled—i.e. the bug icon in the lower right is “lit up”—when you reload the page (don't ask me why) or if you install Venkman, the official Mozilla JavaScript debugger. Or if you don't have Firebug installed, of course. It still occurs even with the latest (alpha) version of Firebug, but much less frequently. We haven't worried too much about this since it's a very platform-specific problem.

Text rendering in Google Chrome is a little funny (it's too dark), but it's still legible.

JQuery's attempt at preventing the default event action doesn't work in Opera, so pressing the spacebar to fire will also move the page down.

Disabling and then re-enabling the R-tree might not be 100% reliable, since we didn't really do much work to support that. It's best to reload the page after disabling the R-tree if you want to turn it back on.

Documentation

We created a simple game using basic flocking techniques.

White boids follow a rather straightforward flocking model (cohesion, alignment, and separation), with the extension that they place a large weight on following “homing boids” and on avoiding collisions with the player's ship.

The red “homing boids” attempt to actively ram the player's ship. They incorporation cohesion and separation (but not alignment, as they're the “leaders”) when the ship is not in their sight range—however, when the ship is visible, that's essentially their only concern.

Location information for all the boids and moving objects (ship, missiles, etc.) is stored within an R-tree for fast access. It works pretty well, even though the R-tree is recreated on every location update. This is used both for the flocking inputs and for collision detection. It also improves the frame rate substantially (on the order of 2-3x) when lots of boids are on screen. Enabling the “R-tree debug” option will show the sight range for each boid, their bounding box, and the number of boids they can “see” (including themselves).

Location updates for all objects on the screen work off of a fixed tick rate that's independent of framerate. It's currently set to 100 Hz, and it interpolates between ticks to avoid temporal aliasing. We're not sure if the interpolation really helps.

The basic flocking code is based on the flocking demo from the ProcessingJS website, but it's been tuned a bit for speed. We focused on reducing computation and function calls within the draw loop as much as possible, and it seems to have improved things.

Game Aspect

While the project is already operating as a simple game that involves avoiding the homing boids and eliminating all the boids on screen by firing, there are definitely some things that we wish we had more time to implement.

Some of these include: sound effects and music, multiple ships and/or multiple ship types (possibly allowing the player to buy upgrades), allowing the homing boids to convert the regular boids, more complex artwork, different levels of play, and a more complex goal structure (e.g. avoid killing a color of boids, reach a certain point score).

Performance Analysis

Setup

The machine used in all tests was a Mac Pro 2.26GHz 2x Quad-Core Intel Xeon with 6GB of DDR3 RAM.

Firefox

In Firefox 3.5.7:

Performance starts to suffer at around 50 boids as the frame rate drops to an average below 20 and movement becomes slightly jerky. Between 100–200 boids play becomes a slide show and 500 boids completely locks the browser up. There are some errors when the program reaches around 150 boids, where input events from the keyboard are lost, resulting in errors where the game can't be restarted or it becomes very hard to adjust the program on the control box.

Safari

In Safari 4.0.4:

Performance starts to suffer at around 150 boids as the frame rate drops to around 20. Safari seems to be scale up much better and its keys are still responsive at 800 boids.

Google Chrome

In Google Chrome 4.0.249.49:

Maximum fps seems much much higher on Google Chrome but as boid numbers increase it doesn't scale up as smoothly as in Safari. This could be due to a number of factors, including hardware compatibility.

Opera

In Opera:

Performance seems to scale a bit better than in other browsers and seems to drop at set points rather than linearly as boids increase.

Other

Performance varies widely depending on machine but it was very interesting to see the differences between how browsers limit performance and the grace with which they scale up.

Profiling suggests that, in browsers other than Firefox, drawing takes the most time. A close second is the flocking calculation (computing distances and averages, etc.), and in third are R-Tree lookups. We can't do much to speed up drawing since we rely on ProcessingJS.

However, it seems like it would be possible to speed things up perhaps by approximating the distances (pre-computing a lookup table and then rounding distances to the nearest value in the table).

Also, there's probably a better data structure than an R-Tree for handling boid locations and collisions. The performance is pretty respectable as it is, but R-Trees aren't really designed to be destroyed and recreated on every frame like we're doing.

Finally, we can always cheat. When dealing with more than, say, 100 or so boids, the playfield is small enough that we could get away with not drawing all of them. We'd still have to maintain their position (so we could put them in as boids are destroyed), but we could save the graphics time.

Experimentation Analysis

We did a lot of experimenting with the UI, first attempting to implement the control box in ProcessingJS and eventually moving to use of jQuery and passing values between the HTML page and the program. There was also some experimentation with taking inputs using the ProcessingJS keyCode and key functions, but we ended up switching off of this because the ProcessingJS code appeared to be buggy (failing to fire all events when two keys are released simultaneously). A majority of our issues involved attempting to debug the code and trying to track down where the code translation of ProcessingJS didn't work very nicely.

For starting values in the control box we first tried to establish a baseline of the ship not having enough speed to escape a homing boid on a straightaway but having a better turn radius to evade collisions and move out of their sight range (so a “skilled” player could make a boid lose track of him).

We also wanted the homing boids to have a slightly greater speed and more maneuverability than the regular boids to provide more of a challenge to the player in avoiding them. Following the principles listed, we then set the values through trial and error, experimenting to try to find a happy medium that wasn't impossible or too easy for a player. The default value is perhaps a bit too easy, but it's a good introduction for most players.

Attributions

JQuery and ProcessingJS, by John Resig.

R-Tree library by Jon-Carlos Rivera.

The class ProcessingJS tutorial and zipfile.

The ProcessingJS flocking demo.

Controls

W
accelerate
A
rotate left
S
decelerate
D
rotate right
spacebar
fire gun