Crowd simulation serves as an important tool in architecture, where efficiency and safety could be improved with the knowledge of how large groups of people behave, and computer graphics as well as entertainment industry, where demands of animating large amounts of avatars exist. This project has implemented and evaluated an approach of crowd simulation based on the Principle of Least Effort, a fundamental rule of human behavior. The approach is capable of simulating thousands of agent in real time, and can be parallelized naturally to utilize the power of multiprocessor.
The approach has been implemented using C++ and OpenMP. Results show that the approach generates smooth, collision-free, and visually plausible agent trajectories. To evaluate the approach in a quantitative manner, a set of metrics have been defined, and a set of test cases have been selected. By comparing the approach with RVO, a similar approach that does not consider the Principle of Least Effort, the evaluation shows that optimization based on the principle leads to agent trajectories that cost less effort and time. In further case studies, the approach has been proved to be able to generate a number of emergent phenomena verified in real crowd.