Chapters
Table of Contents

On this page

All lessons

Algorithms

Anytime Search

Anytime Weighted A*
CPD Searchcurrent

Jump Point Search

Jump Point Search
soon
Modern Jump Point Search
soon
JPS+
soon
JPS-3D
soon
Rectilinear JPS
soon

Temporal Planning

Why Time is Hard
soon
Time Expanded A* (TXA*)
soon
Safe Interval Path Planning (SIPP)
soon

Playground

Playground
Back to AWA*
Chapter 1

CPD Search (Anytime A* with Perfect Distances)

CPD Search is an anytime algorithm that runs A* with a precomputed distance table as its heuristic. Before search, a BFS from the target (on an unweighted map) gives a perfect lower-bound distance for every node. This becomes both the heuristic and an initial upper bound — enabling aggressive pruning and fast convergence to optimality.

Open (BFS frontier / A* open)
Closed (processed)
Current node
Forest (cost ×5)
Water (cost ×10)
Incumbent path
Tool:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
D
E
F
G
H
I
J

Statistics

Upper Bound (UB)—
Lower Bound (LB)—
Open Set Size0
Nodes Expanded0
Nodes Pruned0

Draw your map above, then click Run A* to generate the step trace.

How CPD Search works

Phase 1 — Preprocessing. A BFS runs backwards from the target on an unweighted copy of the map (all non-wall cells cost 1). This builds a table of perfect distances dist[n] from every node n to the target. Numbers on each cell during this phase are those BFS distances.

Initial upper bound. The unweighted shortest path from start to target is extracted from the BFS. Its actual weighted cost (including terrain) becomes the first upper bound (UB). We have a valid solution before the main search even starts.

Phase 2 — A* with perfect heuristic. Standard A* runs with f(n) = g(n) + dist[n]. Because dist[n] is the exact unweighted distance — always ≤ the true weighted cost — it is admissible, so A* will find the optimal weighted path.

Anytime pruning. Any node whose f(n) > UB is pruned immediately — no path through it can beat the current best. When the lowest f-value in OPEN (the LB) reaches the UB, optimality is proven and search terminates.

In this demo: The water band (cost ×10) sits on the direct route. The BFS path runs straight through it, giving a high initial UB. A* then discovers the cheap route around the water — cutting the cost dramatically — and the tight heuristic quickly proves this new path is optimal.
Chapter 2

CPD Search vs AWA*

Both are anytime algorithms, but they tackle the problem differently. CPD Search (left) gets an immediate upper bound from its precomputed path, then uses perfect distances to prune aggressively. AWA* (right) uses an inflated heuristic (w=10) to rush toward the goal, then backtracks to find cheaper routes. Edit either grid to run both simultaneously.

Open set
Closed set
Current node
Water (cost ×10)
Incumbent path
Tool:
CPD Searchf = g(n) + dist[n]

CPD Search Statistics

Upper Bound (UB)—
Lower Bound (LB)—
Open Set Size0
Nodes Expanded0
Nodes Pruned0
AWA*f = g(n) + 10·h(n)

AWA* Statistics

Upper Bound (UB)—
Lower Bound (LB)—
Open Set Size0
Nodes Expanded0
Nodes Pruned0

Modify the grid above, then click Run animation to compare both algorithms side by side.

Continue your Learning

Read the original CPD Search paper to understand how Compressed Path Databases are constructed and why they produce such tight bounds in practice.

Anytime Weighted A*
Dijkstra's Soon

Found this helpful?

These resources are free — if they saved you time, a coffee keeps them going.

Buy me a coffee