Search code examples
c#game-engineminimum-spanning-treeprocedural-generation

How do I construct a Minimum Spanning Tree from a list of vertexes, using QuikGraph C#?


How do I get from a list of vertexes/nodes to a graph that I can use with QuikGraph to e.g. produce a Minimum Spanning Tree?

EDIT:( I've been forward and backward over the QuikGraph wiki https://github.com/KeRNeLith/QuikGraph and every example I can find glosses over graph creation )

Background

My program procedurally generates game levels. My plan is to use an UndirectedGraph from QuikGraph to store the level information, so I can use library functions to semi-intelligently lay out level content, set up patrols, etc.

My first stage packs the level with rooms based on configurable parameters. My second stage seeks to connect the rooms with the minimum amount of nonsense hallways - ie, connecting adjacent rooms with a single direct hallway. I will break some connections and add other connections later. This seems like a simple case of building a minimum spanning tree.

I expected to find some sort of algorithm that takes a list of graph nodes (and some method of determining the weight/distance between any two graph nodes), and return a list of edges or something. I can't seem to find that - everything seems to assume you already have a list of edges, ie an existing graph.

What's the best way to set this up? "A list of all possible combination of edges between nodes" seems crazy, but I can't think of anything else.

Note

I'm not working with a game engine. The output is intended to be a static text description suitable for use by a human when setting up a pen-and-paper roleplaying game. All the graphics and input handling and physics and sound and network and etc are overkill...


Solution

  • I've received some good advice on how to prepare my graph - using a Delaunay triangulation routine will set up a graph connected by proximity, and efficiently. I found the Delaunator library on NuGet, which seems to be doing the job well.