• Advertisement
Sign in to follow this  

Crowd simulation

This topic is 1214 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, im attmepting to create a crowd simulation with multiple entities to create crowds that avoid each othwer realistically, what would be the best way to create this (navigation mesh, grid based)?

Share this post


Link to post
Share on other sites
Advertisement

Do they need to do anything other than move randomly and avoid each other?

 

The most important element to realism isn't the AI, but the animations and their blending:  The bumping, the turning, the movement in the arms.

 

Just simulating a bunch of entities as points with repulsive forces acting as an inverse square is a start.  Filling them in with living and believable sprites is the real challenge.

Share this post


Link to post
Share on other sites


The most important element to realism isn't the AI, but the animations and their blending:

 

It is still an important matter however. Most people err on the side of caution. A believable crowd scarcely avoid one another to be fair (hence the occasional bump due to miscalculations and unexpected assessments). People tend to take the shortest path to their destination and aren't very happy to derive from it, so they tend to force the other to do a lot of the legwork.

That probably also tells you a lot about my opinion of most people though :P

Share this post


Link to post
Share on other sites

Well, how accurate are you going for?

On one end of the spectrum, you have a fuzzy logic control system with clustering, opinions, and remedial information propagation (Whether through Backpropogation with NN, or just super basic AI one approaches AI two, AI one says "The player did this", AI two now dislikes player). On the other side the spectrum, you have a super elementary Roaming algorithm. It all comes down to how detailed you want it to be

Share this post


Link to post
Share on other sites

People tend to take the shortest path to their destination and aren't very happy to derive from it, so they tend to force the other to do a lot of the legwork.


Actually, you should observe a real crowd sometime. People very rarely plan optimal paths - they may approximate a decent path, but virtually never optimal. They also are remarkably adept at adjusting speed, heading, and cadence to avoid collisions and other interactions - usually completely subconsciously. It's modeling this that is hard about crowd simulation.
 
 

On one end of the spectrum, you have a fuzzy logic control system with clustering, opinions, and remedial information propagation (Whether through Backpropogation with NN, or just super basic AI one approaches AI two, AI one says "The player did this", AI two now dislikes player). On the other side the spectrum, you have a super elementary Roaming algorithm. It all comes down to how detailed you want it to be


This seems like a false dichotomy to me (although it's more like a... false spectrum?). The sophistication of the behavior model is orthogonal to the implementation technique. Don't confuse "fuzzy logic control system" with "the only way advanced AI works" (because "fuzzy logic control system" is so poorly defined as a term that it's basically meaningless).

Moreover, you have conflated accuracy with detail. This is a common beginner mistake, though. Accuracy is a measurement of how close you are to the desired outcome, regardless of what the outcome is. Detail is a measure of how subtle the outcome can be and how many inputs the system can meaningfully process. It is possible to be incredibly accurate and very barebones, or incredibly detailed and thoroughly comically wrong.

This is important because it informs the choice of implementation technique. You're correct that there is a large question unanswered here (what does the OP wish to accomplish). But the question should be asked more carefully:


How would you like the agents in your crowd to behave? What kind of world are they in (2D, 3D, space, etc.) and how do they move in that world? Are there limitations to their movement, such as turning radius or acceleration limits (think cars)? Do they have goals and destinations?


These questions are a good enough cross-section of the implementation concerns to get a decent idea of what implementation strategies might suit the OP.

Share this post


Link to post
Share on other sites

I wasn't stating that "This is the way that advanced AI work" I was giving a comparison that a system with various features would be most likely more complex than a system that consisted only of a roaming algorithm implementation. But yeah, I see what you mean, the reply I made was worded poorly. Obviously extremely complicated behavior can be made with finite state systems, and/or various other methods.

 

Also, I completely forgot there was a difference between accuracy and detail (My physics professor would have killed me haha)

Edited by WireZapp

Share this post


Link to post
Share on other sites

A believable crowd scarcely avoid one another to be fair (hence the occasional bump due to miscalculations and unexpected assessments). People tend to take the shortest path to their destination and aren't very happy to derive from it, so they tend to force the other to do a lot of the legwork.

That probably also tells you a lot about my opinion of most people though tongue.png

 

They more kind of just barely veer around each other when they get close.  Procedural motion adaptation is really important for that, if you're looking for something like Assassin's Creed.  If you're talking about something less sophisticated, you could just keep them are arm's length.

 

The general mechanics can be easily enough simulated with a particle system where they exert slight repulsive forces on each other at close range (and stronger the closer they get).

 

If you wanted to get more accurate, you could have those forces act more strongly based on facing.

That is, I am more repelled by something I am moving toward rather than something I am moving away from, since I'm going to be mostly unaware of things that are behind me in a crowd.

 

I don't think any sophisticated pathfinding is necessary, though.  People mostly just try to bully through in the general direction they want to go, unless we're talking about a chase scene where somebody's acting abnormally and weaving in and out of the crowd.

 

People are drawn more into open areas, but that can be handled well enough by repulsive forces.

 

 

They also are remarkably adept at adjusting speed, heading, and cadence to avoid collisions and other interactions - usually completely subconsciously. It's modeling this that is hard about crowd simulation.

 

True, although that applies more in a sparse crowd.  In a dense crowd, it can be approximated pretty well as repulsive forces since they're only really aware of those right next to them (visibility being limited).

 

You're right that we need a lot more information, though, since I'm making a few assumptions here about the nature of this crowd.

 

 

This is important because it informs the choice of implementation technique. You're correct that there is a large question unanswered here (what does the OP wish to accomplish). But the question should be asked more carefully:



How would you like the agents in your crowd to behave? What kind of world are they in (2D, 3D, space, etc.) and how do they move in that world? Are there limitations to their movement, such as turning radius or acceleration limits (think cars)? Do they have goals and destinations?


These questions are a good enough cross-section of the implementation concerns to get a decent idea of what implementation strategies might suit the OP.

 

 

Good questions.

 

 

I think overall it's important to remember that crowding is really a result of a lack of intelligent planning on the part of the individuals contributing to the crowd.  It's more a well oiled machine which is flowing coherently and without incident that requires real investment in AI for a solution, which is somewhat the counterpoint of a human crowd.

Share this post


Link to post
Share on other sites

I am not an expert. Having said that, I have read some papers about combining steering behaviors with more global systems such as navigation fields. The point of the global systems is to reduce the amount of calculation per agent without them getting stuck or conflicting with too many other agents. Examples are staying to the left/right on footpaths, going through subway turnstiles, and avoiding complex obstacles. For a randomly Googled example, see http://rll.berkeley.edu/~sachin/papers/Patil-TVCG2011.pdf

Share this post


Link to post
Share on other sites

Grid can be a good approximation (squares big enough to hold a person without too much crowding - scaled to say 4 feet by 4 feet)  or a more irregular Navmesh of similar 'cell' dimensions that closer matches upto the irregularities of the terrain.

 

Looking into D*  (Dynamic A*) might be useful as a mechanism (or a variant of it) which reserves ahead of the moving object some space (with an added time dimension) to simulate the looking ahead behavior people use while moving in crowds.

 

Variations would only reserve a short time ahead and require near constant reevaluations and implementing conventions like 'keep to the right'  that some people get used to in situations (like sidewalks) whhere there are conventions. 

 

Depending on the setting (like a cityscape) there are also other factors -- traffic lights at crossings and vehicles moving by their own rules which might complicate the situation)

 

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement