Update 3

This week we have worked on making some improvements to existing code, but we have added some new features as well. We had quite a large issue before regarding the transition of agents to new cells and the subsequent update of the densities. Basically, what happened was that every time an agent left a cell, the density in that cell became zero during one frame. In the very next frame, the density value was normal again. This could actually be seen in the color representation of each cell. It was of great importance that we dealt with these sudden density drops as they could have turned out to cause problems later on. So that is what we did! And we succeeded! The solution was rather simple. By letting the agents themselves manage the transition into new cells and the update of densities, the problem was solved.

The video below is that from the previous post were you can clearly see that the cells flicker.

In the following video, the change in color is much smoother and the flickering is completely gone.

As mentioned before, apart from the improvements made, some new features have been added to further enrich the visualization. We have added green arrows pointing in the direction of the preferred velocity and red arrows that visualize the velocity component that is added upon collision to avoid other agents. The actual velocity is the sum of these two vectors. This way of visualizing the different velocities turned out much better looking than visualizing the actual velocity itself. It clearly shows what happens when agents try to avoid fellow agents.

update3pic1

We also added the possibility to show the trajectories of each agent consisting of a line connecting its current position and its target position. This looked quite neat too.

update3pic2

And finally, here is a video showing these visualizations in action!

Update 2 – Prototype 1 Completed

We are excited to announce that our first prototype is now complete and fully functional. Since last time, we have made a lot of general improvements of our code. We can now, to some extent, customize the way we want the program to run, straight from the Unity UI, which is really convenient.

Most importantly, we have implemented a way of handling collision between the agents so that they keep their distances at all times. Our approach to narrowing down the number of agents that need to be compared every frame is using a method similar to the particle-in-cell method, which is otherwise used to determine the densities and velocities in every cell. For each agent, we always look at all the agents in the same cell. It is when we look at agents in adjacent cells that we have implemented the method mentioned. Basically, what the algorithm does is that it only considers agents close to the boundaries of the cell, and for each of those agents it uses the agent’s position relative to the cell to determine which of the adjacent cells are of interest. In other words, the algorithm makes sure so that collision handling is only carried out for agents in the cells closest to the agent in question.

However, it doesn’t stop there, as we have added even more to this first prototype. In fact, the particle-in-cell method, which calculates the density field, has been implemented already at this stage. We now have a matrix with the density-values for each cell and it is only used, at this moment, to change the color of the cell, which looks pretty neat. A cell with the density 0 has a dark grey color and as the density increases, the color becomes much lighter until it is completely white. This is one of the features which can be enabled directly from the Unity UI.

Back to the collision handling algorithm. When testing this new algorithm we have noticed that it performs really well, in most situations. It performs well, as long as it doesn’t have to deal with large clusters of agents that are moving inwards toward a point in the center. In this scenario, what happens is that the agents keep on pushing inwards, causing the agents in the middle to be crushed and sort of fused together. This is basically what happens when we spawn agents in the outer cells and tell them to go to the exact opposite side of the grid. We end up with the scenario described above. This is not an issue though, because when we have implemented the unilateral incompressibility constraint later on we will never arrive at this scenario ever again. In fact, it seems, at this stage, that our collision handling algorithm will work really well in collaboration with the UIC, upon its implementation, and we really look forward to seeing them in action together.

Update 1

Today, we have come a long way since we first started off with the very simple random movement generator. First of all, a uniform quadratic grid has been implemented and we have made preparations for storing the velocity and density fields later on. The grid itself is an object and consists of several cells, which, in turn, are separate objects themselves. This way of implementing the grid greatly simplifies the way we handle all of the agents. For example, the spawning of the agents is carried out in each cell, which makes it really easy for us to specify in which part of the grid we want the agents to spawn. The idea is that you will eventually be able to choose which spawn configuration you want, simply by the input of a string. Another great advantage with treating every cell as a separate object is that each cell, by itself, can keep track of every agent within its boundary just by keeping the object references in a list. It is then really easy to pass on an agent to an adjacent cell, when necessary.

