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