8
\$\begingroup\$

I'm trying to generate a fairly large two-dimensional star map that shows different factions / states, each owning one or more star systems. I'd like to automatically create borders / areas for the factions.

The idea is to essentially go from something like this (the dots represent star systems on a 2d plane, colors are faction affiliations)

Star systems and their faction affiliation

to this

Star systems with faction areas

Generating maps like this seems like a fairly common requirement, so my actual question is this: Are there standard algorithms for generating state areas as shown? If so, could you point them out to me? If not, can you think of a good algorithm (basic idea or pseudo code are fine)?

The algorithm's performance is not a primary concern to me, so I'd rather have a "prettier" map than a faster-to-generate one. This similar question offers an approach that is probably applicable to my problem, albeit with some "prettification" needed: How to create a map from graph

Let me explain what I mean when I say prettier: At the bottom of the linked question, the asker presents her end result after implementing the accepted answer. My first issue here: The areas for nodes #6, #9 and #12 are very small and oddly shaped. Also, instead of the sharp edges, I would prefer a smoother, curved look.

My own ideas so far, including the respective drawbacks / questions I see with them:

  • Generate a "convex hull" polygon for each faction, then expand outwards a bit. Problems: No concave features. Also, how do you deal with overlaps?
  • Generate a voronoi graph for the dots, then use the voronoi polygon edges between neighboring systems of different factions as borders. Problem: Large polygons at the map edges - how do I identify and fix those?
  • Generate a fixed-size polygon for each dot, union all polygons for a single faction (resulting in one large, potentially complex "faction polygon"). Then do something to reconcile overlapping areas between two factions. Problems: How would I do this exactly? Not exactly a trivial process. What if there is overlap between more than two factions?

Your help is appreciated.


Addendum: After thinking about the first two answers and their respective approaches to solving the problem, I've realized that my requirements above are incomplete.

I have to add that the map can have sparsely populated areas, meaning that there may be an isolated star or cluster of stars. I'd like to display each of those clusters with their own contiguous colored area. Something like this:

Star systems with faction areas, different clusters

I realize that this might necessitate a first step which identifies clusters, and then running the actual algorithm for each of the clusters.

\$\endgroup\$
  • \$\begingroup\$ (brainstorming) You might be able to fill in the rest of the space with blue noise (e.g. poisson disc) and then run voronoi to get a color assignment. The added points would be assigned the white background region. \$\endgroup\$ – amitp Jun 21 '18 at 13:10
  • \$\begingroup\$ @amitp Hey Amit, it's an honor to have you commenting on here! I've taken a tremendous amount of inspiration and practical knowledge from reading your Red Blob Games articles. More on topic: The idea of generating additional dots makes sense, any particular reason why you're mentioning blue noise specifically? \$\endgroup\$ – Grüse Jun 21 '18 at 13:39
  • \$\begingroup\$ ... I guess because it looks like a more natural distribution than other noise flavors. \$\endgroup\$ – Grüse Jun 21 '18 at 13:46
16
\$\begingroup\$

I think the Voronoi idea is a good one. Each star becomes a seed point for Voronoi, and then the Voronoi regions show the areas owned by each faction. However, there are some changes that will make it work better:

  1. As you mentioned, there are empty areas that shouldn't be assigned to a faction. Voronoi will create large polygons that extend out to areas where the faction shouldn't reach. To fix this, use a blue noise algorithm like poisson disc to fill the unoccupied space with "owned by no one" stars. Blue noise is random but evenly distributed (it might also be useful for generating your star locations).
  2. Voronoi produces blocky regions. To produce rounder cells, replace Voronoi's circumcenter calculation with a centroid calculation. I've written a little about this here with some comparison images.
  3. Voronoi produces polygons, but you want round areas. At each corner, there are three polygons. When all three are the same faction, you can leave it alone. When two are the same faction, introduce a quadratic bezier curve that shifts the boundary towards the other faction. When all three factions are different, you can either leave the corner alone, or you can introduce three bezier curves to move all of the boundaries away from one another. I'm not sure which looks better.

Here's the output:

Blobby map

I also wrote a page which lets you paint the regions to see what they'd look like.

\$\endgroup\$
  • \$\begingroup\$ This fits my use case perfectly, thank you very much! I have to say it's equally impressive and depressing that you were able to put together an interactive example so quickly, while it will probably take me at least a few days to even reproduce what you presented here :) Looking forward to that tutorial article. \$\endgroup\$ – Grüse Jun 21 '18 at 18:18
4
\$\begingroup\$

One of many methods is an influence map. You can search for specific code implementations, but the basic algorithm is fairly simple.

For each faction object (e.g. star system), assign a positive (hot) value. For all other factions' objects assign a negative (cold) value. The magnitude of hot or cold should be based on how much influence you think the object exerts on its surroundings and neighbors. These values do not have to be proportional if you ultimately want to keep a "dmz" between factions.

Use these details to create a temporary grid (e.g. array) that approximates your map's pixels. You can build such a grid to the resolution you desire including 1:1.

Next, use the heat/field transfer equation to iterate and propagate the faction objects' strengths (heat) against the adversaries' objects' strengths (cold) for each neighbor cell in the grid.

Rinse and repeat for each Faction on your map by creating separate faction grids for each.

Finally, interpolate the faction grids together to produce a contour of influence for each faction. Then transfer that grid back onto your pixel map given the resolution that you used for the grid (adding any faction specific colors, etc).

The art in this process is to determine how much influence each object should have and what game elements you use to quantify that value.

As an aside, the products of this method can be used for all kinds of other things, like your ai decision-making.


Additional reference: discussion thread on origins of influence mapping.

\$\endgroup\$
  • \$\begingroup\$ This approach should be obvious, but it never occurred to me. Thanks for bringing it to my attention! A thought: My maps can be sparse in certain areas, while other areas are densely packed with stars of different affiliations right next to each other. Is there a way to use different grid cell sizes for the different areas? Thinking along the lines of a quadtree or similar. \$\endgroup\$ – Grüse Jun 21 '18 at 6:25
2
\$\begingroup\$

You should look into Voronoi diagrams. Here is the definition on wikipedia:

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

The basic points are usually randomly generated and are often called nodes. In your case, each node could be your stars. That way, the faction associated with the stars can be associated with the voronoi cell surrounding the star and when every cell has been calculated, you join those with the same faction together and you should have a pretty neat border around your stars.

FastNoise library has support for Voronoi Diagrams, so maybe you should look at it.

Smoothing of the regions

Keep your stars in a « safe array » and use a copy of it where you actually add more points via interpolation of the nearest neighbors and generate the diagram from those points. It should give you smoother regions.

Other ideas The fortune algorithm is based on a straight line that sweeps the cartesian plane. An interesting idea would be to use a circle to sweep the plane from the center of your galaxy/space instead, maybe that could lead to some interesting shapes too.

Geometry manipulation

Your last idea of combining smaller polygons into bigger ones and then fixing the edges will require advanced spline algorithms to modify the shapes. Not sure if that would make it efficient or good looking. I’m pretty sure that the voronoi diagram with extra tessellation is the way to go as it fixes the edge problem by itself and can even offer some extra data by itself like the distance from the borders (which could be used to determine the zones of conflict between the different factions, the probability of encountering different kinds of ships, etc.)

\$\endgroup\$
  • \$\begingroup\$ Note that OP already referred to an answer using Voronoi diagrams, so they're aware of the technique, but have asked for specific modifications to change the appearance of the borders. Can you expand on your answer to address those specific requests? \$\endgroup\$ – DMGregory Jun 20 '18 at 18:09
  • \$\begingroup\$ Sorry, misread the post \$\endgroup\$ – BadgerBadger Jun 20 '18 at 18:47
  • \$\begingroup\$ Thank you for amending your answer! The smoothing idea is interesting. I have two issues with the Voronoi approach: One: How do I detect and limit the "outer" points so that the borders don't stretch all the way to the edges of the screen (see my question's second image). Two: In sparsely populated areas, Voronoi does not give great results because the polygons become huge. Maybe there is an obvious solution to those that I fail to see? \$\endgroup\$ – Grüse Jun 21 '18 at 6:31
  • \$\begingroup\$ Would that be an option to add points on your own to frame the area? Then, when you render the graph, if a line reaches the actual edge of the picture, you simply dont draw it as it wont be part of the game area. The second problem should be fixable with the smoothing. You could add more points when they are further appart so you keep some kind of consistent « grid size ». \$\endgroup\$ – BadgerBadger Jun 22 '18 at 17:20
  • \$\begingroup\$ @BadgerBadger yep, I'm experimenting with adding points right now \$\endgroup\$ – Grüse Jun 23 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.