Over the past month we’ve changed the algorithm that searches the map to find routes. It is now much more like the A*search algorithm. The results it produces are identical to those produced previously, but it happens faster.
A* is fast because it uses a clever way of minimizing the amount of map it needs to check to find a route. From the start point the distance as the crow flies to the finish can easily be estimated from the map using geometry (if you had a paper map you could measure it with a ruler and refer to the scale). To search for a route, follow these steps:
- Examine each of the neighbouring junctions. They may be nearer to or further from the finish.
- For each junction record the total of the crow-fly distance from there to the finish and distance travelled from the start point.
- Keep a list of the junctions ordered by the total, lowest first.
- Repeat these steps for the first junction on the list until either the finish is reached or the list is empty.
This algorithm is actually simpler than previously and has enabled us to refactor and simplify the code. The only hard bit is keeping an efficient ordered list of junctions. Fortunately the language we are using to implement the algorithm (PHP5.3) has recently expanded its library to include SPLPriorityQueue which we were able to use directly.
The effect of these changes has been to speed up this part of the route planning process. This part of the algorithm used to take several tens of seconds to find a 10 mile route across London, but that can now be done in less than 2 seconds. Our attention is now turning to other aspects of the whole route generation process where further time savings can be made.
