RRT* Motion Planning — Rapidly-Exploring Random Trees

RRT and RRT* are sampling-based motion-planning algorithms that solve the "find a route from start to goal through obstacles" problem in continuous space, without ever building a grid or graph up front — the classic way this is instead handled by A*, Dijkstra or BFS. This simulator grows a real 3D rapidly-exploring random tree through a field of spherical obstacles: each iteration samples a random point, connects the tree's nearest node toward it with a fixed step, and rejects the extension if it collides. In RRT* mode two extra optimality passes run every iteration — choosing the cheapest nearby parent for the new node, then rewiring any neighbour that would get cheaper by routing through it — visibly straightening and shortening the tree's branches as more iterations run, exactly as it does inside real robot and vehicle motion planners.