algorithmsgame AItutorial

From Map Geometry to Pathfinding: Implement A* with Heuristics for Different Map Sizes

UUnknown

2026-02-21

11 min read

Practical A* guide: implement, tune heuristics, and scale pathfinding from tiny arenas to grand maps like Arc Raiders' 2026 additions.

Struggling to make A* fast and reliable across tiny arenas and sprawling open maps? You're not alone.

Game developers and students often get A* working on a small test grid — then hit a wall when maps grow tens or hundreds of times larger (or change shape entirely, as recent 2026 updates to games like Arc Raiders promise). This guide shows a practical, step-by-step implementation of A* and how to choose and tune heuristics and architectures so your pathfinding scales from compact indoor maps to grand outdoor battlegrounds.

The most important idea up front (inverted pyramid)

A* is simple: it expands nodes toward a goal using cost-so-far (g) plus a heuristic estimate (h). To scale A* across map sizes you must: pick an appropriate heuristic (and keep it admissible), optimize the data structures for memory and CPU, and switch to hierarchical or hybrid approaches (navmesh + local A*, HPA*, JPS, or GPU-assisted search) for very large maps. We'll give a working implementation, benchmarks, and concrete tuning rules for small, medium, and large maps.

Who this is for

Students learning game AI who want a clear A* implementation with heuristic tradeoffs.
Indie and mid-size game devs preparing for games with varied map sizes (like Arc Raiders' 2026 map roadmap).
Engineers prototyping and profiling pathfinding for performance and memory.

2026 context: Why heuristics and scalability matter now

Late 2025 and early 2026 game-development trends accelerated two forces that change pathfinding requirements:

Studios are shipping a wider spectrum of map sizes — from tight competitive arenas to expansive open worlds (Arc Raiders is a recent, public example of that pattern).
Engine and tooling advances (data-oriented systems, compute shader support, and more common multi-threaded navmesh libraries) make it feasible to choose more sophisticated hybrid strategies.

That means the old approach — a single grid-based A* tuned for one map — is no longer enough. Instead, design a flexible pathfinding stack that: uses cheap heuristics for small maps, enables JPS/Theta*/navmesh for medium maps, and employs hierarchical or GPU-accelerated techniques for truly large maps.

Quick recap: A* core equations and invariants

g(n): exact cost from start to node n.
h(n): estimated cost from n to goal (heuristic).
f(n) = g(n) + h(n): priority used by A*.
Heuristic must be admissible (never overestimates) to guarantee optimality. Consistency (monotonicity) ensures no re-opening of closed nodes.

Step-by-step A* implementation (Python) with a heuristic parameter

The code below is intentionally simple, easy to test, and designed so you can swap heuristics or plug it into a higher-level system.

import heapq
import math

class Node:
    def __init__(self, idx, x, y):
        self.idx = idx
        self.x = x
        self.y = y
        self.g = math.inf
        self.f = math.inf
        self.parent = None

def heuristic(a, b, type='euclidean'):
    dx = abs(a.x - b.x)
    dy = abs(a.y - b.y)
    if type == 'manhattan':
        return dx + dy
    if type == 'chebyshev':
        return max(dx, dy)
    # default: euclidean
    return math.hypot(dx, dy)

def reconstruct_path(node):
    path = []
    while node:
        path.append((node.x, node.y))
        node = node.parent
    return list(reversed(path))

def astar(grid, start_coords, goal_coords, heuristic_type='euclidean', weight=1.0):
    # grid: 2D array of walkable bools. start_coords/goal_coords: (x,y)
    rows, cols = len(grid), len(grid[0])
    nodes = [ [Node(r*cols + c, c, r) for c in range(cols)] for r in range(rows) ]

    sx, sy = start_coords
    gx, gy = goal_coords
    start = nodes[sy][sx]
    goal = nodes[gy][gx]

    start.g = 0
    start.f = weight * heuristic(start, goal, heuristic_type)

    open_heap = []
    heapq.heappush(open_heap, (start.f, start.idx, start))
    closed = set()

    while open_heap:
        _, _, current = heapq.heappop(open_heap)
        if current.idx in closed:
            continue
        if current is goal:
            return reconstruct_path(current)
        closed.add(current.idx)

        for dx, dy, cost in ((1,0,1),( -1,0,1),(0,1,1),(0,-1,1),(1,1,math.sqrt(2)),(1,-1,math.sqrt(2)),(-1,1,math.sqrt(2)),(-1,-1,math.sqrt(2))):
            nx, ny = current.x + dx, current.y + dy
            if nx < 0 or nx >= cols or ny < 0 or ny >= rows:
                continue
            if not grid[ny][nx]:
                continue
            neighbor = nodes[ny][nx]
            tentative_g = current.g + cost
            if tentative_g < neighbor.g:
                neighbor.parent = current
                neighbor.g = tentative_g
                neighbor.f = tentative_g + weight * heuristic(neighbor, goal, heuristic_type)
                heapq.heappush(open_heap, (neighbor.f, neighbor.idx, neighbor))
    return None

Notes on the sample implementation

The weight parameter implements Weighted A*: higher than 1.0 makes search faster but may sacrifice optimality.
Eight-directional moves are supported. For grid-based maps you can remove diagonals if movement is 4-directional.
This representation keeps nodes in memory — good for small/medium maps. For huge maps, use index-based arrays, pooling, or streaming chunks.

Choosing heuristics: when to use Manhattan, Euclidean, Chebyshev, or others

Pick the heuristic based on your movement model and map geometry. Here are concrete rules:

Manhattan (h = |dx| + |dy|) — Use for 4-connected grids (no diagonal move). Cheap and admissible.
Chebyshev (h = max(|dx|, |dy|)) — Use for 8-connected grids when diagonal cost equals straight cost.
Euclidean (h = sqrt(dx^2+dy^2)) — Use when movement is continuous or diagonal cost ~ straight*sqrt(2). Good for navmesh start/goal heuristics.
Octile — grid-specific hybrid accounting for different diagonal costs; use when diagonal cost != straight cost.

Always keep admissibility in mind: a heuristic must not overestimate true cost. A small admissible heuristic will be safe but slow — a slightly larger but inadmissible heuristic (weighted A*) can be acceptable in many games when you prefer faster, near-optimal paths.

Tuning heuristics by map size (practical rules)

Use these rules-of-thumb when you know the problem scale and constraints. We'll assume uniform grid movement unless specified.

Small maps (arena-style; up to ~128x128 tiles)

Use an exact admissible heuristic: Manhattan or Chebyshev depending on connectivity.
Prefer full A* with a binary heap. Memory and CPU are low, so optimality matters.
Enable tie-breaking on nodes with equal f (prefer higher g) to choose shorter routes and reduce pointless expansion.

Medium maps (complex levels; 128x128–1024x1024 tiles)

Use Jump Point Search (JPS) for uniform-cost grids — often reduces expansions by orders of magnitude.
If using A*, choose Octile/Euclidean heuristics and consider a small weight (1.0–1.2) for speed vs. optimality.
Consider precomputing reachability data or partial hierarchies (HPA* with 16x16 clusters).

Avoid raw grid A*. Instead: build a navmesh, abstract graph, or HPA* hierarchy, then run A* at the abstract layer and refine locally.
Use landmarks/ALT (A* with Landmarks and Triangle inequality) or multi-level heuristics to get better guidance.
Leverage engine features: multi-thread nav queries, GPU compute (if available), and streaming to limit memory footprint.

Advanced methods that complement A*

When simple heuristic tuning isn't enough, these methods are the industry patterns used in 2026:

Hierarchical Pathfinding (HPA*): cluster the map into sectors, build a coarse graph, run A* on the coarse graph, then refine inside sectors. Great for open-world maps.
Jump Point Search (JPS): optimizes grid A* by skipping symmetric nodes. Excellent on uniform-cost grids and commonly used for medium-sized maps.
Navmesh + Local A*: typical for non-grid maps. Compute path on the navmesh graph, then use local steering for character movement.
Weighted A* and anytime algorithms: trade optimality for speed. Perfect for real-time gameplay where first response matters.
D* Lite / Incremental: preferred for dynamic environments where obstacles change and you want to reuse previous search work.

Performance engineering: data structures, priority queues, and memory

Small changes in implementation make huge differences when you scale.

Priority queue: binary heap is fast and simple. For integer bounded costs, consider a bucketed radix heap for O(1) amortized operations.
Node storage: prefer compact arrays of primitives to object-per-node if your language allows it. Pool Node objects to avoid GC pressure.
Open/closed handling: use integer-stamped visited arrays instead of hash sets for O(1) checks and minimal memory overhead.
Cache locality: iterate neighbors in memory-order, align structures to reduce cache misses.
Parallelism: run multiple path queries in parallel on separate threads. For large single queries, consider GPU-based techniques cautiously — they can outperform CPU only when batch sizes or map structures fit well into parallel paradigms.

Benchmarking and profiling (actionable)

Before picking a final design, measure. Here's a simple benchmarking checklist you can implement:

Create representative map samples for small/medium/large. Include narrow choke points and open areas.
Record these metrics: nodes expanded, time per query (ms), memory allocated, path length.
Run tests with multiple heuristics and weights (e.g., weight = 1.0, 1.1, 1.2, 1.5).
Average over many start-goal pairs distributed across the map (not just corners).
Profile hotspots (priority queue ops, neighbor generation, heuristic computation) and optimize the largest contributors first.

# Pseudocode for a micro-benchmark harness
for map in [small_map, medium_map, large_map]:
    for heuristic_type in ['manhattan','chebyshev','euclidean']:
        for weight in [1.0,1.1,1.2,1.5]:
            run 1000 random queries
            measure avg_time_ms, avg_nodes_expanded
            log results

Practical examples: heuristics tuned for Arc Raiders-style maps

Arc Raiders' 2026 roadmap emphasizes a spectrum: tiny competitive maps, standard five-locale maps, and some more grandiose maps. Here's how to approach each:

Tiny competitive maps: Use grid-based A* tuned for minimal latency. Manhattan/Chebyshev with tie-breaking and binary heap is your friend. Keep weight <=1.05 if you must compromise.
Standard mid-sized locales: JPS or navmesh + local A*. JPS reduces expansions indoors; navmesh handles irregular geometry.
Grander new maps: use HPA* or a multi-layer navmesh system. Run abstract A* on the coarse graph and refine along corridors. Consider precomputing waypoints and caching cross-sector paths.

Edge cases and gotchas

Heuristic that is not admissible => non-optimal paths. If game tolerates near-optimality, document it clearly.
Diagonal moves with different costs require octile heuristic; otherwise you break admissibility.
Dynamic obstacles can invalidate cached paths. Use D* Lite or incremental replanning when agents must adapt.
Floating point noise in heuristics can cause tie-breaking oddities. Use deterministic tie-breakers where necessary.

Pro tip: in many real games, players accept slightly longer paths if they are more believable. Use smoothing and steering to improve perceived quality without always insisting on optimality.

Path smoothing and movement after A*

Once you have a path, smoothing and local steering turn it into believable movement.

Raycast between waypoints to remove unnecessary nodes.
Use a simple string-pulling algorithm on navmesh corridors.
Blend with local obstacle avoidance (ORCA, RVO, or engine-native steering systems) for multi-agent scenarios.

Checklist to ship a scalable A* system (actionable takeaways)

Choose heuristic by movement model (Manhattan/Chebyshev/Euclidean/Octile).
Use Weighted A* for time-critical queries and document quality tradeoffs.
Implement JPS for uniform grids and navmesh for irregular geometry.
For very large maps, adopt HPA* or multi-level abstraction and cache cross-cluster paths.
Optimize memory: arrays and integer stamps rather than per-node objects and hash sets.
Benchmark across representative maps (small/medium/large) and profile hotspots.
Use incremental planners (D* Lite) for dynamic obstacles to avoid full replan costs.

Future predictions & 2026 trends you should watch

As of 2026, expect these trends to influence pathfinding design over the next few years:

More hybrid navigation stacks combining navmesh, hierarchical graphs, and sampled local planning.
Increased use of data-oriented designs (ECS/DOTS-style) for massive numbers of agents and parallel path queries.
Growth of compute-shader and GPU-based methods for batched multi-query pathfinding in open-world scenes — best for large batch workloads rather than single queries.
More tooling around procedural map generation, requiring dynamic pathfinding data structures and on-the-fly navmesh rebuilding.

Conclusion: Build a flexible stack, not a single A*

To reliably handle the spectrum of maps (from compact competitive arenas to the grand maps hinted at in Arc Raiders' 2026 updates), don't treat A* as a single monolith. Start with a clear, correct A* implementation, benchmark it, and then add the next layer: JPS for uniform grids, navmesh + local A* for irregular spaces, and HPA*/abstract graphs for large maps. Tune heuristics by movement model and map size, and always measure. Small heuristic choices and data-structure changes often yield the best payoffs.

Call to action

Try the sample A* code on three representative maps (small, medium, large). Log nodes expanded and time per query. If you want a ready-made benchmarking harness, templates for HPA* and JPS, or an interactive notebook that visualizes expansions and heuristics in real-time, visit our GitHub or drop a question below — we’ll walk through your map and pick the best pathfinding stack for it.

Unknown

Contributor

Senior editor and content strategist. Writing about technology, design, and the future of digital media. Follow along for deep dives into the industry's moving parts.