Using Kruskal's MST algorithm for warp lane generation

Almost every sci-fi / space themed game has warp lanes connecting the star systems in the game. I've come across this quite often so here is a small piece of code that implements a Minimum spanning tree between the stars to guarantee all of them are reachable.

public class WarpLaneBuilder
    {
        List<HashSet<StarSystem>> sets = new List<HashSet<StarSystem>>();
        public void GenerateWarpLanes(List<StarSystem> stars)
        {
            foreach (var star in stars)
            {
                var set = new HashSet<StarSystem>();
                set.Add(star);
                sets.Add(set);
            }
            var edges = BuildEdges(stars);
            var results = new HashSet<Edge>();
            foreach (var edge in edges)
            {
                var set1 = Find(edge.Source);
                var set2 = Find(edge.Target);
                if (!set1.Equals(set2))
                {
                    results.Add(edge);
                    Union(set1, set2);
                }
            }
            foreach (var result in results)
            {
                result.Source.WarpLanes.Add(result.Target);
                result.Target.WarpLanes.Add(result.Source);
            }
        }
        private List<Edge> BuildEdges(List<StarSystem> stars)
        {
            List<Edge> edges = new List<Edge>();
            for (int i = 0; i < stars.Count - 1; i++)
            {
                for (int j = i + 1; j < stars.Count; j++)
                {
                    edges.Add(new Edge(stars[i], stars[j], stars[i].DistanceTo(stars[j])));
                }
            }
            edges.Sort((x,y) => x.Weight.CompareTo(y.Weight));
            return edges;
        }
        private HashSet<StarSystem> Find(StarSystem star)
        {
            return sets.First(x => x.Contains(star));
        }
        private void Union(HashSet<StarSystem> set1, HashSet<StarSystem> set2 )
        {
            sets.Remove(set1);
            sets.Remove(set2);
            set1.UnionWith(set2);
            sets.Add(set1);
        }
        private class Edge
        {
            public StarSystem Source;
            public StarSystem Target;
            public double Weight;
            public Edge(StarSystem source, StarSystem target, double weight)
            {
                Source = source;
                Target = target;
                Weight = weight;
            }
        }
    }

Metadata

238 words

Using Kruskal's MST algorithm for warp lane generation

Metadata

Similar posts