# Using Kruskal’s MST algorithm for warp lane generation

May 9, 2018

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>();
}

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))
{
Union(set1, set2);
}
}

foreach (var result in results)
{
}

}

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.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);
}

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;
}
}
}
``````