Does anyone have a general idea about efficient path finding and collision avoidance for a crowd simulation?
Thanks 
I have pondered something similar to this for my current project. What I though about is this: I get the positions of the (10) nearest objects to the owner. I then find the distances between each of those objects and find the smallest distance. I get the average position of the two objects (right in between them), and move the owner there. I came to this idea by asking myself: How would a human do it?
There’s a good tutorial on path following and group behaviour http://natureofcode.com/book/chapter-6-autonomous-agents/
This should be a good start. The code is in processing but should be easily translated.
Per actor pathfinding is most likely right out the window.
What is the crowd supposed to do?
As a group move to a place?
Simulate a busy environment?
Is the map dynamic and complex or simple?
Complex mazes, or static streets/terrain?
I have had a lot of luck with semi-random movements.
I would basically have the npc move in a random direction, where the objective direction has better weights.
They would only respond to npc in the immediate vicinity.
As there is no actual path-finding required, simulating 2000 npc was no hassle 
They were fairly competent on simple terrain.
Maybe the main point for me is that path-finding and collision avoidance are not the same thing.
Think robotics, like roombas, ir-sensors and whiskers 
I’d humbly get down on my knees and beg a developer to expose detour’s built-in crowd management.
Think robotics, like roombas, ir-sensors and whiskers
Having done a mechatronics (robotics) engineering degree, I can say with confidence that AI in games is very very similar to AI in robotics. AI in games is slightly easier because you don’t have to justify the cost of sub-micrometer-accurate Lidar sensors every time you want to cast a ray…
For a crowd? Probably the simplest trick I can think of is that you don’t need to simulate all of them. Examples:
- Pathfind only for the center of the group, and use that to get a direction for all the people in the crowd to move in. Study the crowd distribution to see if it has split into multiple groups
- Collision avoidance only needs to happen for agents near the edge. Imagine putting the agents as dots on a texture, and distorting the polygon it’s mapped on. If you can define an agents position as an interpolation of other nearby agents, then it will not even need to try avoid them most of the time, even as the whole crowd moves around obstacles. A simple distance check to nearby agents can signal that this agent needs more attention to make it fit into the crowd (assuming the crowd isn’t too dense).
If #1 and #2 are done properly, most agents do nothing at all except move from one defined location to another without needing any checks to avoid collisions. Only the edge ones need clever obstacle avoidance.
- If you do a raycast for an agent, raycasts along similar directions from similar places need not be run. Caching is your best friend. Have a look at pythons build in lru cache, and consider rounding the values in raycasts to better use the cache.
- Seperate the crowd into a seperate collision group so internal raycasts don’t need to consider the level geometry, and collision avoidance raycasts don’t need to consider the crowd.
Also look up boids.
I have had success with this by having simple behavior add up,
Like the closest agent to the door pathfinds out,
Another useful scenario was the zombie ai that if they saw a zombie chasing a player, they chased the zombie, the next zombie chases the second and so on.
Find a path for the group then move them in the same direction using per agent basic collision avoidance.