Post date: Mar 6, 2012 12:29:26 AM
1. What is this
This project is about to write a massive particle simulation using OpenCL and OpenGL.
Detailed description of this project on the course website is here: http://joysword.com/doc/cs525/p2.html
(To make it available longer, I copied the source code from Andy's course webpage and pasted it to my server)
I finished C level requirements and some of the B levels. And under some conditions, this application can run on different map textures, which is an A level requirement.
The video I created as a demonstration is here: http://youtu.be/Yn7gyIxgRb0
Go to the bottom of this page to download the source code and the resource. Or you can scroll down to the bottom of this page, you can find source code in attachment.
2. How to Start
It is recommended that you have an AMD ATI card with AMD APP SDK to run this application. I'm not sure if there will be any problem if run using nVidia card.
And it should be running on Mac with Xcode.
You should first install OpenGL, GLUT and AMD APP SDK on your mac.
When you are ready, follow next steps to start:
Open cs525p2test.xcodeproj with Xcode;
Go to main.cpp and simulaucer.cl, change all the file paths in them to your path. (Something went wrong with the relative path, so I have to use absolute path)
Build and run.
If you change image_width and image_height in main.cpp to 2000 and change the names of texture files, you can see another city. But because of the coordinate of target is still the same, boids may act weird.
3. What I did
3.0 Introduction
3.0.1
Development environment is Mac OS 10.7.3 with Xcode 4.3. Graphic card is AMD Radeon HD 6770M(1024MB).
3.0.2 Basic Plot
People are visiting United States' famous heart, the Washington D.C, some of them are going to the White House, some are going to see Abraham Lincoln and some are going to take the metro. Life is beautiful and peaceful.
As an engineering major student, you have a lot of homework and projects to do, especially in Professor Andy Johnson's courses. You don't have time to play with friends, with family. You are very envy about these happy people in DC.
So you decide to destroy them and turn them into zombies. First, if they arrive Chicago, you don't have to submit projects any more as long as they are in front page of Sun-Times; Second, they may find Andy and have a fight with all those plants in his backyard. No matter which side will during plants vs zombies, you'll be very happy.
You send in an army of yellow UFOs consists of at most 5 of them by pressing A, each time for one saucer.
When you see people in pink (not have a target to go) or blue (have a target) turned white and shiny in horror and finally turn to red zombies eating other citizens, you are very satisfied.
But you poor guy who is totally insane want more. You zoom the map by holding right mouse button and move up and down, you pan the map by holding left mouse button and move around. You even press SPACE BAR to freeze the time so that you can enjoy this moment more cheerfully. You can also change map view by pressing M.
The story should not end here, justice shall be done, human kind deserves a bright future. BUT, I didn't make it to finish implementing the army, so our boys from Rangers won't be the hero to save the world.
If you find your conscience back, press ESC to exit.
3.1 Behavior rules
3.1.1 Citizens
Citizens with a target will mainly go toward it. After they arrive, they will just hanging around, like those citizens who never has a target.
Citizens will not align with others like animal, but they will avoid to hit other citizens when they are in normal.
During dangers, citizens will mainly run away from dangers with a lower will to get avoid others. And if they once had a target, now they forget it totally.
3.1.2 Saucers
Saucers will search for citizens in certain range and move towards them. If it is close to one citizen, it will chase directly to that poor guy.
Saucers will keep out of other saucers' way.
Saucers may hit the Washington Monument, I didn't implement the collision avoiding mechanism.
3.1.3 Zombies
Zombies will chase to the nearest citizen, basically.
3.1.4 Army (not implemented)
Most Army will set off from the Pentagon, and their goal is the Whiskey Hotel.
Army will fight zombies and saucers during their way to the Whiskey Hotel, but they won't search for them.
After they arrive, some of them will hold there, while others will spread to the city to save citizens.
----
I prefer not add source code for this part because it will be too long. If you are interested, please download the source code, this part is in 'si
mulaucer.cl'.
3.2 Implementation
3.2.1 Boids structure
struct Boids
{
float pos[2]; //position
float vel[2]; //velocity
int type; //type, can be citizen, saucer, zombie or army
int target; //where the boids will go
int seeStrange; //if it feels in danger
};
3.2.2 Seeding algorithm
The boids are randomly seeded in the map, with 60% probability around Mall area and 2 of 3 boids will have a target.
for (pCounter = 0; pCounter < orignumBoids; pCounter ++)
{
// 60% of boids will be in Mall area
int ttt = rand() % 10;
int tX, tY;
if (ttt<6)
{
tX = (rand() % 880) + 352;
tY = (rand() % 428) + 588;
//check if this area is accessible
while(texturePtr[(tY*image_width + tX )] >= 0.005){
tX = (rand() % 880) + 352;
tY = (rand() % 428) + 588;
}
}
else
{
tX = (rand() % image_width);
tY = (rand() % image_height);
//check if this area is accessible
while(texturePtr[(tY*image_width + tX )] >= 0.005){
tX = (rand() % image_width);
tY = (rand() % image_height);
}
}
origBoids[pCounter].pos[0] = mapVal(tX, 0, image_width, xmin, xmax); //change the coord system
origBoids[pCounter].pos[1] = mapVal(tY, 0, image_height, ymax, ymin);
origBoids[pCounter].vel[0] = (rand() % 100)*0.001;
origBoids[pCounter].vel[1] = (rand() % 100)*0.001;
origBoids[pCounter].type = citizen;
// 2 of 3 boids will have a target
int _target = (rand() % 3);
if (_target % 3 != 0)
{
int _which = (rand() % 3);
switch (_which) {
case 0:
origBoids[pCounter].target = Whisky_Hotel;
break;
case 1:
origBoids[pCounter].target = Lincoln;
break;
case 2:
origBoids[pCounter].target = Smith;
break;
}
}
else origBoids[pCounter].target = no_target;
origBoids[pCounter].seeStrange = 0;
}
The saucers are randomly spawned from a random direction at first, but won't show up or move or take part in calculation until users let them do.
for (int i=orignumBoids;i<orignumBoids + MAXNUMSAUCER;i++)
{
switch (rand()%4) {
case 1: //left
h_particleData[nd * i + 0] = -2000;
h_particleData[nd * i + 1] = rand()%2000 - 1000;
h_particleData[nd * i + 2] = 1;
h_particleData[nd * i + 3] = -h_particleData[nd * i + 1] * 0.001;
h_particleData[nd * i + 4] = saucer;
h_particleData[nd * i + 5] = no_target;
h_particleData[nd * i + 6] = 0;
break;
case 2: //right
h_particleData[nd * i + 0] = 2000;
h_particleData[nd * i + 1] = rand()%2000 - 1000;
h_particleData[nd * i + 2] = -1;
h_particleData[nd * i + 3] = -h_particleData[nd * i + 1] * 0.001;
h_particleData[nd * i + 4] = saucer;
h_particleData[nd * i + 5] = no_target;
h_particleData[nd * i + 6] = 0;
break;
case 3: //bottom
h_particleData[nd * i + 0] = rand()%2000 - 1000;
h_particleData[nd * i + 1] = -2000;
h_particleData[nd * i + 2] = -h_particleData[nd * i + 0] * 0.001;
h_particleData[nd * i + 3] = 1;
h_particleData[nd * i + 4] = saucer;
h_particleData[nd * i + 5] = no_target;
h_particleData[nd * i + 6] = 0;
break;
case 0: //up
h_particleData[nd * i + 0] = rand()%2000 - 1000;
h_particleData[nd * i + 1] = 2000;
h_particleData[nd * i + 2] = -h_particleData[nd * i + 0] * 0.001;
h_particleData[nd * i + 3] = -1;
h_particleData[nd * i + 4] = saucer;
h_particleData[nd * i + 5] = no_target;
h_particleData[nd * i + 6] = 0;
break;
}
}
3.3 Specs
Num of Boids: about 3600.
Resolution of Textures: 1992 * 1992
3.4 Issues
1. Because of some issue with the collision map and some issues with detection algorithm, boids may stuck.
4. What I've been through - The Development Log
You may already find that I'm behind schedule again this time. These projects are difficult to start.
2/8 - 2/9 did research on boids; scanned 2010 projects.
2/10 installed Adobe Illustrator, did research on how to get map information, both for collision detection and for displaying.
2/16 read the Galaxy sample; did research on my ATI card on desktop computer and my Intel integrated card on Macbook and some header files of CUDA; installed AMD APP SDK, CUDA Toolkit and GPU Computing SDK; started to draw maps.
2/17 read 2010 projects in detail; wrote the plot (principle of actions) for the simulation; continued to draw maps.
2/18 watched again the speak-very-fast-guy intro video from AMD; read Ch2 of Heterogeneous Computing with OpenCL (HCWOCL); built development environment while trying to run examples from HCWOCL;
2/19 wrote the main application based on 2010 project and Galaxy code (to be continue); continued to draw maps; started to write the pseudocode of the kernel.
2/20 continued to write the main application based on 2010 project and Galaxy code.
2/20 Issue: found that my plot, which contains 7 different kinds of boids, is not meeting the requirement. Need to add "goal seeking" and "obstacle avoid". Due to the complexity, I decided to cut off unnecessary fancy features in my plot and keep only 4 basic kinds of boids, Saucers, Human and Army.
2/21 think about path finding algorithm;
2/21 Issue: need an algorithm to generate boids information;
2/21 basically finished the main application (What a long 'going through' of 2010 project and Galaxy code); read Galaxy kernel;
2/21 scanned Ch 10 of HCWOCL.
2/22 did research on Ch 4 of HCWOCL.
2/23 wrote a new plot to make it simpler.
2/25 did research on project 2010 kernel code
2/25 read several papers roughly and research some of them
2/26 started to implement ideas about simulation
2/27 found that I may not finish the whole project in time, so re-wrote the plot, this time in a very detail, code-friendly way.
2/27 Issue: there still some features in the plot that I've no idea how to implement.
2/28 wrote kernel sketch for citizen, zombie and army.
2/29 thought I should make things work asap, so make a simple main function and compile it successfully.
3/1 Issue: how to load initial data info.
3/1 initial part can be successfully run.
3/2 dealt with kernel reading.
3/2 dealt with render textures for whole night.
3/3 - 3/5 didn't have to time to record, did a lot of work, made lots of things that 90% complete to 100% complete (this part is almost as difficult as the first 90%), solved a lot of problems, caught up the progress a lot but still one day later.
5. What I Learned
I did it not as well as I imagined at first, but I do learn a lot. Way more than what I did in Project 1.
First of all, when you plan to purchase a computer for you education, you'd better think through it to decide what to purchase.
Second, I should have make things work asap. But I guess I can achieve this if there was no issue with my laptop.
But, I do need to change the way I worked. I'd better focus on sub-problems other than consider them as a whole. It made me exhausted and frustrated.
And I should have used other's project that has successfully compiled and built before and make change of it to make it a new project, instead of create a new project and wrote it based on other's project. This may cause unexpected compiling and building problems.
This time, I tried this but failed because platform issues. So I write my own code, but after the qjulia version of Galaxy code was released, I should have use that as the new start point. It's better than continue my work.
And may not start make change too early. Sometimes I only changed part of code that should be changed together.
The format of textures are different in my project 1 and those guys 2 years earlier, but I failed to change all places that should be changed together, which makes I spent whole day to see why the texture just don't come up.
And there is more. Unfortunately, on the last few days, I have to keep working, keep making progress and didn't have time to record what I encountered, the reason of it and how I resolve it.
But I think I'll recognize them or avoid them subconsciously when I meet them next time.
And life is life, you won't know when something will happen. You should consider unexpected problem outside the project domain when you planning the project.
This time I was [beep---] by some piece of shit private affair.
6. Who to Thank
Andy Johnson http://www.evl.uic.edu/aej
Kahler http://dotslashed.com/gpu_project2.html
Bhargava http://www2.uic.edu/~rbharg2/cs525p2/index.html
Craig W. Reynolds http://www.red3d.com/cwr/
and
Shao Ming, Sun Shouqian, GPU-BASED PARALLEL ISED REAL-TIME CROWD SIMULATION, Computer Applications and Software, Vol.28 No. 1, pp.8 - 25
Shao Ming, GPU-based motion path matching and crowd simulation, A Dissertation Submitted to Zhejiang University for the Degree of Master of Engineering
CraigW.Reynolds, Steering behaviors for Autonomous Characters, Sony Computer Entertainment America 919 East Hillsdale Boulevard Foster City, California 94404
Craig W. Reynolds, Flocks, Herds, and Schools: A Distributed Behavioral Model, Computer Graphics, 21(4), July 1987, pp. 25-34