Every voyage in Privateer, my roguelike naval game, starts with a fresh map: a web of beacons you sail between, a start on the left, a boss on the far right, and a tangle of routes in between that you never saw last run. Regenerate the one above a few times and no two are alike. What you don't see is how much has to go right for it to be a map at all, and not just a pile of dots.
Because the naive version, scatter some random points and draw lines between the near ones, produces garbage. Points clump into knots and leave dead voids. Some beacons strand with no way in. Whole regions pinch off so you can never reach the boss. A map has to be even, connected, and playable, and none of those come for free. This is the pipeline that gets there: scatter, triangulate, prune, guarantee.
Scatter Without Clumps
Uniform random points are not evenly spread. Ask a random number generator for a hundred coordinates and you get clusters and bald patches, because nothing stops two points landing on top of each other. For a map you want the opposite: beacons spaced out, none too close, none too far, filling the sea evenly. That's a Poisson disc distribution, and Bridson's algorithm generates one fast.
It keeps a list of active samples. Pick one, fire up to 30 candidate points into the ring between one and two radii around it, and accept the first candidate that isn't too close to any existing sample. Accepted points become active themselves; a sample that fails all 30 tries is retired. The map config scatters across a 300 by 190 rectangle (roughly the 1.5 to 1 aspect of an FTL sector) with a radius of 45, which lands around twenty beacons a run.
var angle = (float)( 2 * Mathf.PI * _randomService.GetNextDouble( RandomFeatureType.Map ) );
var r = Mathf.Sqrt( (float)_randomService.GetNextDouble( RandomFeatureType.Map ) * 3 * _radius2 + _radius2 );
var candidate = sample + r * new Vector2( Mathf.Cos( angle ), Mathf.Sin( angle ) );
if( _rect.Contains( candidate ) && IsFarEnough( candidate ) ) {
found = true;
samples.Add( AddSample( candidate ) );
break;
}The one trick that keeps it fast is the "too close" test. Checking a candidate against every existing sample would be quadratic, so the sampler keeps a background grid with cells sized radius / sqrt(2). At that size each cell holds at most one sample, so a candidate only has to check the few cells around it, never the whole set. The Points stage in the widget shows just this scatter: even, gapless, no clumps.
Who Connects to Whom
A cloud of well spaced points still isn't a map. Something has to decide which beacons link to which, and "connect anything within distance X" gives you either a hairball or a scattering of islands depending on X. The clean answer is a Delaunay triangulation: the one way to triangulate a set of points that avoids thin sliver triangles and connects each point to its natural neighbours, the ones actually surrounding it. Flip to the Delaunay stage and you'll see the full mesh.
I run the points through DelaunatorSharp and read the triangle edges back into an adjacency list, each beacon's neighbours sorted nearest first so later steps can prefer short links.
foreach( var edge in delaunator.GetEdges() )
{
var a = edge.P.ToVector2();
var b = edge.Q.ToVector2();
if( a == b ) continue;
if( !adjacency[a].Contains( b ) ) adjacency[a].Add( b );
if( !adjacency[b].Contains( a ) ) adjacency[b].Add( a );
}That web is complete and connected, which is the good news. The bad news is it is a solid mesh with no shape, no branches, no choices. Every beacon touches all of its neighbours. As a map it reads as noise. It needs thinning.
Pruning, Then Guaranteeing
Thinning is easy: drop every edge longer than a maximum length, 95 units in the config. Long spans across the sector vanish, and what's left is a web with genuine structure, short hops, branches, the occasional dead end. It finally looks like somewhere you'd chart a course.
And it is also, at this exact moment, broken. Pruning is blind. It will happily snip the only link to a corner beacon and strand it, or sever the thread holding a whole cluster to the rest of the map, and now the boss sits behind a wall you cannot cross. A map that is sometimes unwinnable is worse than one that is always ugly. So pruning is followed by two hard guarantees.
First, every beacon keeps at least two links. If pruning left one with fewer, pull its nearest Delaunay neighbours back in, ignoring the length limit, until it has two. No dead ends that trap you with a single exit.
foreach( var candidate in adjacency[point] )
{
if( neighbours.Count >= MinDegree ) break;
AddEdge( point, candidate );
}Second, the whole map must be reachable from the start. Flood fill outward from the start beacon; if anything is left unreached, find the nearest reachable and unreachable pair and bridge them, then flood again. Repeat until every beacon is on the reachable side.
var reachable = ReachableFrom( _startPoint );
while( reachable.Count < _points.Count )
{
// find the closest reachable/unreachable pair...
AddEdge( bestIn, bestOut );
reachable = ReachableFrom( _startPoint );
}This is the heart of it. The random scatter and the triangulation are the fun part, but they are not what makes the map work. These two loops are. They turn "usually fine" into "always playable," and they are the difference between a generator you can ship and one that hands a player an impossible run at 2am and takes the blame in a review.
A map that is only usually connected is not a random map. It is a bug with a random trigger date.
Start Left, Boss Right
An FTL run enters at the left of a sector and leaves at the right, and Privateer keeps that reading. Before anything is triangulated, the generator finds the leftmost beacon near the vertical middle and pulls it out to the far left edge as the Start, and the rightmost middle beacon out to the far right as the Boss. Doing it before the triangulation means the Delaunay web and every step after already treat those two as fixed anchors, so Start is unambiguously the entrance and Boss the exit, each hanging off the edge with nothing above or below it.
What Each Beacon Is
A connected web of identical dots is a shape, not a journey. Each beacon still needs a role: a battle, an event, a store, a treasure, the boss. Those are rolled by weighted rejection sampling, a config gives each type a probability slice, and a roll picks one. The interesting part is the constraints. A beacon next to a store rerolls until it is not a store, so you never get two shops kissing, and the roll retries a bounded number of times before failing loudly rather than looping forever.
var mapType = doesPointHaveStoreNeighbours
? _mapPointRuffleService.RuffleMapPointType( MapPointType.Store )
: _mapPointRuffleService.RuffleMapPointType();
mapPoint.MapPointType = mapType;
mapPoint.Modifier = _mapPointRuffleService.RuffleModifier( mapType );Same Seed, Same Sea
The whole generator is a plain class with no MonoBehaviour and no scene access: config in, a seeded random source in, a finished graph out. Every roll goes through one IRandomService tagged as map randomness, so the same seed always charts the same sea. A map that broke in a playtest is reproducible from a single number, the pipeline is covered by unit tests that assert it stays connected and every beacon keeps its links, and degenerate input (too few points to triangulate) throws so the caller can retry instead of shipping a malformed sector.
The Takeaway
The recipe generalises well beyond a naval map. Poisson disc scatter for even placement, Delaunay for natural neighbours, prune for shape: that is a solid way to grow a graph out of empty space, whether it's a star map, a dungeon layout, or a web of territories. The scatter is where the randomness lives, but it is the least important part.
What actually ships a generator is everything you bolt on after the randomness to make the result always hold: minimum two links so nothing is a trap, a connectivity pass so the boss is always reachable, fixed anchors so the map always reads left to right, a no adjacent stores rule so it always feels authored. Generate the fun part, then spend your real effort guaranteeing the parts that are not allowed to fail.