...And all the men and women merely players.
A blog about the state of gaming and technology

Thursday, September 15, 2011

Herd Mentality - Crowd AI for games

I was recently having a conversation with someone and we got to talking about crowd AI in games. It raised some interesting ideas for me, and I decided to explore those a little.

Specifically, I was interested not in the actual movement of crowds of people, and I wasn't interested in their behavior as individual entities, but how their behavior as a crowd can be modeled. I was most intrigued thinking of the spread of information through a crowd.  We've all seen a knot of people looking at something, and gone over to see what they're all staring at. There's also the behavior of protesters, mobs, or rioters - behavior that starts with a few individuals but has the potential to sweep up others in a wave of emotion and carry them along as part of the growing throng.  I was also struck by something I've seen described as "soccer fight" behavior, where an interesting event causes some farther-away people to press close, while those nearby want nothing more than to get away from the violence, creating an interesting crush of opposing desires.*

A basic existing model for the behavior of large numbers of entities in a simulation is Craig Reynolds's "Boids" flocking behavior.   It produces pretty impressive results for things like flocks of birds or schools of fish - they will generally stay together, change directions in moments, but stay a small distance away from each other.  We can easily imagine modified versions of that behavior looking like a crowd of people, albeit one that doesn't swoop around as gracefully. But there was something that interested me more than just the movement of the boids: one of the techniques it uses to create the flocking behavior is that neighboring boids will tend to align their velocities, attempting to match the speed and heading of other boids in the flock.

If instead of velocity, we imagine emotional state as a vector, won't this model an interesting flow of information and feeling in a crowd? Curious people headed towards something interesting would cause others around them to be curious about the attraction and join the crowd, frightened people fleeing something might cause others to flee as well, without ever seeing the danger, and a raging mob shouting slogans would tend to pull others into its passion.

So I decided to prototype this in a really basic Flash app, using the excellent Flixel for the first time. I've done a fair amount of ActionScript coding when I was BioShock 2's GUI programmer, and Flixel's tools make it easy to whip up a simple game-like object in a few hours. Still, I was rusty and this was my first Flixel app, so I was learning a bit as I went. It was tons of fun, though, and I definitely recommend it for quick-and-dirty prototyping.

In the prototype, I used a simple one-dimensional vector representing a Fear/Curiosity spectrum. A more nuanced approach would be possible, but I wanted to keep things simple and also couldn't think of anything that would add anything as a second axis. A two-dimensional scenario might have a happiness axis and a passion axis, though, where fear and curiosity are the negative and positive happiness points at max passion, or something. There are lots of options.

Here's the code for the function that spreads emotion through the crowd:

public function EmotionalAlign(OtherEntities:Array):JVector
            var NeighborDist:Number = 24;
            var sum:JVector = new JVector(0, 0);
            var count:Number;
            var i:Number;
            var loc:JVector = new JVector(x, y);
            for (i = 0; i < OtherEntities.length;i++)
                var OtherLoc:JVector = new JVector(OtherEntities[i].x, OtherEntities[i].y);
                var Distance:Number = JVector.Distance(loc, OtherLoc);

                if (Distance > 0 && Distance < NeighborDist /*&& JVector.Distance(Emotion, OtherEntities[i].Emotion) < 1.0*/)
            if (count > 0)
            if (sum.Mag() > 0)
            return sum;

It's pretty simple - we  sum up the emotional vectors of nearby Boids, take the difference of that with our current emotional "heading", and impose a max "emotional acceleration" on it so that it changes gradually.  This is then applied over time as an acceleration to the emotional direction of the boid.  As you can see, we use the physical distance of nearby boids as the determining factor of whether to add them to the calculation or not. I also experimented with requiring boids to be within a certain "emotional distance" of each other, but it caused the simulation to be less interesting, so I left it in commented out.

The "Create Boid" button will drop a new Boid with random weak emotions somewhere in the playfield, and left-clicking anywhere on the playfield will create an object that terrifies nearby boids but attracts boids who are slightly farther away.

In this particular model, fear doesn't decay over time, so terrified boids will eventually accumulate and run in frenzied packs around the landscape, dragging down the framerate and necessitating a reset. Adding general emotional equilibrium would be a good improvement.  One of the other interesting things to me about information propagation through a crowd is the idea that the emotions can affect members even without being able to see or being near the cause - this would be more clearly apparent in a larger environment with intervening terrain and just more subtlety in general.

It would also be cool to explore the idea of imperfect information transfer, so that if a crowd gets large enough the emotions propagating through might change over time, approximating something like false rumors or confusion over motives.

In the demo here, entities physically flock in addition to emotionally flocking, which leads to big moblike clumping. That's not necessarily a bad thing, but for more variance the movement would ideally be more independent and allow for splinter groups and so on. Since once an entity gets within physical proximity it will always accelerate to be in emotional parity as well, there's not a lot of subtlety to the flow of emotions in a crowd.

Also there are other emotions one could model instead of just the Fear/Curiosity dimension. Another game mechanic idea I had involved an angry mob, or rioters - as entities get swept up in the emotions of the mob, they get pulled along in a vortex of anger, and the player's job would be to prevent that happening - perhaps through strategic dropping of calming influences such as really chill people (or maybe cops) or perhaps by cleverly keeping the individual entities from being able to form into an effective mob until their anger dissipated somewhat.  Of course, being based on Craig Reynolds's flocking work, there's only one possible name for a game using that mechanic...

Wait for it...

Angry Boids.

I'm done.

* Sadly, this can't really be done in a modern game - while it's easy enough to have crowds of people crushed up against each other and unable to move because of collision, there's no way you would be able to animate the press of a fight scenario like this in a realistic manner. It would work perfectly in a abstract, top-down game, though. Yet another way that the quest for visual fidelity undermines the really interesting simulational and mechanical aspects of games!

No comments: