Skip to content
Computational Lab.

RRT & RRT*

Trees that feel their way through obstacles.

Advanced / search / sampling / planning

Rapidly-exploring random trees grow from a start point by sampling, steering, and collision-checking. RRT* adds the crucial refinement: new nodes pick the cheapest nearby parent and existing neighbors get rewired, so the path cost falls as samples accumulate. The cost metric shows the difference the star makes.

Tagged: rapidly-exploring tree, sampling-based, rewiring, path cost

Live simulation

RRT* keeps rewiring neighbors - its path cost falls where RRT stops.

Speed

RRT* keeps rewiring neighbors - its path cost falls where RRT stops.

Mathematics

Sampling-based planners grow a tree of feasible motion: sample a point, steer the nearest tree node toward it by a fixed step, keep the edge if it is collision-free. RRT is provably rapid at exploring; RRT* is provably asymptotically optimal.

nearest: x_new = x_near + min(step, |x_sample - x_near|) * unit(x_sample - x_near)

RRT* parent choice: minimize cost(x_new) = cost(x_parent) + |edge|

rewiring: for neighbors j with |edge| < r: cost(j) <- min(cost(j), cost(x_new) + |j - x_new|)

The star's two extra loops - choosing the cheapest parent in a neighborhood and rewiring neighbors through the new node - are what turn a feasible path into an improving one. The cost metric lets you run both variants on the same obstacle field and watch the gap open.

How it works

The tree lives in parallel typed arrays (x, y, parent, cost). Each tick takes a fixed number of samples with 8% goal bias; every candidate edge is collision-checked against the circular obstacles by projecting the circle center onto the segment.

RRT* keeps a rewiring radius proportional to the step size and rechecks segments in both phases. Reaching the goal circle snapshots the best path and cost.

Implementation

