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!

Advertisements

Segmentation of social news sites

Giles Bowkett: Summon Monsters? Open The Door? Heal? Or Die?

I have to admit, I almost stopped reading after the first couple paragraphs justifying himself being jerk-ish, but he does have a healthy dose of good points towards the middle.

The underlying assumption of ‘wisdom of the crowds’ is that people make independent decisions, and they have the same amount of time to do it. Neither are true in social news sites. The former being untrue because you can up vote stories that are already on the front page. That just makes it into a positive feedback system that blows up and amplifies small signals. It’s ok when the community is small, but as it gets larger, the more likely that noise will make it.

The second point I didn’t think about until Giles pointed out explicitly–that since votes come for free, that people that spend their time on the sites are the ones that influence it the most.

Combine the two effects, you have a recipe for amplification of noise. The problem is, you need the amplification mechanisms like up voting on the front page in place when the site is small to grow it, and then when it reaches a certain size, the mechanics of social sites need to change (to what, none of us exactly figured it out yet) to protect the users from themselves.

I’m venturing to guess personalization and fuzzy segmentation to be one solution. As Paul Buchheit mentioned earlier about how twitterers hardly get any spam, it’s because if anyone’s saying stuff you don’t want to hear, you can just unfollow them. Twitter works in this regard because there is a built-in small world network with a relatively low transmission rate between nodes (as opposed to facebook which has a small world network, but high transmission rates of information between nodes…which results in lots of unwanted invitations to bite zombies and vampires). Social sites like Digg, reddit, and hacker news, don’t really have a network. It’s just one single “place”, where what happens on it affects everyone, and small perturbations get amplified.

However, I don’t think such a strategy would work well in the beginning. The very thing that helps a small community in the beginning hurts a larger community, and the very thing that would protect a larger community from itself would stunt the growth of a new smaller one.

I think this would be an interesting topic and ripe for research. It actually reminds me of ant colonies, where younger ant colonies will act like teenagers, taking more risks, focus on growing, and experimenting. Older ant colonies are more about taking less risks, maintaining the brood, and surviving. There’s some sort of decentralized mechanism that kicks in for ant colonies to do that, or maybe once they reach a certain size. I think looking into the literature for that might yield some clues into how to design community sites so that they can grow in the beginning, and not implode when they get bigger.

Erlang Advocacy and the class of problems it solves

I spend more time than I should reading hacker.news. Granted, I sometimes feel like it’s the US Weekly or Maxim of the tech world, when stories like “5 ways you know you’re failing at your start up” and the general hubbub over Facebook back in June or the recent Microsoft and Yahoo buyout. However, the quality of the comments there is generally high, and on occasion, I’ll start replying to a comment, and before I know it, two hours have passed, and it’s better off as a blog post.

The challenge of the Erlang advocate is not to convince me, over and over, that Erlang wins its class; the challenge is to convince me that Erlang’s class of problem is so important to my life that I should study Erlang rather than vascular surgery, or television repair, or other obscure technical skills that I don’t know that much about.

The follow-up question then would be how many existing problems can be converted to the type that Erlang can solve well? And how many problems previously impractical are now practical to solve? So if it ends up to be a bigger class than you thought, you may well be limiting the number problems that you can solve easily and practically out of the ones that will be important in the future.

I like Erlang (aside from some syntax ugliness), so I’ll give it a shot. I think it’s important because it allows a program to easier to scale out rather than scale up. If it was running an algorithm that are parallelize-able, then you can just technically add more cheap processors to it for a speed up, rather than designing a faster processor. We’d want speedups in this way because CPUs are becoming multi-cores, and to take advantage of them one will have to write some type of parallel program, since it’s proven difficult to fully automate parallelizing serial programs. In addition, with bandwidth pipes getting bigger and the internet more and more pervasive, it is possible that you can leverage other computers you don’t own (but given permission) for computational or storage resources in the future most of whom don’t belong to a single entity. (think more SETI@home than Amazon)

