Abstract We present an automatic system to generate locomotion gaits with different speeds and styles for imaginary terrestrial creatures. Despite the great achievements in this domain, like the prominent evolutionary work by Karl Sims [1], optimal gait for animal locomotion [2], or the recent developments in the field of reinforcement learning [3,4], there are still only a few options in designing an automatic tool to make a creature run given only information on its shape. We propose a gradient free optimization approach that requires no intuition on the locomotion task, which is particularly useful when animating fanciful creatures. We search for the parameters of a periodic signal generator that minimize a given cost function of traveled distance and speed. We show that finding natural gaits is possible even without a good initial or pre-authored motion, and the resulting locomotions are both visually plausible and complex.