Howdy, Greg!

Thank you for raising a really important point. Once unit density starts to increase past the trivial numbers that are typically used in action games, you quickly start to run into the group dynamics problem. A lot of people (OK, almost everybody) underestimate this problem, and it can be at least as hard a problem to solve as pathfinding.

Fortunately, a lot of these problems have been solved (or at least addressed) in real-time strategy games. The main obstacle in applying these techniques to real-time 3D games is usually the difficulty of adapting them from the flat grid world of most strategy games to the complex 3D environments of RTS games, platformers, etc.

Here are some of the better resources I'm aware of:

- Dave Pottinger of Age of Empires fame wrote some great articles on coordinated unit movement:

http://www.gamasutra.com/features/19990122/movement_01.htm
http://www.gamasutra.com/features/19990129/implementing_01.htm

- Jeff Orkin's navigation-mesh-cost-based avoidance system can be very useful for this sort of thing (http://www.aiwisdom.com/bytopic_flocking.html). I'm happy to say I used them for a couple of the creatures in Metroid Prime 2: Echoes and was very happy with the results.

- There was also a really great talk at the AIIDE this year on a technique that I believe was called "Windowed Cooperative Hierarchical A* or some such. It was essentially a way of doing temporal path-locking in order to implement pathfinding as a global operation that would take the paths of all units into account, rather than the standard technique of each unit doing pathfinding alone and ignoring all other units' paths. There was a great demo of 40 orcs on either side of an east-west bridge (20 on each side), and he sent them in opposite directions across the bridge (east->west and west->east). In WarCraft, they got hopelessly stuck against each other; his talk built up to a neat demo where they all sidestepped each other perfectly as they crossed a bridge.

He also gave some fairly convincing performance metrics for his system; performance was almost identical to A* with a low number of units and degraded very gracefully as more units were added.

The AIIDE website seems to be down at the moment and I'm having trouble finding a URL for this, but I'll see if I can track down a reference to it sometime in the near future.

Yes, coordinated group movement and cooperative pathfinding address some of the issues, but I think that's just scratching the surface. Real civillian crowds in real public spaces rarely move as coordinated groups, and cooperative pathfinding still assumes a bit too much cooperation and ignores the influence of dynamic steering.

For independent not-so-cooperative NPCs, it seems like as crowd density increases you hit a point where A* style pathfinding is too discrete and too forward thinking, but steering behaviors and collision avoidance is too continuous and short-sighted.

It's like you want to find a long range path estimate through static obstacles and continuous crowd densities, but then you want to move through the crowd with some sort of discrete pathfinding through the voronoi graph of the local crowd. All with some sort of feedback that continuously updates the long-range path estimate based on crowd density changes.

As an example, the player is on a crowded subway platform and an NPC wants to get right next to them--say to have a conversation or maybe stab him. :) Maybe something like the cooperative pathfinding idea would work, but it would seem very strange if the crowd cooperatively parted for the NPC, or even worse if the NPC gave up because he didn't know how to squeeze through the crowd.

Welcome Greg! You've touched on one of my great hopes for next-generation character AI : real-world crowd densities. If we can turn increased horsepower to avoiding every game being set in an 'adandoned complex', 'evacuated city', or 'barren wilderness', that would be just great :)

I see two main challenges here:

1. Navigation systems need to rise to the challenge, as you describe.

2. If we have 1000s of character models on-screen surrounding a small number of ever more complex interactive story agents, then game NPCs will need to become 'variable cost' objects; not just in terms of run-time simulation and possibly rendering, but also in authoring terms.

Incidentally, Namco's Frame City Killer for XBox 360 has a lovely concept demo showing real-world densities in a market street, from 0:30-0:40 of the first official trailer:

http://www.gamespot.com/xbox360/action/framecitykiller/index.html

However, check out the in-game screens; I count a maximum of EIGHT on-screen NPCs, compared with up to 800 in the trailer :)

Now, I'm a lowly designer, so I'm probably going to embarass myself here, but, I was at this conference a while back where crowd AI was simulated in a virtual museum, and to avoid paths of people around it, a kind of potential field was placed every tick around AIs, creating a steep slope infront of an AI's direction. This was then interpreted by other AIs, and they would evacuate the area (and incedentally, start moving behind, and with the group leader). So it was a bit like they were avoiding each other by acting a little like water... thus, AIs were left like wake behind the movement of the other AIs.

Now, I've no idea how useful this kind of abstraction is (although I have a feeling that something like this needs to be used to avoid impossible numbers of local behaviours?) but it certainly stimulated my imagination. Wasn't it Sun Tzu who said that armies move like a body of water? Could there be some amount of truth applying fluid dynamics to crowds? Am I 60 years behind in terms in AI research in this area?

It sounds like the solution here is simply an expanded local pathing algorithm, perhaps modeling social conventions? For instance, people in crowds tend to stay to either the left or right, depending on the country. Within these 'streams', there tend to be clusters of people going to the same place, etc. Is there anything to suggest that a hierarchical pathing system would struggle with this?

I am not sure the density issue will come up this generation. There is a huge different in rendering cost between 8 characters and a few hundred. While the next gen consoles are certainly more powerful, characters (visually) would have to be simplified from this current generation tech to make density an issue.

