Hi all! I am currently re-doing our avoidance implementation. The context is, as stated in the topic subject, crowd avoidance in a dynamic environment where paths are calculated using a dynamic navmesh and A*. I've looked around but everything I have seen is a variation of the usual seeking / avoidance / separation methods which consists in steering the NPC according to where he wants to go, what he needs to avoid and how close he is to the borders. There are a lot of variation on this theme and we already tried many of those along with some customs ideas. However, since we are giving it more time and still a few serious problems, I was curious to ask about other ways to tackle this problem. So, feel free to share your experience / ideas! Thanks!

One alternative is pre-planned avoidance, as David Silver covered in Cooperative Pathfinding. It's a clever approach, but it quickly becomes problematic for continuous state spaces, especially when units may move at different speeds. The social forces model is fraught with problems, but most of these problems have solutions. What problems have you run into?

The most annoying problems I've had come from agglomeration of people.

First it causes the algorithm to fail since close individuals units are not considered as a group. Blending the avoiding vectors components then sometimes give a senseless result that make the pawn bump right into the group of people/objects. (Someone tried a grouping algo to solve that but it seems it was too CPU intensive for our navigation budget)

Second, when many people are avoiding other people/objects at the same time and suddenly start avoiding each other they sometime choose to avoid in the same direction and it either blocks (because they both thought they could pass on a given side but since they moved at the same time they get stuck) or cause a visually annoying hysteresis. (I hope I am clear, this is a bit hard to explain in text).

Third, I had quite a hard time performing the navmesh border analysis relative to the surrounding objects and pawn radius to determine what side is best to avoid. Now it (seems to :)) work fine but I am still curious about solution to that particular part of the avoidance problem.

Finally, it is hard to make natural looking avoidance, we usually have to make a decision at the last minute but in an ideal world we start avoiding from much further away to keep things smooth. However, in a dynamic environment with limited cpu resources, we can't plan too far ahead. Also, taking too much into account make the analysis clumsy and bug-ridden.

Other problems (more or less avoidance related)
We do not yet deal with the case where we are out of space to avoid, but this is more of a behavioral problem so it's not really a priority right now.

And also the eternal problem of the player running around in the crowd where it is pretty hard to make the pawns bumping into each other and avoiding as best as the can look credible... But again, this is not a pure avoidance problem.

I am currently reading your pre-planned avoidance article. However we have quite a lot of pawn traveling at different speeds...

Adding explicit queueing behaviors can help a lot with bottlenecks. Check out this paper by Nuria Pelechano for more. Her other papers may also be of use to you; a couple of them center around user-controlled avatars within simulated crowds.

BTW, as long as I'm bibliographizing, I should note Terzopoulos' exclusively rule-based crowd simulation. His approach is rather resource-intensive, and I'm a little skeptical of the breadth of its applicability since I don't know of any outside implementations--but it at least deserves a read-through for ideas on how to do rule-based collision avoidance. Such approaches have the potential to be more robust than fuzzy social forces models, since there's less to tweak and more to reason about.

Thanks! I'll look into it at the beginning of the afternoon and let you know.

The cooperative pathfinding has a few good ideas. I find the whole time-conscious A* concept very clever. I will keep thinking about it, it would probably be worth using as part of a better path finding algorithm for multiple NPC/crowd games. But, realistically, we are too far in the project to consider revising the whole path finding layer. On the other side, I have a problem seeing how you can parse a navmesh into a grid... Especially a dynamic one where tessellation happens in real-time (which is our case). Triangles can be of any size, which require splitting single triangle into many cells and vice-versa. Also, it does not deal with the problem of dynamic objects which do not have their own path but still create bottlenecks and must be avoided in real-time. Note that those are just my first thoughts, I am sure they are ways around those problems.

Don't hesitate if you have any other references, reading other ideas always opens the mind to new solutions

Quote: Original post by Fred@ss
On the other side, I have a problem seeing how you can parse a navmesh into a grid... Especially a dynamic one where tessellation happens in real-time (which is our case).

That's the big problem. To get it to work with a non-grid motion space, the reservation table has to have fairly high resolution, with each entity taking up many grid cells during a particular timestep. This leads to high memory and computational load. I've implemented Silver's approach with really good results when my world really was a grid, but when it came time to go to a non-grid world I changed over to a social forces system.

I just finished reading Nuria Pelechano's paper and I think it contains a lot of good ideas. It's interesting because her basic force model in section 4 is very similar to what we are doing here. Afterward, the idea of reacting according to crowd density, the stopping rule, the area of influence and other similar topics seem like very powerful (yet not too complex) extensions to this system. It could probably solve some of my main problems. I also like the idea of people falling to the ground when to many forces are directed towards them, it's a nice way out of this situation :)

Very useful, I'll try some of those ideas for sure.

Out of curiosity, in what game/project context did you implement this solution and how did it go? Like you many agents did you deal with, in what kind of environment, where there any dynamic objects, etc?

Also, I'll try to read the Terzopoulos paper tomorrow and again, I'll let you know.

Thanks.

Quote: Original post by Fred@ss
Out of curiosity, in what game/project context did you implement this solution and how did it go? Like you many agents did you deal with, in what kind of environment, where there any dynamic objects, etc?

The cooperative pathfinding stuff was implemented for a grid-based RTS game with a few dozen agents, about 5% occupancy, and no dynamic objects. It worked well, much better than the rule-based stuff it replaced, but when it came time to move beyond a grid space my initial tests with cooperative A* were very disappointing from a performance standpoint. Most of my experience with the rest of the stuff is osmotic--I worked in a research lab with Nuria, and did a teeny bit of the programming--though I did write a vaguely related paper on crowd modeling, and I was a test subject for the VR crowd stuff.

Alex had an article that touched on some of this over at AIGameDev. Might be some good stuff there to look at.