Balancing Game Loop Efficiency With Pathfinding Complexity

The Pathfinding Bottleneck – Discussing How Pathfinding Can Tax Game Performance If Not Optimized Properly

Pathfinding algorithms are critical for controlling unit movement in real-time strategy games, RPGs, MMOs, and other game genres. However, these algorithms can become a bottleneck that taxes the game loop and reduces frame rates if not optimized properly.

Games with many units making simultaneous path requests can see severe performance degradation. For example, commanding 200 archer units to move across a game map can cripple frame rates and gameplay responsiveness if each unit pathfinds independently. The more units, map complexity, and pathfinding depth increases – the worse this bottleneck becomes.

Common signs of pathfinding bottlenecks include:

Lag spikes when many units are given movement commands
Delays between user input and unit movement
Low frame rates when the game camera viewport contains many moving units
Excessive memory usage from pathfinding allocation

Without optimization, complex pathfinding algorithms like A* search can consume more CPU, memory, and GPU resources than even rendering graphics. For example, calculating paths across a 500×500 navigation mesh for hundreds of units per frame can exceed the capabilities of even high-end hardware.

Game developers must balance pathfinding complexity with game loop performance. The objective is maximizing AI navigation quality without compromising responsiveness or frame rates.

Common Pathfinding Algorithms

Game developers have several pathfinding algorithms to choose from, each with different performance implications:

A* Search – High path quality but costly in resources
Dijkstra’s Algorithm – Guarantees shortest path but exponential complexity
Theta* – Faster than A* but paths may require more movement
Jump Point Search – Fast and memory efficient but suboptimal paths

The sections below discuss techniques to optimize these and other pathfinding algorithms for real-time games.

Benchmarking Pathfinders

Comparing pathfinders on performance metrics helps select the best algorithms before game integration. Useful benchmarks include:

Memory Usage – Bytes allocated per path request
CPU Time – Microseconds to compute a single unit path
Path Quality – Path directeness, avoidance of obstacles
Frame Time – ms required to pathfind all units each frame

For example, benchmarks might reveal:

A* Search provides the most direct paths but averages 500 microsecond path time.
Theta* paths average 350 microseconds but are 15% less direct.
Jump point search requires only 100 microseconds per path but quality suffers.

Given gameplay priorities and hardware constraints, developers can best determine which pathfinder maximizes navigation quality within budget.

Profiling Pathfinding Overhead

Profilers are invaluable for quantifying pathfinding costs during real game conditions. Measurements to capture:

Per-frame pathfinder CPU time and memory allocation
Number of paths generated, smoothed, post-processed
Data structure traversal counts (nodes expanded in A*, jumps traced)

Profiles reveal optimization opportunities such as reducing 20,000+ path smoothings per frame to just 100 most critical paths.

Load Testing with Thousands of Units

Load tests help catch scaling issues early before gameplay suffers:

Measure frame time and FPS while ratcheting up unit counts into the thousands
Verify game loop remains responsive despite 10x normal path loads
Confirm no memory leaks or excessive paging during sustained pathfinding loads

Addressing issues found during load testing avoids surprises down the road.

Simplifying Maps to Reduce Pathfinding Overhead

Complex game maps represent more navigable coordinates for units to traverse, exponentially increasing pathfinding computation:

A simple 64×64 grid has 4,096 nav points
A sizable 500×500 map has 250,000 nav points
A massive 1,000×1,000 map has 1,000,000 nav points!

The more map coordinates to explore, the longer pathfinding algorithms take to find optimal unit trajectories.

Navigation Mesh Culling

Navigation meshes provide 2D/3D walkable coordinates for pathfinding. Culling simplifies meshes to minimize traversable area:

Removing narrow corridors or small obstacles units cannot enter
Collapsing indoor rooms or layered terrain into fewer representative polygons
Choking walkable space around immovable buildings/mountains

This reduces total navigable coordinates, lowering search spaces for pathfinders without affecting movement quality.

Waypoint Graphs

Waypoint graphs simplify continuous maps into discrete nodes interconnected by permissible transitions:

Map areas become abstract nodes like “North Field” or “3rd Floor Hallway”
Pathfinding focuses on sequencing permissible node transitions
Fewer expansions than searching all map coordinates

Units navigate between waypoints instead of full coordinate paths. AI avoids obstacles not represented.

Grid-Based Decompositions

Grids overlay maps with fewer normalized cells for movement:

1024×1024 map becomes 64×64 evenly spaced grid
Units pathfind cell-to-cell instead of coordinate-to-coordinate
Grid cells marked unwalkable simplify collision avoidance

Projecting maps to grids limits path complexity helping some search algorithms like Jump Point Search.

Prioritizing Game Units to Reduce Pathfinding Load

Pathfinding load scales linearly with unit count – 1,000 units mean 1,000 concurrent paths to update each frame.

Prioritizing units receiving updated paths each frame maintains responsiveness despite thousands of game agents.

