Crowd simulation plays a critical role in modern films, games, and architectural design. However, despite decades of algorithmic improvements, crowds use sub-optimal heuristics, are primarily constrained to 2D surfaces, and show few if any social dynamics. This dissertation proposes that a solution to these problems lies in altering how each agent perceives its environment as opposed to new obstacle avoidance algorithms. First, this dissertation presents a theoretical look at optimal agent movement. Next, in order to place crowds on arbitrary 3D manifolds, algorithms are proposed that change how each agent perceives its environment. The resulting crowds move naturally across a large range of surfaces with up to 100,000 triangles in real-time. Additionally, these algorithms are shown to work in real-time strategy game settings by using the GPU to determine which parts of the surface are visible to each agent. Results show that these algorithms can do visibility testing for up to 200 agents in real-time. Lastly, these same principles are used to create believable social dynamics with crowds based on the transactional analysis area of psychology. These social dynamics allow agents to stop and talk, pair walk, and have repeated social interactions. All this is done by changing how agents perceive the world based on their social reward.



College and Department

Physical and Mathematical Sciences; Computer Science



Date Submitted


Document Type





crowd simulation, 3D crowd simulation, optimal crowd simulation, social crowd simulation