QuadPath Lab · Quadtree Pathfinding

QuadPath Lab is a pathfinding experiment. Pick a map, set a start and goal, and watch which regions each algorithm explores. Then compare path lengths and expanded-node counts.

Try a run

1. Pick a test scene, or draw your own map with the obstacle, erase, start and goal tools.
2. Choose A* or Dijkstra and press Run to watch the search.
3. Run the other algorithm and compare the two runs in the Results tab.

Use the controls below the map to pause, step through the search or change its speed. All computation stays in your browser; map data is not uploaded.

What each concept is responsible for

A quadtree answers “how should the space be represented?” A regular grid treats every cell as a separate node. A quadtree begins with the entire map and recursively splits it into four. A uniform region becomes one large leaf; only a mixed region containing both free and blocked cells is subdivided again. Open space can therefore be summarized by a few large nodes while obstacle boundaries retain detail.

Dijkstra answers “how do we guarantee the shortest route?” Starting at the source, it always expands the node with the smallest accumulated cost. It makes no guess about the direction of the goal. With non-negative edge weights it finds a shortest path, although it usually explores more broadly.

A* answers “how can we search with more direction?” It combines Dijkstra’s accumulated cost g(n) with a heuristic estimate h(n) to the goal and orders expansion by f(n) = g(n) + h(n). The Lab uses geometric distance as the heuristic, so the search tends to concentrate toward the destination.

Their relationship can be summarized as:

Grid map
  ↓ recursive subdivision
Quadtree leaves
  ↓ spatial adjacency and movement cost
Searchable graph
  ├─ Dijkstra: cost already travelled
  └─ A*: travelled cost + estimate to the goal

The quadtree is not a third pathfinding algorithm and it does not replace A* or Dijkstra. It reduces and organizes the search space; the two algorithms decide how to move through that space.

How the pieces are integrated

Whenever the map changes, the Lab rebuilds the quadtree and collects every traversable leaf. Two free leaves are connected when their regions share a boundary, and the edge weight comes from the geometric distance between their centers. The start and goal are mapped to the leaves that contain them, then both algorithms run on exactly the same graph.

That makes the comparison fair: spatial structure, endpoints and edge weights remain identical. Only the expansion strategy changes. Each run records visit order, final path, expanded-node count, path length and computation time.

The comparison uses paths defined by this adjacency graph and its edge weights. Different runs can return different routes with the same length; the lines need not match exactly.

Blue regions on the map show spatial nodes already expanded by the search; the orange polyline is the final route. The inspector on the right explains how map regions were recursively divided. The D3 force-directed window shows the parent-child hierarchy of the quadtree, not the adjacency graph used for pathfinding. Purple links mark the hierarchy path from the root to the selected node.

Inspect the spatial structure

1. In Inspect mode, click a map region to locate its tree node. Move deeper through the quadrant navigator to see how each level covers the original map.
2. Open Topology for a movable window. Drag nodes, zoom the canvas, collapse subtrees or rebuild the layout while keeping the map visible behind it.
3. Change the row and column counts or obstacle layout to see how the quadtree and search size change.

Switch between Chinese and English or light and dark themes from the upper-right controls.