Massively Multithreaded Crowd Simulation – Paradise

Crowd Flow, Island Paradise, Multithreading, and more

The Paradise tech demo is a massive crowd simulation of a 1000 individual AI’s all walking toward shared goal locations. Each AI utilizing one of many shared flow maps for navigation, and its own individual steering for avoidance. Once an individual AI actually reaches their goal they will randomly swap to another goal location and begin walking toward this new location.

The idea behind Paradise was born from AMD’s Froblins paper and demo. The key difference between AMD’s implementation and Paradise is where multithreading takes place. In Froblins all threading was offloaded to the GPU while in Paradise all threading was run on the CPU, implemented with Intel’s Thread Building Blocks.

Shown at the Spring 2011 USC Demo Day

the Island

in the wild

the Masses

the Tech

Libraries

» Intel Thread Building Blocks

TBB was used for their general purpose task based threading model. Each AI was executed in an individual general purpose thread.

» Ogre Render

Ogre was the 3d renderer used to display the simulation. Post effects like Bloom as well as the Ocean were modified shaders provided by Ogre.

» Ogre Animation

Animating the many characters were performed through Ogre’s built in animation support.

» Havok Physics

The entire simulation was driven with Intel’s multithreaded physics engine. Each AI was supported by a rigid body capsule simulating against a mesh terrain.

» OpenSteer

Local steering for each AI was provided through the OpenSteer library. Additional wandering, seeking, and local avoidance where used per AI.

Utilities

» World Machine

An arbitrary terrain generation program that was used to create the Island driving the entire simulation.

Assets

» Loopix-Project

Provided free tropical trees, shrubs, and palms that litter the large island.

» 3DRT

Purchased the main character model from www.3drt.com

» ATB

Used the song, No Fate, as the background song for the Paradise video.

the Glorious Code – snippet

Just a taste

std::vector<CrowdCharacter*> CrowdSceneCreator::createAIs(
    const unsigned int number,
    const unsigned int lower,
    const unsigned int upper,
    const std::vector<std::vector<Ogre::Vector2> >& excludes){

    unsigned int remaining = number;
    unsigned int x,y;
    float height;
    std::vector<CrowdCharacter*> crowd;

    int x1, x2, y1, y2, y_max, x_max, y_min, x_min;

    while(remaining){
        x = rand() % x_width;
        y = rand() % y_width;

        bool exclude = false;

        for (unsigned int i = 0; i < excludes.size(); i++){
            if (excludes[i].size() != 2)
                continue;
            x1 = excludes[i][0].x;
            y1 = excludes[i][0].y;

            x2 = excludes[i][1].x;
            y2 = excludes[i][1].y;

            y_max = (y1 > y2) ? y1 : y2;
            x_max = (x1 > x2) ? x1 : x2;
            y_min = (y1 < y2) ? y1 : y2;
            x_min = (x1 < x2) ? x1 : x2;

            if (x < x_max && x > x_min && y < y_max && y > y_min){
                exclude = true;
                break;
            }
        }

        if (!exclude){
            height = getHeight(x,y);

            if (height >= lower && height <= upper){
                crowd.push_back(createAI((float)x,(float)y,CrowdCharacter::TAN_RED));
                remaining--;
            }
        }
    }
    return crowd;
}