In addition, parallelized systems (not just erlang) can be more fault tolerant and can fail more gracefully (or hobble along, if you’d like to call it that). Sensor networks are one example. Instead of a single radar to detect the environment, you throw a bunch of sensors out there, and they network themselves and report what they see/hear back to you. If some of them gets destroyed that’s ok, because the system’s still functioning with less sensors.

A swarm of UVAs doing surveillance in an area is another example. If you have a single computer commanding all the UVAs, it’s actually quite hard, because you don’t want them to crash into each other, so that’s N^2 comparisons (less if you do oct-trees, probably). And if a target comes into the area, it becomes a non-trivial allocation problem: how do you decide which UVA to assign to monitoring it, and when do you switch them out when their fuel runs low? It ends up that doing it in with an actor model, where each UVA decides what to do at any given moment (local interactions) might not be optimal, but it’s redundant and fault-tolerant.

Biological systems work this way as well. Gene expression is actually a network of genes being turned on and off by proteins expressed by other genes being turned on and off recursively. If one gene can’t activate another, it might not always be detrimental, because there might be other pathways to express that gene. Since I’m not as familiar with the intricacies of biological systems, I’ll refrain from saying anymore.

I was surprised when I was watching a video of Alan Kay talking about OOP that the OOP C++/Java I learned in college wasn’t what he had in mind. Rather, he meant OOP to be more like biological systems and more process orientated. Encapsulation was only meant so that objects (analogous to actors in erlang) would have to pass messages to each other (method calls).

So what concrete examples of problems fall into this class Erlang is good at? The obvious ones are the embarrassingly parallelized algorithms, like genetic algorithms, neural networks, 3d rendering, and if I’m not mistaken, FFTs. Indexing web pages is another. But then again there are other algorithms that are inherently serial like protocol handshaking or newton’s method.

I don’t know what the ratio is between embarrassingly parallel and Serial problems are, but my gut is that with the advent of multi-cores and availability of the internet, I think there will be plenty of parallel problems to go around.

Ruby and Haxe language writers are both implementing the actor model like Erlang, if that’s any indication of how important they think it is. While I don’t think Erlang will be the 100 year language, the ideas by which it’s a poster child will reverberate in the descendant languages for a long time to come.

Model Reduction of Complex Dynamics

Model Reduction of Complex Dynamics

Alright, for some actual news. This is something that has been hard to achieve in computer graphics–that is believable fluid mechanics like water or smoke. Traditionally, they’ve been modeled as really large particle systems, which gets to be pretty expensive computationally.

These guys have managed to reduce the amount of computation required to make these computations to simulate fluids, detailed in this paper.

I’ve only glanced at the paper, but it looks like they were able to frame the problem in such a way that they were able to use dimension reduction techniques to reduce the number of computations they need to do, but have the least noticeable effect. By noticeable, I mean not only to the eye, but also to physics. It also conserves kinetic energy in the simulation.

I don’t understand much of the math in there, as it’ll take some time to go through it, but it reminds me of lossy compression algorithms and search engines. Not every piece of information is important, or is important in the same way. If you can frame the problem so that you can throw away less important information and still have approximately the same thing. It’s kind of novel to think of it as applied to a computational process, rather than a stream of data.

Comments on the death of computing

This article is starts off as a complaint or a lament in the area of edge CS, and probably serves as a warning, though the conclusion is probably not as hopeful or optimistic as it could be. Or it could possibly be the lack of imagination. To start:

There was excitement at making the computer do anything at all. Manipulating the code of information technology was the realm of experts: the complexities of hardware, the construction of compliers and the logic of programming were the basis of university degrees.

However, the basics of programming have not changed. The elements of computing are the same as fifty years ago, however we dress then up as object-oriented computing or service-oriented architecture. What has changed is the need to know low-level programming or any programming at all. Who needs C when there’s Ruby on Rails?

