Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Velocity at high ranges causes the game to crash #4225

Closed
ghost opened this issue Mar 10, 2019 · 10 comments
Closed

Velocity at high ranges causes the game to crash #4225

ghost opened this issue Mar 10, 2019 · 10 comments
Labels
bug Something in the game is not behaving as intended
Milestone

Comments

@ghost
Copy link

ghost commented Mar 10, 2019

Describe the bug
When firing a weapon with a velocity above 3200 or so the game crashes.

To Reproduce
Steps to reproduce the behavior:

  1. Equip a weapon with a velocity above 3200
  2. Fire it
  3. Game crashes

Expected behavior
The weapon to fire without consequence.

System (please complete the following information):

  • OS: Windows 10 Home, version 1803 build 17134.590
  • Game Source: nightly
  • Version: nightly, commit hash 1cb4da1
@jafdy
Copy link
Contributor

jafdy commented Mar 10, 2019

Do you mean range or velocity? They aren't the same thing, plus range is a product of velocity and lifetime so is unlikely to cause a crash (although it might still be correlated).

@ghost
Copy link
Author

ghost commented Mar 10, 2019

Do you mean range or velocity? They aren't the same thing, plus range is a product of velocity and lifetime so is unlikely to cause a crash (although it might still be correlated).

I meant velocity, sorry.

@Amazinite
Copy link
Collaborator

Are you sure this is what is causing the crash? Could you paste the data of the weapon you think is causing this crash? I just set the beam laser to fire at a velocity of 3200 and I didn't get a crash.

@tehhowch tehhowch added the unconfirmed More information is needed to be sure this report is true label Mar 11, 2019
@Amazinite
Copy link
Collaborator

Amazinite commented Mar 11, 2019

Doubled the velocity to 6400 and my game crashed. If you are using a plugin weapon with a sprite that spans that 3200 range, perhaps this has something to do with drawing the projectile at such a distance, not the velocity itself. (Edit: Changed my beam laser sprite. No effect as far as I can tell by using a 3200 range laser projectile.)

By changing the velocity of the Beam Laser:

Velocity Crash
3200 No
6400 Yes
4800 Yes
4000 No
4400 Yes, BUT only when firing up or down, not left or right.
4200 Yes, as above
4100 Yes, as above
4050 No
4090 No
4095 (2^12 - 1) I did crash the game, but the circumstances don't seem as solid as 4100 and above; I was able to do a full rotation, but the game then crashed while I was pointing my ship at about 4 o' clock.
4094 No
4096 (2^12) Yes, same circumstances as 4100+

@Amazinite Amazinite added bug Something in the game is not behaving as intended and removed unconfirmed More information is needed to be sure this report is true labels Mar 11, 2019
@Amazinite
Copy link
Collaborator

Amazinite commented Mar 11, 2019

So it seems like we have some sort of edge case at 2^12 velocity. @Variance-Moment Can you replicate my results, with 3200 specifically not crashing the game, but anything seemingly higher than 2^12 giving a clear crash?
To note, my laptop screen is 1920x1080 and 15.6". Since I'm only getting crashes around that point if I'm aiming at the top or bottom of my screen, that may be important.

@jafdy
Copy link
Contributor

jafdy commented Mar 11, 2019

The physical size of the screen won't matter. You could try telling windows (or whatever OS you use) that you have a 720p screen and see if that effects it, if it is an effect then I would expect to see it crash at around 2730 (~4096*2/3). The 2^12 hypothesis seems more likely.

@ghost
Copy link
Author

ghost commented Mar 11, 2019

I seem to get similar results:

Velocity Result
4096 Immediate crash
4095 Crashes after I begin to turn my ship
4094 - 4093 Crashes after I begin to turn my ship, but seems to also be triggered if I cycle targeting (it could just be a delay?)
4092 No crash

Sprite size also doesn't seem to matter.

@tehhowch
Copy link
Collaborator

This is related to integer overflows in the CollisionSet class, specifically when computing the scale parameter

int scale = max(mx, 1) * max(my, 1);

and other parameters that involve multiplication, like diff.
For mx and my values whose product exceeds the computer's representable signed integer values for its given int, the value of scale (or whichever product is being computed) will be different than expected (depending on the magnitude of the overflow). So for example, a common int size is 32 bits, which means the product of mx and my exceeding 2^31-1 (2,147,483,647) results in anomalous behavior. There are additional multiplications that occur in the CollisionSet code with these derived values, so the anomalous behavior may be invoked at smaller velocity values than one might expect.

It's possible the allowable maximum velocity can be shifted to larger bounds by using unsigned ints or larger ints (e.g. int64_t), but these won't truly resolve the issue - just shift the "critical velocity" that causes the application to hang. Probably we need to go through this logic more carefully and address any places which may overflow, and perform the needed calculations in a manner cognizant of that limitation.

