Curve Generation in “Warring States”

Motivation

In “Warring States,” my latest multiplayer strategy game, players can move units along a map. Each map consists of a grid of “nodes,” indicated as black spots, and are connected by “roads,” indicated as lines. Each turn, units can move along a road to relocate to another node. Here’s what a 4-player map looks like:

As you can see, most roads are straight, but some roads are curved. The straightforward solution for generating the curved roads would be to have a sprite with a texture of a 90-degree curved line. However, the curvature of the line may change based on the number of players. For example, in a 6 player game, the map would look like this:

We could have a texture for a 90-degree curve, a 120-degree curve, etc, but that would be tedious to create and update. A better solution would involve procedurally generating a curved edge based on the position of the nodes.

More formally, given two nodes, “node 1” and “node 2,” and the two nodes behind them, “from 1” and “from 2,” we need to be able to generate a smooth curve that seamlessly connects the line segments created by FROM1-NODE1 and FROM2-NODE2.

Our solution has the following steps:

1. Locate the circle center. Since the curve is circular, locating the center of the circle will make the curve easier to draw.
2. Generate a list of Vector3 positions along the curve, which can then be passed to other methods for generation, either as a line renderer or a procedural mesh.

Locating the Circle Center

To locate the circle center, we first need to make the following observations:

1. If we calculate the vector “V1" pointing from “FROM 1” to “NODE 1”, we see that it is orthogonal to the radius vector pointing towards the circle center.
2. We can calculate “Interior Angle,” the bisection of the circle sector, using “Exterior Angle” which is the angle formed by “V1” and “V2.” V2 is the vector pointing from “FROM 2” to “NODE 2.”
3. If “D” is the length of the bisection of the line segment from “NODE 1” to “NODE 2” and “R” is the length of the radius, then sine of “Interior Angle” equals D / R.

Using these 3 observations, we can calculate the radius vector pointing from NODE 1 to the circle center, as well as the length of the radius. We can then use these two values to locate the circle center.

Code

First, we’ll calculate and store the node 1 and node 2 positions, as well as v1 and v2.

Next, we’ll calculate the exterior angle using v1 and v2, and calculate the interior angle from the exterior angle. We can also calculate d by halving the distance between pos1 and pos2. Using interior angle and d, we can then calculate the length of the radius.

Now we can cross Vector3.down and v1 to get the radius vector pointing towards the circle center. Using the radius vector, the radius length, and pos1, we can calculate the circle center.

Calculating the Curve Positions

To calculate the curve positions, we can use arctangent to calculate the angles from the circle center to node 1, and from the circle center to node 2. Then, we can lerp from the first angle to the second angle with a number of steps determined by the “CurveSteps” constant. We can then use the intermediate angle and the radius length to calculate the intermediate curve position.

Constructing the Curve

With the positions calculated, the Edge class passes the list of Vector3 positions into the virtual method CreateCurve. Child classes such as LineEdge and MeshEdge can override the CreateCurve method to construct the curve accordingly.