Well, part of it is probably a lament by the author–presumably a scholar–on the loss of status and the general dilution in the quality of people in the field. And the other part is about how there’s nowhere interesting left to explore in the field.

To address the first part, it’s well known that engineers, programmers (or any other profession) likes to work with great and smart people. Usually, when a leading field explodes you’re going to attract these great and smart people to the field. However, the nature of the field of technology is to make doing something cheaper, faster, or easier. And as technology matures, the more the barriers to entry in the field lowers. And as a result, you’ll get more people that couldn’t make it before in the field and the average quality of people dilutes. People use to do all sorts of research on file access. But now, any joe programmer doesn’t think about any of that and just uses the ‘open’ method to access files on disk. But that’s the nature of technology, and it’s as it should be.

The environment within which computing operates in the 21 century is dramatically different to that of the 60s, 70s, 80s and even early 90s. Computers are an accepted part of the furniture of life, ubiquitous and commoditised.

And again, this is the expected effect of technology. Unlike other professions, in engineering one is able to make technology which gives people leverage over those that don’t use it. This gives the advantage of acceleration and productivity that’s scalable that you won’t find in other professions. If you’re a dentist, there is an upper limit to the number of patients you can see. In order to be even more productive, you’ll need to create a clinic–a dentist farm–to parallelize patient treating and you need other dentists to do that. If you’re an engineer, the technology that you build is a multiplier, and you don’t even need other people to use the multiplier.

But at a certain point, the mass adoption of a technology makes it cheaper, and hence, your leverage over other people isn’t that great, and you begin to look for other technologies to make your life easier or give you an edge over your competition. But these are all applications arguments to CS; while important in attracting new talent, it doesn’t address where the field has yet left to go on the edge.

As for whether CS is really dead or not, I think there’s still quite a bit of work to be done at the edges. Physics in the late 1800’s claimed that there wasn’t much interesting going on there until General Relativity blew up in their face. Biology has had its big paradigm shift with Darwin, but there’s still a host of interesting unknown animals being discovered (like the giant squid) and I’m sure alien biology or revival of Darwin’s sexual selection would help open up another shift. Engineering suffered the same thing in the early 1900’s, when people with only a background in electromechanical and steam powered devices thought there wasn’t much left to invent or explore, until the advent of computing spurred on by the Second World War.

In terms of near-term computing problems, there’s still a lot of work to be done in AI, and all its offshoot children, such as data mining, information retrieval, and information extraction. We still can’t build software systems reliably, so better programming constructs are being ever-explored. Also, since multi-core processors are starting to emerge, so better concurrent programming constructs are being developed (or rather, taken up again…Seymour Cray was doing vector processors a long while back)

But I’m guessing the author of the article is looking for something like a paradigm shift, something so grand that it’ll be prestigious again, and attract some bright minds again.

In the end, he is somewhat hopeful:

The new computing discipline will really be an inter-discipline, connecting with other spheres, working with diverse scientific and artistic departments to create new ideas. Its strength and value will be in its relationships.

There is a need for innovation, for creativity, for divergent thinking which pulls in ideas from many sources and connects them in different ways.

This, I don’t disagree with. I think far-term computing can draw from other disciplines as well as being applied to others. With physics, there’s currently work on quantum computers. In biology, there’s contribution to biology from bioinformatics and the sequencing of genes, as well as drawing from it like ant optimization algorithms and DNA computers. In social sciences, there’s contribution to it using concurrent and decentralized simulation of social phenomenon, as well as drawing from it like particle swarm optimization.

One day, maybe it will be feasible to hack your own bacteria, and program them just as you would a computer. And then, a professor might lament that any 14 year old kid can hack his own lifeform when it use to be in the realm of professors. But rest assured, there will always be other horizons in the field to pursue.

Erlang and neural networks, part I

So it’s been a whole week since my interesting post about the OwnershipFilter. I was investigating several things all at once, all the while wrestling with internal motivation (another post, at another time). In any case, I thought I’d blog about it entirely when I had something full and concrete to show you. However, if it takes me that long, I might as well blog about it as I go along–and it might be more fun for you anyway.

