Games and experiences designed for virtual or augmented reality usually require the player to move physically to play. This poses substantial challenge for level designers because the player’s physical experience in a level will need to be considered, otherwise the level may turn out to be too exhausting or not challenging enough. This paper presents a novel approach to optimize level designs by considering the physical challenge imposed upon the player in completing a level of motion-based games. A game level is represented as an assembly of chunks characterized by the exercise intensity levels they impose on players. We formulate game level synthesis as an optimization problem, where the chunks are assembled in a way to achieve an optimized level of intensity. To allow the synthesis of game levels of varying lengths, we solve the trans-dimensional optimization problem with a Reversible-jump Markov chain Monte Carlo technique. We demonstrate that our approach can be applied to generate game levels for different types of motion-based virtual reality games. A user evaluation validates the effectiveness of our approach in generating levels with the desired amount of physical challenge.