2077-gps-mod/contrib/re/docs/gps-routing-research.md

GPS Routing Research Notes

Current date: 2026-06-27.

This note summarizes the research pass prompted by the realization that "prefer highways" is a proxy, not the goal. The actual player-facing goal is a route that feels fast and drivable in Cyberpunk 2077, especially when the player is driving aggressively and ignoring normal traffic rules.

The conclusion is that the next patch should not be another broad highway multiplier. Production route engines and routing papers treat route quality as multi-criteria: edge traversal cost, transition/turn cost, road hierarchy, intersection delay, and user preferences are separate signals. For manual Cyberpunk driving, the best analogue is a momentum/corridor model: prefer routes that preserve speed and minimize decision points, sharp turns, short-segment churn, and awkward ramp transitions.

Sources Reviewed

• Bast et al., "Route Planning in Transportation Networks": https://arxiv.org/abs/1504.05140
• Jiang and Liu, "Computing the Fewest-turn Map Directions based on the Connectivity of Natural Roads": https://arxiv.org/abs/1003.3536
• Sacharidis and Bouros, "Routing Directions: Keeping it Fast and Simple": https://arxiv.org/abs/1309.4396
• Hlineny and Moris, "Generalized Maneuvers in Route Planning": https://arxiv.org/abs/1107.0798
• Dibbelt, Strasser, and Wagner, "Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs": https://arxiv.org/abs/1509.03165
• OSRM profile docs: https://github.com/Project-OSRM/osrm-backend/blob/master/docs/profiles.md
• OSRM car profile: https://github.com/Project-OSRM/osrm-backend/blob/master/profiles/car.lua
• GraphHopper profile docs: https://github.com/graphhopper/graphhopper/blob/master/docs/core/profiles.md
• Valhalla turn-by-turn API costing docs: https://valhalla.github.io/valhalla/api/turn-by-turn/api-reference/
• Valhalla auto costing implementation: https://github.com/valhalla/valhalla/blob/master/src/sif/autocost.cc
• RoutingKit README: https://github.com/RoutingKit/RoutingKit
• OSRM license: https://github.com/Project-OSRM/osrm-backend/blob/master/LICENSE.TXT
• Valhalla license: https://github.com/valhalla/valhalla/blob/master/COPYING
• GraphHopper license: https://github.com/graphhopper/graphhopper/blob/master/LICENSE.txt

High-Level Findings

There Is No Single "Good GPS" Objective

The route-planning survey by Bast et al. frames road routing as shortest-path search over nonnegative edge weights, then shows that most practical complexity comes from speed, preprocessing, traffic, and multiple criteria. It explicitly notes there is no single best route-planning method because systems are judged by different tradeoffs: query time, preprocessing effort, space, robustness to changing inputs, and model quality.

For our mod, that means "shortest distance" and "prefer highways" are both too thin. A better route is the minimum of a cost function we choose. The game already appears to run an A*/Dijkstra-style solver with a geometric heuristic and nonnegative edge costs. Our task is not to replace that algorithm; it is to feed it a better cost surface.

Production Engines Separate Edge Cost From Transition Cost

OSRM profiles define way speed/rate/weight separately from turn processing. The docs say speed should estimate actual travel time, while rate or weight should encode preference; changing speed to express preference skews duration estimates. OSRM also has a process_turn stage that can assign turn penalties by angle, traffic signals, obstacles, U-turns, road classes, and intersection context.

Valhalla does the same separation. Its auto costing computes edge cost from time, distance preference, density, surface, tolls, alley/service/track factors, and highway preference. Transition cost then adds turn/intersection behavior: OSRM-style turn duration, stop impact, turn type, ramp transition cost, roundabout cost, and U-turn penalties. This is exactly the split we should mirror: road class is only one part of the edge cost; turn and transition costs are a separate part of the route's feel.

GraphHopper's profile model reinforces this. It exposes road prioritization, turn costs, speed, priority, and distance_influence as separate tuning surfaces. Its docs also warn that reusing preprocessed heuristic data can require new weights to be greater than or equal to base weights to preserve correctness. That maps to our A* concern: negative bonuses and broad discounts can make a geometric heuristic less trustworthy. Nonnegative additive penalties are safer than "make good edges cheaper" as a first serious patch.

Human-Friendly Routes Minimize Turns And Decision Points

Jiang and Liu's fewest-turn paper is directly relevant even though Cyberpunk is not normal driving. The paper argues that people often choose routes by road continuity rather than segment-by-segment geometric distance. It highlights fewer turns as lower cognitive burden and explicitly connects fewer turns to fewer slow-down/speed-up events.