Trace it back

It started with an article about how the free lunch is over for software engineers that a friend sent to me about two years ago. It basically stated that developers have been riding on the wave of Moore’s law to save their butts, and it’s not going to last forever. In addition, it’s been known for a while that chip manufacturers are moving towards multi-core processors to increase performance. If developers are going to take advantage of hardware like they have been, they’re going to have to learn how to program concurrent programs.

The problem is, programmers suck at it. It’s well known that concurrent programming, as it stands, is not easy for humans. Even Tim Sweeney, the guy that architected the Unreal Engine (no mere programming mortal), thought it was hard. It was when I started looking beyond threads as a concurrency abstraction that I tripped over a programming language developed specifically for concurrency.

Yet Another Programming Language

A friend of mine, who is a teacher (i.e. not a programmer), recently asked me, “Why learn more than one programming language?” Ahh, little did she know that programming languages inspire what verges on religious debates between programmers. My short answer was, “Each tool is better at one task than another.” I was looking for another language that might do concurrency better.

I had always thought that I should learn more about functional programming. It seemed like an odd beast to me, especially since you don’t change state through side-effects. “How do you get anything done?” It’s kinda like when you first learned that you don’t need GOTO, and subsequently, when you learned that FOR loops suck.

And yet, I never really found a need or a small project I could do with functional programming that might prove to be satisfying. It was only due to the search for better concurrency abstractions that I ran across Erlang, a functional programming language that is used explicitly because it’s good at concurrency. In fact, it’s pretty much the only one out there that touts concurrency as its strength.

It uses the actor model, where processes share no data and just pass messages around. Because there’s nothing shared, there’s no issue of synchronization or deadlocks. While not as sexy-sounding as futures or software transactional memory, the actor model falls nicely along the lines of complex and emergent systems–systems that have locally interacting parts with a global emergent behavior. Hrm…could one of these systems be good for a small side project to do in Erlang?

How Gestalt, Mr. Brain

Artificial neural networks seemed to be the perfect thing actually. A quick, quick diversion into what they are.

A feed-forward artificial neural network is basically a network of perceptrons that can be trained to classify (ie. recognize) patterns. You give the network a pattern as an input, it can tell you the classification of that input as an output.

You can think of a perceptron much like a neuron in your brain, where it has lots of inputs and one output. It’s connected to other perceptrons through these inputs and outputs and there are weights attached to the input connections. If there is a certain type pattern of input, and it passes a threshold, the perceptron ‘fires’ (i.e. outputs a value). This in turn might activate other perceptrons.

Even simpler, a perceptron is modeled as a function that takes a vector x as an input and outputs a number y. All it does is take the dot product of the input vector x with weights vector w, and pass it through a non-linear and continuous thresholding function, usually a sigmoid function. And you connect them up in layers, and you get an artificial neural network, that can learn to recognizeclassify patterns if you train it with examples.

It has to learn patterns by adjusting the weights between perceptrons in the network after each training example, and you tell it how wrong it was in recognizing the pattern. It does this by an algorithm called back propagation. It’s the same page I lifted all these pictures from. I put all their pictures in an animated gif to illustrate (click on it to watch):

In the first part, the example propagates forward to an output. Then it propagates back the error. Lastly, it propagates forward the adjusted weights from the calculated error.

I think the shoe fits, sir

Why would this be a good fit as a subject to play with Erlang? Well, if you’ll notice, each perceptron only takes input from its neighboring perceptrons, and only outputs to its neighbors. This is very much in line with the actor model of concurrency. Each process would be a perceptron, and would act as an autonomous agent that only interacts with other processes it comes into contact with–in this case, only other perceptrons it’s connected to.

