Busy day, still haven't read Terzopoulos's papers. However I had a look at Alex article and already had both white papers (Continuum crowd, Steering behavior for autonomous characters) printed and on my desk ;). Those are the two original references we read before implementing the first version of the system and this is where we took the basis of our seeking/avoidance/separation system. Nice animation engines ideas for pushing and bumping also but, as said, it's a little bit more combat oriented even though it could be used to simulate crowd pushing. It's also a bit too complex to justify implementation in my case.


I know I still got some reading to do but I have difficulty seeing how you can efficiently steer an agent through dynamic environments without having him getting stuck between a concrete wall and a dynamic object when multiple forces act on him at once.

How do we guarantee that he is not gonna end in a space too tight for him without doing some pretty intense geometry analysis with the walls and dynamic objects bounding volumes? (That is what we do now but it seems nearly impossible to correctly handle all situations without unacceptable amount of math). Since object are dynamic the agent can steer itself in a dead end caused by a wall and a (currently immobile) dynamic object).

Something like that (Agent A tries to go EXIT but steers away from agent B and end up in a dead end caused by the wall and the triangular dynamic object ) :

----------------
....A->/|......|
....../_|......EXIT
..<-B..........|
----------------

Is there a general way of detecting /handling / avoiding these kind of impasses.

Maybe the answer is right before me but I have not seen it yet.

P.S. Sorry I had no way to put a real picture.

Quote: Original post by Fred@ss
Busy day, still haven't read Terzopoulos's papers. However I had a look at Alex article and already had both white papers (Continuum crowd, Steering behavior for autonomous characters) printed and on my desk ;).

I've known a lot of people who tried to replicate Treuille's Continuum Crowd stuff, and none of them got satisfactory results. IMHO it hasn't proved itself to be a practical approach.

Quote: I know I still got some reading to do but I have difficulty seeing how you can efficiently steer an agent through dynamic environments without having him getting stuck between a concrete wall and a dynamic object when multiple forces act on him at once.

Well, there's two potential problems there. One problem is a local minimum in the potential field. This is a danger with any potential field method, and there's no good solutions I know of other than careful level design if you go with a potential field method.

The other problem is where there's a passageway that's just too darn narrow. The best solution there, IMHO, is to compute the Minkowski sum of all obstacles with a circle that is the size of the largest unit's bounding circle. (Put simply, all obstacles are puffed outwards in all directions.) The math can be hairy or not, depending on how much of a problem intersecting (or self-intersecting) objects are in your pathfinding method. You can also find the bounding hexagon or octagon and use that instead, which avoids any curved surfaces in the resultant summed obstacles.

Again, some of the caveats that are being brought up are not a failing of the system(s), but rather a failing of the designers. We simply are trying to solve the wrong problem... a common setback in many situations.

One significant problem that reactive agent-based systems will always have in this situation (such as potential fields -> steering) is that they don't mimic one important part of crowd or even multi-user interaction... that of "Oh, am I standing in your way? Sorry, I'll move."

Remember, if some dumbass is standing in front of the door in real life, we either ask him directly to move or make it rather obvious that we need to get by him - at which point, he hopefully responds and moves. That eliminates those "stuck areas" like local minima. If humans were truly reactive, we would not take into account what anyone else may be wanting to do, nor would we communicate our desires to those around us.

On the contrary, since we are ostensibly trying to model humans, we need to look beyond purely reactive systems and towards a rudimentary awareness of other agents... not just for selfish purposes, but for other agents' purposes. i.e. "Am I standing in a bad spot for that dude coming this way." Nothing needs to be signaled visibly... just an awareness passed. This can be done with either of the two standard methods: polling and messaging - with the later being far more efficient in this case.

Thanks for all the info guys, last week was just a quick analysis of what needed to be done, now I have other stuff to take care of for a few weeks and than we will reimplement/correct the crowd avoidance system. I'll keep on reading and thinking about the stuff discussed here so that when I start I have a good idea of the direction I want to go with that. Don't hesitate if you have any other good references.

I'll let you know when I start working on it, I'll probably have a few more questions anyway ;)

Thanks again

Fred