Overview
A scalable city traffic simulation in Unreal Engine 5 supporting 100+ concurrent AI vehicles with smooth lane-change logic, dynamic spawning/despawning, and sub-frame recovery behaviours. The system is organised into three layers executing at different frequencies: graph construction (once at load), navigation (on demand), and motion control (every tick).
The article accompanying this project walks through two performance-critical optimisations — Grid Hash junction detection and A* min-heap pathfinding — and the steering model that ties them together.
Optimisation 1 — Grid Hash Junction Detection
Before any vehicle can navigate, the system needs to know where roads intersect. Two roads meet wherever their spline sample points are within a detection radius of each other.
The Problem: Brute-Force O(R² × S²)
With R roads and S sample points per road, a naive implementation compares every sample on road A against every sample on road B, for every road pair — four nested loops. With R = 100 and S = 200, this is 400,000,000 distance computations at startup.
The Solution: Grid Hash O(N)
The optimised implementation divides the world into uniform cells of side length
CellSize.
Every sample is inserted into exactly one cell. To find nearby points, only the
27 cells in the 3×3×3 neighbourhood are searched — points in any other cell are
skipped with zero work.
The key property: K (average points per neighbouring cell) is constant. It does not grow as more roads are added. Total work becomes O(N × K) ≈ O(N).
| Metric | Brute-Force | Grid Hash |
|---|---|---|
| Time complexity | O(R² × S²) | O(N × K) ≈ O(N) |
| Operations (R=100, S=200) | 400,000,000 | ~1,000,000 |
| Relative speed | 400× slower | 1× (baseline) |
| Scales with map size | Exponential blow-up | Linear growth |
Optimisation 2 — A* Binary Min-Heap
Each vehicle runs A* to find a route to its destination. The heuristic is Euclidean distance between node world positions.
Original: O(n²) Linear Scan
The original open set was a plain TArray<int32>.
Finding the lowest F-score required a full linear scan, and removing it required
TArray::Remove
— also O(n). Both repeat once per expanded node, making the total search O(n²).
Optimised: O((V+E) log V) with Lazy Deletion
The replacement uses Unreal's built-in HeapPush
and HeapPop
on a TArray<TPair<float,int32>>.
Updating a node's score uses lazy deletion: push a new lower-score entry
and discard stale pops via a TSet ClosedSet check in O(1).
| Operation | Original | Optimised |
|---|---|---|
| Find min F-score | Linear scan O(n) | HeapPop O(log n) |
| Remove processed node | TArray::Remove O(n) | ClosedSet skip O(1) |
| Open set membership | TArray::Contains O(n) | TSet::Contains O(1) |
| Score update | In-place write | Lazy push, stale skip |
Pursuit Point Steering
Each tick the vehicle steers toward a look-ahead point on the path rather than the nearest spline position. Look-ahead distance scales with speed:
GetPursuitPoint
walks forward through the segment array, subtracting each segment's remaining length
from the budget until it's spent, then samples the spline at the exact position.
This handles cross-segment look-ahead seamlessly without gaps or jumps.
Turn Signal & Direction Detection
When a new segment is added, ComputeTurnAtJunction
classifies the upcoming junction using dot product and cross product:
- Dot product > 0.866 (cos 30°) → straight, no signal
- Dot product < −0.866 → U-turn
- Cross product Z > 0 → right turn (UE5 left-handed Z-up)
- Cross product Z < 0 → left turn
The result drives both the blinker activator and the Hermite arc radius scaler for outer-lane junction smoothing.