A* tricks for videogame path finding
Game developers and algorithm enthusiasts trade techniques for making A* pathfinding fast, believable, and scalable in everything from small 2D games to massive RTS battles and city builders. They explore hierarchical graphs, heuristic tweaks, alternative data structures, and hybrid approaches (like flow fields, steering behaviors, and group-level paths) to cope with dynamic obstacles, large agent counts, and limited knowledge of the map. Several commenters also point to more advanced or specialized methods—contraction hierarchies, differential heuristics, RL-based approaches, and GOAP-style planning—highlighting how a “solved” problem like pathfinding still hides a deep design and optimization space.
Reinforcement Learning vs. Classical Pathfinding
- Some wonder if a small RL policy (NN or decision tree) could replace A*, possibly with fewer hand-crafted edge cases.
- Others argue it would just learn a worse A* with harder-to-debug failures, reflecting broader unease about opaque learned systems.
Beyond Basic A* and Research Directions
- Multiple advanced methods are mentioned: contraction hierarchies, time-dependent variants, hierarchical search, bidirectional A*, landmarks, reach, transit nodes, arc flags, differential heuristics, etc.
- Several survey papers, lectures, and talks are cited; some are called outdated, with claims that the field has progressed rapidly.
Behavioral Tricks for “Smart” Enemies
- Delayed re-pathing and randomized update intervals make enemies seem to “hesitate” or be trickable, and also save CPU.
- Targeting tiles ahead of the player gives “cutoff” behavior (e.g., Pac‑Man ghost–like).
- Using A* paths as guidance for steering (corner-cutting, smoothing) and breadcrumbs/pheromone trails produces more organic motion.
Hierarchical, Large-Scale, and Multi-Agent Navigation
- Hierarchical graphs (city / building / room, or streets vs interiors) are widely used to keep queries fast.
- For many enemies, running Dijkstra from the player and having each enemy follow gradients is suggested.
- Large-formation games (RTS, Total War–style) separate long-range pathfinding from local crowd simulation; per-unit A* is seen as wasteful and unrealistic.
- Flow fields and flocking/steering are proposed for group movement.
Performance and Data-Structure Optimizations
- Tricks include: bucketed priority queues, storing search metadata on nodes, asynchronous/off-thread pathfinding, limiting nodes per tick, and all-pairs preprocessing (e.g., Floyd–Warshall on small grids).
- MPAA (multipath adaptive A*) is praised for incremental re-use; JPS (jump point search) draws mixed reviews due to overhead.
Map Representation, Costs, and Edge Cases
- Debate over pixel-based vs tile-based search; tiles reduce work when movement is tile-aligned, but fine-grained pixels may be needed otherwise.
- Precomputed metadata (distance to nearest obstacle, egress bitmasks) speeds collision checks and pathfinding.
- Handling teleporters, varying terrain costs, convex regions, and multiple movement modes is noted as tricky.
- A* tie-breaking, C-shaped obstacles, and “never give up” searches are identified as common pitfalls, with real-game bugs cited (e.g., mobs or animals stuck forever).
A* Beyond Movement
- A* and related search are also applied to decision/planning graphs (GOAP, strategy search), not just spatial maps, giving a unified “planning” feel to game AI.