Rose Liu (roseliu), Elly Zheng (ellyz)
Simulate collisions between agents in a large crowd using a quadtree in parallel.
We implemented a crowd collision simulator with a parallel quadtree in OpenMP. The crowd collision simulator consists of a number of agents on a grid that are given a starting cardinal direction (north, east, south, or west), and each agent moves in their specified direction until a collision with either another agent or the grid edge. If two agents are predicted to move onto the same grid space, they bounce off each other and change directions instead of overlapping. We ran our algorithm on the GHC machines and the PSC machines to check scalability. Additionally, we also created a visualization tool with SDL to map out the agents as they move and interact with other agents on the grid to show how the crowd collision simulation works.
- Revised project goals and implementation (Rose + Elly)
- Redefined project statement from crowd control to crowd collision
- Complete sequential implementation of crowd collision simulation (Elly)
- Create visualization tool to debug unexpected behavior of collisions (Rose)
- Write small input files (grid size of 128x128) to test the validity of the code (Rose)
- Integrate quadtree-based spatial partitioning (Rose)
- Parallelize algorithm with OpenMP (Elly)
- Finish project milestone report (Rose + Elly)
- Add functions to verify that the code is working as expected (Rose)
- Analyse bottlenecks and explore optimization techniques (Elly)
- Parallelize building of quadtree and collision check algorithm
- Analyse bottlenecks and explore optimization techniques (Rose)
- Find ways to reduce the number of collision checks
- Test code with larger input files (ex. grid size of 8192x8192) (Elly)
- Experiment with PSC to test scalability (Rose + Elly)
- Gather results and examine key metrics (Rose + Elly)
- Finish our final report and prepare for presentation (Rose + Elly)
- Finalize Github repository code and documentation (Rose + Elly)