Fun with stale quadfields

By Sai Nane2020-08-30

Two players had a very interesting interaction in this match in Zero-K, a free open-source RTS.

In Zero-K, there is a unit called the Widow. The Widow is an invisible spider which requires a large amount of energy to keep invisible, and fires a single shot that paralyzes a unit for a very long time, on a long cooldown.

In this match, one player built a Widow very early on, and tried to use it to paralyze an enemy Reaver which was out in the open. However, the shot had no effect. This isn’t supposed to happen! Given the high (for early-game) investment had no payoff, the game was over in five minutes.

What happened here? The lead developer, GoogleFrog, commented that it looked like an issue they’d encountered and reported a year prior, and nobody knew what had happened then, either.

Hypothesis: Memory corruption

Simply tracing the process running the replay, a breakpoint for LightningCannon::FireImpl is never triggered!

Running a new build with sanitizers, we instead get a SIGBUS with operator delete() on the top of the stack, trying to delete an object of size 24 when the real object has size 16: deleting a RawPacket when the object was created as a PackPacket. Making the destructor virtual, as it should be, gets past this issue. Sanitizer warnings are then reduced to be mostly about serialization or streflop code.

That isn’t great, but it’s probably not going to be observably harmful, and streflop is well tested.

Hypothesis: Raytracing algorithm

The lightning cannon is functionally a hitscan weapon. Travel time is instant at the frame when it’s fired, and if there’s anything in the way, it hits that.

However, performing the raytrace at length 120 (the normal weapon range, and what happens in the replay), doesn’t hit anything. Nor does a manual raytrace with a length of 120.01, 120.1, 121, or 130. But a raytrace with a maximum length of 220 does find a hit on the Reaver! It even reports that the distance was 110.451.

This is now a nicely localized and reproducible bug! But the raytracing algorithm looks correct. Indeed, if it searches far enough, it gets correct results. What if there’s something wrong with the data structure used to find units by position?

Hypothesis: Quadfield

The Spring RTS engine uses a quadfield to look up units by area. This is a fixed grid of cells, each of which contains all of the units which overlap that cell. I’ve seen this structure referred to as a blocklist, elsewhere. There’s a lot of competing code around: there is a quadtree implementation, even code which relies upon it with a completely distinct pathfinding implementation (!), but it doesn’t seem to be used.

Immediately before the Widow fires, this is what it looks like:

Screenshot of Zero-K paused immediately before the Widow fires. The in-game drawing system is used to mark the grid boundaries and cells in the area.

TraceRay searches quads 832 and 872 for units when fired with a range of 120. When fired with a range large enough to search four quads, it searches 832, 871, 872, and 911 for units, where quad 871 contains the Reaver (unit ID 21246).

At frame 9026, the Reaver is at (4097.61621, 262.219788, 2742.02466), in quad 872: x=4096 is the boundary between quad 871 and 872. But the quadfield says the Reaver is contained exclusively in quad 871.
At frame 9027, the Reaver is at (4099.31836, 261.691193, 2741.8623), in quad 872. The quadfield still has it stored in quad 871. The Widow fires, RayTrace is performed without examining the contents of quad 871, and does not find any collision.

This is the issue! The quadfield is updated at 2Hz. This is slow enough for projectiles and rays to sometimes clip through their targets, due to the outdated quadfield information. There is a fudge factor for extending units close to the boundary to adjacent quads, but it doesn’t seem to be large enough.

Aside: Reaver unit radius

The Reaver has a unit radius of 7 elmos in practice, here. But the Reaver’s radius should be 24.

Tracking this down, Zero-K uses the lua callout SetUnitRadiusAndHeight somewhere to change the Radius from 24 to 7, though keeping the height at 38.

This is very weird, as even the Glaive, a tiny raider, has a radius of 16.

Inspecting the UnitDefs, Anarchid found we also have non-uniform scales on x/z, and indicated that these should be equal:

  collisionVolumeScales  = [[26 36 26]],
  collisionVolumeType    = [[cylY]],

< Anarchid> so perhaps here's another theory: the colvol is not inscribed in the model radius, so weirdness occurs. At some points in time this gave Locusts directional invulnerability
< esainane> lightning cannon checks to the model edge before firing, while the actual hit check uses TraceRay

Having the radius used for quadfield membership be much, much smaller than the actual collision volume compounds the problem. But the root cause is that the quadfield has incorrect information.

Discussion and workarounds

Top down screenshot of Zero-K paused at frame 8959, a few seconds before it gets to the boundary between 871 and 872 when the Widow fires. The grid clearly shows the Reaver well within quad 871. The quadfield exclusively has it in quad 870. On the next frame, frame 8960, the quadfield updates, and considers the Reaver to only be in quad 871.

(20:38:11) < esainane> the next frame, the engine updates and considers the reaver to overlap with quad 871 and only quad 871
(20:38:56) < Anarchid> oh i know! it's unit speed contingent in a bad way and should be unit speed contingent in a good way
(20:39:02) < GoogleFrog> that seems wrong on a level that is hard to hack around with fudge factors
(20:39:05) < Anarchid> "how many of its own radii can this unit travel per slowupdate"
(20:39:15) < GoogleFrog> what if it teleports?
(20:39:23) < esainane> you could construe an example where a widow (or whatever) would fire at frame 8959 where the length of the beam never intersects with quad 870, so units in quad 870 are never checked for intersection
(20:40:23) < esainane> if lua calls eg SetUnitMidAndAimPos then QuadField::MovedUnit is invoked outside of the usual movetype slow update cycle
(20:40:33) < Anarchid> baking it the bad way: imagine reaver standing flush to quad edge right until slow update, then it starts moving at full speed to the next quad. how large a radius does it require to not be able to escape the first quad before slowupdate hits?

