This is a devlog for a space grand strategy game I'm interested in making.
I will post periodically between other projects.
I thought i'd have ago at making the game i'd like to play myself.
This all started early last year, back when i posted this thread.
construct.net/en/forum/construct-3/general-discussion-7/canvas-rendering-issuequick-186038
At the time i had been working on recreating the Stellaris star map, which i did using a combination of events, js, meshes and the drawing canvas.
The main issues were that it was cumbersome, and the drawing canvas had a hardcoded triangle limit. It's also basically just a big texture so it uses an insane amount of memory. Another niggle was that it doesn't support mitred lines (for borders), just individual segments that don't connect, which looks bad up-close, so i had to use meshes.
This led me down the plugin making rabbit hole, and after a spending some time learning on other plugins, i finally had the knowledge to try this again.
The idea is to put it all into one plugin, have the plugin do all the calculations, and render the map using polygons.
Since there is little info on how exactly Paradox make their star map, i had to figure it out as i went.
I don't know if anyone will find this interesting but this is what i did.
1. Star Generation: Poisson Disc Sampling
The first step is populating the galaxy. Instead of placing stars randomly (which creates unsightly clumps and large empty voids), the code uses Poisson Disc Sampling (specifically an implementation of Bridson’s algorithm).
The algorithm picks a random starting point within the galaxy For every point, it attempts to spawn new neighbours in a ring around it.
It checks a background grid to ensure no new point is too close to an existing one.
The result is an organic but evenly distributed set of stars, ensuring that empires have fair starting densities.
2. Territory Definition: Delaunay Triangulation
Once stars are placed and assigned to teams, the plugin calculates territory borders. It relies on the relationship between Delaunay Triangulation and Voronoi like regions.
Delaunay Triangulation connects neighbouring points into triangles in a very specific pattern, so they cartwheel around the point, otherwise meshes would appear distorted.
Normally you'd produce Voronoi cells, but i find these cells are blobby enough for me. Heres an early attempt.
So instead we use a centroid approach. For every triangle in the mesh, the geometric center (centroid) is calculated.
For each specific star, the code looks at all the triangles touching it. It connects the centroids of those triangles in a sequence called an Alpha Shape, which is the outer bounds of a cluster of points.
This produces a polygon surrounding the star. Mathematically, this approximates a Voronoi cell, representing the region of space closest to that star.
3. Geometry Processing: The "Blob" Pipeline
At this stage, we have jagged, mathematical polygons for every single star. To create the organic, smooth "Stellaris-style" empire borders, the code runs a series of geometry modifiers.
A. Merging (Union)
If a team owns multiple stars next to each other, their individual polygons share edges. The code detects these shared edges and removes them, merging the individual cells into one large continuous shape (or "cluster").
B. Padding (Offsetting)
To create the "No Man's Land" or gap between empires, the code shrinks the polygon.
It calculates the normal vector for every edge and moves the vertices inward by a specific distance. This is optional.
C. Smoothing (Chaikin's Algorithm)
The raw polygons are very angular. The code applies Chaikin Smoothing, a corner-cutting algorithm.
It replaces every corner vertex with two new vertices along the adjacent edges (interpolating at 25% and 75%).
After 2 or 3 iterations, or whatever i set in the plugins properties, sharp corners turn into smooth, organic curves.
D. The "Cookie Cutter" (Sutherland-Hodgman Clipping)
To ensure empires don't expand infinitely or look square at the edges of the map, the code generates a large 72-segment ellipse representing the galaxy boundary.
The Sutherland-Hodgman algorithm is used to "clip" the empire polygons against this ellipse. Any part of an empire extending outside the galaxy bounds is sliced off cleanly.
4. Hierarchy and Holes
A complex part of the code handles "Enclaves" (an empire entirely surrounded by another).
All polygons are sorted by area size. The code checks if a smaller polygon is strictly inside a larger one using a "Point in Polygon" (Ray casting) test.
It builds a hierarchy where larger shapes are "Parents" and smaller shapes inside them are designated as "Holes." This ensures that when the renderer draws the big empire, it knows to cut out the empty space for the smaller empire inside.
A technique called "ear clipping" is used to fill the area with connecting triangles and render a complete filled shape.
5. The Border (Mitered Lines)
Drawing a thick border around a complex shape often results in ugly overlaps at sharp corners. Seen here as the dark spots.
The code implements a custom Mitered Stroke algorithm.
It calculates the angle of every corner and mathematically projects where the inner and outer edge of the thick line should be.
If a corner is so sharp that the miter projection overlaps itself (creating what called a "bowtie" artifact), the code detects this crossover and snaps the inner points to a midpoint, flattening the artifact and creating a bevel.
Here is what the event sheet looks like. Much simpler than my original event sheet!.
+ System: On start of layout
-> StellarisMap: Generate 150 random stars
-> StellarisMap: Set params: Chisel 35, Clean 0.5, Padding -1, Smooth 5x (0.20), Border 10
----+ (no conditions)
-----> StellarisMap: Set Team "A" color to (255, 0, 0, Opacity 100%)
-----> StellarisMap: Set Team "A" border to (0, 0, 0, Opacity 50%)
-----> StellarisMap: Set Team "B" color to (0, 255, 0, Opacity 100%)
-----> StellarisMap: Set Team "B" border to (0, 0, 0, Opacity 50%)
-----> StellarisMap: Set Team "C" color to (0, 0, 255, Opacity 100%)
-----> StellarisMap: Set Team "C" border to (0, 0, 0, Opacity 50%)
-----> StellarisMap: Set Team "D" color to (255, 100, 255, Opacity 100%)
-----> StellarisMap: Set Team "D" border to (0, 0, 0, Opacity 50%)
-----> StellarisMap: Set Team "E" color to (155, 120, 25, Opacity 100%)
-----> StellarisMap: Set Team "E" border to (0, 0, 0, Opacity 50%)
-----> StellarisMap: Set Team "G" color to (20, 10, 10, Opacity 100%)
-----> StellarisMap: Set Team "G" border to (0, 0, 0, Opacity 50%)
----+ System: Repeat StellarisMap.StarCount times
-----> StellarisMap: Set Star UID StellarisMap.GetStarUID(LoopIndex) to Team choose("A","B","C","D")
----+ (no conditions)
-----> StellarisMap: Run full territory analysis
The next step is to add textures to the polygons.