The question is basically: Does anyone have any ideas on how to generate line/vector based borders for towns in a strategy game?
I’ve tried a delaunay based system but it didn’t work out since the output was disfigured when there was no bordering town and it couldn’t handle having towns inside another’s field of influence, and currently a SDF based system that I’d optimally want to combine with the vector borders for a visual style similar to paradox games.
I’ve been trying to search for ways to do this but there only seems to be solutions for static province maps like in paradox games
Image of the current SDF borders(the red dot is a extension point of the circled town):
The current system uses a higher resolution texture(12288x12288) for the colors and edge detection, and a lower resolution one(4096x4096) for the distance field. The problem is that i need the borders to be editable(drag and drop vertices basically) by the player which i can’t do with just a texture.
I dont really know how I can explain dragging and dropping better
The player would optimally be able to just click on a vertex of the border and move it, in for example a peace deal or smth, but with a distance field texture theres no way to manipulate it like that
Oh it’s literally dragging and dropping? What happens if the player drags a vertex very far or into the center of the blob?
You need to describe how the whole thing is supposed to look from player’s point of view, in detail. And by “extents” I meant things like the order of magnitude of blobs/curves count, how large can the map get, is it planar or heightfield etc…
The best would be to make an animated visual mockup of the wanted behavior or link a video of an existing game that does what you want.
I mean obviously there would be a minimum distance for the border to be from a town otherwise it would be kinda broken.
And i don’t know how knowing how the map is handles is relevant but its a chunked heightfield baked at game start and it doesn’t change during the game. Only the southern portion of the map will have towns at game start but i expect during gameplay there’s going to be more since there’s so much space. Here’s a picture of a stylized map:
And there really is no existing game(to my knowledge) that does this, the closest are paradox games where the borders for countries/states/provinces are baked at game start like this:
That may be obvious to you but you need to write that down when asking for help. Is it obvious that there will be a maximal distance? If yes what it is and from which point is it measured?
It’s not your call to decide what’s relevant. Otherwise you would have the solution and would not ask for help. Provide as much info as possible. How many towns can be visible at once? how large can a territory grow? What happens when several territories overlap? How do you define territories, is there some sort of underlying hex/quad grid? Etc…
The problem you presented is not well defined or described. Please do a bit better if you hope to get workable solutions.
Yes the maximum distance of the borders from a town is defined by the “level“(just a int) of a town that is multiplied by a constant. The distance is measured from the town’s Vector2 position on map.
The amount of towns visible would be in the 50-80 ballpark at game start, but as the game progresses there would be more.
When the areas of towns overlap they should stop in the middle like actual Borders instead of intersecting, which is the actual problem, since i know how to generate circles. The closest to generating proper geometry for the borders I’ve been was Delaunay triangulation but the sides not bordering another town are not handled properly by Delaunay.
As mentioned I need the borders as basically a 2d mesh consisting of lines and vertices defining the outer border of a town as there is no grid other than the purely visual sdf texture shown in the screenshot.
Square march the distance field to get the contour lines, join segments into continuous lines, optionally smooth the corners, extend along normal, render into subviewport and composite over the main map.
Here’s a more detailed breakdown. Presuming there’s no “dragging” of borders but instead each city’s territory is represented by a list of circular blobs, each defined by its center/radius.
If you only want to draw the shapes/silhouettes, you can do it in shader. For neat textured contour lines you’ll have to do square marching (on the cpu side) as I described in my previous post. So:
To produce a distance field for a city:
calculate the joined distance field of city’s blobs (by min-ing individual circular dfs) (D1)
do the same for all the nearby blobs of other cities (D2)
mix the two distance fields as follows:
if D1 is less than D2: use D1
otherwise: use D1 - D2
zero-step the result, gaussian sample it for smoothing if needed, and render.
This is more or less some df/voronoi mashup @kit1 was mentioning.
To get actual outline geometry for drawing textured borderlines, you’ll need to run a marching squares (or triangles) algorithm on this thresholded distance filed, to produce one or more line loops/strips. Once you have that, you can make neat fat textured outlines in the way I described in my previous post. It’s several steps of relatively easy computational geometry.
As a proof of concept, here’s the first part (making the distance field) implemented in shader. I used shabby box sampling so the contour is not as smooth as it would be with gaussian sampling. The black is the city we’re calculating the borders for, orange blobs are all other cities:
Alright I’ve been bashing my head against this problem since sunday and there’s been improvement but I haven’t found a good way to render/build a mesh after I’ve found the borders.
Path3D and CSGPolygon:
Finding the borders clearly works and my sorting algorithm looks to be working, but Path3D and CSGPolygon can’t handle non continuous paths so i need to find another way to render them
EDIT: Thought I’d add how i got the edge detection to work :D. Basically i just do marching squares on the control texture and build the borders as separate instances so I have more control over the visuals for the individual borders:
Marching squares should result in a bunch of liner segments. Join them into continuous poly-line strips or loops. Once you have that connectivity structure you can construct triangle strip meshes for nice rendering. To get vertices, offset the poly-line to the left and right along its normal, and to get the texture coordinate measure the length of the poly-line at each point.
How would I go about sorting the vertices the marching squares returns? I’m using a marching squares algorithm I based off of this one:
The border instances are non continuous(which makes this a bit harder in my opinion) since I generate them for the indices of the towns basically like this:
generate_border_func(a, null) # To generate borders where there is no neighbouring town
for a:Town in towns_array:
for b:Town in other_towns_in_the_area_array:
generate_border_func(a, b) # To generate borders with neighbouring towns
