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; } } }
238 words
Powered by TF-IDF/Cosine similarity
First published on 2018-05-09
Generated on 13 Dec 2024 at 12:12 AM
Mobile optimized version. Desktop version.