OpenCL Alien Invasion Simulation

The goal of this project was to simulate a an alien invasion on Washington DC and Chicago, IL. using OpenCL and OpenGL.  

Initially, there are 4,096 red-orange-yellow triangular 'boids', each representing a person, moving through the streets and in the parka on the national mall in Washington DC.  While the size of the humans in this scene, and their rate of movement, are not to scale, the human boids avoid obstacles and each other - they never completely overlap - and cohere and align to variable degrees, creating an uneven and natural distribution of people in the scene. 

When you press the space bar, a large blue and pink UFO appears hovering over a random location in the scene.  While the human boids in the scene will flee if the UFO's get sufficiently close, the UFO's intend no harm.  If they pass over a human, this 'pod person' slows down, and loses all fear and simply wants, to love and be loved and are  filled with a sense of joy and peace.  Once a pod person, the boid takes on the color of its benevolent overlords.  

Misunderstanding the intentions of the alien visitors, and desiring to to 'keep America safe for Democracy', 15 seconds into the invasion, the military responds, sending a stream of blue and green tanks from the massive secret underground military bunker beneath the Pentagon.  (Or the secret underground bunker beneath Navy Pier in Chicago).  The tanks will target the UFO's, moving as best they can through the city - mowing down everything in its path- human and pod person alike.  Bodies of dead pod people and humans (black with small amounts of color) who cannot run faster than the tanks, will begin to litter the streets.  

Once a tank is close enough, it will engage its weapons system, consisting of lasers and energy that drain the UFO of its power until, when surrounded by 8 tanks, the UFO is destroyed.  The tanks will then identify and seek out a new target.  

To simulate natural behaviors I referenced the excellent compilation of literature (   ) on animated 'boids' and attempted to capture this behavior in my simulation. 

How to obtains and run the program:

The program can be downloaded from HERE 

Included is an executable for MacOSX 10.7.  To compile the program, you need to have libPNG installed and you must point pkg-congif to this library. To run, type ./project2 or ./project2 d for dc and ./project2 c for chicago.

Design Platform:

The program was created for my 2007 MacBook Pro, and it runs on the NVIDIA GeForce 8600M GT .  While the program is designed to be compatible with multiple systems, it is possible that the program may run more quickly on more modern machines- which might pose problems for boid navigation.

How to Control the program:

Program will run in 2 modes:  DC or Chicago.  DC is the default, but Chicago can be run as well.  This can be specified as command-line arguments to the program,
To run DC, open a terminal, change to the directory containing the program and type:  './program2 d'  or './program2 dc' .
To run Chicago, do the same but type: './program2 c' or './program2 chicago'

You can view the boids either behind a graphical representation of the area or a satellite photo.  To switch between these views, type 'm', for map.  

To navigate within the map, you can use the arrow keys to move up, down, right and left.  To zoom in, press the '+' or '=' key, to zoom out press the '-' or '_' key.  

To launch a UFO, hit the space bar.  The UFO will drop down on a random location in the city and begin 'turning people'.  

About 30 seconds after the aliens begin their invasion, the military will respond, emerging from either the Pentagon, in DC or Navy Pier in Chicago.

To exit the program, hit 'esc'.  

Boid 'Flocking' behavior:

Cohesion:  The tendancy of an individual to move toward the average position of its neighbors 

While humans wandering around the National Mall are not as cohesive as a flock of birds, to simulate natural patterns of movement, where people collect, form groups and then dissipate, I gave all humans in the population a cohesiveness degree between 0.0 and .9.  I worked on varying this value so that the population would neither look too organized, like a flock of birds, nor too disorganized- where every boid is on its own. 

Alignment:  Similar to cohesion, alignment refers to the tendency of individuals to move at the same rate and in the same direction as their neighbors.

As with cohesion, people will not always mimic the pattern of movement of their neighbors.  However, some people surely are visiting the national mall in groups targeting a similar destination, so I worked to give the population of people a variable degree of alignment, between 0.0 and 0.7.

