We present a novel, general-purpose Model-Predictive Control (MPC) algorithm that we call Control Particle Belief Propagation (C-PBP). C-PBP combines multimodal, gradient-free sampling and a Markov Random Field factorization to effectively perform simul- taneous path finding and smoothing in high-dimensional spaces. We demonstrate the method in online synthesis of interactive and physically valid humanoid movements, including balancing, recov- ery from both small and extreme disturbances, reaching, balancing on a ball, juggling a ball, and fully steerable locomotion in an en- vironment with obstacles. Such a large repertoire of movements has not been demonstrated before at interactive frame rates, espe- cially considering that all our movement emerges from simple cost functions. Furthermore, we abstain from using any precomputation to train a control policy offline, reference data such as motion cap- ture clips, or state machines that break the movements down into more manageable subtasks. Operating under these conditions en- ables rapid and convenient iteration when designing the cost functions.