Pathfinding

One of the more interesting aspects of game development is to pick and implement a variety of pathfinding algos.

For now I settled on three kinds of pathfinding algos for the game:

1. Traffic A Star – a specialized A implementation optimized for vehicle navigation on one-way road networks*.
2. Grid-Based A* in Cython – a standard A* algo for player directed movement.
3. Nav Graph A Star – a pre-computed navigation graph A* implementation that creates a sparse waypoint network for efficient pathfinding. Used to simulate paths of tens of thousands NPCs.

Traffic A Star

This version of A* is tailored specifically for vehicles navigating city roads. Instead of scanning the full grid like traditional pathfinding, it uses pre-computed, one-way lane connections.

How It Works

• Standard A* algorithm adapted for traffic systems.
• Uses Manhattan distance as the heuristic.
• Instead of generating neighbors dynamically, it uses precomputed lane connections to control movement.

Traffic-Specific Optimizations

• One-way lanes: Uses a one_way_lanes dictionary mapping each road tile to its allowed next positions (enforces directional flow).
• Uniform movement cost: All movements cost 1 – no diagonals, no complexity.
• Manhattan heuristic: Keeps pathfinding optimal and predictable for grid-aligned roads.

Performance

• Precomputed connections: No need to calculate valid moves at runtime. Roads define them upfront.
• defaultdict for g-scores: Lightweight memory usage, avoids preallocating large data structures.
• Early termination: Exits immediately once the goal is found.
• Simplified logic: No diagonal support = fewer edge cases, faster execution.

This system is built specifically for the simulation’s vehicle movement layer.

• Vehicles follow defined traffic lanes, including one-ways.
• Paths are strictly constrained to the road network, no free roaming.
• It scales well across city-sized grids with many active vehicles.

Grid-Based A* in Cython

I also implemented a classic grid-based A* for situations where full pathfinding over the grid is needed- like short-range movement such as when the player clicks a pawn to move elsewhere on the street. This one runs fast thanks to Cython.

How It Works

• Standard A* pathfinding, compiled with Cython for speed.
• Supports 8-directional movement (cardinal + diagonals).
• Uses Chebyshev distance as the heuristic (i.e. max of x/y delta)

Core Components

• Wraps the collision map with built-in bounds checking.
• Precomputes all 8 movement directions for quick neighbor lookup.
• get_neighbors() filters out blocked tiles and infinity-cost cells.
• Costs: 1.0 for straight moves, √2 for diagonals.
• Open set is a priority queue (min-heap) sorted by f-score.
• Builds path by backtracking from goal using a came_from map.

Performance Tweaks

• Compiled with Cython for near-C-level speed.
• Disabled bounds checking with @cython.boundscheck(False).
• Inlined hot-path functions (like neighbor filtering and cost calc).
• Pre-allocates direction arrays to avoid repeated construction.

All in all great for more accurate and efficient path-finding when user/player takes control of a pawn.

Nav Graph A Star

High-Level Overview

• I precompute a navigation graph made up of waypoints on walkable ground.
• Then I use A* to find paths through this graph.
• Finally, I interpolate between waypoints to generate smooth paths on the grid.

The idea is to trade some memory and upfront setup time for much faster pathfinding when the game is running.

Building the Navigation Graph

The graph is created using a combination of structured and random sampling:

1. Grid Sampling
   • Regularly places nav nodes on walkable tiles using a set spacing.
2. Random Sampling
   • Adds extra nodes randomly in open areas to improve coverage and avoid gaps.
3. Spatial Partitioning
   • Buckets nearby nodes to avoid O(n²) connection checks – this keeps it fast.
4. Line-of-Sight Connections
   • Connects nearby nodes if there’s a clear path (using Bresenham’s algorithm).

Pathfinding Flow

1. Find Closest Nodes
   • Uses a KDTree to quickly find the nearest nav node to both start and end points.
2. Run A*
   • A* search runs on the sparse graph using a simple Manhattan heuristic.
3. Interpolate the Path
   • Once waypoints are chosen, I fill in the steps between them using line interpolation.

Key Optimizations

• Auto-tuned parameters (like spacing and connection radius) adjust based on map size.
• Spatial bucketing drops graph connection checks from O(n²) to O(n).
• KDTree keeps nearest-node lookups super fast.
• The random node sampling favors areas near obstacles to help with tight corners.

This setup makes pathfinding super cheap at runtime – even with lots of NPCs asking for paths. The upfront cost of building the nav graph is worth it. Fast, smooth, and scalable.