1. This paper presents a global search algorithm that is capable of generating multiple novel trajectories for Spacetime Constraints (SC) problems from scratch. The key elements of this search strategy are a method for encoding trajectories as behaviors, and a genetic search algorithm for choosing behavior parameters that is currently implemented on a massively parallel computer. 2. The Spacetime Constraints paradigm, whereby the animator specifies what an animated figure should do but not how to do it, is a very appealing approach to animation. However, the algorithms available for realizing the SC approach are limited. Current techniques are local in nature: they all use some kind of perturbational analysis to refine an initial trajectory. 3. Finding globally optimal solutions to SC problems is hard for two main reasons 3.1 Multimodality¡ªeven when the problem is suitably discretized, there are an exponential number of possible trajectories that a creature can follow, many of which may be locally optimal or near optimal. 3.2 Search-space discontinuities¡ªa small change in the behavior of a creature¡¯s actuators can lead to a large change in its trajectory. 4. Algorithm outline 4.1 A dynamics module simulates a physically correct virtual environment in which the effects of creature behaviors may be tested by trial and error. 4.2 A behavior module generates such behaviors using a parameterized algorithm that is based on the concepts of stimulus and response. 4.3 A search module uses a genetic algorithm to choose values for the stimulus and response parameters that will generate near-optimal behaviors according to the evaluation criteria for the given SC problem.