The important concept is "natural roads": sequences of segments joined by good continuity. A curve along a ring road is not necessarily a "turn" in the human navigation sense; changing from one road/corridor to another is the turn. The paper used a 45-degree deflection threshold when generating natural roads, but the exact threshold is less important than the idea: penalize route changes and poor continuity, not curvature by itself.

Sacharidis and Bouros extend this into a useful tradeoff model. They define route length and route complexity separately, with complexity as turn/road-change cost. They then discuss near-fastest routes that are as simple as possible and near-simplest routes that are as fast as possible. This is a good conceptual target for us: do not minimize turns at all costs, and do not minimize distance at all costs. Prefer a near-fast route that is much simpler and smoother.

Maneuvers Are State-Dependent

Hlineny and Moris model maneuvers such as turn prohibitions, traffic light delays, roundabouts, and multi-edge restrictions. Their important point for us is that a maneuver depends on how a vertex was reached, not only the current vertex. A plain Dijkstra state of "best cost to node" is insufficient when cost depends on a sequence of prior edges. Their M-Dijkstra expands state to vertex-plus-context.

We probably should not implement a full context-expanded solver inside a game binary patch. But the paper explains why our next hook needs predecessor or incoming-direction information. A turn penalty computed only from the current node flags is inadequate. The local RE already found the game keeps predecessor state at solver-state +0x1e, and the relax call receives current state, neighbor state, and candidate state. That is enough for a practical one-step turn/corridor approximation without redesigning the whole solver.

Speedups Are Mostly Not The Problem Here

Modern routing engines use A*, bidirectional search, contraction hierarchies, landmarks, arc flags, and related preprocessing to answer large road-network queries quickly. This matters academically, but not as the primary mod target. Night City's graph is small enough that the game already computes paths during play. The player's complaint is not "the route takes too long to compute"; it is "the route is dumb."

That said, we should respect solver assumptions. The game uses a straight-line heuristic in the full async solver. If we add only nonnegative penalties to g and to the candidate f = g + h, the heuristic remains conservative relative to the original distance-like base. If we add negative bonuses or deep highway discounts, we may make the heuristic too optimistic or otherwise distort ordering. The proof highway multiplier worked, but the 0.55/0.35 tests already showed how quickly discounts become pathological.

Open-Source Routing Engines

It is viable to use open-source routing software, but there are three different levels of "use":

• Use an engine's ideas and cost model.
• Use an engine offline to preprocess or classify Night City.
• Link or run an engine as the actual in-game route planner.

The first two are practical. The last one is possible, but much more invasive than patching the native solver.

Candidate Engines And Libraries

RoutingKit is the most interesting native-library candidate. It is a C++ route planning library under a BSD-2-Clause license. Its README emphasizes customizable contraction hierarchy support, flexible arc weights, and millisecond-or-better queries on continental-scale data. It exposes direct graph, index, and query APIs. If we wanted a true replacement solver inside a RED4ext DLL, RoutingKit is the most plausible starting point.

OSRM is a high-performance C++ routing engine and service under a permissive BSD-style license. It has excellent production lessons: profile-based cost modeling, turn processing, road classes, and CH/MLD preprocessing. However, it is built around its own extraction/preprocessing pipeline and OpenStreetMap-like data. Embedding OSRM directly would likely mean generating OSRM-compatible data from Cyberpunk resources, running preprocessing, shipping those artifacts, then calling libosrm or a local service.

Valhalla is a C++ routing engine under the MIT license. Its costing model is especially useful because auto routing separates edge cost from transition cost, includes highway preference as a mild factor, and explicitly handles ramps, U-turns, stop impact, density, alleys, service roads, surfaces, and closures. Direct embedding has the same issue as OSRM: Valhalla expects its own graph tiles and attribution model.

GraphHopper is Apache-2.0 and has a strong custom model/profile system, but it is Java. It is useful as a design reference and potentially as an offline analysis tool, but bundling a JVM or running a Java service beside Cyberpunk is not a good first mod architecture.

Generic graph libraries such as Boost.Graph or LEMON are options if we only need Dijkstra/A* and want to own the data model ourselves. They are lighter than OSRM/Valhalla but do not bring road-routing domain logic; we would still write the road/corridor cost model.

Integration Problem

External engines need a graph they own. Cyberpunk's GPS solver operates on internal route/node records, packed handles, and final route records. Linking an engine does not solve either boundary.

