viksoe.dk

Routing in Seoul

Routing in Seoul


This article was submitted .


I kind of like exploring the Asian continent, so every year I choose a country in Asia to travel to.

To help me with the hassles of globetrotting, I have written a travel app for my phone, which includes a complete travel guide, my own logs and notes, live weather reports, news feeds and lots of other good stuff. The travel guide content is mostly compiled from the Wikipedia and Wikivoyage websites, and also integrates with the Nokia HERE Maps mapping and navigation services. HERE Maps is rather excellent and natively built into every Windows Phone device.
And the best part is: in my app everything works offline.

The next two countries on my travel list is South Korea and Japan. And as it turns out, both of these countries have a weird law that prevent Google and HERE Maps from offering offline mapping services. As a consequence my app will become somewhat useless to me without integrated offline maps and navigation.

So I'm faced with the task of building my own Google Maps service.

Building offline maps

To limit the scope of this project, I decided that my app's offline viewer should display detailed maps only of the cities I'd expect to travel to. Also, it should use pre-rendered tiles, similar to how your average online mapping service just downloads tiles off a web-service and displays them as images in your web-browser without much processing.

I will be using data from the fantastic OpenStreetMap project. If you are not familiar with this project, please go to the website right now and explore and participate. It's basically a community driven version of Google Maps, and all data is free.

Since open-source map viewer controls already exists, I took to the web to search for an existing solution. One requirement is that it must work on my Windows Phone, so I thought I'd be limited in choices, but one particular project, Clemens Fischer's XAML Map Control, turned out to be my saviour. Not only does it have really great quality map viewer functionality, it even includes a plugin system to allow various caching mechanisms. One of these caching plugins simply stores new tile images downloaded from the web in a local database!!

With a little tweaking of the XAML Map Control, I was able to compile a desktop C# version, enable the cache plugin and simply pan over the target travel destination area. This would slowly build a tile cache database. An hour later, and now armed with a 250 MB tile cache, I recompiled the Windows Phone sample included in the project and added the cache file to the phone's external storage, and presto... a working offline mapping service with very little effort spent.

Building offline navigation

Now for the tricky part: offline routing and navigation.

At a minimum, the scope of my project must include subways and bus ride navigation. I think I will get by without street navigation, merely using my new offline map viewer and some visual cues in the travel app instead.

Still, it seems like a daunting project.
Routing will require collecting actual data detailing connectivity of subway stations, bus stops and maybe even streets.

Again we turn to the OpenStreetMap (OSM) project.
Go to the OSM Overpass Turbo website to access one of the export functions of the OpenStreetMap service.
Pan the map over the city of Seoul in South Korea and paste the following snippet:
[out:json][timeout:60];
(
  relation[route=subway]({{bbox}});
);
>>;
out body;
Press the "Search" button, then hit "Export" and choose the "Raw Data" format. Here's a quick link.

This will export a rather large JSON file. It contains the Nodes, Ways and Relations of the actual OpenStreetMap data.
Relations are high-level descriptions of bus routes and subway lines for each direction of travel. A Relation is composed of Ways and Nodes, where Ways describe the physical street-level trail, and the Nodes placed directly under a Relation lists the subway stations/stops made on that line. So to enumerate the entire subway network of the city of Seoul, we just traverse all the Relations and their collection of Nodes marked with the "stop" role.

To import the JSON file into your project, we need to define its structures in C#. For the Desktop version, I'm using the default Microsoft DataContractJsonSerializer.

[DataContract]
class OsmOverpass
{
  [DataMember(IsRequired=true)]
  public string version = null;
  [DataMember(IsRequired = true)]
  public string generator = null;
  [DataMember(IsRequired = true)]
  public List<OsmElement> elements = null;
}

[DataContract]
public class OsmElement
{
  [DataMember(IsRequired = true)]
  public string type = null;
  [DataMember(IsRequired = true)]
  public ulong id;
  [DataMember]
  public double lat;
  [DataMember]
  public double lon;
  [DataMember]
  public OsmTags tags = null;
  [DataMember]
  public List<OsmMember> members = null;

