screeps-clockwork

A* and Other Optimizations

The venerable A* algorithm provides the baseline for pathfinding in Screeps.

Within a single room, the Clockwork implementation of the A* algorithm alone is competitive with PathFinder. However, across longer distances (greater than a single room), PathFinder’s JPS optimizations make a significant difference.

We’ll experiment with a few different options.

Optimizations

• Jump-Point Search is also used under the hood by PathFinder
• Pre-computed landmarks for more accurate A* heuristics

Landmarks

The theory:

1. Pick a non-wall spot near the middle of the room and Dijkstra-map out from there.
2. Cache the center spot, one exit on each of the (1-4) sides, and cost for each.
3. Use these points as landmarks for the A* heuristic.

Drawbacks:

Cost matrix used for calculating landmarks needs to be the same as cost matrix for pathing

Other interesting variants

• Cooperative Pathfinding (building a table of the paths of other units)
• Incremental heuristic search (tracking moving targets)
• Parallel Breadth-First Search

This site is open source. Improve this page.