Initial incredulity and jest in #zkdev

(20:48:49) < esainane> it's fairly hard to do a but-for test on model radius
(20:49:26) < esainane> setting model radius to 26 for that particular reaver does leave it stunned, but it also desyncs harder and gets stunned further away from the quad boundary
(20:58:55) < esainane> It *is* easy to do a but-for test on MovedUnit frequency however, and keeping the quadfield up to date causes a proper stun
(20:59:13) < esainane> It happens a few frames earlier too, so I suppose it makes everything snappier
(20:59:29) < GoogleFrog> what with aiming?
(20:59:52) < esainane> vanilla aiming, vanilla raytracing, no range boosts
(21:00:25) < esainane> It knows that the reaver is in the quad where the stun is, so it checks the reaver to see if it hit the reaver
(21:05:57) < esainane> The interesting part is that the engine already has a fudge factor for inclusion into neighbouring quads
(21:06:01) < esainane> I wonder if it's too small

Checking if a larger model radius can work around the issue

(21:48:43) < esainane> How would people feel about having the widow have the target call SetUnitPosition on its existing location as the widow fires? It's kinda horrid, but it would ensure that the target has correct quads for the imminent hit test, and is a lot cheaper than the alternatives I can think of
(21:52:41) < esainane> You could do this for all lightning cannon weapons, but I'm not yet sure how much of knight being bad against air is down to inherent inaccuracy, rather than this bug just manifesting much more against very high speed targets
(22:09:59) < Anarchid> That sounds like an adequate intermediate fix at the very least
(22:51:24) < esainane> they both ultimately use TraceRay::TraceRay, it's just the BeamLaser has code to handle shield refraction
(22:52:19) < GoogleFrog> doing SetPosition sounds ok as long as it doesn't screw with unit physics too much
(22:52:42) < GoogleFrog> eg if you use a widow on a cyclops, does the setposition cause a movement interrupt even if it is not stunned?
(22:53:07) < GoogleFrog> Reaver can have a larger model radius
(22:53:38) < GoogleFrog> the terraform by mouseclick option was removed because people could accidentally enter that UI, and I think that UI is terrible
(22:54:14) < GoogleFrog> having your mouse anchored to a spot on your screen because you click and hold for too long is really bad if you don't know what is coming
(22:54:35) < GoogleFrog> and as for a UI that someone may want to use, the options that don't require you to click and hold for a second seem far better for flo
(23:00:08) < esainane> The exact sequence as far as I understand it is unit loses collision properties -> unit is moved -> unit regains collision properties -> eventhandler.unitmoved is fired -> quadfield.movedunit is fired
(23:00:40) < esainane> where "unit is moved" means pos, midpos, and aimpos are updated; there doesn't appear to be anything regarding momentum
(23:01:50) < esainane> with that said, preFramePos is updated, so deltatime rendering is going to be off until the next update
(23:02:22) < esainane> it's *only* read in rts/Rendering/UnitDrawer.cpp, though
(23:02:32) < esainane> so no sim side effects
(23:07:02) < GoogleFrog> it could screw with the pathfinder or pathfollower
(23:07:09) < GoogleFrog> all that can be done is a test
(23:13:18) < esainane> that was an exhaustive list, where everything except eventhandler.unitmoved is a function on the fringe of the call graph
(23:14:09) < esainane> The only viable listeners for UnitMoved seem to be GroundDecalHandler and LegacyTrackHandler
(23:14:32) < esainane> So I suppose you get a duplicate decal as a side effect
(23:16:46) < esainane> An alternative could be to add a new synced lua callout, something along the lines of ForceQuadUpdate, which does nothing but update the quadfield for the provided entity
(23:17:17) < esainane> That approach would need to wait for an engine update, though
(23:18:35) < Sprung> what about wait-wait? it forces a unit slowupdate iirc so might work as a ghetto way to refresh before a cheaper way exists
(23:19:02) < GoogleFrog> it forces a slowupdate?
(23:19:18) < GoogleFrog> I thought it forced the in-engine version of CommandFallback
(23:19:23) < GoogleFrog> essentially resets the command AI
(23:22:13) < esainane> I don't /think/ command slowupdate is the same as the movetype slow update
(23:35:09) < GoogleFrog> wait wait seems to force an update
(23:35:10) < GoogleFrog> for commands
(23:35:37) < GoogleFrog> iirc CommandFallback happens in slowupdate. It can happen off-frame if wait wait or similar happens
(23:36:12) < Sprung> well right it can't be a true slowupdate since that probably also involves emp dissipation for instance
(23:36:30) < GoogleFrog> yes

Discussion around explicitly calling SetUnitPosition when significant hitscans happen, as a potential workaround

I made a pretty detailed report on the SpringRTS Mantis, so hopefully it’ll be fixed in the engine soon.

Update: We implemented the SetUnitPosition workaround for now, specifically for Widow. While this is a low-frequency bug, it feels really bad when it does happen.