  // Shared vertices
  public List<Vertex> shared = null;
  ...
and so on.

For the Windows Phone version, I'm using the JSON.NET library. The Desktop version loads instantly, but on Windows Phone the 1.9 MB JSON file takes more than 2 seconds to load.

Then we import the file...
var stream = File.Open(@"export.json", FileMode.Open);
var js = new DataContractJsonSerializer(typeof(OsmOverpass));
OsmOverpass import = js.ReadObject(stream) as OsmOverpass;

And we need to index all the elements found in the JSON file.
This will improve performance when we begin to process them in a moment.
var routes = new Dictionary<ulong, OsmElement>();
var nodes = new Dictionary<ulong, OsmElement>();
var hash = new HashSet<ulong>();
foreach (var el in import.elements)
{
  if (hash.Contains(el.id)) continue;
  if (el.type == "node") nodes[el.id] = el;
  if (el.type == "relation") routes[el.id] = el;
  hash.Add(el.id);
}

Introducing A Star

To effectively route from one point to another, we need to find the shortest path between those two points.

In computer graph theory, and in particular for computer game developers, the Dijkstra's search algorithm and generalizations of it with the A-Star Search algorithm, is the holy grail when it comes to pathfinding. But since algorithms better suited for large-scale routing are available, we should be able to explore these as well.

Once again, I'm not going to implement it, but instead will find an appropriate implementation on the Internet. The QuickGraph.Net graph library has excellent support for several of the most popular Shortest Path algorithms. I'm particular interested to see how the A-Star does with this data-set, because it's likely to perform better, but not always find the most optimal path because of the way the heuristics work.

The QuickGraph.Net library will allow us to toggle between several search algorithms.

