Origami-based mechanisms have emerged as a promising solution for developing locomotion systems. Its light-weight nature, scalability, and possibility for 2D monolithic manufacturing makes origami an attractive option for various applications, such as mobile robots and meta-surfaces. While various types of origami-based locomotion exist, constant-height walking locomotion does not have an origami-based solution yet. To achieve this, we present a 2-DOF crease pattern with two internal vertices and geometric constraints that can perform the required output path. A parametric study performed on the presented pattern reveals many different feasible geometries. Subsequently, these geometries are evaluated based on their capabilities to produce a path with minimized displacement along the Z-direction and minimal change in velocity of the end effector during propulsion. As a demonstration, we then utilized these results to optimize the design of a locomotion system for active surfaces. Finally, the results are verified with experiments using a physical prototype. In conclusion, the analysis of the results provides valuable insights in the behavior of the crease pattern, which can be utilized for designing and optimizing an origami-based locomotion system for other applications with different requirements.