This paper presents a method that combines constraint logic programming with model-based simulation to efficiently generate realistic and COLREG-compliant maritime navigation paths. These paths are generated in two phases: first, an abstract path is derived based on dynamic factors such as the initial position, destination, environmental conditions (e.g., leeway), obstacles, and depth data. Second, the path is implemented in a simulation, and feedback is collected for correction. To reduce the complexity of path planning, we introduce additional constraints in the incremental refinement of path planning, based on the geometric conditions of ships’ movement. Based on preliminary experiments, this has reduced the complexity of the path search space—by up to 90%, thereby improving the overall path planning efficiency.