Desktop Stampede

Khairi Reda
mreda2 at uic dot edu

Screenshots

Download application

To run the application, you need Electro (revision 1042+). Change your working directory to 'src' and type 'electro main.lua'

Documentation

  1. Overview and Story
  2. Characters and Models
  3. Implementation
  4. Interaction
  5. Eye Candy

I. Overview and Story

If paper clips could walk and run where would the go, and what would they do? Well, paper clips are social creatures by nature, they don't like to be separated from each others. Although a single paper clip doesn't show a high level of intelligence, it turns out that a herd of paper clips interacting together exhibit a highly coordinated behavior, much like a colony of aunt (ok, maybe to a lesser extent).

Imagine that a mug containing an infinite number of paper clips is tipped over letting loose of those paper clips. What will happen? Run the program and see for yourself :)

Storyboards

Here are some storyboards that I did at the beginning. The final application ended up similar to the initial concept, except for the destination of the clips which finally became a hole in the desk. I also added some eye candies such explosions and paper clips being thrown in the air as a result of colliding with rockets.

 

II. Characters and Models

There are two types of paper clips: walking paper clips, and rocket riding paper clips. Naturally, the paper clips with rockets move faster, but they have less maneuverability than walking paper clips. In addition to paper clips, there are magnets, which try to catch the paper clips employing their magnetism. Finally, there are a bunch of obstacles on the desk: a paper puncher, a small globe, a pencil, and a clock.

Walking paper clip
Rocket riding paper clip
Evil magnet
Paper puncher
Clock
Globe
Pencil
Source mug: paper clips start here

III. Implementation

Choice of graphics engine

The graphics engine I've used to implement this application is Electro. The reasons are:


Smooth turning

I wanted to address the issue of smooth turning from the beginning. Therefore, I made a simple restriction and made the design around this restriction. The restriction was: a boid can only move forward and in one direction, the direction of its positive Z axis. If the boid wants to turn, it must do so by aligning its Z axis with the desired direction by rotating itself about Y. Moreover, the boid is limited to a certain rotational speed (angular speed). By interpolating the rotation we ensure it looks smooth and realistic.

Boid rules

The rules of the Boid model are evaluated independently resulting in one normalized vector for each rule. The vectors are then weighed and blended together resulting in one final desired vector which the boid will align its Z axis with. The rules are:

  1. Move to target (the hole)
  2. Match heading: match the boid's heading with its neighboring boids
  3. Collision avoidance: avoid colliding with neighboring boids, obstacles, and magnets
  4. Edge deflection: avoid the edge of the desk

Rule 1: Move to target

This rule simply returns the displacement vector between the target's position and the boid's current position.

Rule 2: Match heading

This rule averages the headings (local Z axis) of neighboring boids. This average is returned

Rule 3: Collision avoidance

To avoid an obstacle, we calculate the distance between the boid's position and and center of the obstacle. If the distance is below a certain threshold and the angle between boid's heading (Z axis) and displacement vector is within the field of view (that is, the boid will crash into the obstacle if it kept going in the current direction), the inverse of the displacement vector is maintained. An urgency factor (between 0 and 1) is calculated based on the distance to the obstacle (the closer the boid, the higher the urgency).

The inverse of displacement vectors for each obstacle are weighed with their urgencies and averaged. The resulting vector is returned along with the maximum urgency which will be used later when blending the results of the 4 rules.

Collision is avoided with neighboring boids using exactly the same method, though the avoidance neighborhood for boid avoidance is smaller than that of obstacles. Also escaping from magnets is implemented in a similar fashion except that the field of view parameter in this case is set to 360 degrees so that the boid is constantly running away from the magnet regardless of its heading (if it's close to the magnet)

Rule 4: Edge deflection

This rule returns a vector the pushes the boid towards the desk area if it is close to the edge. An urgency factor is also calculated and returned.

Vector blending

Reynolds indicated in his paper that the integration module responsible for combining the results of individual rules must provide some intelligence so that it performs arbitration between the (sometimes) conflicting rules. A weighted average might for example simply cancel collision avoidance desire resulting in the boid crashing.

Our implementation uses the collision avoidance urgencies to make some arbitration so that collision avoidance has the highest priority. The idea is that as the collision avoidance urgency growing, it starts taking more of the share of Rules 1 (target) and 2 (flocking) in the final desired vector. If the urgency reaches a maximum of 1, collision avoidance completely takes control over the boid to avoid crashing.

The Flocking Weight parameter (0 to 1) specifies how much the boids should be interested in flocking together versus reaching the their target point.

Magnet and magnetic attraction

Magnets are animated using a similar set of boid rules and integration module. However, as opposed to a static target, magnets look for the closest paper clip as their target.

Magnets also attract paper clips that are close to them. The attraction force increases linearly as the distance between the paper clip and the magnet decrease. This attraction is implemented by moving the paper clip in the direction of the displacement vector rather than using a boid rule because it should not affect the heading of the paper clip directly.

IV. Interaction

Scene

The scene can be manipulated as follows:

If you get lost, press the H button on your keyboard (for Home) to reset the view.

Real-time parameters adjustment

The parameters that control the speed of the boids, the avoidance and flocking neighborhoods, Field of View, and the Flocking Weight can be adjusted in real-time using the built-in GUI. Simply move the mouse pointer to the bottom edge of the application's window to display the control panel. Adjust the parameters by dragging and dropping the appropriate slider.

Here's a brief description of each slider from left to right and from top to bottom:

To facilitate debugging, the desired direction vector of each boid can be visualized as a small arrow by hitting the D button (for debug).

V. Eye Candy

Some eye and ear candies include:


Copyright (C) 2008 Khairi Reda <mreda2 at uic dot edu>. Last update: March 15, 2008