path-planning / bilalkah

Five C++ path planners, running in your browser.

A*, BFS, DFS, RRT and RRT* from bilalkah/path-planning, compiled to WebAssembly. Click the map to place a start and a goal, then press R or Run.

Loading the C++ planners (WebAssembly)…

replay idle

Each run calls FindPath in the compiled C++ inside a Web Worker, then replays GetLog(), the log the native SDL3 visualizer draws. For RRT*, the bindings also record the best path each time it changes, so the replay shows the first path when it is found and every improvement after it. Its log holds only the final tree, so tree edges are drawn to each node's final parent. Keys: R run · Space pause · 1–5 planner.

01

How each planner searches

Grid planners search cell by cell. Tree planners sample free space and join points with straight segments.

A path planner answers one question: how do I get from the start to the goal without crossing a wall? The five planners here answer it in different ways, and each trades three things against the others: how good the path is, how much of the map it has to look at, and what it can promise.

planning/grid_base

Grid search: one loop, three containers.

Every free cell is a node. Its neighbours are the 4 or 8 adjacent cells (search_space), and every move costs 1, diagonals included. A*, BFS and DFS run the same loop: take the next node, skip it if it was already visited, log it, mark it visited and push its free neighbours with the current node as their parent.

The container that holds the frontier is the only real difference. It decides which node comes out next, and that decides how much of the map gets explored and what the path looks like.

the shared loop, simplifiedastar.cpp · bfs.cpp · dfs.cpp
while (!search_list.empty() &&
       !IsGoal(next(search_list)->node, goal_node))
  {
    auto current_node = next(search_list);
    search_list.pop();
    if (!IsFree(current_node->node, map_copy))
      continue;  // already visited

    log_.first.emplace_back(current_node);
    map_copy->SetNodeState(current_node->node,
                           NodeState::kVisited);

    for (auto &direction : search_space_)
      // push each free neighbour, parent = current_node
      search_list.push(neighbour);
  }
std::queue · front()→BFS
std::stack · top()→DFS
std::priority_queue · lowest f→A*
Expansion order on lak505d, from the C++ log.
grid · std::queue

Breadth-first search

Explores the map in order of distance from the start. Cells wait in a first-in, first-out queue, so the ones found first are expanded first and the search spreads in rings: every cell one move away, then two moves away, until the goal reaches the front of the queue.

How it works
  1. Put the start in the queue.
  2. Take the oldest cell. If it is the goal, stop.
  3. Queue each free neighbour not seen yet, noting where it came from.
  4. Follow those notes back from the goal to read off the path.
Path
Fewest moves. Every move costs 1, so the first time the goal comes out of the queue no shorter path exists.
Cost
Expands every cell closer to the start than the goal, in every direction.
Best for
Small or unweighted grids where the shortest route in moves matters.
Expansion order on lak505d, from the C++ log.
grid · std::stack

Depth-first search

Follows one branch as far as it goes. Cells wait on a last-in, first-out stack, so the newest cell is expanded next: the search keeps walking forward and only backs up to the most recent fork when it runs into a dead end. The path is the chain of steps that happened to lead there.

How it works
  1. Push the start on the stack.
  2. Pop the newest cell. If it is the goal, stop.
  3. Push its free neighbours; the last one pushed is explored next.
  4. At a dead end, the stack hands back the most recent branch not yet explored.
Path
Any path that reaches the goal, usually far from the shortest. On the maze it is about 4.5 times longer than BFS's.
Cost
Unpredictable: it can stumble on the goal early or sweep most of the map first.
Best for
Checking that the goal can be reached, or visiting every corner. Not for good routes.
Expansion order on lak505d, from the C++ log.
grid · std::priority_queue

A*

Adds a sense of direction. Every cell gets a score f that combines g, the moves taken from the start, and h, the straight-line distance still to go. The cell with the lowest f is expanded next, so the search heads for the goal and only spreads sideways when walls force it to.

f = (1 − w) · g + w · h

The weight w (heuristic_weight) sets how much the estimate counts. At 0.5 cells rank as in classic A* (g + h); at 0 h is ignored and the search behaves like BFS; at 1 g is ignored and it becomes greedy best-first search. The repository uses 0.7.

How it works
  1. Score the start and put it in a priority queue.
  2. Take the cell with the lowest f. If it is the goal, stop.
  3. Score each free neighbour (one more move, its own h) and queue it.
Path
Short, not guaranteed shortest. That guarantee needs an h that never overestimates; here a diagonal move costs 1, so the straight line can overestimate, and w = 0.7 trusts it more.
Cost
A fraction of the cells BFS expands when the straight line is a fair guide. In a maze, dead ends that point at the goal lead it astray.
Best for
Large maps with a good estimate of the distance left. The usual choice in games and robot navigation.
planning/tree_base

Sampling: grow a tree through free space.

RRT and RRT* never walk the grid. Each iteration picks a random free cell, finds a tree node to grow from, and steps toward the sample by at most max_branch_length cells. Steps shorter than min_branch_length are dropped.

Before a step joins the tree, Get2DRayBetweenNodes lists every cell on the straight line between the two points. One occupied cell rejects the step. Paths come out as straight segments at any angle, not moves between neighbouring cells.

one RRT iterationrrt.cpp
for (auto i = 0; i < max_iteration_; i++)
  {
    auto random_node{RandomNode(map_copy)};
    auto nearest_node{
        GetNearestNodeParent(random_node, log_.first)};
    auto new_node{WireNewNode(max_branch_length_,
        min_branch_length_, random_node, nearest_node, map_copy)};
    if (new_node == nullptr)
      continue;  // too short, or the ray hit a wall

    log_.first.emplace_back(new_node);
    if (EuclideanDistance(new_node->node, goal_node)
        <= goal_radius_)
      return ReconstructPath(goal);
  }
