Standard A* pathfinding evaluates every neighboring grid cell, quickly choking CPU threads when dozens of enemy units navigate large maps simultaneously. Jump Point Search (JPS) speeds up grid pathfinding by up to 30x by pruning symmetric paths and jumping horizontally and vertically until an obstacle or turning point is encountered.
1. Pathfinding Algorithm Performance Comparison
| Algorithm | Grid Evaluation Strategy | Nodes Expanded (512x512 Map) | Relative Execution Time |
|---|---|---|---|
| Standard A* (Euclidean) | Checks all 8 adjacent orthogonal/diagonal neighbors. | ~15,000 nodes | 100% (Baseline) |
| Jump Point Search (JPS) | Prunes symmetries; jumps along straight lines. | ~600 nodes | ~3% – 8% (12x – 30x faster) |
| Hierarchical A* (HPA*) | Pre-computes portal graphs between 16x16 chunk clusters. | ~250 nodes | ~2% – 5% (Ultra-fast long distance) |
