Big, Fast Crowds on the Sony PlayStation 3

Craig Reynolds first introduced flocking to the computer graphics area by creating the Boids artificial life simulation in 1986. It was a computer model of coordinated animal motion such as bird flocks or fish schools, that allowed for collision avoidance and goal seeking. This model has had various applications such as bat swarms and penguin flocks in the movie 'Batman Returns'. A video of the early model can be seen below, further details can be found here


The above model has a complexity of O(n²), as each boid needs to consider each other boid in order to determine whether its a nearby flockmate. The complexity can be reduced to O(n), by the use of spatial hashing that keeps the boids sorted according to their location, and therefore, increase the population of the boids.

Craig now works for the US R&D group of Sony Computer Entertainment. Recently he created a crowd simulation on the Sony PlayStation 3, which extends from the very early model above. As spatial hashing is used in order to accomodate large numbers of agents, here, it forms the basis of a scalable multi-processor approach to create large, fast crowd simulations. The PlayStation 3 has Cell processor, which consists of a Power Processor Unit (PPU), multiple Synergistic Processor Units (SPU) - 6 available to the model, and an RSX GPU. The model makes use of this architecture to spatially subdivide regions, and use the multiple SPUs to update a number of regions in parallel, accelerating the crowd simulation. The model has been able to incorporate 15,000 agents running at 60fps. A video can be seen by clicking the picture below:


It is interesting to see how different architectures can be used to create crowd simulations, and how the parallel processing nature of today's video games consoles, make them low-cost and high performance platforms for parallel execution. I will be looking forward to see other general purpose applications of the Sony PS3.

GPU Crowd Simulation

This is a conference sketch by Shopf, J., Oat, C., Barczak, J., presented in Siggraph Asia 2008.

I've been talking about how I am looking into creating a crowd simulation on the GPU. The sketch states that, to their knowledge it is the first implementation of a massive crowd simulation entirely on the GPU. A video clip of the simulation can be seen by clicking the picture below, and the slides of their Siggraph Asia 2008 presentation can be found here.



The implementation consists of a simulation of 65,000 agents at realtime frame rates. They have used a framework that combines a continuum-based global path planner (similar to the continnuum crowds post I did earlier), with a local avoidance model at a finer scale.

This also allows the level of detail to change as the view is scaled. There are other conference sketches by ATI, such as 'GPU Tesselation for Detailed, Animated Crowds', and 'GPU-Based Scene Management for Rendering Large Crowds' that must have been used in the simulation.

These sketches give an interesting insight into the capabilities of the GPU for simulating massive crowds, and how the level of detail can be varied based on the scale.

Pedestrian model for a Tokyo style intersection of Oxford Circus

As has been recently announced, Oxford circus is to get a pedestrian-friendly revamp. Here is a video of a pedestrian model, first referred to me by Duncan Smith, a PhD student at CASA. The model consists of 5000 people, where a particle-based system was used to run the simulation. These particles were then replaced by animated people.

The model was created by designhive, and a map of the redesign can be seen here.




Here, the pedestrian and traffic simulation models are combined with a 3D Studio Max model of the Oxford Circus proposals, which makes this finished video very realistic.

This is a type of application, where a 3D visualisation of the model can be used to enhance the communication of ideas, and making it more accessible to others.

Continuum Crowds

This is a paper by Treuille, A. Cooper, S., and Popović, Z, presented in Siggraph 2006.
It's a real time crowd model based on continuum dynamics. The motion of crowds is controlled by a dynamic potential field, which allows it to avoid moving obstacles without the need of explicit collision avoidance. Their paper and video can be downloaded here.



This paper presents a lot of potential in creating a real time crowd simulation with large crowds. It would be interesting to see other implementations of this technique.

Netlogo to 3DMax: Pseudocode

As mentioned in an earlier post that I will be posting a pseudocode for a Netlogo to 3DMax implementation.
This pseudocode is mainly for the Netlogo traffic simulation, but I will try and make it as general as possible in order to use in other models.

Netlogo:
For each tick:
1. Output to file - x coordinate, turtle id, y coordinate

Please note, that when the data is exported into a text file, it will have other test such as 'turtle id:', all text needs to be deleted, and should leave you with 3 numbers. An example for 3 turtles (1 tick) can be seen below:



This creates a file that has the turtle id and locations for each tick. Now, our next step is to import it into 3DMax, but this time each tick represents a frame. I did this by creating a script that would store the data in an array for each frame.


3DMax:
1. Initialise an object (eg, box), for each turtle in the output file
2. Read in netlogo output file, and store xy coordinates for each object per tick in an array. (I stored the array in a 2D form [object id][xy coordinates])
3. Initialise positions of each object for first frame
4. While not end of array
5. Advance frame, and update object position corresponding to the object id in the array
6. Keep repeating step 5 till end of file is reached.
7. Render final animation

Same process for traffic lights, where each traffic light is a turtle in netlogo.