To replace the solver, we need:

• Extract or observe the full drivable graph: directed edges, coordinates, flags/classes, turn/intersection topology.
• Convert that graph into the engine or custom graph format.
• Map live start and target positions to graph nodes.
• Compute a route.
• Convert the chosen path back into handles/records the game expects, or hook late enough to draw and consume a custom route.
• Keep manual GPS, AutoDrive, pedestrian, quest-pin, and custom-pin behavior sane.

This is a bigger RE surface than modifying native edge relaxation. It may be worth it if the native solver proves too rigid, but it is not the cheapest next step.

Practical Ways To Use Engines

Best near-term:

• Use Valhalla, OSRM, and GraphHopper as cost-model references.
• Implement their proven split inside the native solver hook: edge cost plus transition cost plus mode/user preference.
• Use additive nonnegative penalties first.

Best offline/precompute:

• Extract VAND/navigation and traffic companion data.
• Build a standalone graph in the repo.
• Use RoutingKit or a small custom A* to experiment rapidly outside the game.
• Generate baked labels: corridor id, natural-road id, intersection complexity, ramp/connector classification, slope/airtime risk, and road-class confidence.
• Feed those labels back into the RED4ext patch as compact lookup tables.

Possible long-term replacement:

• Use RoutingKit or a custom solver in-game.
• Hook full solver output building around 0x818ba8 or later result materialization.
• Emit game-native route records from our computed node/handle path.

This replacement path is feasible only after we can round-trip a native route: decode a vanilla route into graph handles, reproduce it externally, then inject the same route back without changing behavior.

Recommendation

Do not link a full production engine yet. Use RoutingKit or a small custom graph runner offline to prototype and validate the cost function, then patch the native solver relaxation/cost surface. The native patch has hard game integration for free: target selection, start projection, route output, minimap/world-map drawing, and AutoDrive consumers.

Revisit full engine integration if:

• Predecessor/current/neighbor geometry is inaccessible.
• Native route output cannot express the desired route.
• The cost model requires expanded solver state that the game's one-label node state cannot support.

Implications For Cyberpunk 2077

Manual Player GPS Should Optimize Momentum

A real GPS assumes legal speed, stop signs, lights, congestion, safety, and human compliance. A Cyberpunk player in a Caliburn does not. The manual-driving cost model should assume:

• Posted speed is weak evidence. The player can exceed it.
• Traffic simulation metadata is useful but secondary. The player often cuts through or around traffic.
• Highway classification is useful but not decisive. Short freeway hops can be worse than a straight arterial or side-street corridor.
• Route smoothness matters because every hard turn, ramp dive, or intersection chain costs player speed and control.
• Roads with good continuity should be preferred even if they are not highways.

AutoDrive Should Remain More Traffic-Like

AutoDrive behaves more like an NPC/legal driver than the player does. It should benefit more from road hierarchy, speed limits, traffic-sim classes, and avoiding odd local shortcuts. Manual drive and AutoDrive probably should share the same hook site if possible, but they may need different parameter presets.

The previous warning still stands: do not accidentally apply a manual-only surface to AutoDrive while leaving manual GPS on another surface, or vice versa, unless the mode split is deliberate and documented.

Recommended Cost Model

The next prototype should use additive penalties at the solver edge-relaxation site rather than more highway discounts.

Base:

candidate_g =
  vanilla_g
  + short_segment_penalty
  + turn_or_continuity_penalty
  + intersection_complexity_penalty
  + ramp_transition_penalty
  + grade_or_airtime_risk_penalty
  + optional_road_class_penalty

Where:

• vanilla_g is the game's current current.g + delta * nodeMultiplier * directionMultiplier.
• short_segment_penalty discourages stair-stepping through many tiny edges.
• turn_or_continuity_penalty is based on predecessor/current/neighbor angle, not on road class alone.
• intersection_complexity_penalty approximates stop-start risk and decision points, probably from node degree, flags, or short connector density.
• ramp_transition_penalty applies when moving highway <-> non-highway through a short/angled connector.
• grade_or_airtime_risk_penalty applies when vertical delta or local shape indicates a steep launch/drop. This is lower priority until we prove the height fields are stable.
• optional_road_class_penalty can still mildly prefer highways/arterials, but should be subordinate to continuity.

Avoid negative "bonuses" in the first real version. If a road is desirable, make its alternatives pay an added cost. This preserves a safer A*/Dijkstra-style cost surface and avoids the pathological over-attraction seen with highway discounts.