It definitely does sound like an interesting problem though. :)

Finally, perhaps this is off topic, but why the cheap shots at Carmack? The man is a graphics programmer - what kind of AI commentary are we expecting from him? In my opinion, these shots at him cheapen this board.

Moving even further off topic, Aubrey, do you work with Steve/Ren/Adrian over at StreamLine? If so, tell them Brian said 'hi'. ;)

> [Aubrey]
> I was at this conference a while back where
> crowd AI was simulated in a virtual museum,
> and to avoid paths of people around it, a kind
> of potential field was placed every tick
> around AIs, creating a steep slope infront
> of an AI's direction

This kind of repulsor-based system only really works well when there are no obstacles in the environment. The problem is that it's not really compatible with a pathfinding system -- you can have your A* pathfinder telling you to go one way, and the crowd pushes you off into some cul-de-sac that you can't get out of.

The kind of problem Greg is discussing really demands a solution that fully integrates a solution to the pathfinding problem ("how do I get from A to B while avoiding obstacles on the terrain?") with a solution the dynamic obstacle avoidance problem ("How do I avoid other NPCs and any other dynamic obstacles I might run into along the way?").

> [BrianL]
> Finally, perhaps this is off topic, but why
> the cheap shots at Carmack?

I'm sure everyone on this blog recognizes that Carmack has done more than anyone to bring gaming into the 21st century.

Having said that, somebody as smart and respected as Carmack owes it to himself to keep up-to-date with what's going on in game AI. A lot of people take Carmack's words as gospel (particularly in the media), so when someone of that stature misrepresents game AI, it makes our jobs that much more difficult.

The industry has changed, and the biggest thing holding game AI back at this point is outdated attitudes.

Paul, I think I've brought down the IQ on this board a few points, but thanks for explaining it to me. I think I get it now.

Brain, sure! I'll tell them you said hi, although Adrian is at a different Dutch developer right now.

And for what it's worth, I thought the Carmack jibe was a harmless injoke. I don't think even he'd take offense to it.

Hah! I just called you "Brain". Sorry Brian.

excellent post. first thing I thought of was in a bit of a different vein though - http://www.monzy.org/audience/

...one wonders if there might not be some hints towards innovative crowdplay in there?

I'm new to AI and Game Development as a whole (just started my MPhil and no obligatory "HEY I'm gonna make games that ROxXxOr blog yet.") but I was wondering if a look at nature might help pathfinding for large groups.

The suggestion of a rule of thumb on which side to pass on when faced with oncoming traffic seems good; I believe the idea of keep left originated in roman times and keep right came about with the french revolution. But another thing that came to mind is the way ants navigate - I don't mean laying down some sort of invisible trail that grows stronger as more people pass on it, though that may work for non-human characters (would look strange for people) - instead I mean depending apon speeds, or I guess how badly an ant wants to get past, that ant simply shoves the others out of the way. That sort of motivation weight could possibly help NPCs that are crucial to story-line (for example the guy trying to stab someone on the subway) get to their intended destination while allowing non-crucial NPCs do what they do best... mill around and look pretty.

Or am I just talking out of my ass?

We've been looking at a lot of research on crowd dynamics, as is usually applied to modelling pedestrian behaviour in public spaces for design and safety purposes, in an attempt to scale up our pedestrian system to handle hundreds of NPCs on-screen at once.

Some of the research that we've looked at uses flow-based models that have their parameters tweaked from video analysis of crowded public spaces. These techniques give rise to meta-structure such as queues of pedestrians moving in the same direction, without "keep left" rules having to be explicit in the code.

Definitely worth looking at, if only for interest's sake. Some examples (hopefully Google will find these for you):

Joel A. Kirkland and Anthony A. Maciejewski, "A Simulation of Attempts to Influence Crowd Dynamics"

Michael Batty, "Agent-Based Pedestrian Modelling"

Robert Kukla, Alexandra Willis and Jon Kerridge, "Application of context-mediated behavior to a multi-agent pedestrian flow model"

Celine Loscos, David Marchal and Alexandre Meyer, "Intuitive Crowd Behaviour in Dense Urban Environments using Local Laws"

... the list goes on. We must have referenced upwards of thirty papers on this topic alone.

- Jason Hutchens.

Any chance I could get that list of publications from you Jason? I am doing some background reading on crowd simulations for a project here at ICT.

Hi guys,

You may find the paper "Large Scale Animation of Autonomous Pedestrians in Urban Environments" (SIGGRAPH2005) interesting. It demonstrates that simple steering behaviors can indeed give rise to the crowd streaming behavior we see in high density groups of people. You can find videos here:

http://mrl.nyu.edu/~weishao/research/penn/siggraph2005/siggraph2005.html

And the paper here:

http://www.google.co.uk/url?sa=t&ct=res&cd=1&url=http%3A//mrl.nyu.edu/%7Edt/papers/sca05/sca05.pdf&ei=6eAeQ_DhLKGORfWg_M4M

It’s good reading.

Mat

Paul, I only just read your comment... 'twas lost to me among all that spam. To get the papers, try entering the full title, in quotes, to scholar.google.com. I've just checked, and that retrieves the PDFs of three of the four papers I listed. Good luck!