# Algorithm for a dense crowd of people who avoid the player?

I want to make a game like this. When player moves other humans will move too. And other humans will push people around. Are there any algorithm for this ? How can i solve this very efficient way ?

I dont want to check all objects at scene with loop. And i dont want people overlap.

Video:

https://youtu.be/V5ZMicq05LQ

• Consider taking a tour of the site: gamedev.stackexchange.com/tour and What types of questions should I avoid asking? (gamedev.stackexchange.com/help/dont-ask) Commented Jun 14, 2019 at 23:02
• Out of curiosity, what type does this question fit in? I for one would love to see some of the possible answers for this Commented Jun 15, 2019 at 0:01
• What language are you using to code it? Java? Commented Jun 15, 2019 at 1:16
• You might want to convert that video to an animated gif. Commented Jun 15, 2019 at 1:41

## 3 Answers

If you create a grid of weights, you can have each person's AI be fairly simple and go towards the lowest weighted location nearby.

I kind of imagine this as representations of gravity, but instead of making pits and attracting, they're forming mountains and repelling. They're all smelly and want to move away from each other.

Since we want the player to have plenty of space and override pretty much everything else, they can have ridiculously large values to ensure the AI people move away.

When calculating where each person should move, they should ignore their own aura they're adding to the grid (probably by subtracting their values or something).

This should work well and not be too noticeable it's a grid if you make the grid small enough.

• There's definitely a name for this kind of AI algorithm, but I can't remember what it is Commented Jun 15, 2019 at 10:00

It's very simple, you can measure the distance of the humans to the player, if it's below a certain threshold, move them away from the player. The vector for the last step is simply the position of the human minus the position of the player.

• I think you can improve the answer by hinting at how the OP can speed up the calculation of the distances without looping over all the people in the crowd (since he asked for efficiency). For example, with space partitioning. Also, I think the solution is not as simple as moving the people away from the player. You should take into account interactions among people in the crowd as well so that they do not overlap when moving. I suggest some very-short-range repulsive interaction so that it can be sped up as well with a finer spatial partitioning. Commented Jun 15, 2019 at 8:47
• Yes my main issue is overlap . Otherwise i am currently measure distance and push them but all players stay same distance and overlap . Commented Jun 15, 2019 at 9:28
• @user1924375 you might want to improve the question by stating what you are currently doing. Any suggestion here is more efficient than nothing at all. Commented Jun 15, 2019 at 15:24

its a good question but its too general. avoidance can be compeletly different in different scenarios and styles of game. first of all if you are not good in math, learn about vector math. but the most basic scenario is when you are moving forward, the other object as enemy or civilian people should move aside(let or right). so you have a forward vector. to find movement direction of avoiding object, just calculate the Perpendicular vector of player forward movement. next step is to check if there is open space in left o right or add some random direction for reality or randomness.