src/engine/experiments/rrt-rrt-star.ts · 245 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4interface Obstacle {
5 x: number;
6 y: number;
7 r: number;
8}
9
10/**
11 * Rapidly-exploring random trees on a obstacle field. Plain RRT grows toward
12 * random samples; RRT* additionally rewires neighbors through cheaper
13 * parents, and the cost metric shows the difference accumulating.
14 */
15export class RrtExperiment extends BaseExperiment {
16 readonly id = "rrt-rrt-star";
17
18 private xs = new Float64Array(0);
19 private ys = new Float64Array(0);
20 private parents = new Int32Array(0);
21 private costs = new Float64Array(0);
22 private nodeCount = 0;
23 private obstacles: Obstacle[] = [];
24 private status: "growing" | "reached" = "growing";
25 private goalPath: number[] = [];
26 private bestCost = Infinity;
27 private samplesUsed = 0;
28 private readonly start = { x: 0.06, y: 0.5 };
29 private readonly goal = { x: 0.94, y: 0.5 };
30 private readonly goalRadius = 26;
31
32 protected params(): ParameterDef[] {
33 return [
34 {
35 key: "mode",
36 label: "Variant",
37 options: [
38 { value: "rrt", label: "RRT" },
39 { value: "rrt-star", label: "RRT*" },
40 ],
41 defaultValue: "rrt-star",
42 },
43 { key: "samples", label: "Samples per tick", min: 1, max: 20, step: 1, defaultValue: 4 },
44 { key: "step", label: "Step size", min: 10, max: 60, step: 2, defaultValue: 26, unit: "px" },
45 { key: "obstacles", label: "Obstacle count", min: 0, max: 14, step: 1, defaultValue: 7 },
46 ];
47 }
48
49 protected onReset(): void {
50 const capacity = 6000;
51 this.xs = new Float64Array(capacity);
52 this.ys = new Float64Array(capacity);
53 this.parents = new Int32Array(capacity).fill(-1);
54 this.costs = new Float64Array(capacity);
55 this.nodeCount = 1;
56 this.xs[0] = this.start.x * this.width;
57 this.ys[0] = this.start.y * this.height;
58 this.obstacles = [];
59 for (let i = 0; i < this.num("obstacles"); i++) {
60 this.obstacles.push({
61 x: (0.2 + this.rng() * 0.6) * this.width,
62 y: this.rng() * this.height,
63 r: 20 + this.rng() * 46,
64 });
65 }
66 this.status = "growing";
67 this.goalPath = [];
68 this.bestCost = Infinity;
69 this.samplesUsed = 0;
70 }
71
72 protected onParameterChange(key: string): void {
73 if (key !== "samples") this.reset();
74 }
75
76 resize(width: number, height: number): void {
77 this.width = width;
78 this.height = height;
79 this.reset();
80 }
81
82 private segmentHitsObstacle(x1: number, y1: number, x2: number, y2: number): boolean {
83 const dx = x2 - x1;
84 const dy = y2 - y1;
85 const len2 = dx * dx + dy * dy || 1;
86 for (const o of this.obstacles) {
87 let t = ((o.x - x1) * dx + (o.y - y1) * dy) / len2;
88 t = Math.max(0, Math.min(1, t));
89 const cx = x1 + t * dx;
90 const cy = y1 + t * dy;
91 if ((cx - o.x) ** 2 + (cy - o.y) ** 2 < o.r * o.r) return true;
92 }
93 return false;
94 }
95
96 private nearest(x: number, y: number): number {
97 let best = 0;
98 let bestD2 = Infinity;
99 for (let i = 0; i < this.nodeCount; i++) {
100 const d2 = (this.xs[i] - x) ** 2 + (this.ys[i] - y) ** 2;
101 if (d2 < bestD2) {
102 bestD2 = d2;
103 best = i;
104 }
105 }
106 return best;
107 }
108
109 protected onUpdate(): void {
110 if (this.nodeCount >= this.xs.length - 8) return;
111 const mode = this.str("mode");
112 if (mode === "rrt" && this.status === "reached") return;
113 const stepSize = this.num("step");
114 const samples = this.num("samples");
115 for (let s = 0; s < samples; s++) {
116 if (mode === "rrt" && this.status === "reached") break;
117 if (this.nodeCount >= this.xs.length - 8) break;
118 this.samplesUsed += 1;
119 // Goal bias: 8% of samples aim straight at the goal.
120 const tx = this.rng() < 0.08 ? this.goal.x * this.width : this.rng() * this.width;
121 const ty = this.rng() < 0.08 ? this.goal.y * this.height : this.rng() * this.height;
122 const near = this.nearest(tx, ty);
123 const dx = tx - this.xs[near];
124 const dy = ty - this.ys[near];
125 const dist = Math.hypot(dx, dy) || 1;
126 const nx = this.xs[near] + (dx / dist) * Math.min(stepSize, dist);
127 const ny = this.ys[near] + (dy / dist) * Math.min(stepSize, dist);
128 if (nx < 2 || ny < 2 || nx > this.width - 2 || ny > this.height - 2) continue;
129 if (this.segmentHitsObstacle(this.xs[near], this.ys[near], nx, ny)) continue;
130
131 const i = this.nodeCount++;
132 if (mode === "rrt") {
133 this.xs[i] = nx;
134 this.ys[i] = ny;
135 this.parents[i] = near;
136 this.costs[i] = this.costs[near] + Math.hypot(nx - this.xs[near], ny - this.ys[near]);
137 } else {
138 // RRT*: choose the best parent among neighbors, then rewire them.
139 const rewireRadius = stepSize * 2.4;
140 let bestParent = near;
141 let bestCost = this.costs[near] + Math.hypot(nx - this.xs[near], ny - this.ys[near]);
142 for (let j = 0; j < this.nodeCount; j++) {
143 const dj = Math.hypot(this.xs[j] - nx, this.ys[j] - ny);
144 if (dj > rewireRadius) continue;
145 if (this.segmentHitsObstacle(this.xs[j], this.ys[j], nx, ny)) continue;
146 const candidate = this.costs[j] + dj;
147 if (candidate < bestCost) {
148 bestCost = candidate;
149 bestParent = j;
150 }
151 }
152 this.xs[i] = nx;
153 this.ys[i] = ny;
154 this.parents[i] = bestParent;
155 this.costs[i] = bestCost;
156 for (let j = 0; j < this.nodeCount - 1; j++) {
157 const dj = Math.hypot(this.xs[j] - nx, this.ys[j] - ny);
158 if (dj > rewireRadius || j === bestParent) continue;
159 if (this.segmentHitsObstacle(nx, ny, this.xs[j], this.ys[j])) continue;
160 const candidate = this.costs[i] + dj;
161 if (candidate < this.costs[j]) {
162 this.parents[j] = i;
163 this.costs[j] = candidate;
164 }
165 }
166 }
167 const distToGoal = Math.hypot(nx - this.goal.x * this.width, ny - this.goal.y * this.height);
168 if (distToGoal < this.goalRadius) {
169 this.status = "reached";
170 const candidateCost = this.costs[i] + distToGoal;
171 if (candidateCost < this.bestCost) {
172 this.bestCost = candidateCost;
173 let node = i;
174 this.goalPath = [i];
175 while (node !== 0) {
176 node = this.parents[node];
177 this.goalPath.push(node);
178 }
179 }
180 }
181 }
182 }
183
184 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
185 ctx.fillStyle = theme.bg;
186 ctx.fillRect(0, 0, this.width, this.height);
187 ctx.fillStyle = theme.fgTertiary;
188 for (const o of this.obstacles) {
189 ctx.beginPath();
190 ctx.arc(o.x, o.y, o.r, 0, Math.PI * 2);
191 ctx.fill();
192 }
193 ctx.strokeStyle = theme.fgSecondary;
194 ctx.globalAlpha = 0.55;
195 ctx.lineWidth = 1;
196 ctx.beginPath();
197 for (let i = 1; i < this.nodeCount; i++) {
198 ctx.moveTo(this.xs[this.parents[i]], this.ys[this.parents[i]]);
199 ctx.lineTo(this.xs[i], this.ys[i]);
200 }
201 ctx.stroke();
202 ctx.globalAlpha = 1;
203 if (this.goalPath.length > 1) {
204 ctx.strokeStyle = theme.accent;
205 ctx.lineWidth = 2.5;
206 ctx.beginPath();
207 for (let k = 0; k < this.goalPath.length; k++) {
208 const i = this.goalPath[k];
209 if (k === 0) ctx.moveTo(this.xs[i], this.ys[i]);
210 else ctx.lineTo(this.xs[i], this.ys[i]);
211 }
212 ctx.stroke();
213 }
214 ctx.fillStyle = theme.viz[2];
215 ctx.beginPath();
216 ctx.arc(this.xs[0], this.ys[0], 4, 0, Math.PI * 2);
217 ctx.fill();
218 ctx.strokeStyle = theme.accent;
219 ctx.beginPath();
220 ctx.arc(this.goal.x * this.width, this.goal.y * this.height, this.goalRadius, 0, Math.PI * 2);
221 ctx.stroke();
222 }
223
224 getMetrics() {
225 return {
226 mode: this.str("mode") === "rrt" ? "RRT" : "RRT*",
227 nodes: this.nodeCount.toLocaleString("en-US"),
228 samples: this.samplesUsed.toLocaleString("en-US"),
229 pathCost: this.bestCost === Infinity ? "n/a" : this.bestCost.toFixed(0),
230 status: this.status === "reached" ? "Goal reached" : "Growing",
231 };
232 }
233
234 describe(): string {
235 if (this.status === "reached") {
236 return `${this.str("mode") === "rrt" ? "RRT" : "RRT*"} reached the goal region with ${this.nodeCount} nodes; best path cost ${this.bestCost.toFixed(0)}.`;
237 }
238 return `${this.str("mode") === "rrt" ? "RRT" : "RRT*"} is growing: ${this.nodeCount} nodes from ${this.samplesUsed} samples.`;
239 }
240
241 entities(): number {
242 return this.nodeCount;
243 }
244}
245

Performance

Time per tick
O(n log n) amortized per sample with spatial indexing; O(n) nearest-neighbor here
Space
One node record per accepted sample
Notes
Plain RRT stops improving the moment it touches the goal; RRT* keeps tightening forever.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.