One RRT iteration: a random sample, its nearest tree node, and a new node one branch length toward the sample. A second step is rejected because its ray hits a wall. ray hits a wall: rejected max_branch_length nearest new node random sample goal_radius start
Sample, nearest node, a step of at most max_branch_length, then a ray check.
tree · rapidly-exploring random tree

RRT

Does not search cells at all. It grows a tree of straight branches from the start: pick a random free point, find the closest node already in the tree, and grow a short branch toward the point. Random points fall mostly in the large unexplored regions, so the tree is pulled outward quickly.

How it works
  1. Sample a random free cell.
  2. Find the tree node nearest to it.
  3. Step toward the sample by at most max_branch_length. Drop the step if it is shorter than min_branch_length or if its straight line crosses a wall.
  4. Stop as soon as a new node lands within goal_radius of the goal.
Path
The first one found. Every branch points at a random sample, so it zigzags, and RRT never shortens it.
Cost
Depends on the space and on luck. Open maps are quick; narrow corridors starve it, and on the one-cell maze it finds nothing.
Best for
Large open spaces, and problems with many dimensions, such as robot arms, where a grid would be far too big.
One RRT* iteration: the new node attaches to the cheapest neighbour within neighbor_radius, then a neighbour that is cheaper to reach through the new node is rewired under it. neighbor_radius new node 1 · attach to cheapest neighbour 2 · rewire old edge dropped
Choose the cheapest parent in reach, then rewire neighbours that get cheaper.
tree · RRT with rewiring

RRT*

Grows like RRT but pays attention to cost. A new node attaches to whichever nearby node gives it the cheapest route from the start, not simply the nearest one. Then it rewires: neighbours that would be cheaper to reach through the new node switch their parent to it. The tree keeps straightening itself, so the path keeps improving after the first one is found.

How it works
  1. Sample and step as RRT does.
  2. Among the tree nodes within neighbor_radius, attach to the cheapest one a straight line can reach.
  3. Rewire the neighbours that become cheaper through the new node.
  4. Keep going for all max_iteration samples, holding on to the best path so far.
Path
Starts out like RRT's, then shortens as the tree is rewired. Cost here is the number of branches plus their length.
Cost
Uses every sample and searches a neighbourhood for each one: more work than RRT for a better path.
Best for
When path quality matters and there is time to spend. It can be stopped at any point with the best path so far.

At a glance

Planner Explores Next node Always finds a path if one exists? Path quality
BFSGrid cells, 4 or 8 neighboursOldest in the queueYesFewest moves
DFSGrid cells, 4 or 8 neighboursNewest on the stackYes, on a finite mapAny path, often very long
A*Grid cells, 4 or 8 neighboursLowest f = (1 − w)·g + w·hYesShort; shortest only with an estimate that never overestimates
RRTRandom free samplesNearest tree node, one step toward the sampleOnly in probability: more samples, better oddsThe first path found, jagged
RRT*Random free samplesCheapest node in reach, then rewireOnly in probability, like RRTImproves the whole time it runs
02

The ideas behind them

Six ideas that explain why the same map gives five planners such different results.

4 neighbours 8 neighbours

A grid is a graph

Each free cell is a node, joined to its 4 or 8 neighbours (search_space). With 4, paths move like city blocks; with 8 they can cut corners diagonally. Every move costs 1 here, diagonals included, so a diagonal step is as cheap as a straight one.

complete: some path optimal: the best one

Complete and optimal

Two promises a planner can make. Complete: if a path exists, it finds one. Optimal: the path it finds is the best one. BFS keeps both, counting moves. DFS is complete on a finite map but not optimal. A* is optimal only when its estimate never overestimates.

g h real route

Heuristics guide the search

A heuristic estimates the distance still to go; A* uses the straight line. Trusting it more (a larger weight) expands fewer cells but can give a longer path. Walls are where the straight line is most wrong, which is why a maze slows A* down.

every cell only the samples

Search the grid, or sample the space

Grid search grows with the number of cells: double the resolution and there are four times as many. Sampling planners only place points where they look, so their work depends on how hard the space is, not on its resolution. That is why robot arms with six or seven joints are planned with RRT-style methods.

a narrow gap

Narrow passages

A sampling planner only gets through a gap when a random sample lands where a straight step can pass, and the narrower the gap, the rarer that is. In one-cell corridors almost no step fits, so RRT and RRT* stall; give the same kind of maze wider corridors and they get through.

first path no path yet cost samples →

Luck, and paths that get better

RRT and RRT* are complete only in probability: with more samples the chance of finding a path that exists approaches certainty, but any single run can fail. RRT* is also an anytime planner: it has a usable path early, improves it while it runs, and is designed to approach the shortest path as samples grow.

03

Run the same case natively.

The config below follows the demo: change the planner, map or points above and it updates.

The native build opens an SDL3 window and draws the log while the planner runs. Put these values in config/, then build and run. A Docker setup is in docker/.

shellnative build
git clone --recurse-submodules https://github.com/bilalkah/path-planning.git
cd path-planning
./build.sh       # CMake configure and build
./build/main     # reads config/main.yaml

Maps: Moving AI Lab 2D pathfinding benchmarks (N. Sturtevant, “Benchmarks for Grid-Based Pathfinding”, 2012). In the .map format, . and G are passable; planning::Map treats every other cell, including trees, water and swamp, as occupied. The two mazes come from tools/maze/make_maze.py: maze has corridors one cell wide, maze_wide leaves room for the tree planners.

config/ for the current demo