Circular Raycasting | Slow Rush Studios

Improving performance of the atom simulation has been like pulling teeth: slow, painful, and not well suited to being featured in short videos paired with a couple hundred explanatory words.

So let's talk about something a tiny bit more fun: geometry! And a light serving of mathematics!

I know I've got you hooked now, so let's set the stage.

The Integer Grid

The atom simulation divides the entire game world into a discrete "integer grid" - and every atom occupies one place in that grid.

And so while most games check for collisions between lines and various shapes¹, in this game an awful lot of logic boils down to "atom raycasting", aka "draw an imaginary line and see which atoms it hits":

Can this enemy see that player? Sure, if only transparent atoms are in the way.
Where should this mine spell lodge in the ground? At the first solid atom it hits.
Can this atom move to there? Only if there are only empty atoms in the way.

And some logic ends up asking about "points in an area" - for example, do the atoms in a rectangle in front of an enemy make up a slope or a wall?

This is all fine! Checking an individual grid position for an atom is quick, and checking a line (or shape) of points is also fast.

But... sometimes we have to mix the two.

Take explosions: raycast from the center of a circle to each point in that circle to apply force to atoms, but also reduce the force for each "fixed in place" atom (e.g. stone) hit:

Explosions need to apply forces to many atoms in a big circle around some center point.

Spells that need to spawn or damage atoms around their impact point need similar logic.

So can we make it faster?

Raycasting in a Circle

Raycasting to all atoms in a circle seems so easy:

Ask your barely-competent-but-ever-present mathematical consultant² how to find integer points in a circle. ³
Raycast to each of those points, just like normal.

Unfortunately that ends up checking a lot of points many times:

Yellow lines are the raycasts; green points are solid atoms found, red points are visited (increasingly red per visit), purple points are unvisited. You can see that solid atoms are accurately detected, but most points are quite red, indicating we wastefully visit them many times.

Checking the same points over and over is slow! Ideally we'd visit each point in the circle exactly once.

Okay, no problem! We're all smart people here.

Obviously the raycasts to the points on the circumference of the circle are going to hit the points in the circle (..right?) so we can dust off our high school trigonometry and draw lines at various angles to hit all atoms on the circumference (..right?):

Now we calculate raycasts (yellow lines) based on angles, and color the resulting points on the circumference orange. This approach makes us miss points in the circle (colored purple), and sometimes that means we miss detecting solid atoms!

One step forward, and two steps back: we're doubling up on points less, but now there also are some points we're not visiting at all.

We could reduce the difference in angles between lines so we do more raycasts, but then we'll visit more points again, and the correct angle-difference would depend on the radius of the circle.

Hmm.

What if we calculate points on the circle's circumference⁴ and raycast to those directly?

Calculating integer points on a circle's circumference and raycasting to them. Now it handles circles of different widths better, but there are still points we miss.

We're missing fewer points, but we still visit points close to the circle's center multiple times.

This approach just wasn't going to work. ⁵

Circular Raycast Tree

I eventually realized that if I wanted to visit each point inside the circle exactly once, I could work backwards from the list of points to "build the ray casts":

Generate all the points in a circle centered at the origin.
Sort the points by distance from the origin.
In order of increasing distance from the origin, connect each point to the parent point that's closest to the origin.

This gives you a tree-like structure, where the center of the circle branches out to other points that are plausibly reachable.

By traversing the resulting tree from the center point outwards, we can finally satisfy our two criteria:

we can be guaranteed to hit all points exactly once, and
we can also stop going in a given direction if we hit something.

It is faster⁶ than the "cast many separate rays" approaches I explored above - at least for largish circles⁷ - though slightly less accurate:

Blue points are points that are actually reachable via the shown blue lines, but they were incorrectly discarded. As before, red points are visited (exactly once!) points, green points are detected solid atoms, and purple points are unvisited points in the circle.

A small inaccuracy like that shouldn't be noticeable during the game. (..right?)

Playable web build‎

Here's a hacked up build with the tree raycast logic hooked up to the cursor position (use mouse wheel to change its size), so you can play with it:

Press F1 for help, including to see keyboard/mouse controls. Mobile devices probably won't work!

I still need to actually integrate this new approach into explosions, mind, so you won't notice any difference there.

PS: Yes, there's a bug with atoms getting stuck floating in the air sometimes. It's a performance optimization gone awry! Just pretend like you didn't see it.

E.g. Does the line between the enemy's eyes and the player have any shapes between it? Is the sphere that represents the player's feet intersecting with any shapes that make up the level? Etc

OpenAI's GPT4o - or Anthropic's Claude when I'm in a big spender mood.

The approach: check every integer point in a square whose sides are sized to twice the circle radius r, and if the point is less than r distance away from the center, it's in the circle! I could have worked that one out myself.

⁴

Using for example Bresenham's circle algorithm.

⁵

Though perhaps if you're a real mathematician, you can devise a clever analytical way to make this work? Let me know.

⁶

As long as you build the raycast tree structure once and reuse it over and over.

⁷

For small circles, the overhead of traversing the tree data structure is more than just visiting the same points multiple times.
It is probably possible to further optimize the tree data structure as a cache-friendly array of points to visit, but that is complicated by having to support bailing out of a given ray at any point so I haven't done that yet.