Development of Island Overdrive is continuing nicely, with new features being added all the time. This week I have mostly been working on adding some GPS-style navigation. The idea has been used in most racing games over the last 10 years, so it seemed like something I should add!

As always, the internet is our friend here. I found this cracking article, complete with source code, that explains in a little detail how to implement Dijkstra’s algorithm – a way of finding the shortest path between two nodes in a graph. The important step here is actually creating the graph. Fortunately I am still using my heavily modified version of CiDy, a Unity asset for creating roads that is based around a similar node graph. It didn’t take long before I was able to extract the CiDy road data into the new Dijkstra-style graph.

A few modification were necessary to the graph code, mostly so I could store some extra data like the position of a node and the CiDy road that corresponds to a Connection in the graph. To test the code, a little test like this can be used:

var nodeA = GetNode(0);
var nodeB = GetNode(80); // there are quite a few roads on this island...
nodeB.SetAsStartNode();
ShowRoute(nodeA);

I have modified the ShowRoute method to do something useful rather than just output some log – namely enable some of the meshes that show the GPS direction.

Visualising the GPS navigation is a slightly different subject and very much depends on how you want to present the navigation to the player. At the moment I’m aiming for both displaying on the minimap and on the actual road surface. I may also choose to add visual cues like “Turn Left” or “Turn Right” as the player approaches a junction (something done to good effect in Burnout Paradise, one of my favourite driving games and a real inspiration behind Island Overdrive).

To get the centre marking I am duplicating the road mesh, moving the vertices in to match the width specified. This is done via a custom editor script rather than at runtime. At the moment the same mesh is used on the road and on the mini-map, but I will separate those out soon.

There are two materials, one with an arrow pointed up, one pointing down (forgive the quality of the arrow, it took all of 2 seconds to make :). At the point at which a route change is detected we iterate through the nodes in the graph. From a pair of nodes we get a Connection object, and from that obtain the actual CiDy road. If the first end of the road matches the current node then set one material, otherwise the other material is used.

So there it is – the starting point of a very useful feature. Lots to do though! The most obvious missing feature is that the GPS markers are missing from the intersections. I’d also like to change the materials to be transparent, more colourful and animated too. Separate the road and mini-map meshes so I can use a wider solid colour line for the mini-map. And there is no interface for actually selecting a destination point, so it’s pretty useless as it always takes you to the same point!