Separation:  Separation is the inclination of individuals to avoid collisions and keep space between individuals, even in tightly packed groups. 

This is a strong force for people, who generally avoid crowding, especially in open spaces.  All individuals at the start had a degree of separation of 1.2, which means that this force contributes more strongly to the movement of the population than cohesion and alignment. 

Obstacle Avoidance:  People move smoothly around obstacles, such as buildings and bodies of water. 

This was one of the most challenging behaviors to create for my human boids.  I used the following approach:
1)  Create 3 'scan lines' - one in the direction of the velocity and two at a 30 degree angle from this orientation.  
2) Scan forward for some range until a obstacle is detected.  
     If no obstacle detected in any direction, no brake or steering force is applied
3)  If an intersection is detected, apply a braking force, inversely proportional to the distance of the boid from the object, and proportional to the magnitude of the velocity. In principle, the braking force increases as the object gets closer, and its direction is in the reverse of the forward velocity. 
4)  After applying a braking force, apply a steering force that is lateral to the forward velocity, and is most strongly weighted toward the closest intersection point.  (Eg. if the scan line on the right is closer to the object, then the change in lateral velocity will be weighted away from the right side. 

This force is applied to the velocity after the flocking behavior above is calculated.  

Obstacles are classified based on the color of the map- with water and buildings being off limits.  The boids generally speaking slow down before hitting an obstacle and smoothly steer around it.  The greatest problem came in finding a balance with the other forces on the boid (particularly when under attack).  Occasionally, the boids get 'stuck' in spots where they shouldn't be able to go.  I believe this occurs when avoiding other boids or fleeing from danger.  Similarly, though braking and steering are inversely proportional to velocity, high speeds seem to have a negative effect on the force. 

Behaviors during the "invasion"

In this behavior, the boids look within a local neighborhood and identify the positions of all threats (eg. a UFO, a pod person).  Then, the boid shifts its velocity in the reverse direction of the average position of the threats.  This way, if there are multiple threats, the boid responds to all of them.  If there is a close threat, this should shift the magnitude and the direction of the flee vector away from this proximal threat.  The boids accelerate under these conditions as well, by normalizing the vector and multiplying it by the maximum boid velocity.  

This force is applied after the flocking forces at the same time as the obstacle avoidance force.   

Boids flee UFOs and pod people, as well as the military.  The military stops for no one and will run over and kill any people in the way.  Pod people, therefore, also, flee the military.  UFO's, who just want to love and be loved, do not understand why the military is attacking and thus does not respond with force. 

'Pursue' and the creation of Pod People:  the UFO's behavior
This behavior involves the identification of a target and moving gradually toward it.  The directional vector toward the target defines the change in velocity.  In the case of the UFO's, pursue is toward the average position of the neighboring people, so that they will come to love the UFO's and become a pod person.  This is roughly the inverse of flee.  Meanwhile, the humans flee the pursuing UFO, creating an interesting game of cat and mouse.  Once the UFO has converted a person to a pod person, they no longer target it.  They trust it will go forth and spread the love. 

'Pursue': the Military's behavior
The military tanks target the UFO's.  Initially, all tanks have a target, but if there is a UFO closer, within a certain radius, the tank will shift toward the proximal UFO.  Once the UFO has been destroyed, the tanks shift to a new target. 
The 'pursuit' behavior of the tanks is different from the pursuit behavior of the UFO's.  In the absence of a second UFO, all tanks will make their way toward the invading UFO- even if it involves crossing a river and moving to the other side of town.  The navigation of the military across town can be inconsistent.  I have seen the military directly travel from the Pentagon, across the river, through winding streets, until they reach the UFO.  I have also seen the military wander in circles, repeatedly missing the right path.  

I did a fair amount of work to correct this, and I am not sure if I found the right balance.  If I had too many other forces- such as separation to keep the military from piling atop each other, then it seemed the navigation would suffer.  Ideally, there would be some sort of 'intermediate goal' map to refer to, since the correct route is not always the shortest or most direct.  However, I didn't have time to implement this sort of approach. 

Attack: the Military's behavior
  When a tank is close enough to a UFO it engages its advanced laser weapon system, which slow the UFO down, so more tanks can come.  The health of the UFO is indicated by the color, which gradually turns black until the UFO is destroyed.  This occurs when it is targeted by 8 tanks.  

Optimization Experiments: 

First un-optimized version:
    1024 people, up to 512 tanks and 64 UFOs 
    kernel time:  17ms before invasion and 29ms after invasion
    frame rate: 20.85 fr/s before invasion and 15 fr/s after invasion

First improvement:   
Instead of looping through all people, ufo's and military, loop through a random sample of people.  (Note:  My program still needs to loop through all military and ufo's for appropriate targeting).  Looping through a smaller portion of the human population means fewer global memory lookups.
    1024 people, up to 512 tanks and 64 UFOs
    kernel time: 3ms before invasion, 4 ms after invasion
    frame rate: 35 frames/s before invasion and 27 frames/s after invasion