At this stage, the global planning is really easy. The agents are spawned in the outer cells, at random positions within each cell. The global planning is carried out simply by constructing a target position at the exact opposite side of the grid. The agents then move straight to that position without considering the other agents.

This is what our program does at this moment and the only thing we need to further implement, before the first prototype is completed, is a simple way of avoiding collision among the agents.

The Very First Iteration

The first iteration of our program was really simple. It included a grey background and green particles moving around randomly. Every particle had a red circle around it showing its ”personal space”. Basically, the ”personal space” is the circle into which no other particle should enter. At this moment, however, no collision handling had been implemented. As a result of that, not only were the personal spaces intruded on, the particles even went straight through each other.

At startup, the particles were spawned in random locations and began to move. The random movement algorithm was really simple. Basically, for every frame, small random velocity changes were applied to every particle and their positions were updated accordingly.

This was our very first iteration of the program and laid the foundation for the whole project.

Project Specification

Background

Simulation of the movement of large dense crowds has numerous applications spanning across several different areas. Whether you’re animating really large armies, for films and video games, or whether you are studying the effectiveness of evacuation procedures in big venues, an effective way of simulating the behaviour of crowds on such a large scale is key to your success. Innovative methods need to be provided to be able to handle such massive amounts of data and to get results as close as reality as possible. We will tak on this challenge by using a dual representation of the crowd, both as discrete agents and as a single continuous system.

Project Layout

  • Background research
    Involves researching the main paper and other useful references to prepare for the implementation of the algorithm.
  • Algorithm

– Global planning
Determines the preferred velocities for each agent, ignoring the presence of other agents.

– Continuous representation
The positions and preferred velocities of the agents, respectively, are projected onto a grid where they are stored as two continuous density- and velocity fields.

– Unilateral incompressibility  constraint (UIC)
By solving a continuity equation, while maintaining the UIC, the continuum velocity is determined, ensuring that the maximum density is never exceeded.

– Calculation of new position
By interpolating between the continuum velocity and the agent’s own preferred velocity, taking the crowd density into account, the actual velocity is determined. Thus, the new position (after one time step) can be calculated. A small correction is applied to prevent pairwise collision.


  • Optimization
    The search of more effective code, to further improve performance.
  • Demonstration
    Simulation of different scenarios and rendering of videos and screenshots.
  • Finalization of report
    Here, the final draft of the report is produced.
  • Presentation
    The preparation leading up to our final presentation.

Implementation

In order to facilitate the integration of our project in larger projects, the Unity Game Engine will be used and all the scripting will be don in C#. Additionally, since assets in Unity are already provided, it is convenient to use this environment. These assets, though, will not be used from start. Instead, simple objects will be used as placeholder for simplicity.

Prototypes

Prototype 1

  • Very simple global planning where agents are told to go to the opposite cell on the grid.
  • The grid will be implemented, but will only be used to simplify calculations.
  • No UIC will be implemented at this point.
  • When calculating new positions, prevention of pairwise collision will be used.

Prototype 2

  • Very simple global planning where agents are told to go to the opposite cell on the grid. The same as before.
  • The grid will be implemented and used the way it is supposed to.
  • The UIC will be implemented.
  • When calculating new positions, prevention of pairwise collision will be used.

Prototype 3

  • An effective algorithm for global planning will be implemented.
  • The UIC will be implemented.
  • When calculating new positions, prevention of pairwise collision will be used.
  • This will be the algorithm in its entirety, with all the necessary functions, although still visualized with balls.

Time Plan

Task Due date
Prototype 1 2015-02-15
Prototype 2 2015-03-08
Email WIP title, authors and supervisor to carin@kth.se 2015-04-01
Prototype 3 2015-04-12
WIP check-reading 2015-04-14
Voluntary presentation training with WIP, apply to mart@kht.se 2015-05-13
Presentation of project according to schedule 2015-05-18
Submission of final report 2015-05-21