Trajectory planning aims to provide a time-related control target that contains the concerned states. For an underactuated surface vehicle (USV), planning challenges include limitations on curvature, speed, acceleration, and jerk. These challenges are relevant for the precise control of USVs. To solve these problems, an on-line double S method and multi-scale A* trajectory planning algorithm is proposed by integrating Reeds–Shepp curves (RSC), where a quad-tree-based graph is used for path planning and collision detection. Simulations illustrate that the proposed method has a better performance than the smooth rapid-exploration random tree (smooth-RRT) method and jump point search (JPS) method, and that path length and the state limitations are satisfied.