Sunday, May 18, 2008

XNA, Boids and Buffalo! Oh My!

So I've spent my time since my last post basically re-writing the entire Boids project. I've thrown out the GDI UI and have replaced it with an XNA based one. I also rewrote my Boid type to be a class which inherits from the Body type in the Farseer 2D physics engine, making the simulation much more realistic. I’ve now got mass, rotation, torque, collisions, drag and friction to play with.

I've also refined and rewritten most of my rules, fixing the stationary swarm problem, and have added more random noise making things much more interesting. Random Boids will peel off from the group, wander around and then later rejoin. Sometimes the herd separates into two or more sub-groups then later coalesces back into a single herd. There is definitely some additional tweaking of the rules to be done, but I’m definitely headed in the right direction.

Oh, and this is one of my favorite parts, I replaced the dots that represented the Boids in the old simulations with little buffalo which rotate to reflect the actual heading of the Boid. So I have a little herd of buffalo roaming around in my computer, for some reason that makes me very happy.

This being a learning exercise, I separated the F# rules and logic into multiple files so that I could play with modules and namespaces, and have now tackled almost every subject in the Expert F# book. I don’t quite live in F# yet, but I’m getting much faster and am programming with fewer mistakes which is a good sign.

Playing with XNA was also quite fun. I am by no means utilizing all of the functionality provided, but from the limited area that I have touched it appears that Microsoft did a pretty good job. I played with OpenGL a couple of years ago, creating a planetary body orbit/gravity simulation with my roommate, and I remember it being painful. With XNA this was definitely not the case, it was very simple to get something up and running quickly. I am by no means a Microsoft fan-boy but you have to give them credit, they do make nice development tools.

So where do I go next? I need to do some mundane things like tweak the existing rules, and port all of the XNA code from C# to F#. I also need to go through and clean up some of the code, I know I’m not doing several things very efficiently and as a result my laptop has trouble with 100 or more Boids. I also want to implement several more rules: herd leaders, predator/prey behavior, obstacle avoidance etc… I still want to rewrite the nearest neighbor search portion of the code, but that is slower going. One of the problems of being a college drop-out is that I never took discreet math or linear algebra, so understanding some of the algorithms takes a little bit more time than I anticipated. It’s not exactly hard, just requires more research on my part but it’s good for me. Also now that I’ve been reading computational geometry books I see solutions to problems that I encounter all the time, I just wasn’t aware of the body of work that existed. I don’t feel too guilty though, I don’t think any of these algorithms were taught at an undergraduate level anyways at the U of Arizona. Who knows, when I was there 2001-2004 the program was in a real state of decline and was rife with in-fighting and I was all too eager to leave.

FYI: The project has gotten too big to keep posting code in the blog, so I created a project on Google Code.

Print this post

3 comments:

Taumuon said...

Hi!

I've been playing with some boids recently in C# (see www.taumuon.co.uk/jabuka), but am interested in seeing how to go about it in F# (I'm interested in seeing if a functional programming style might make multithreading easier - by isolating out the program state).

In your example, your boid type holds its data (position and velocity), and all boids use the same boidList - this is pretty much how my C# example is structured? Do you know this would look in a more pure functional style? (where should the data/program state live?)

The boids_update() call with its async stuff looks interesting though! I'll have to get more into F#. Is there any chance you could zip up your google code and provide it for download on your google code site? (I still haven't gotten around to downloading a SVN client).

Thanks!
Gary

The Eclectic Engineer said...

I tagged the source in it's current state as 0.5.0 and created a zip file for you. The zip is available in the downloads section of the project, the direct link is: http://fsharp-boids.googlecode.com/files/fsharp-boids-0.5.0.zip

The closest example to a purely function style would be in my post titled "Boids: Revision Two" in May of this year. In that example I use only immutable data structures and the use of asynchronous work flows could be taken even further by by executing each rule independently. I broke the purely functional style when I started using the physics engine and XNA which required an imperative programming style in order to avoid a huge performance penalty.

Taumuon said...

Thanks for posting the code!

It's interesting what you're saying - by making things immutable, we're relying on having to create more objects. I knew that'd be the case in C#, but that's also true in F#? It hasn't got any magic to get around this?

I'll have to get my hands dirty on F# I suppose before I can see what the advantages are.

Thanks!!!