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
- I’ve always wanted to make my own game. A lawnmowing game comes to mind.
- 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:
- Attraction: Move towards the perceived center of the flock according to your neighbors
- Repulsion: Avoid colliding with your neighbors
- 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!