Advanced Techniques

Beyond Basic Algorithms

A* is fast—remarkably so for most problems. But what happens when "most problems" isn't good enough? What about massive game worlds with millions of cells? Or real-time systems where every millisecond counts?

This is where advanced techniques come in. Each one exploits a specific property of the search space to achieve dramatic speedups. Some cut the search space in half. Others skip entire regions. A few can even handle maps that change while you're navigating them.

The key insight is that there's no single "best" pathfinding algorithm. The right choice depends on your constraints: grid uniformity, map size, whether the environment changes, and how much preprocessing you can afford.

Bidirectional Search

The most intuitive optimization is also one of the most powerful: search from both directions.

Instead of exploring outward from the start until we hit the goal, we simultaneously explore from both the start and the goal. The search terminates when the two frontiers meet in the middle.

Why does this help? Think about search space. If the shortest path has length $d$, a single-direction BFS explores roughly all cells within distance $d$ of the start—a circle with radius $d$. Bidirectional search explores two smaller circles, each with radius approximately $d/2$.

Since the area of a circle grows with the square of the radius, two circles of radius $d/2$ have a combined area of:

That's half the area of a single circle with radius $d$. In practice, the savings can be even more dramatic, especially in open environments where the frontier expands freely.

Watch the two waves—blue from start, red from goal—expand and meet in the middle. Notice how the total visited count is often much smaller than a single-direction search would require.

Bidirectional search works with BFS, Dijkstra, and A*. The main complication is determining when the frontiers have truly found the optimal meeting point. For BFS on unweighted graphs, it's straightforward: the first cell visited by both frontiers lies on a shortest path.

Jump Point Search

On uniform-cost grids (where every step costs the same), A* often explores many cells that don't matter. If there's a long corridor with no obstacles, does it really need to visit every single cell?

Jump Point Search (JPS) answers: no, it doesn't.

JPS exploits path symmetry. On a uniform grid, many paths between two points have identical cost. JPS identifies "jump points"—cells where the optimal direction might change—and leaps directly to them, skipping all the symmetric cells in between.

A jump point occurs when:

• We reach the goal
• There's a forced neighbor (a cell we can only reach optimally by passing through this point)
• We're moving diagonally and a cardinal direction finds a jump point

The result? On open terrain, JPS can reduce the number of expanded nodes by an order of magnitude or more.

Toggle between JPS and A* to see the difference. The orange diamonds mark jump points—the only cells JPS actually examines in detail. Everything else gets skipped.

JPS is particularly powerful for games with large open areas. A character running across a field doesn't need to evaluate every blade of grass—JPS jumps straight to the points that matter.

Caveats: JPS only works on uniform-cost grids with 4-directional or 8-directional movement. It doesn't apply to weighted graphs or non-grid structures.

Hierarchical Pathfinding

What if your map is so large that even JPS isn't fast enough? Modern game worlds can have millions of cells. Searching at full resolution is impractical.

Hierarchical pathfinding solves this by adding levels of abstraction. Instead of searching cell-by-cell, we first find a path at the region level, then refine it locally.

The process works in two phases:

1. Abstract search: Divide the map into regions (clusters of cells). Build a graph where regions are nodes and connections between neighboring regions are edges. Find a path through this abstract graph.

2. Local refinement: For each pair of adjacent regions in the abstract path, find the detailed path within those regions.

This is like planning a road trip. First, you decide which cities to pass through (abstract). Then, you figure out the exact streets in each city (refined).

Click through the phases to see hierarchical planning in action. First, the map is divided into colored regions. Then, the high-level path identifies which regions to traverse. Finally, the refined path fills in the details.

Hierarchical methods scale beautifully. A 1000×1000 grid has a million cells, but if we cluster them into 10×10 regions, the abstract graph has only 10,000 nodes—100× smaller. Add another level and it shrinks again.

HPA* (Hierarchical Pathfinding A*) and Navigation Meshes are popular implementations of this idea. Most commercial games use some form of hierarchical pathfinding for large environments.

Dynamic Replanning

All the algorithms we've discussed assume the map is static—obstacles don't move, costs don't change. But real robots navigate real environments, and real environments change.

Dynamic replanning algorithms handle this gracefully. Instead of recomputing the entire path when something changes, they update incrementally.

D* (Dynamic A*) and its successor D Lite* are the standard choices. They maintain information from the initial search and efficiently repair the path when the environment changes.

The key insight is that most changes only affect a small part of the search space. If a new obstacle appears far from the current path, no replanning is needed. If it blocks the path, we only need to reconsider cells in the affected region.

Start the agent moving, then add an obstacle in its path. Watch how it quickly computes a new route without starting from scratch.

D* Lite is particularly popular in robotics, where sensors continuously discover new obstacles. A Mars rover can't afford to replan from scratch every time it spots a rock.

Performance in Practice

Numbers speak louder than theory. Let's see how these algorithms compare head-to-head on the same map.

The benchmark reveals what the theory predicts: JPS dramatically reduces node visits on open grids, while A*'s heuristic helps it beat BFS. But remember—this is just one map. Different layouts produce different winners.

Choosing the Right Technique

No single technique dominates all scenarios. Here's a practical guide:

Real-world systems often combine techniques. A game might use hierarchical pathfinding for long-distance travel, JPS for medium distances, and basic A* for local navigation—all dynamically switching based on the situation.

Key Takeaways

• Bidirectional search explores from both ends, potentially halving the search space by reducing the effective radius
• Jump Point Search exploits grid symmetry to skip redundant cells, offering massive speedups on uniform grids
• Hierarchical pathfinding uses multiple abstraction levels to scale to enormous maps
• Dynamic replanning (D* Lite) efficiently updates paths when the environment changes
• Real-world pathfinding combines multiple techniques based on the specific constraints of each situation