How to Generate Semi-Organic Shapes for a 2D Map Generator in Dominions Game?

[twoski]

Hello,

I am working on a map generator for a game called Dominions. I plan to make it open source once it's functional. Maps in this game typically wrap vertically and horizontally, so the generator must create maps that seamlessly wrap on the X and Y axis.

Typically (for even player counts), the provinces are randomly arranged in 4x4 chunks. Player starts are assigned to the bottom left province in this chunk.

Representing this grid conceptually is trivial. We construct a grid of nodes (for the provinces) and generate the province connections afterwards and assign data (ie. what sort of terrain the province has).

Here is a screenshot what i have created so far.

This is what i assumed to be half of the work. The other half is generating the actual visual map. The first step here is generating polygons for each province. A polygon belonging to a node needs to connect to all other neighboring polygons such that it satisfies the node's connections.

This is where i am stuck. I have it generating basic polygons but this is not quite where it needs to be.

So my question is this... If you have nothing but a node's position and you know which nodes it connects to, how can you make a nice semi-organic shape that satisfies these constraints?

If anyone knows a cool algorithm or has experience working on something like this before i'd like to hear your thoughts.

 

[jedishrfu]

The diagram is pretty cool. What programming language and graphics are you using?

Are you using OpenGL or SVG?

It looks like the figures center around the larger circles and the polygon edges are connected to the smaller circles. What are the rules that define if a smaller circle is part of the polygon node.

I would construct an array of big nodes with a smaller array of Boolean array of 8 elements to say if the small circles are a part of the polygon shapes. You would have to do an analysis to set the small circle Boolean and then later when you draw the shape draw it relative to the big circle nodes.

Does that make sense?

 

[twoski]

I'm using Unity with C# since it has built in UI stuff, and making interactive things with unity is much easier.

The large circles denote provinces (ie. the center of a province) and the small circles (with their colored line) denote a connection between 2 province nodes.

My first attempt at the algorithm to draw polygons was to just loop through a node's connections and each midpoint of every connection becomes a vertex for the polygon. This obviously doesn't work well with diagonal connections, as you can see all the gaps.

 

[Ibix]

I'd suggest Voronoi tesselation using both your province and connector dots. This gives you a plane-filling set of polygons, one per dot. Then divide your connector polygons in two and assign half to one connected province and half to the other (Edit: or possibly better, replace your one connector dot with two dots at 0.45 and 0.55 of the way along the connection, and merge the two connector polygons to the connected province polygon it is nearer to), or just randomly assign the whole thing to one province or other. I think this gives polygons with the same connectivity as your grid.

You will need to expand your N × N grid to an (N+2) × (N+2) grid and add a perimeter that duplicates opposite edges so that the polygons wrap. You can drop the duplicated points again when polygon generation is done.

That'll probably look a bit rigid, but if you perturb the points a small random amount it'll look a lot less patterned.

 

[Tom.G]

For this to work, your grid of nodes for the Provinces must be everywhere convex. This is to handle open connections in the middle of a side when the adjacent corners are valid connections. Make the tiles octagons such that each possible connection is on a vertex.

Start with the 8 bit boolean connectivity map that @jedishrfu suggested.
We will draw (find co-ordinates of) triangles from the Province to each of the connection points.

• Save co-ordinate of Province
• Search bit map for First Connection, save co-ordinate (or relative co-ordinate)
• WHILE (more vertices)
  • Search bit map for Next Connection, save co-ordinate
  • This gives three triangle vertices, fill the triangle
  • Copy co-ordinate in Next Connection to First Connection
• ENDWHILE (for 8 possible vertices)
  (remember you have to visit the first Connected vertex twice, once to start, second time to complete the triangle from the last vertex)
• END

UNDEFINED IF:
There is only one connection.
There are only two connections that are diametrically opposite each other.

Cheers,
Tom

p.s. It's late here, so please verify well before committing!

 

[twoski]

I'm afraid i don't see how this logic would remove the gaps.

Assuming that you're using the connection center when constructing triangles...

In situations where a province has no diagonal you can see the issue.

 

[Tom.G]

Perhaps I mis-understood the requirement. I attempted to color fill to the border of a Province only where there is a connection to a neighbor.

Could you indicate on your most recent drawing the undesirable gaps?
Is it correct that the Red squares are the same as the larger circles in the first post?

 

[twoski]

The red squares are the big circles, the yellow squares represent the 8 potential connections that the big circle can have.

In that example image, the leftmost province has 8 connections. The top left and bottom right province have a diagonal connection which means the top right cannot have any diagonal connection in that spot. The issue is with the top right province. When we iterate through its connections, we jump from the left connection to the bottom connection which results in a triangular gap inside of that triangle of connections.

 

[Tom.G]

If I followed correctly, you want the color fill (Green in your example) regardless of the connections; i.e. that Yellow triangle in the middle of the drawing should be Green. In that case, Green-fill the (Yellow) square first and overwrite with the Red and the connections.

The lower Province shows that. The Green square is two by two units centered on the Province. (Or could be considered an 8-connect of half-unit squares to the Province center; or a 4-connect of unit squares on diagonals of the Province)

Or is one or both of us still confused?

 

[Ibix]

Another approach.

If you look at the square formed by four provinces, there are only two types - those with a NW-SE diagonal and those with a SW-NE diagonal. So you could define a small library of ways to divide up the square into four with the appropriate connectivity. That defines one quarter of the polygon for each province, and if your boundaries always go through the midpoint of the edge of the square then you can stitch the quarter polygons together essily enough.

There are 2⁴ ways a province could be connected. If you define half a dozen manual solutions you have 6⁴ distinct polygons for a given connectivity, giving 20,736 possible province shapes.

 

[twoski]

Okay, so it turns out the simplest approach was this:

The center of each triangle formed by node connections becomes an anchor point for the polygons being drawn around the nodes.

It works well except now i need an algorithm to sort these points in order to create a polygon which may or may not be convex.

You can see here that the polygon vertices are correct but their order is incorrect, which means the polygon renders incorrectly.

 

[Ibix]

Work out the vector from the province centre to each vertex. Work out the angle each vector makes to the horizontal. Sort by that angle.

 

[twoski]

Ah yes, that worked nicely. A few corner cases to work on and it'll be functional.

Next thing to work on: Currently the polygons are very basic. I want to introduce some variance to their edges, with the goal being to create some more organic-looking shapes.

Take, for example, this:

Basically, given 2 vectors, i need to generate a list of vectors in between them that form a nice smooth line when connected. My first thought was to just introduce random jitter, but that would make the edges too jagged.

 

[twoski]

Made some progress. Using bezier splines for province edges has given them a much more natural look. I need to add more bezier knots on the edges that are larger i think. Promising results so far though.