February 7, 2019

Steering Behaviors - or how not to evacuate a building

One good book I read is The Unthinkable: Who Survives When Disaster Strikes - and Why. It discusses an aircraft accident where many people died even though the computer simulations said they should have survived. What went wrong? The answer is that the computer simulations assumed people move in the same way as water.
For a long time, engineers assumed people would move out of a building like water. They would fill the space they had, coursing down the staircases and flowing out to safety like a river of humanity. Buildings were constructed accordingly. The problem is, people don't move like water.

So if you are trying to model real people, you have to take pain and fear into consideration. People make decisions, they stumble and fall, and they fill up space unevenly. On their way out, they pause to rest when they can. But if you are just trying to make a simple game, you can treat people like water. Treating people like water in games is also known as Steering Behaviors. These individual behaviors are supposed to work like Lego bricks - you can combine several of them to get the final character behavior you need.

Let's say you have a character that's following a path. It will work fine until the character is meeting another character moving in the opposite direction? One solution now might be to calculate a new path with some pathfinding method like A* (A star). But this will take some unnecessary computation power. A better way is to use these steering behaviors, which will make the character avoid the other character and then continue following its path.

The following shows a combination of the behaviors:
  • Seek - move along the flowfield direction
  • Solid obstacle avoidance - is in this case finding the closest point on the wall (the walls are just lines), and if the character is predicted to collide with the wall it should steer away from the closest point)
  • Moving obstacle avoidance - is in this case moving a character away from the character it's colliding with. So it's not a steering behavior but a commonly used cheat to avoid intersecting characters

While researching steering behaviors I learned that the most difficult of the behaviors is avoiding moving obstacles, so there are multiple algorithms trying to deal with the problem. 

Algorithm 1. The most simple obstacle avoidance behavior is trying to just avoid the most dangerous obstacle by predicting where it will be in the future, while ignoring all others.


Algorithm 2. Is trying to avoid all of the dangerous obstacles by predicting where they will be in the future, and then scale the prediction so that obstacles closer to our character are considered more dangerous. 


Algorithm 3. This one has a name and it's Power Law. It's similar to Algorithm 2, but is also calculating an energy. As you can see, the characters are finding their way through the congestion in a slightly more realistic fashion.


Algorithm 4. RVO. This is what Unity is using to make characters avoid each other on their navmesh. I never implemented this behavior but might do it in the future.

As you can see, some of the characters are intersecting with each other. This is a commonly used cheat and the idea is to avoid congestion, you shrink the radius of each character until it's not anymore stuck. This cheat was used in the game Planet Coaster (as explained in this article) and they sold millions of copies, so it should be allowed in your game as well!  

No comments:

Post a Comment