Sector Map Generation

The tactical battles in Arduxim Squadron Command will be linked by a strategy layer where you move your fleet between systems. At the moment I'm planning for a campaign to take place in one sector of space where all the star systems are connected through hyper gates (these gates were seen in several missions in Starfighter Arduxim).

One play-through will either consist of a single large sector, or several smaller sectors where the player can choose the next sector to tackle. This second design makes the game more rogue-like (possibly more correctly rogue-lite) and I'm not sure if I want it to be like that, but it's something that can be narrowed down as development progresses.

Either way, the game needs to generate random sector maps for each campaign. I put a basic generator together in a couple of hours which gives pretty good results:

The way it works is as follows. I use the terms node and edge as this algorithm is really generating a graph (and so it may be used for other structures than the sector map).

Start with a cuboid with integer dimensions (say 4x3x10). Choose some random nodes from the possible points within the cuboid. By limiting the points to integer coordinates it avoids a common problem with random generation where several nodes bunch up or overlap.

To avoid the integer grid being too obvious, move each node by a small random direction and magnitude (controlled by Position Variation in the editor). If this is less than 0.5 then the nodes can't overlap.

Create edges in the graph to join each node to its nearest neighbour. This ensures it's possible to get to every node in the map and makes 'sensible' connections in terms of being a sector map, as systems would likely have links to nearby systems instead of distant ones.

To make the graph/map more interesting add some additional edges. This makes some systems more valuable than others in terms of accessing more of the map.

This gives surprisingly good results for how simple it is. There are a couple of bugs - I haven't seen it yet but there is no checking of whether an edge between two nodes passes through a third node, which wouldn't make sense in the context of the game.

If you've any comments please leave them below.