Footstep navigation for dynamic crowds

Abstract The majority of steering algorithms output only a force or velocity vector to an animation system, without modeling the constraints and capabilities of human‐like movement. This simplistic approach lacks control over how a character should navigate. This paper proposes a steering method that uses footsteps to navigate characters in dynamic crowds. Instead of an oriented particle with a single collision radius, we model a character's center of mass and footsteps using a 2D approximation of an inverted spherical pendulum model of bipedal locomotion. We use this model to generate a timed sequence of footsteps that existing animation techniques can follow exactly. Our approach not only constrains characters to navigate with realistic steps but also enables characters to intelligently control subtle navigation behaviors that are possible with exact footsteps, such as side‐stepping. Our approach can navigate crowds of hundreds of individual characters with collision‐free, natural steering decisions in real‐time. Copyright © 2011 John Wiley & Sons, Ltd.