Thursday, February 12, 2009

Introducing Frock, a flocking chicken simulation written in Lua with Löve

I recently learned about LÖVE, a 2D game framework for Lua off HN. It looked simple enough, and when I ran the particle system demo and it was pretty fast. It seemed faster than what Ruby Shoes would be able to do. I got rather excited because
  1. I've always wanted to make my own game. A lawnmowing game comes to mind.
  2. I wanted to see if I could create a large flocking simulation
Also, I've decided a while back to start writing more great projects and do less reading of tech news garbage. While #1 would be on the backburner for the time being, #2 was fairly easy to do in a couple of hours. (I think about a weekend's worth of hours total tweaking things).

I've been fascinated with decentralized systems since right after college--one of them being flocks. But how do they work? For a long time, ornithologist (bird scientists) had no clue how birds flocked. Birds seem to be able to move in unison, as a super-organism, swooping, expanding/contracting, splitting. When you see massive waves of these things (these are starlings), it's something to behold. Who is the leader? How do they coordinate these flocks?



We still don't exactly know, since we don't yet have the capabilities to tap into a bird's decision making mechanism in real time. However, in the 1990's, Craig Reynolds demonstrated that you can get very convincing flock-like behavior generated procedurally, using three simple rules. And it ends up that you don't need a leader to get flocking behavior. All interactions can be local, and each flock member (or boid, as he called it), just needed to follow three simple rules:
  1. Attraction: Move towards the perceived center of the flock according to your neighbors
  2. Repulsion: Avoid colliding with your neighbors
  3. Alignment: Move in the same direction and speed (velocity) as your neighbors.
Add up all these vectors together and you get a resultant velocity vector. Different amounts of the three influences leads to different looking types of flocks. As an aside, particle swarm optimization works on the same sort of principles.

So here it is. Introducing Frock, a flocking simulator in Lua Love.


I release it now, because while it's primitive, it works (release early, release often!). The screenshot doesn't really show it well, they fly about in a flock, hunting for plants to eat. It's rather mesmerizing, and I find I just stare at it, the same way I stare at fish tanks.

It was originally a port of the Ruby Shoe's hungry boids, but I used flying chickens lifted from Harvest Moon instead. I originally had cows flying about, but without flapping, it just wasn't the same. I also made the repulsion vector increase as a function of decreasing distance. Otherwise, the chickens didn't mind being right on top of each other if they were on the inside of the flock.

My immediate goal is to make it support more chickens, so I can get a whole swarm of them. Right now, I'm using an inefficient algorithm to calculate which chickens are neighbors (basically n^2 comparisons). So if any of you have good culling techniques applicable here, I'd love to hear it. I'm currently looking at R-trees.

There are different possibilities as to where it could go. I think while lots of people have written boid simulations, they haven't taken it much further than that. While I've seen ones with predators, I haven't seen anything where people try to evolve the flock parameters, or try to scale it up to a large number of chickens. One can also do experiments on whether different flock parameters have different coverage of the field, or which set of parameters minimizes the time a plant is alive.

If at the basic, it becomes a framework for me to write 'me and my neighbors' decentralized algorithms, that'd be useful too. And since Lua is suppose to be embeddable into other languages, that makes it an even more exciting possibility. Later on, I'll write a little something about Lua.

Well, if you decide to try it out yourself, get to the Frock github repo, and follow the readme. Patches are welcome, but note I haven't decided on a license yet--but it will be open source. If you have questions, feel free to contact me or comment. Have fun!

9 comments:

  1. Anonymous11:31 AM

    If you wanted to bite off something complicated for your neighbor comparison ... :)

    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8944

    ReplyDelete
  2. Hi there. Great Port! Flying chickens!

    I especially like your changes to the avoidance vector calculation. Keep up the good work.

    ReplyDelete
  3. Anonymous5:16 PM

    cool.
    instead of r-tree, you could use the simpler quad-tree, there's a nice python/pygame implementation here that i imagine wouldn't be too difficult to translate to lua:
    http://www.pygame.org/wiki/QuadTree

    ReplyDelete
  4. great idea and, as a brazilian, i'm proud to see u using lua!

    ReplyDelete
  5. Using the voronoi diagram as a mechanism to maintain the area of interest for a sim works very well. Here's the videos of my predator/prey simulations using the technique.

    ReplyDelete
  6. Anonymous12:30 PM

    A minor point - chickens don't flock. Ducks do very nicely, but not chickens. There's a project from 1998 that showed robot gathering ducks, designed in a simulator. The video on the page shows the ducks flocking.

    http://www.cs.sfu.ca/~vaughan/projects/RSP.html

    ReplyDelete
  7. Did you end up optimizing this at all in the end? I'm working on a similar project, currently using Processing but it's not totally adapted to making games and was thinking of switching to Löve... problem is I'm hoping for 400ish boids on an aging Pentium M (about as powerful as a current Atom n270) and i had doubts that it would run in Lua seeing how it struggled in Java.

    ReplyDelete
  8. No I hadn't finished doing that. I know it's been a while, but I've started working on other things. However, this is something that I always want to come back to.

    Love is pretty easy to use, and Lua is quick to pick up (with some exception to its barebones object model).

    I think in this case algorithmic optimization really helps out in perceived speed. In games especially, every corner you can cut and still have perceived realism is enough.

    Also try reducing the resolution your boids "think" at. You can have them do that every five time steps. If you check out Craig Reynold's work, he talks about how to optimize boid sims in his papers.

    ReplyDelete
  9. Cool post - and interesting video - those noises at 4:12 though are a little silly… I'm curious to see the flock (or, perhaps, frock) that you made…

    ReplyDelete