Candidate Patch Sites

The proven but blunt hook:

• 0x40bb98: road-tail multiplier block in 0x40bb40.
• It sees solver and node and can inspect flags such as Highway.
• It cannot see predecessor/current/neighbor geometry, so it cannot distinguish a good corridor from a bad ramp hairpin.

The better next hook:

• 0x40b304 and 0x40b540: neighbor expansion helpers.
• They compute vanilla tentative g, straight-line heuristic h, and then call 0x40ba58.
• At the 0x40ba58 callsites, the live context includes solver pointer, current state, neighbor state, current node, neighbor node, candidate state, route mode, progress/delta, and enough vector data for one-step geometry.

The likely patch shape:

• Inline patch at the relax path, not a C detour on a tiny helper.
• Adjust candidate g and candidate f by the same nonnegative penalty before vanilla 0x40ba58 compares against neighbor_state+0x14 and writes neighbor_state+0x10.
• Keep the first build low-noise. Logging every edge expansion is pathological; route-window sampling or aggregate counters are enough.

First Prototype Parameters

Start conservative. The goal is to prove the model changes routes in the right direction without causing highway hairpins or search blowups.

Suggested first-pass terms:

• Short segment churn:
  • If edge distance/progress delta is under roughly 25-40 meters, add a small fixed penalty or a penalty proportional to the missing length.
• Turn continuity:
  • If predecessor position is available, compute normalized vectors prev -> current and current -> neighbor.
  • No penalty for very straight movement.
  • Mild penalty for shallow deflection.
  • Stronger penalty for 60-120 degree turns.
  • Very strong penalty for U-turn-like reversals unless near origin/destination.
• Corridor continuation:
  • Treat same-road or good-continuity transitions as neutral, not discounted.
  • A curved ring/highway should stay cheap if it is continuous.
• Ramp churn:
  • Penalize highway/non-highway transitions when the connector is short and the turn angle is high.
  • Do not penalize a long smooth ramp the same way.
• Intersection complexity:
  • Penalize nodes with many outgoing options or multiple short connectors if the relevant fields can be identified.
• Slope/airtime:
  • Start as logging-only unless height deltas clearly correlate with known bad places. Add as a later penalty.

Testing Plan

Keep the route set from previous testing:

• El Coyote / city-center custom pin, because it exposed the bad hairpin.
• Side job, Sinnerman, and Claire from the fixed car save.
• Violence / No-Tell Motel cross-city routes.
• The Gig / Cassius Rider long Watson route.
• Aldecaldo / Badlands routes.
• Cyberpsycho sighting on the unfinished highway.

Add tests targeted at the new model:

• A straight long side-street corridor in Heywood vs a short freeway hop.
• A route with several 90-degree stair-step alternatives.
• A known suspended-highway offramp or hilly road that causes airtime at speed.
• AutoDrive on the same destination, to check whether its behavior remains sane.

Practical Next Step

The static pass around 0x40b304, 0x40b540, and 0x40ba58 is complete enough for the first prototype:

• 0x40ba58 has four direct callers: 0x40b175, 0x40b4ac, 0x40b6d5, and 0x40bca7.
• The ordinary adjacency walkers are the two clean first patch sites: 0x40b4ac from 0x40b304, and 0x40b6d5 from 0x40b540.
• At both ordinary sites, the live context contains solver, current state, neighbor state, current node, neighbor node, current progress, neighbor progress, vanilla g, and vanilla f.
• A disabled-by-default RED4ext prototype now patches the two ordinary sites by adding a fixed nonnegative per-edge penalty before calling vanilla 0x40ba58.

Remaining static work before the full momentum model:

• Confirm candidate vector layout at 0x40b8f0/state allocation.
• Confirm route-mode values at solver+0xc4 for manual driving vs AutoDrive.
• Identify a cheap way to detect road-class transition from current/neighbor node flags.
• Decode predecessor geometry from state+0x1e well enough to compute predecessor/current/neighbor turn angle.
• Decide whether the later turn/ramp model should also patch the special/helper relax paths (0x40b175, 0x40bca7) or keep them vanilla.

Next implementation step is to enable and test the smallest additive prototype with route-result comparisons. If the fixed per-edge penalty moves paths in the right direction and remains stable, extend it into a live-tunable cost file and then add turn/continuity penalties. Keep highway multiplier support available as a diagnostic knob, but do not use it as the primary default behavior.