PSP: Flocking Boids

For our “Console Development” module in the second year of my university degree, we had to produce a tech-demo for the Sony PlayStation Portable using industry-standard development kits.

I wrote a “flocking” algorithm in C, optimised to use the PSP’s VFPU (Vector Floating Point Unit) for increased performance with inline MIPS Assembly. The boids have a simple 3D wireframe mesh, but their movement is limited to a 2D plane. My coursework was awarded with a “B-” grade.

PSP Boids

The algorithm is based on Craig Reynolds‘ steering behaviours, a widely published article from GDC 1999. Here’s a video of it in action, recorded directly from the VGA output of the development kit:

Read on for the details of this project.

Project Details

The red boid provides the debug information on the left, in terms of position on screen and behaviour outputs. The behaviours are known as “Separation”, “Cohesion” and “Alignment”, respectively.

Separation makes the each boid maintain a small distance from those surrounding it so that they avoid bumping into each other; Cohesion makes the boids head toward the average position of those nearby, helping them stay clumped together; and Alignment makes each boid head in approximately the same direction as other nearby boids. These three behaviours combine to produce a “desired velocity” for the boid, which is then added to its position to create the algorithmic movement that you see.

More realistic movement can be achieved by limiting the boid’s ability to react to its desired velocity, versus its actual velocity. For example, if the boid were a car, its turning circle would get wider the faster it went, and it would also take longer to accelerate or brake.

About these ads

3 thoughts on “PSP: Flocking Boids

  1. Nice project. Regarding performance issues: once you hit ~100 boids, the O(n^2) effects start to dominate. If you revisit this kind of simulation, look at improving algorithms and data structures, particularly spatial hashing. See the boids plug-in of OpenSteer (http://opensteer.sourceforge.net/ specifically: http://opensteer.svn.sourceforge.net/viewvc/opensteer/trunk/plugins/Boids.cpp?revision=181&view=markup) or this PS3 implementation: http://www.research.scea.com/pscrowd/

    Cheers,
    Craig

    • Thanks very much for taking the time to look at my project! I found your work fascinating. Had this module run for longer, it would have been nice to implement spatial partitioning to squeeze more performance out of the PSP, and also to add some more of the behaviours described in your articles.

  2. Pingback: Introduction | Online Portfolio

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s