The complexity of a legged robot's environment or task can inform how\nspecialised its gait must be to ensure success. Evolving specialised robotic\ngaits demands many evaluations - acceptable for computer simulations, but not\nfor physical robots. For some tasks, a more general gait, with lower\noptimization costs, could be satisfactory. In this paper, we introduce a new\ntype of gait controller where complexity can be set by a single parameter,\nusing a dynamic genotype-phenotype mapping. Low controller complexity leads to\nconservative gaits, while higher complexity allows more sophistication and high\nperformance for demanding tasks, at the cost of optimization effort. We\ninvestigate the new controller on a virtual robot in simulations and do\npreliminary testing on a real-world robot. We show that having variable\ncomplexity allows us to adapt to different optimization budgets. With a high\nevaluation budget in simulation, a complex controller performs best. Moreover,\nreal-world evolution with a limited evaluation budget indicates that a lower\ngait complexity is preferable for a relatively simple environment.\n