Node based 'Space Map' like Stellaris, Master of Orion, etc.

Question

Sorry I know this question is broad - like asking 'how do I paint the Mona Lisa' - but does anyone have any tips, oversight, or experience with programming something like you would see in the games Stellaris or Master of Orion where each star sector is a node and the nodes then connect to other nodes?

My original design was a grid.... which was was easier as each sector.... 1-1 , 1-2 , etc had rows and columns - so the locations to each other way easy to figure out.

I was to implement star sectors where the sectors are more 'node' based - and will have points in which they are connecting. The class / object side of things are easy enough - the part Im struggling with is -I dont even know how to get started in terms of visually representing these objects on screen. I should add, this is all procedurally generated.

ie: NODE1 <----line between---> NODE2 <-----line between----> NODE 3

Has anyone tackled this sort of concept in game programming? Are there any references/tutorials you can point me to?

Comments

After some digging .... seems like what I'm asking for help with is the visualization part of a weighted Graph.

If it helps anyone else looking for similar... I found this:

https://www.tutorialspoint.com/weighted-graph-representation-in-data-structure

Answer 1

For visualizing you could use DrawCircle and DrawLine. I use a dictionary<Point, GuiVertex>. The point is a struct with a x,y cooridinates and a guivertex is a class with a Point and HashSet (the edges).
Also for computing and testing if a mouse cursor is near a point I suggest you use a KdTree datastructure. With this structure you can very efficiently calculate distances.
I use C# and I use the KdTree package version 1.4.1.

For generation, I loop over the width and height of my map. Then do a check against a value between 0-100 to see if it is larger than my "sparsness" value. If so I generate a point with random coordinates and store that in a list.
To connect all points in my list I use Prims algorithm to create a undirected graph with a certain distance. Then I do another check to see if all points are connected, if not I add the point to the nearest point.

I suggest you use a point struct instead of a vector since they are easier to compare because they use integers and not floats. For a map you don't need the precision a float will give you.
Also with this setup you can use Dictionary<Point,YourFancyNodeWithEncounterInfo>.

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5
https://en.wikipedia.org/wiki/K-d_tree
https://en.wikipedia.org/wiki/Prim's_algorithm

Hope this helps. I might have missed some bits because I implemented this a few months ago, but it at least will give you the general way of implementing this.

Comments

Thank you , I'll look into all of this in detail.