Circle Physics

Real-time strategy (RTS) games like StarCraft and Pikmin are characterized by their ability to simulate large numbers of units. One of the interesting things that I noticed about Pikmin is that it seems that the Pikmin almost always organize into circles when carrying objects, and almost all the enemies have round hitboxes and hurtboxes. Similarly, when calculating how they push each other around, all of the units in StarCraft 2 (and similar games) are also calculated as circles. All this made me wonder if there was some trait of real-time strategy games that made it advantageous to limit all moving objects to circles in their physics simulation.

While I have not spoken to any developers of these games to confirm that RTS games indeed tend to use circles, the following are my observations that potentially explain this:

• RTS games have tons of dynamic units, so even a tiny savings in processing per unit can result in a large overall performance improvement
• Circle collisions are easy to calculate. Circles a and b are colliding if: distance_between(a.position, b.position) < a.radius + b.radius
• Because the objects are circles, their rotation does not change physics behavior, and physics does not have to change rotation. Contrast that to a square, where hitting its corner at an angle will cause it to spin, and it can hit other objects while spinning and move them as a result.

A prelude: axis-aligned halfplane

Assuming 2D space for now, the absolute simplest shape we can define collision detection for is the axis-aligned halfplane. Given a horizontal line that intercepts the Y axis at height y, lets define our halfplane as being the space above that line. We can tell whether a point collides with this halfplane by simply comparing y to the point's Y value:

fn is_above(p: Point, y_intercept: f32) -> bool {
	p.y > y_intercept
}

and given the following points and halplane:

[TODO: plot]

we can easily calculate that is_above(a, y) == true and is_above(b, y) == false, so we know a collides and b does not. Easy peasy!

The main event: circles

To start off, let's do the same thing we did with the halfplane and check for whether a point collides with a circle:

fn is_inside(p: Point, c: Circle) -> bool {
	let distance = sqrt((c.position.x - p.x).powi(2) + (c.position.y - p.y).powi(2));
	distance < c.radius
}

Eek, seems like there are a few nasty operations in there. According to latkin, square roots are about 6 times more computationally intensive than additions or subtractions, and exponents are even worse. Fortunately, since ${a^2 = a * a}$, we can replace all of these operations with well-placed multiplications, at the cost of making the code a bit harder to read:

fn is_inside(p: Point, c: Circle) -> bool {
	let dx = c.position.x - p.x;
	let dy = c.position.y - p.y;
	let d_squared = dx * dx + dy * dy;
	d_squared < c.radius * c.radius
}

(Extra reading on when pow is more expensive than multiplication)

I'm not too worried about readability; people used to do much less readable things in the name of computational efficiency. Plus, the libraries I've used usually have functions for ergonomically calculating d_squared, so it ends up looking more like:

fn is_inside(p: Point, c: Circle) -> bool {
	c.position.distance_squared(p) < c.radius * c.radius
}

Probably the most common thing we would need to calculate when simulating physics for a bunch of circles is figuring out when circles are colliding with each other. For that, we can just use the check from the beginning of the article (distance_between(a.position, b.position) < a.radius + b.radius), using the tricks we know to make things more efficient and clean:

fn is_colliding(a: Circle, b: Circle) -> bool {
	let rad = a.radius + b.radius;
	a.position.distance_squared(b.position) < rad * rad
}

So given the two shapes we've talked about so far, the halfplane and the circle, plus the points that we've tested them with, we can calculate the following collisions:

Comparing whether two points are colliding is pretty trivial, since they are only touching if they're exactly the same, so to complete the matrix, we really just need to figure out how halfplanes and circles collide, which is pretty straightforward.

fn is_colliding(c: Circle, y_intercept: f32) -> bool {
	abs(c.position.y - y_intercept) < c.radius
}

More halfplanes

Let's go back to the halfplane example from earlier for a bit. Why was it necessary to limit it to perfectly horizontal and vertical halfplanes? What if we try to generalize to halfplanes of any slope rather than just the ones aligned with the X and Y axes?

Assuming that the edge of the halfplane is defined by two points p1 and p2, we can tell which side of the edge point d is on by finding the terms to the slope intercept definition y = mx + b. Hopefully you're brushed up on your grade school geometry/algebra:

fn is_above(d: Point, p1: Point, p2: Point) -> bool {
	let slope = (p2.y - p1.y) / (p2.x - p1.x); // m = Δy / Δx
	let intercept = p2.y - slope * p2.x; // b = y - mx
	(d.y - slope * d.x) > intercept
}

[TODO: plot]

Which, in this case, is [TODO: calculation], meaning d is below the edge. As you can see, this takes quite a few more operations than the axis-aligned case, and the division is particularly nasty, as it takes about [4 times as long] as adding or subtracting. If you're clever, you may also be worried about the case where the edge is vertical, when p2.x - p1.x == 0, which will result in a division by zero when calculating slope. To fix this, we can rearrange things to reduce calculations to two multiplications and four subtractions:

$${ \begin{align*} d_y - \text{slope} * d_x &> p_{2y} - \text{slope} * p_{2x} && \text{our original equation} \\ d_y - \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}d_x &> p_{2y} - \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}p_{2x} && \text{slope} = \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}\\ d_y - p_{2y} &> \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}d_x - \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}p_{2x} && \text{add terms to both sides}\\ d_y - p_{2y} &> \frac{p_{2y} - p_{1y}}{p_{2x} - p_{1x}}(d_x - p_{2x}) && \text{factor out slope}\\ (p_{2x} - p_{1x})(d_y - p_{2y}) &> (p_{2y} - p_{1y})(d_x - p_{2x}) && \text{this is actually illegal?}\\ \end{align*} }$$

So it turns out you're not supposed to do that last part because multiplying both sides of an inequality with a negative number will flip the inequality, and since we don't know whether ${p_{2x} - p_{1x}}$ is positive or negative, we can't know whether or not we have to flip the inequality. My solution to this is to simply invert the result when ${p_{2x} - p_{1x}}$ is negative, resulting in the following function:

fn is_above(d: Point, p1: Point, p2: Point) -> bool {
	let check = (p2.x - p1.x) * (d.y - p2.y) > (p2.y - p1.y) * (d.x - p2.x);
	check != (p2.x > p1.x) // != is functionally identical to a boolean XOR
}

That was a lot more work than the axis-aligned case, and even after all that, it's still quite a bit more computationally intensive.

for the future

I do all of my game development these days using Bevy, which has plenty of physics extensions, but I was under the impression that my use case was esoteric enough that it would make sense to implement my own in order to have fine control over efficiency. However, it seems that many of the existing libraries use similar ideas under the hood.

• collisions
  • all the fun collision shapes and the stackoverflow posts I got them from
• nudging
  • i want to refactor this.
• im a little concerned about the unused height axis, but itll probably be fine. but what if I want an attack used on a bridge to not affect any units under the bridge? and what if I do want it to affect them?
• turn speed limiting https://youtu.be/K1bQuMnMqKY?t=546
  • quaternions

Up next: