In order to control high-level goals such as walking speed and direction or position of legged robots, a locomotion controller is required. This complicated task can be solved in many different ways. The approach presented here selects the optimal gait pattern from a discrete, predefined set of possibilities to get closer to a given target position. The method is based on an off-line component: elementary gait patterns are generated by trajectory optimization using a simulation model, and an on-line component: for given robot and target positions the optimal next elementary gait pattern is chosen based on a minimization problem, and the joint space references are derived from it. To ensure feasible subsequent poses, the elementary patterns always begin and end with one and the same pose, so that they can be placed on top of each other like Lego bricks. A great advantage of this method is a straightforward transition between different motion modes, such as switching from trotting to crawling. It is discussed how many different elementary patterns are needed to ensure a stable locomotion control. Finally, in simulation and experiment, it is shown that the robot can master any obstacle course using the proposed locomotion controller.