This allowed me to increase the number of people to 4096.
    4096 people, up to 512 tanks and 64 UFO's
    kernel time: 26ms before invasion and 33ms after invasion

I assumed that decreasing sample size for each iteration would decrease the time.  Surprisingly, behavior was comparable with a sample size of numPeople / 4 and numPeople/ 8.  
       Sample size = numPeople  / 4 :  initial global kernel time = 28ms before invasion, 35 ms after invasion by 5 ufos with 10 military tanks. 
       Sampler size = numPeople / 8 : initial global kernel time = 28ms before invasion ,  33 ms after invasion by 5 ufos with 10 military tanks.

Second Improvement:
This led me to believe that, though the number of people sampled for each boid matters, there are other costs to performance.  In particular, the initiation of the invasion seems to greatly decrease performance.  When I looked into this issue, I discovered that the problem wasn't the deployment of the military or the actions of the UFO's but the problem lay with the pod people.  There wasn't any apparent problem in the pod people code, so I initially struggled to figure out what was going on.  I believe the problem was that pod people work items were next to normal people work items, and executing concurrently.  Since their code was different, the rate of execution of work items varied within a warp.  When I merged the code- so that both pod people and regular people executed roughly the same instructions, the speed improved dramatically. 
     Before: 3072 items formerly would have a kernel time of 40+ ms after running for a minute.
     After:  3072 items have a consistent kernel time of 30ms, even after running for several minutes. 

Third improvement:
I accidentally set the number of military work items to 265, not 256- a multiple of 32, which is the warp size on NVidia cards.  
    Before:  3083 items in kernel time of 27ms
    After:   3072 items in kernel time of 14ms.   


Getting the behavior to 'look right':
I often felt that just as soon as I'd get one aspect of the boids behavior right- say obstacle avoidance- then I'd have a problem with another- fleeing appropriately. When I'd tweak the flee response, it seemed that the obstacle avoidance wouldn't work as well.
If I wanted the military to move in productive directions toward the UFO target, it seemed to come at a cost of people not getting stuck in the water or off the edge of the screen.
There is much I would continue to work on in this respect if I had more time.  My biggest annoyance- I should have done separation force by computing the intersection between entities, not by the faster method I used.  I think this is why the boids thrash and get stuck.  

Further optimizations
I wanted to implement a 'binning scheme' coupled with local and shared memory so that my boids wouldn't have to look through so many individuals each cycle.  The main problem I faced figuring this out was concurrency- how to handle that fact that items had to occasionally move to new work groups, if organized geographically.  How to avoid writing into someone else's space in memory.  In the end I did not have time to figure this out, but it would be a good optimization.  

Missing features:
I could not seem to read out of a buffer from the kernel to get the current counts of people, pod people, dead people etc.  For some reason the buffer wouldn't copy over properly. I will have to tackle this in the next project.
Speed variations- I couldn't get this feature working consistently, so I had to drop it.  It would be nice to speed up the simulation to see where things end up.

OpenCL Alien Simulation