Group Movement Orders

Group selection allows players to command 100+ units simultaneously. Group movement issues a single path request instead of 100+:

Path represents centroid trajectory for entire group
Units follow path using local steering behaviors
Avoids spike of 100 separate path requests

This favors group movement whenever tactically viable.

Flow Field Pathing

Flow fields guide individual units toward targets without explicit paths:

Vector field encodes optimal direction to move from any map coordinate
Units query field to steer themselves toward end position
Avoids per-unit pathfinding costs

Flow fields act as precomputed guidance maps units independently follow.

Movement Managers

Centralized movement managers throttle pathfinding requests:

Units enqueue movement goals instead of direct requests
Manager processes queue at defined rate matching hardware
Unblocks other game systems from pathfinding spikes

Decentralized steering coordinates individual units after paths generated.

Predictive Path Reuse

Predicting unit movement allows precomputing viable paths:

Anticipate troop formations and likely repositionings
Proactively pathfind predicted destinations
Cache and reuse precomputed paths when guesses match

Correct predictions provide free pathfinding results without runtime costs.

Multithreading Expensive Pathfinding Logic

Pathfinding algorithms like A* search stall the main game loop, reducing frame rates. Distributing work across CPU cores increases responsiveness:

Pathfinding Thread Pool

Dedicated thread pool for path requests:

Game loop adds path jobs to concurrent queue
Worker threads pull requests and calculate paths
Notify game logic asynchronously upon completion

Keeps main loop responsive during expensive searches.

Vector Field Bake-Off

Bake flow field volumes in background:

Lazy initialize vector volumes on demand
During gameplay, spawn thread to generate volume
Game ticks read old volume until bake finishes

Staggers precomputation from interactive simulation.

Pathfinding Strips

Parallel strip-wise decomposition:

Divide map into vertical zones or “strips”
Concurrently pathfind units in each strip
Stitch strip paths into a final result

Speeds individual pathing through divide-and-conquer.

Example Code for Efficient Pathfinding

Below are code snippets demonstrating optimized pathfinding techniques discussed above.

Navigation Mesh Simplification (C++)

  // Original complex mesh
  NavMesh* navMesh = loadedMeshes["complex_map.nm"]; 
  
  // Simplified mesh
  NavMesh* simpleMesh = new NavMesh();

  // Chokepoint reduction filter
  ChokepointReductionFilter filter;

  // Filter original mesh down 
  filter.Reduce(*navMesh, *simpleMesh);

  // Replace meshes
  delete navMesh;
  loadedMeshes["complex_map.nm"] = simpleMesh;

Path Queue Throttling (C++)

  // Pathfinding manager 
  PathfindingManager pm;

  while(gameIsRunning) {

    // Enqueue this frame's movement goals
    for(auto& unit : units) {
      pm.QueuePathTo(unit, unit.nextDestination);
    }

    // Process path backlog gradually
    int maxPathsPerFrame = 100;
    for(int i = 0; i < maxPathsPerFrame; i++) {
      if(pm.HasQueuedPaths()) {
         pm.ProcessNextPath();
      } else {
        break;  
      } 
    }

    // Advance units along paths
    for(auto& unit : units) {
      unit.Advance();
    }

    // Render scene
    RenderWorld();
  }

Offloading Pathfinding to Threads (C++)

  // Queue for path requests
  ConcurrentQueue requests;

  // Worker threads pull requests and process
  void PathfinderThread() {
    
    while(running) {

      PathRequest req;
      requests.Pop(req);

      NavMesh* mesh = req.mesh;
      Vector3 start = req.start;
      Vector3 end = req.end;

      // Actually pathfind
      Path p = CalculatePath(start, end, mesh) 

      // Notify game logic
      req.callback(p);

    }
  }

  // Enqueue path request from game loop
  void RequestPath(NavMesh* m, Unit& unit) {

    PathRequest req;
    req.mesh = m;
    req.start = unit.position;
    req.end = unit.destination;
    req.callback = unit.OnPathResult;

    requests.Push(req);

  }

Balancing Performance and Quality

Optimizing pathfinding comes down to balancing tradeoffs between practicality and realism.

On one end of the spectrum lies expediency - simplified movement using waypoints, grids, flow fields and other techniques maximizing CPU efficiency. Units appear less lifelike but game performance shines.

The other extreme emphasizes nuanced locomotion - planning high-quality paths with A* or Dijkstra's algorithm over dense nav meshes. Motion mimics real organisms but risks uncompromising game logic to achieve.

As always, moderation is key. Thoughtfully combine elements from both extremes to accomplish an optimal middle ground for gameplay:

Use waypoint graphs for distant navigation but patch to full paths locally
Enable group movement when tactically appropriate but pathfind individuals occasionally
Precompute flow fields for most requests butindividually pathfind hero units

Keep the user experience central above all else when balancing pathfinding. Employ techniques judiciously to maximize both AI quality and overall responsiveness.