In this paper, we develop a new approach based on discrete mechanics to a gait generation problem for the compass-type biped robot. First, both continuous-time and discrete-time models of the compass-type biped robot are derived. We next formulate a discrete gait generation problem for the discrete compass-type biped robot as a finite dimensional nonlinear optimal control problem and show an algorithm to solve the problem based on the sequential quadratic programming. Then, we propose a transformation method that converts a discrete-time control input into a continuous-time zero-order hold one and apply it to gait generation for the continuous compass-type biped robot. Some simulations are also shown in order to verify the effectiveness of our new approach.