Until recently at work, we’ve been using the excellent QuickGraph library for finding optimal haul routes across pits. This week, I replaced it with my own creation, SpryGraph, written from the ground up for performance. (SpryGraph is not a replacement for QuickGraph, due to only having a tiny subset of the features)

Path finding is a much-researched topic in computer science. For a good overview see this paper [pdf].

Some brief performance comparisons:

How to use it:

First define your graph, vertex and edge classes:

using System;
using System.Collections.Generic;
using Alastri.SpryGraph;

namespace MyApp
{
    public class MyGraph : IMinimalPathFindingGraph<MyVertex,MyEdge>
    {
        public IReadOnlyList<MyEdge> GetOutEdges(MyVertex vertex)
        {
            return vertex.OutEdges;
        }
    }

    public  class MyEdge : ICostedEdge<MyVertex>
    {
        public MyEdge(MyVertex source, MyVertex target)
        {
            Source = source;
            Target = target;
        }

        public MyVertex Source { get; private set; }
        public MyVertex Target { get; private set; }
        public double GetCost()
        {
            return MyVertex.Distance(Source, Target);
        }
    }

    public  class MyVertex : IHeuristicVertex<MyVertex>
    {
        public MyVertex(double x, double y, double z, IReadOnlyList<MyEdge> outEdges)
        {
            X = x;
            Y = y;
            OutEdges = outEdges;
            Z = z;
        }

        public double X { get; private set; }
        public double Y { get; private set; }
        public double Z { get; private set; }

        public IReadOnlyList<MyEdge> OutEdges { get; private set; }

        public static double Distance(MyVertex a, MyVertex b)
        {
            double dx = a.X - b.X;
            double dy = a.Y - b.Y;
            double dz = a.Z - b.Z;
            return Math.Sqrt(dx * dx + dy * dy + dz * dz);
        }

        public double Heuristic(MyVertex destination)
        {
            return Distance(this, destination);
        }
    }
}

Second, create some code to do path finding:

using System;
using Alastri.SpryGraph;

namespace MyApp
{
    class Program
    {
        static void Main()
        {
            //create our graph
            MyGraph myGraph = new MyGraph();

            //create some vertices
            MyVertex v1 = new MyVertex(1,2,3);
            MyVertex v2 = new MyVertex(4,5,6);

            //add an edge from v1 -> v2
            v1.OutEdges = new[] {new MyEdge(v1, v2)};

            //read the graph into an efficient data structure
            GraphReader<MyVertex, MyEdge> graphReader = new GraphReader<MyVertex, MyEdge>(myGraph);

            //get a re-usable path finder, starting at v1
            IPathFinder<MyVertex,MyEdge> pathFinder = graphReader.GetAStarPathFinder(v1);

            //find path to v2
            MyEdge[] path;
            if (pathFinder.TryGetPath(v2, out path))
            {
                foreach (var item in path)
                {
                    Console.WriteLine("{0},{1},{2} -> {3},{4},{5}", v1.X, v1.Y, v1.Z, v2.X, v2.Y, v2.Z);
                }
            }


        }
    }
}

If successful, it should print:

1,2,3 -> 4,5,6

The full source is available here.