Standard A* uses Euclidean distance as its heuristic, the straight-line cost from the current node to the goal. In a flat open space this is a pretty good estimate. In a complex 3D environment full of corridors, stairs, and rooms that you can see across but can't walk straight through, it's often deeply misleading.
Across all 38 Quake 1 maps, the mean ratio of true shortest path cost to Euclidean distance is 1.46, meaning the real path is on average 46% longer than the straight-line estimate. Some source-goal pairs have correction factors above 20. Every time A* follows the Euclidean heuristic into a dead end, it's paying for that underestimate.
The question this project tried to answer: can a learned model predict how much the Euclidean estimate is off, given the local geometry around each node pair, and can plugging that correction into A* meaningfully reduce the search effort without producing bad paths?
The first thing to figure out was how to get the geometry. Quake 1 stores its maps in a Binary Space Partitioning (BSP v29) format, a binary file that the game engine uses for fast rendering and collision detection. There's no navigation mesh, no pre-built graph. Just the raw BSP.
The BSP parser reads the binary directly: extracting face vertices, computing face centroids, determining which faces are walkable surfaces, and building edges between adjacent walkable faces. This produces a navigation graph where each node is a face centroid and each edge connects two geometrically reachable faces. Running this across all 38 maps gives a collection of graphs that actually reflect the 3D structure of the environment.
With graphs in hand, the next step was generating training data. Dijkstra's algorithm was run across approximately 625,000 source-goal pairs (sampled from each map) to compute true shortest path costs. The regression target is the correction factor (correction_factor = true_path_cost / euclidean_distance).
This formulation is scale-invariant across maps of very different sizes. The model only needs to learn how much above 1.0 the true cost is, it doesn't need to predict absolute distances. The label is log-transformed before training to compress the right-skewed distribution and stabilise training.
Seventeen hand-crafted features capture the spatial and graph-structural context around each source-goal pair. They fall into three groups:
Spatial (7 features): Euclidean distance, horizontal distance, height difference, height ratio, and signed dx/dy/dz components.
Source node context (5 features): Local node density within 150 units, degree, average edge length, maximum edge length.
Goal node context (5 features): Mirror of source context. Two additional ratio features compare source and goal context directly.
The feature importance analysis later confirmed that height features dominate,
height_ratio and height_diff together account for nearly half
the total XGBoost gain. This makes intuitive sense: height differences are the main reason
Euclidean distance underestimates true path cost in Quake geometry. You can see across a
large room vertically, but you have to find stairs or a ramp to actually get there.
Two models were trained: a small MLP in PyTorch (three hidden layers, ReLU activations, trained with early stopping) and an XGBoost regressor. Both were plugged into A* as multiplicative corrections, at each step, the heuristic is the Euclidean distance multiplied by the model's predicted correction factor. Predictions are clamped to a minimum of 1.0 since a correction factor below 1.0 is geometrically impossible.
Splitting randomly by sample would leak map topology into the test set, if some samples from a map appear in train and others in test, the model has implicitly seen the map structure. The split is by episode instead: train on episodes 1 and 2, validate on episode 3, test on episode 4 and deathmatch maps. The model has never seen the geometry of the test maps during training.
| Method | Mean nodes expanded | Path cost ratio | vs Euclidean |
|---|---|---|---|
| Dijkstra | ~all nodes | 1.000 | N/A |
| Euclidean A* | 96.2 | 1.000 | Baseline |
| MLP A* | 56.7 | 1.020 | −42.4% |
| XGBoost A* | 56.9 | 1.020 | −42.2% |
42% reduction in nodes expanded across all 38 maps · Benchmarked on 38,000 total queries (1,000 per map)
Paths ~2% longer than optimal on average · Performance holds on unseen episode 4 and deathmatch maps
MLP and XGBoost produce near-identical results, the representation bottleneck dominates over model capacity
The near-identical performance of MLP and XGBoost (42.4% vs 42.2% reduction) is arguably the most informative result in the project. Both models have access to the same 17 features. Both achieve the same improvement. This suggests that the bottleneck isn't model capacity, it's the feature representation. Richer features like BSP leaf membership, leaf volume, or same-leaf indicators would likely improve both models equally.
A graph neural network that learns directly from nav graph topology without hand-crafted features would be the natural next step. The current 17-feature representation is already capturing most of what's extractable from simple spatial and local graph statistics. Getting meaningfully better would require letting a model learn what features matter from the graph structure directly.
Strict admissibility requires that the heuristic never overestimates the true cost, i.e., the correction factor must always be ≤ the true ratio. The models are trained with an admissibility penalty on predictions below 1.0, and predictions are clamped at inference time. This produces near-admissible rather than strictly admissible heuristics: around 2% of paths are suboptimal by roughly 2% on average, which matches the ~1.020 path cost ratio in the benchmark results.
For the purposes of this project that's a reasonable trade-off, significant reduction in search effort with minimal path quality loss. A strictly admissible version would require more conservative predictions and would likely sacrifice some of the node expansion gains.
Full source code and benchmarks on GitHub →