Repository navigation
Routes
3DAndreas finds routes on the paths of the game: the roads vehicles drive, the lanes for boats and the paths pedestrians walk, which the map database holds since version 0.7.0. A route is found inside the native that asks for it, in some tens of microseconds, with no thread and no callback.
The game has 30,587 nodes on its roads and 37,650 on its paths for pedestrians. Most of them only lead from one node to the next, so the component joins them into chains between junctions: 2,304 junctions and 3,185 chains for the roads. A node is a junction where more than two ways meet, where a road starts or stops being one way, and where the kind of road changes.
Each link of a road knows how many lanes go each way, from the navigation nodes of the game, and 11,524 of the 59,620 links of the roads go one way. Routes for vehicles keep to them, except A3D_ROUTE_ANY_WAY.
The roads come in three kinds, which set the speeds of Route types: highways, roads the traffic of the game drives, and roads it leaves alone, such as dirt roads, tracks, alleys and the ends of drives and car parks. A3D_ROUTE_TRAFFIC keeps to the first two.
A route goes from chain to chain, and each change at a junction costs time by its angle: two seconds to the right, five to the left and thirty to turn back. So a route does not zigzag across a grid of streets where a straight way costs the same, and turns back only where it must, at a dead end or after a wrong turn. A3D_GetRouteTurn gives the turns a driver takes, and Turns tells what they mean.
A vehicle already moving gives its heading to A3D_FindRoute. Starting against it costs a turn back, so a route keeps going the way the car faces unless turning around saves more than half a minute.
When the server starts, the component builds a contraction hierarchy for each type of route, on a thread of its own, in about a second. A hierarchy adds shortcuts between junctions in order of importance, and a route then climbs from both ends to meet in the middle, visiting a couple of hundred junctions instead of thousands. Until a hierarchy is ready, its routes are found with A* on the chains, in about a millisecond, and come out the same.
| Question | Time |
|---|---|
| A3D_FindRoute across the map, with its points | 30 to 50 µs |
| A3D_MeasureRoute across the map | 10 to 20 µs |
| A3D_FindNearestByRoute of 50 places | 0.3 ms |
| A3D_GetNearestPathPoint | 1 to 2 µs |
| A3D_GetRouteProgress | 1 to 5 µs |
Each type was checked over 500 random pairs against A* on the chains, which always finds the best route: the hierarchies gave the same cost every time. Performance compares the routes with a GPS plugin.
The ends of a route go to the nearest point of a road or a path, along the line between its nodes, rather than to the nearest node. Height counts twice, so the road under a bridge is farther than the road beside.
Some pieces of road do not connect to the rest, such as a car park whose only way out is one way. When the nearest roads to both ends do not connect, the ends go to the nearest roads of the main network instead.
A3D_ROUTE_WALK follows the paths pedestrians walk in the game, and the roads where there are none, a little slower so the paths come first and the highways last. The paths and the roads meet where the ends and the junctions of each lie within 20 metres of the other.
With the navigation mesh, a walk shorter than 500 metres goes the shortest way across squares, yards and car parks, and a longer one walks on the mesh from its start to the paths and from the paths to its end.
A3D_ShowRouteForPlayer draws a route on the radar and the map of a player, and moves the line on as they go, five times a second. The line is made of gang zones sent straight to the client of the player, so it takes no gang zone of the server and no memory there. A3D_OnRouteArrived and A3D_OnRouteLeft tell the script when the player arrives or strays, and A3D_OnRouteAdvanced when the next turn or the distance to it changes.
examples/gps.pwn in the repository is a filterscript that makes a GPS of all this. A player marks a place on the map of the pause menu, a line leads there on the radar, the next turn shows on the screen, and the route is found again when they stray or get in or out of a vehicle.