In addition, you’ll also notice that in the animation, the perceptron values are calculated neuron by neuron. In a concurrent system, there’s no reason to do this! You can actually do the calculation layer by layer, since the calculations of any individual perceptron only comes from the outputs of the perceptrons in the layers before it. Therefore, all outputs for perceptrons in a layer can be calculated in parallel.

Notice, however, that layers need to be calculated serially. I had originally thought that with the learning process propagating back and forth, maybe it could be pipelined. On closer examination, however, the best one can do is to feed-forward the next input one layer behind the adjusting of weights, to make the learning process go faster.

So I’m going to give it a shot on the side, and document it along the way, since a quick search on google revealed that though people talked about it, no one’s ever really given some snippets on it. Wish me luck!

Erlang and Neural Networks Part I
Erlang and Neural Networks Part II
Erlang and Neural Networks Part III

For the love of programmers, we need better concurrency abstractions

Lately, I’ve been pretty interested in parallelism. Processors are moving to multi-core architectures. And while I expect that computers will keep following Moore’s Law for a while more, I think that there’s a lot to be gained for figuring how to best make use of multiple processors, especially for the tasks that can be easily parallelized, such as 3D graphics, image processing, and certain artificial intelligence algorithms. If compilers and subsequently programmers can’t take advantage of these multiple processors, we won’t see a performance gain in future software.

However, in terms of programming for multiple processors, the general consensus among programmers is, “avoid it if you can get away with it.” Multi-threaded programming has generally been considered hard, and with good reason. It’s not easy to think about multiple threads running the same code all at the same time at different points, and the side effects that it will have. Synchronization and mutex locks don’t make for an easy abstraction that works well as the code base gets larger.

One of the ways that people have been able to get around it is to reduce the amount of sharing of data that different threads and processes needs to have. Sometimes, this is enforced by a no side-effects policy in functional programming, and other times, it’s by the use of algorithms that are by nature share nothing. Google’s MapReduce seems to be a good example of this.

But there are some programs and algorithms that require the sharing of data, multithreaded programming for shared data is in some sense, unavoidable. Since that’s what we’re introduced with as THE thing for multi-threaded programming, that’s all I knew for a long while. Therefore, I started to wonder, is the current concurrent programming abstraction with synchronization of threads and mutexes the only one that exists?

Apparently not. Like all good ideas in CS, they seemed to have all come from the 1960’s. However, there here are futures, software transactional memory, actors, and joins (scroll down to concurrency). The post from Moonbase gives a probable syntax for these abstractions in ruby–they don’t exist yet, but he’s thinking what it might look like. I’m excited about this, if it makes programming multi-threaded applications easier. That way, programmers can more easily exploit multi-core processors or clusters for speed.

Most of the time, parallelism is exploited for speed, but I think parallelism can be also exploited for robustness. It’s no secret to programmers that code is fairly brittle. A single component that isn’t working correctly is a runtime bug for the entire system. I think parallelism can also be exploited to alleviate this problem, for a trade off of greater execution speed due to parallelism.

The only reason that I think this might be an interesting area to explore is because of the relatively recent interest in natural complex and emergent systems such as ants foraging for food, sugarscape, and termites gathering wood piles. A more technical example are the decentralized P2P technologies, as well as Bittorrent. This seems to be nothing new, as agent based modeling has been around for a while, in the form of genetic algorithms and ant algorithms. However, none of the current popular programming languages has good abstractions for it to exploit it as parallelism-for-robustness.

This might be a bit hard to design for, since it relies on the building of simple actors that will have an emergent system effect, while only sharing or using local information. It’s not always easy to ascertain what the global effect of many interacting simple actors will be analytically, since it might not always be tractable. In the reverse, given a desired emergent global system effect, to find the simple actor that will do that isn’t a walk in the park. However, I think once achieved, it will have the robustness that will make it more adaptable than current systems.

If anyone out there knows of such things, post a comment and let me know.

Update: I found that there was just a debate on Software Transactional Memory just now, and a nice post on how threading sucks. I know nothing compared to these people.