Planning a full reverse-parking maneuver into a tight bay
Plain A* searches a grid and happily produces paths with instant 90° turns, fine for a game character, useless for a car. Hybrid A* searches over the vehicle's actual reachable states instead of grid cells: at every step it only considers moves the car could really drive, respecting its turning radius and letting it choose forward or reverse gears. The result is a path an actual steering wheel can execute, gear changes included.
Click to drop a goal and drag to aim its heading, or just click one of the marked parking slots, and watch the planner search and then drive the maneuver. Manual mode (W, S, A, D) is there for comparison, try parking it yourself first.
Worth trying: turn on "show search" to see the fan of explored states before the final path is chosen, and drop the turn-radius slider to its minimum to force noticeably tighter, more careful maneuvers.
Plain grid A* plans paths a car can't drive: diagonal zig-zags, right-angle corners, spinning in place. Hybrid A* fixes this by expanding nodes with the actual motion model: from each state it rolls the car forward and back through a few fixed steering angles, producing successor states that are always physically reachable. The trick that keeps it tractable: although the car's pose (x, y, θ) is continuous, successors are binned into a coarse grid so the search doesn't drown in nearly-identical states. At most one node survives per cell. So it searches in continuous space but prunes in discretized space, getting drivable paths without exploding.
turn on "show search" and watch the explored states fan out. They curve, because every expansion is a little arc the car could actually follow.
The kinematic bicycle model collapses the four wheels into two: the heading changes only when the car rolls, at a rate set by the steering angle δ and wheelbase L, dθ = (v/L)·tan(δ)·dt. Two consequences define everything here. There's a minimum turning radius R = L/tan(δ_max), so the car physically cannot turn tighter, and a goal just beside it may require pulling forward and back. And there's no sideways motion: you can't slide into a parking spot, you arc into it. Every successor in the search and every Reeds-Shepp segment obeys exactly this model.
drop the turn-radius slider to its minimum and re-park. The planner finds tighter maneuvers. Crank it up and the car needs sweeping approaches.
In 1990 Reeds and Shepp proved that the shortest path between two poses for a car moving at constant speed both forward and backward, with a fixed turning radius, is always one of a small finite catalogue of words: sequences of left-arc, straight, and right-arc segments like L⁺S⁺R⁻, where the sign is the gear. At most five segments, ignoring obstacles. This sim implements the core curve families and picks the shortest valid one analytically, no search, just formulas. Every candidate is reconstructed and checked to land exactly on the goal pose before it's trusted, so the maneuver is correct to a fraction of a unit. It's what lets the car finish precisely in the slot rather than "close enough."
park somewhere with clear space. The final approach (purple) is a pure Reeds-Shepp curve splicing the car neatly onto the goal.
A* needs a heuristic, an optimistic guess of remaining cost, and a good one is what makes Hybrid A* fast instead of exhaustive. This planner takes the maximum of two: one that knows the car's kinematics but ignores walls (the Reeds-Shepp distance to goal, capturing "you'll need to swing around to face the right way"), and one that knows the walls but ignores kinematics (a flood-fill distance through free space, capturing "there's an obstacle, go around"). Each alone has a blind spot the other covers; their max is still admissible (never overestimates) so the path stays optimal, but far more informed. The flood-fill is what stops the search from wandering hopefully into a dead-end alcove.
park behind the obstacle block. Without the obstacle-aware term the search would waste thousands of nodes probing the wall; here it routes around.
Pure grid search struggles to terminate exactly on a continuous goal pose. Binning means it lands in the right cell, not the right point. Analytic expansion fixes this: every so often, instead of expanding a node, the planner tries to connect it straight to the goal with a single Reeds-Shepp curve. If that curve is collision-free, the search is done: the path is "search to get close, then shoot analytically to land." This both guarantees an exact finish and dramatically speeds things up, since the shot often succeeds long before the grid search would have crawled all the way there.
watch the node counter. It usually stops at a few hundred, because the Reeds-Shepp shot connected to the goal early.
A drivable path isn't enough. It should also feel natural, and that's pure cost shaping. Reversing is penalized so the car prefers driving forward when it can; switching gears (forward↔reverse) carries a fixed penalty so it doesn't dither back and forth; steering and steering-changes are penalized so the path is smooth rather than wiggly. None of these change what's possible. They change what's preferred, and tuning them is most of what separates a planner that technically works from one that parks like a person.
push gear-switch penalty to 20. The car works hard to avoid three-point turns. Drop it to 0 and it'll happily shuffle back and forth.