Circle Physics

Last edited: 2024-05-09    8 minute read

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 of why this might be the case:

  • 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
  • Rotation does not change the physics behavior, and physics does not change rotation

A prelude: axis-aligned lines

Assuming 2D space for now, lets start with the absolute simplest collision detection shape: the axis-aligned line. Given a horizontal line that intercepts the Y axis at height y, we can tell which side of the line any point is on 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 line:

[TODO: plot]

we can easily calculate that is_above(a, line) == true and is_above(b, line) == false, so we know a is above and b is below. Easy peasy!

The main event: circles

To start off, let's do the same thing we did with the line and check for whether a point is inside the 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, 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
}

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 line and the circle, plus the points that we've tested them with, we can calculate the following collisions:

pointlinecircle
pointโŒโœ…โœ…
lineโœ…โœ…โŒ
circleโœ…โŒโœ…

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 lines 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 lines

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

Assuming that the line is defined by two points p1 and p2, we can tell which side 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 line. 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 line 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. It does seem, however, 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:

๐Ÿ”€ State machines - Creating a state machine scripting language to implement spells for a MOBA