An Eve Online Path finder Service with WCF and QuickGraph

A good friend of mine is playing the MMO Eve Online and from what I’ve seen it’s a very cool game. The environment is a huge Universe with solar systems, stars, stations, corporations and battleships. But my friend had a problem. From a given solar system he wanted to fly to the nearest solar system which includes a given corporation station.

The cool thing is, CCP, the company responsible for Eve online, let’s you download a big SQL database with all solar systems and much more from their homepage. You can import the database into MS SQL Server or MS SQL Express with the database import tool.

At first I created a new WCF Web Service and added the following Entity Framework Model:

My Model represents 3 from about 100 tables. Note the Many To Many relationship between Solar Systems. In Eve you can jump from one system into another and these connections are handled in the “mapSolarSystemJumps” table.

Now I referenced “QuickGraph.dll”. QuickGraph is an excellent library with a ton of useful graph algorithms and data structures from Microsoft researcher Jonathan de Halleux. You can get it from Codeplex here or install it with the new fancy Nuget tool. The command should be “install-package Quickgraph”.

Let’s write some code! My WCF service will expose one Method “NearestRoute” and one Datatype “MapSolarSystemEdge” wich represent a jump.

[ServiceContract]
public interface IService
{
	[OperationContract]
	IEnumerable<MapSolarSystemEdge> NearestRoute(int fromSolarSystemId, int destinationCorpId);
}

[DataContract]
public class MapSolarSystemEdge
{
	int fromId;
	int toId;

	[DataMember]
	public int From
	{
		get { return fromId; }
		set { fromId = value; }
	}

	[DataMember]
	public int To
	{
		get { return toId; }
		set { toId = value; }
	}
}

Trying to get the shortest route in a big Graph with Dijkstra algorithm takes some time. So it will be nice, if our service runs with only one instance and caches QuickGraphs internal Dijkstra function for a given root solar system.

[ServiceBehavior(InstanceContextMode=InstanceContextMode.Single, ConcurrencyMode=ConcurrencyMode.Multiple)]
public class Service : IService
{
	private EveContext context; // Entitiy Framework Context
	private AdjacencyGraph<MapSolarSystem, Edge<MapSolarSystem>> eveGraph; // Eve Online Solar System Graph
	private Dictionary<int, TryFunc<MapSolarSystem, IEnumerable<Edge<MapSolarSystem>>>> getPathCache; // Dijkstra Function Cache
}

With InstanceContextMode.Single the service will only start one instance and every visitor will connect to the same instance. ConcurrencyMode.Multiple allows my service to be used by with many connections at the same time.
EveContext is the connection to the Entity Framework Model.
AdjacencyGraph holds the complete Eve universe. The Vertices are from type MapSolarSystem and each Edge connects two MapSolarSystems. Note that the edges are a directed. If you want to use undirected edges you can use the UndirectedEdge type.
The Dictionary is my function cache for a given SolarSystem id.

When the service runs for the first time, it has to create a new Graph wich represents the Eve universe. I’m doing this in the service constructor with the following code:

public Service()
{
	context = new EveContext(); // EF Context
	eveGraph = new AdjacencyGraph<MapSolarSystem, Edge<MapSolarSystem>>(); // Eve universe
	getPathCache = new Dictionary<int, TryFunc<MapSolarSystem, IEnumerable<Edge<MapSolarSystem>>>>(); // function cache

	var dbResult = (from s in context.MapSolarSystems
						from e in s.ToSolarSystem
						select new { From = s, To = e }).AsEnumerable();

	var edges = dbResult.Select(a => new Edge<MapSolarSystem>(a.From, a.To)).OrderBy(e => e.Source.solarSystemID).ToList();
	var vertices = context.MapSolarSystems.ToList();

	eveGraph.AddVertexRange(vertices); // Fill Graph
	eveGraph.AddEdgeRange(edges); // Fill Graph
}

To fill my Graph I need a list of all SolarSystems and all Jump connections between them. Getting the Vertices was easy. But for the Edges I had to create an anonymous type first and than select it into an Edge. I’m not exactly sure why, but selecting an Edge directly with “select new Edge<MapSolarSystem>(s, e)” was not possible.

Now our Service is initialized. Let’s implement NearestRoute. NearestRoute returns an IEnumerable of type MapSolarSystemEdge. It’s a list of Edges where each Edge represents a valid jump and in all they are our path from start to finish.

I begin with initializing some variables. allPathes is a list of all possible ways to get from start to finish. But we want the shortest path, witch will be saved into result. from holds the starting position. corpSystems is a list of all SolarSystems containing the requested corporation and tryGetPath is the path function which goes from MapSolarSystem to a List of Edges.

	var allPathes = new List<IEnumerable<Edge<MapSolarSystem>>>();
	var result = new List<MapSolarSystemEdge>();
	var from = context.MapSolarSystems.Where(m => m.solarSystemID == fromSolarSystemId).SingleOrDefault();
	var corpSystems = from station in context.Stations
						  where station.NPCCorporation.corporationID == destinationCorpId
						  group station by station.MapSolarSystem into grouping
						  select grouping.Key;
	TryFunc<MapSolarSystem, IEnumerable<Edge<MapSolarSystem>>> tryGetPath;

The next step is to check if the function is already cached. If not we will create it. Creating the function is an expensive task, as QuickGraph will create an internal data structure for it (I think it’s an adjacency list).

	if (getPathCache.ContainsKey(from.solarSystemID))
	{
		tryGetPath = getPathCache[from.solarSystemID];
	}
	else
	{
		tryGetPath = eveGraph.ShortestPathsDijkstra(v => 1, from);
		getPathCache[from.solarSystemID] = tryGetPath;
	}

ShortestPathsDijkstra needs two parameters. The first parameter is a cost function for Edges. In Eve it can be a function which goes from Edge to Security Level. But I don’t care about it here, so each Edge has a cost of 1. The second parameter is the starting point.

Now I have to go over each SolarSystem wich includes my corporation and run tryGetPath on it. After that I will order the List by the number of jumps to get the nearest SolarSystem:

	foreach (var toCorpSystem in corpSystems)
	{
		IEnumerable<Edge<MapSolarSystem>> path;

		if (tryGetPath(toCorpSystem, out path))
		{
			allPathes.Add(path);
		}
	}

	var shortestPath = allPathes.OrderBy(p => p.Count()).FirstOrDefault();

As I have my shortest path now, I have to add it to my result list of type MapSolarSystemEdge.

	foreach (var item in shortestPath)
	{
		result.Add(new MapSolarSystemEdge() { From = item.Source.solarSystemID, To = item.Target.solarSystemID });
	}

	return result;

That’s all! A clean and simple way to solve this problem and QuickGraph offers a lot of other cool stuff.

If you have question’s or liked this post, just send me note.

This entry was posted in C#. Bookmark the permalink.