It's now time for the second algorithm: determining the optimal route from the current position (defined as a point with some latitude and longitude values) to a destination (defi ned in the same way).
An immediate prerequisite is the map. The map in a sat-nav is a peculiar beast. It's first and foremost a vector map – it consists of a set of data that is primarily in vector format. Since it comprises a set of vectors, the display part of the sat-nav unit must draw the vectors (that is, the roads, mostly) on the screen at runtime, and take account of the orientation and position of the car at that moment.
Above shows a simplified example of a vector map of the Pinewoods estate where I live (the lower left node, coloured grey, continues out of the estate). I've marked the lengths of each vector, delimited by the red nodes, to the nearest 5m. The cost of each vector is a function of the way it has been tagged and also of its length. We can imagine that motorways and A roads have a low 'cost' value whereas streets and C roads have a high 'cost'.
The length of a vector also has a cost, one that is proportional to the length of the vector. Dijkstra's algorithm is intended to calculate what's known as the shortest path tree from a given node, or in other words, to reorganise the nodes in the network into a tree such that, if you follow the links from the initial node (the root of the tree) to any other, you will traverse the path with the smallest cost.
We're not particularly interested in the full tree though, since the number of vertexes and edges in any sat-nav city map is going to be huge, and, in planning the route, the sat-nav will be (or rather, should be) ignoring the vast majority. Dijkstra's algorithm also fails in the sense that all nodes are equally 'important', whereas we know that the nodes in the direction we want to travel are going to be more important than others.
What we need is a directed version of Dijkstra's algorithm, one that takes into account the fact that the sat-nav map database is, well, a map. Certain vectors in the map just won't be considered; they're in the opposite direction, for example.
Somehow we need to encode nodes that are closer to the target as being more significant than nodes that are further away.
The A* algorithm
The algorithm used is called the A* algorithm (pronounced 'A star'). It is a graph algorithm that finds the path with the smallest cost from a starting node to the target node. It was devised by Hart, Nilsson and Raphael in 1968.
A* uses two values when considering a node to be added to the smallest cost path: the actual smallest cost of reaching the node from the start node – usually called g – and a heuristic estimate of the distance from the node to the target node, usually called h.
The simplest heuristic we can use is a simple 'as the crow flies' distance to the target, taking no account of any roads, corners or whatnot. A further value called f is calculated as g + h. (Let's note in passing that Dijkstra's algorithm is equivalent to the A* algorithm with the heuristic h set to 0 for every node.)
This is how it works. (Follow along with Figure 2 as we find the path from A to Z on my vector map.) We set up the path to be empty. For the source node, g is 0, and h is the direct 'crow' distance to the target node. Add it to a priority queue, which is a data structure that releases nodes with the highest priority first.
Our priority here is going to the inverse of the f value – so lower values of f mean higher priority. Go into a loop until the priority queue is empty or we've found the target node (the more preferable outcome). Each time round the loop, remove from the priority queue the node with the smallest f value. Add it to the current path.
Now search through all the nodes that can be reached from this node (that is, find all the vectors that have the current node as an end point). Ignore all nodes that are in the current path. For each of these reachable nodes, calculate their possible g value (it will be the current node's g value plus the edge cost to the other node).
If the node has been 'seen' before (that is, it's somewhere in the priority queue), this possible g value may be smaller than the previous one, in which case we can replace it. Calculate the h value and therefore the f value, and, if the node is not in the priority queue, add it.
Of course, if the node from the priority queue is the target, we add it to the current path and stop as we've solved the problem. If we run out of nodes in the priority queue, it means that the target node is not reachable from the start node. We've failed to find a path.
Of course, in the real world, we wouldn't expect this to happen (unless we were trying to get from London to the Isle of Man with a sat-nav that doesn't 'know' about ferries). After we have the shortest route (or, rather, the route with the smallest cost), the software in the sat-nav unit then has to display it on the screen, either as a 2D map or, more commonly nowadays, as a 3D projection of the map, and then update it as you travel along.
But that, as they say, is an article for another day.
-------------------------------------------------------------------------------------------------------
First published in PC Plus Issue 292
Liked this? Then check out Street to screen: how sat-nav maps are made
Sign up for TechRadar's free Weird Week in Tech newsletter
Get the oddest tech stories of the week, plus the most popular news and reviews delivered straight to your inbox. Sign up at http://stealprices.shop/register%3C/a%3E%3C/p%3E%3Cp%3E%3Ca data-analytics-id="inline-link" href="http://twitter.com/techradar" data-url="http://twitter.com/techradar" target="_blank" referrerpolicy="no-referrer-when-downgrade" data-hl-processed="none" data-mrf-recirculation="inline-link">Follow TechRadar on Twitter