Also note that there is a difference between "the application crashed" and "the application stopped responding". The "stopped responding" is a great hint that a loop is not exiting somewhere (in this case, the while (true) { /* grid cell checking */ } loop). An application crash signifies that some erroneous / undefined behavior or some resource mismanagement is occurring.


So until this is fixed, be cognizant when designing your outfits that the higher the velocity of the weapon, the more taxing it is to the game to calculate its collisions. This means that large battles involving many of these weapons will be even more taxing on players' systems.

@tehhowch tehhowch added this to the 0.9.x milestone Mar 11, 2019
@tehhowch
Copy link
Collaborator

Looking into the CollisionSet a bit further, the deal with 4095 / 4096 is that 4096 results in a signed integer overflow if the projectile is fired at an exact diagonal angle. While unsigned integer overflow is a defined behavior (it loops around), signed overflow is undefined behavior, and observed behavior then depends on the particular compiler and system used to make the executable. The overflow happens when computing the full parameter, as the scale parameter has its maximum value for a particular projectile velocity when mx = my (=v / sqrt(2)).

int scale = max(mx, 1) * max(my, 1);
int full = CELL_SIZE * scale;

We see that 2^31-1 (max value of int) divided by CELL_SIZE (256) is 8'388'607.996, which will cast to 8'388'607. Taking the square root yields 2'896.3, which means if the projectile's velocity along both axes exceeds this, the full parameter will overflow. The corresponding velocity with at least 2'896.3 along both axes is (val * sqrt(2) = ) drumroll........... 4095.99, i.e. the "magic" 4096 noticed here. Depending on implementation, anything can happen. Probably you get a negative number for full, but certainly you get unexpected behavior. The while loop never breaks because there are additional fun things that happen, and the grid cells don't change when they should, so the exit condition (gx == endGX && gy == endGY) is never reached.

If we take the simplest fix route and ensure that scale and full are of type int64_t and not the current int, what's the maximum allowed projectile velocity? Well... it's big enough. I think 454'046 (give or take 1 and your ship's velocity) is well beyond what's reasonable to expect, and doesn't require us making additional changes to the algorithm.

But, can we raise the limit even further? Yes:

First though, we need to know the calculation step that induces the overflow, so we can work around it.

// If not, move to the next one. Check whether rx / mx < ry / my.
int64_t diff = rx * my - ry * mx;

This diff calculation is the limiting step in the CollisionSet algorithm, as in the worst case, rx or ry have the same value as full (which in the worst case is the max representable value of the integral type int64_t, 2^63-1). It's interesting to note that the maximum value of this product doesn't occur at mx=my, but rather when cos(a)*sin(a)~0.47 (about ±10° off 45°). This is due to the mixed products of x and y components and the angular relationship.
image

We can allow larger values by introducing two divisions in (nearly) every grid cell, replacing two multiplications (which are generally faster than divisions, hence their use in this computation-intensive loop). If we perform the divisions instead of the multiplication, this section could look like:

if(!mx)
{
  // Stepping only along y grid cells
  gy += stepY;
  if(gy == endGY)
    break;
}
else if(!my)
{
  // Stepping only along x grid cells
  gx += stepX;
  if(gx == endGX)
    break;
}
else
{
  // Determine whether to advance the x or y grid cell. Because of the scale used, these are always even divisions.
  int64_t xRatio = rx / mx;
  int64_t yRatio = ry / my;
  int64_t diff = xRatio - yRatio;
  /* resume current code */

This will then have shift possible overflows to computing the new values of rx and ry (substituting the _Ratio from above as appropriate):

ry -= my * (rx / mx);

rx -= mx * (ry / my);

With this approach, the overflowing angles are near 0 / 90°, with a maximal projectile velocity in the range of 189'812'818:
image

However, using insane values of projectile velocity is not "free": the number of grid cells that must be checked also increases. Given that up to 3 different CollisionSets are checked (depending on asteroids and minables in the given system), this results in framerate loss (although yes, there are still frames). Equipping just 4 outfits with a 4-frame lifetime and a velocity of 189'812'800 results in an in-game CPU time of ~5600-10000x, depending how many of the guns are firing (my system had both minables and asteroids). With a more "reasonable" (yet-still-insane) projectile velocity of 400'000, I didn't notice any stuttering when activating the same four weapons.

While we can increase the projectile velocity limit further with some extra calculations, given that 454'046 is already a 100x improvement with no algorithmic changes, making algorithmic changes to allow an already-absurd projectile velocity to be increased even further is not going to happen. Framerate in large battles with reasonable weapon velocities is already enough of a concern that we don't want to also require considering "is some mod being extra, extra ridiculous, and that's why there is this player issue?"

I'll put together the fix this week, and include a guard against CollisionSet receiving a velocity that could cause UB.

@tehhowch
Copy link
Collaborator

Fixed via 7541959 and 5f29b6e

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something in the game is not behaving as intended
Projects
None yet
Development

No branches or pull requests

3 participants