  • Dijsktra Shortest Path
  • A-Star Shortest Path
  • Bellman-Ford Shortest Path
  • Directed Acyclic Graph

So we set out to build a graph for the Dijkstra algorithm.

First we'll introduce a graph vertex structure. It will contain references to an OSM Element that define a subway stop, its OSM Relation (the subway route), and most importantly a neighbour list. This list shall contain its immediate neighbours it can travel to.
public class Vertex
{
  public OsmElement el { get; set; }
  public OsmElement rel { get; set; }
};

QuickGraph.Net will take a Dictionary data type, where each vertex is assigned as the Key part of the (Key, Value) pair, and the Value part would be the neighbour list.
var graph = new Dictionary<Vertex, List<Vertex>>();

Let's begin with a big push to add all the subway stops to the graph.
foreach (var route in routes.Values)
{
  Vertex previousVertex = null;
  foreach (var member in route.members.Where(e => e.role == "stop"))
  {
    OsmElement element = null;
    if (!nodes.TryGetValue(member.reference, out element)) continue;

    var vertex = new Vertex() { rel = route, el = element };

    graph[vertex] = new List<Vertex>();
                    
    if (vertex.el.shared == null) vertex.el.shared = new List<Vertex>();
    vertex.el.shared.Add(vertex);

    if (previousVertex != null) graph[previousVertex].Add(vertex);
    previousVertex = vertex;
  }
}
This will add all the subway line stops to a big bag of vertices.

We make sure to add the adjacent next stop to the neighbour list of the current vertex, so we can easily explore the surrunding stops and exits.

At many stations you will be able to exit the train and depart on a connecting subway line. In the code above we also maintained lists of all routes that share the same subway station stop, so now we can expand their neighbour lists.
This is what we do here:
foreach (var vertex in graph.Keys)
  foreach (var v in vertex.el.shared)
    if (vertex != v && !graph[vertex].Contains(v)) graph[vertex].Add(v);

We should make up the start- and destination-vertex:
var beginVertex = new Vertex()
{
  rel = new OsmElement() { id = 1, tags = new OsmTags() { name = "Begin Journey" } },
  el = new OsmElement() { id = 2, lat = 37.558198, lon = 126.936794, ... }
};
var endVertex = new Vertex() 
{
  rel = new OsmElement() { id = 3, tags = new OsmTags() { name = "End Journey" } },
  el = new OsmElement() { id = 4, lat = 37.505737, lon = 126.939289, ... }
};

graph[beginVertex] = new List<Vertex>();
graph[endVertex] = new List<Vertex>();

Now to connect the start- and destination-vertex to the graph, we should add these vertices to neighbour lists of subway stations within walking distance. I'm prepared to walk 1 km to find the subway.
foreach (var vertex in graph.Keys)
{
  if (DistanceEuclidean(vertex.el, beginVertex.el) < 1.0)
    graph[beginVertex].Add(vertex);

  if (DistanceEuclidean(vertex.el, endVertex.el) < 1.0)
    graph[vertex].Add(endVertex);
}

We're getting ready to call the search algorithm.

Before we can call the algorithm, we need to write a support function for it. It computes the cost of traveling between two connected vertices. For simplicity you could just return the distance between them, but we are allowed to add additional cost, such as waiting for a node to become available (ie. a train arrival), or difficulty in passing the terrain (walking speed vs. vehicle speed).
Here it is...
Func<SEquatableEdge<Vertex>, double> edgeCost = (edge) =>
{
  return DistanceEuclidean(edge.Source.el, edge.Target.el);
};

In the final version (available for download below), I have a helper function, DetermineCost, that equally calculates the distance between the two WGS-84 longitude & latitude coordinates, along with incorporating a penalty for walking up to any subway station, and for switching subway lines during travel.

And finally we can call the search algorithm and print the result.
var velg = graph.ToVertexAndEdgeListGraph(kv => 
  kv.Value.Select(n => new SEquatableEdge<Vertex>(kv.Key, n)));
var algo = new DijkstraShortestPathAlgorithm<Vertex, SEquatableEdge<Vertex>>(velg, edgeCost);
var vis = new VertexPredecessorRecorderObserver<Vertex, SEquatableEdge<Vertex>>();
using (vis.Attach(algo))
{
  algo.Compute(beginVertex);
  IEnumerable<SEquatableEdge<Vertex>> path;
  if (vis.TryGetPath(endVertex, out path))
    foreach (var n in path) Console.WriteLine(n.ToString());
}

And it actually works.

Routing result

Now, there are a few areas where we can improve this.

First, we should export bus-routes as well. To do this, just add...
relation[route=bus]({{bbox}});
to the Overpass export snippet.
Mind you, the extra time to load a JSON file of that size may warrant that you change file format.

Now that we have bus-stops in the import, we need to be able to exit the train-station and board a bus within a reasonable walking distance (500 m).
foreach (var vertex in graph.Keys)
{
  foreach (var v in graph.Keys.Where(e => e.rel != vertex.rel)
  {
    if (DistanceEuclidean(vertex.el, v.el) > 0.500) continue;
    if (!graph[vertex].Contains(v)) graph[vertex].Add(v);
  }
}

Also, if no station was located within the 1 km range of the start- and destination-vertex, we could just add the nearest one.

For many cities, the OSM data does not contain a route for each travel direction, so we should detect if we need to reverse the neighbour list.

When traversing the resulting path, you will be able to inspect the references of the OSM Node (ie. train station) and the OSM Relation. Whenever you see the Relation reference changing, you will know the path has changed train- or bus connection, and by comparing the two OSM Nodes, you can inform the user whether he needs to transfer to a connecting train line, or walk out of the train station to catch the near-by bus route.

Similar, to provide more detailed turn-by-turn navigation information, you can inspect the OSM Relation attached to each stop, and locate the OSM Way elements attached to it. From there, you can find and trace the streets that the path follows. I guess it doesn't make as much sense when only dealing with train and bus-routes, but the same principles work for street navigation.

While OpenStreetMap data is plentiful and usually of good quality, the data for other cities may require tweaking or is lacking in other ways. In many cases, data can be slightly out-of-date as timely imports of official public transportation data may not be of great focus of the OSM community in your area. That is why I'll encourage you to participate on the OpenStreetMap website and help improve maps in your area. Go there now and join up.

The Visual Studio project available for download below includes a sample import file and the C# implementation of many of the features explained here. Have fun.

Notes

This sample does not include the entire app project, but only demonstrates the routing part. Maybe I will publish my travel app at some later point. Right now, it is not even available in the Windows Store.

The built-in Nokia HERE Maps integration has since been deprecated in recent Windows Phone versions by Microsoft. Quite sad really. But it just makes my little project even more important for me, as quality for Windows Phone services drops.

Source Code Dependencies

Microsoft Visual Studio.NET 2013
Microsoft .NET Framework 4.5

Download Files

DownloadSource code (126 Kb)

To the top