Virtual Agent Navigation in Open Spaces using Iterative Shrinking Polygons

Populating an urban environment with a virtual crowd provides a dynamic element to an otherwise static scene; bringing the virtual environment to life. One of the fundamental components governing the fidelity of the scene is the realistic simulation of the crowd behaviour. To create a believable crowd simulation one group of methods considers constructing a graph covering the space available to the virtual agents and subsequently performing path planning to allow the agents to navigate their environment by traversing the edges of the graph. To avoid computationally expensive path planning algorithms there exists a tradeoff between the number of edges in the graph and the amount of available space which an agent can visit. In order to alleviate this problem we propose to compute the straight skeleton to provide an initial covering of the environment. This is subsequently augmented using iterative shrinking polygons to generate additional edges in the larger open spaces. The technique developed requires limited knowledge of the urban environment, processes the relevant information automatically and is illustrated in this paper to control the behaviour of a virtual crowd in real time