The game Steel Division 2 has a very nice looking frontline system, where a smoothly curved line is drawn between friendly and enemy units, dividing the map into territorty owned by two teams.
Does anyone know what algorithm I should research for dividing an area using smooth curves based on a few (sparse) points?
Bonus points for pointing me in the right direction for creating a shader/line renderer to shade INWARDS
I'm not familiar with the game in question, but I suspect that they're a combination of Bézier curves and Voronoi cells.
A Voronoi diagram partitions an area into cells using a distance metric (typically, standard Euclidean distance) based on a series of (seed) points. Each seed point gets an associated region. And everything in a given region is closer to the that region's seed point than to any other seed point. Because of that property, Voronoi diagrams are often used to model are of influence. And we have algorithms that are efficient enough to calculate them in real time.
As for finding the front line, I would use a series of Bézier curves. Each curve goes from the middle of a given border line segment to the middle of the next border line segment. The control points depend on the type of Bézier you have. My first choice would be to use quadratic Béziers which have a single control, which I would set to be the corner between the two segments. The drawing tool I had on hand for my diagrams only makes cubic Béziers, which requires two control points. So in that case I'm using the halfway points between the corner of the two border segments and the border midpoints. I think these two methods give equivalent curves - if you want to check the underlying math I recommend Pomax's Bézier curve primer as a resource.
To illustrate, let's say I start with the following and want a frontline for the cross hatched region:
Here are the mid points along the border segments:
Next I'll add in the control points:
Finally, I'll add in the Bézier curves:
Because of how underlying Voronoi diagram dictates the locations of the control points, the individual Bézier curves should join up together into a smooth continuous curve. That said, very short edges in the Voronoi diagram will result in some very sharp turns on the front line. That actually seems consistent with this example animation I found for the game, but it's something to look out for. Applying LLoyd's algorithm to the Voronoi before calculating the front line will reduce the likelihood of short edges, but also skews the area of influence. You may need to experiment to find a suitable balance.
As for the shading, two options come to mind:
