Swarming Mac Hall

CPSC 607 Project
John Brosz

Every day of the school year a swarm of students, staff, and unknowing outsiders descend upon MacEwen Student Center in search of food and seating. The goal of this project is to determine what aspects of this human crowd behavior can be modeled using simple agents. Success of this project may yield a useful tool for analyzing building usage patterns.

Up Proprosal Current Progress 607 Deliverables

Current Progress

Starting Point - startingpoint.tz

I've started with Breve code from a past crowd simulation project by Brett Hardin, Linh Lam, Lillian Tran, Phil Tzeng, and Oscar Yeung. I've started from their Phase5b.tz file.

This code features people that move randomly around a room. While moving around the room, people bounce randomly off walls and, in a fashion resembling solid, inelastic collisions, off of each other. The simulation can then initiate an emergency causing all agents to leave the room, or a sale where all agents head to a particular location in a room.

Phase 1 - Doors, Restaurants, & Movement - phase1.tz

In this step I've expanded on the door objects so that people entering the room come in through the doors. I've eliminated the initial population of people, now the room starts empty. The particular door that an agent enters through is randomly chosen from a list of doorways. There also is a constant controlling the rate that people enter the room. People that collide with the doors are removed from the room.

I've also created objects representing the restaurants. These have an in-patch (yellow?) and an out-patch (orange) that will hopefully act to expedite flow in and around restaurants. More will be done with these later.

Lastly I've slowed the speed of the people so move more like people and less like bugs or particles. I've also removed the random speed setting, giving each person a fairly uniform speed. This will be changed later.

Phase 2 - Targeting - phase2.tz

This phase introduces target goals for each person. This target is initially set to the center of the room (0,0,0). Once a person comes within 1.0 distance of the room, the goal is reset to a random position elsewhere in the room. This will hopefully will come in useful later when I want to send an agent to a specific restaurant, door, or seat.

At each iteration agents check the direction to the target against their current direction and gradually adjust their current direction to match the target direction. This gives the gentle cornering behavior that can be seen after people reach their targets. Significant differences between current direction and target direction cause the person to slow down. This avoids scenarios where people endlessly circle their target. Gradually the person's original speed will be restored as their current and target directions become aligned.

Phase 3a - Wall Collision Handling - phase3a.tz

I was very dissatisfied with the existing wall collision handling where people randomly bounce off wall. Unfortunately this was a tricky problem to solve limited information yielded by Breve Shapes. By creating new wall objects and remembering and applying some long lost linear algebra I have achieved something I am happy with and at least partially seems to resemble people walking around obstacles.

When collision happen between people and walls the system first offsets the person so he/she no longer occupies the same space as the well. Then the current direction of the person is adjusted away from the target direction, towards the nearest corner of the wall. The person's speed is not reduced due to this direction change to keep people from "stalling out" at walls.

After a great deal of tinkering people no longer escape the room or walk through obstacles. Occaisionally a person will get stuck in a corner but this does not seem to be a major problem (yet).

Phase 3b - Wall Avoidance - phase3b.tz

People don't just walk around walls when they actually collide with them. As a person notices a wall they want to bypass they usually pick a side to go around and head in that direction. This is what I call avoidance.

To acheive this, as each person moves I check the person's distance from each wall. Walls closer than a threshold are tested to see if they lie between the person and the person's target. If so, the person alters their direction to head around the closest corner of the wall.

Phase 4 - Person-Person Collision Handling - phase4.tz

Collision handling in this scenario is handled very simply. First I find the vector between the two colliding people. I use this vector to check the distance between the people, if they're intersection I each person back along the vector appropriately. I also adjust the direction of travel to match the displacement direction.

This seems to work well, the people in the simulation now "slide" by each other. The next perhaps should be creating some sort of Person-Person avoidance that steers people away from groups of each other. This may differ greatly depending on current task the person is undertaking so I'm going to leave this for later for the time being.

Phase 5 - People States and First Test - phase5.tz

The end goal of this project is to create some sort of simulation of Mac Hall. People in this simulation have several tasks. The first is finding a restaurant, then to wait and get food, then to find a seat, and then to leave the building. It seems to me that a good way to handle is through having each person in a state based on their current "task". The states are:

For this phase I'll limit my effort to implementing the first two and the last state. So as it stands, a person is spawned near a door based on the spawn rate. This triggers the person to enter the travel to restaurant state. A restaurant is picked at random (yellow square) and the person heads towards the restaurant until they come within 2 units of the target (i.e., selected restaurant) location. This triggers a state change to the wait for food state. In this state the person makes their way to the restaurant exit patch (orange) at a reduced speed. Once the person reaches within 2 units the center of the exit patch, they enter the "travel to exit" state. A door is randomly selected and the person heads toward the door until they reach it and exit the room.

I implemented the state changes, restaurant patches, etc. and exposed several problems in the collision detection/avoidance code.

  • I changed the wall avoidance code so that people traveling around an obstacle wall, decide to go around the corner that is closest to the target. People were not always avoiding walls properly so I changed how avoidance was activated to activating whenever the person comes within 10 units of the walls corners or the closest point on the wall (the point marking the surface along a vector from the center of the wall to the person's location). After this is checked the algorithm tests that the person's target location is on the other side of the wall and that the person would pass through the wall if they walked in a straight line from their current location to the target.
  • I changed the wall collision code so that wall collisions trigger a direction change that blends the direction of displacement necessary to get the person out of the wall with the direction along the wall to the nearest corner.
  • Person-person collision resulted in people slowing down and stopping when they were travelling with a group of other people. I added changes in speed so that a person that collides with a person in the direction they're travelling slows down (and stops), whereas people collided with from the side continue at their current speed, and people collided with from behind increase in speed. This change has yielded much better looking results. We got proper looking queues and fairly realistic behavior in speeding up after slowing down due to collision. I'm particularly found of the way two lines of individuals cross through each other.
  • Lastly I changed the way in which speeds are updated. Previously increases and in speed occured at exponential rates (i.e., speed = speed * 1.1). This resulted in long times to accelerate from a stop whereas in my experience people accelerate less gradually. Change the speed increases to linear rates seems better (e.g., speed += 0.01).

    Lastly to get better flow in and out of restaurants I implemented an avoidance force for the restaurant exits. The force is applied to all agents not in the waiting for food state within 20 units of a restaurant exits. The direction of the force is manually defined for each restaurant exit object (for efficiency's sake) and generally points away from the restaurant wall and towards the restaurant entrance patch (yellow). The magnitude of this force is inversely and linearly related to the distance of a person from the restaurant exit.

    Thus far I'm pretty happy with the simulation and feel that people seem to be moving in a somewhat realistic fashion. The only thing really missing right now is a person-person avoidance force that will allow people to dodge stalled clumps of other people. Of course if I expanded the model to include many different restaurants and obstacles I would probably find more problems with behaviors.

    Hungry people are red, waiting are green, leaving are green.

    Rather than worry about these person-person avoidance forces I'm next going to tackle the issue of finding and occupying empty seats.

    Work to be done:

    • Person-person avoidance.
    • Seating finding behavior.
    • Test of enter, go to restaurant, find seat, exit scenario.
    • Add people that simply walk through the building with no stops.
    • Have people that travel at different velocities.
    • Adjust model to be more similar to Mac Hall.
    • Explore restaurant browsing.
    • Explore groups of people.
    • Make adjustment to help efficiency (i.e., avoid square roots/length calculations, reduce neighbor checks, etc).

By John Brosz, March, 2006. Comments, suggestions or questions? If so, email me (brosz@cpsc.ucalgary.ca).