Bug fix for parabolic projectile collisions

[karadoc]

Here's a bugfix that I recently posted on the xpiratez forum.

The effect of the bug is that many arcing projectiles (eg. arrows fired from a bow) will hit their target without any of the "hit" effects actually taking place. ie. an arrow will collide with an enemy and stop moving; but the enemy will not register as having been hit. They won't take damage etc.


The problem was a mismatch between the coordinates given to TileEngine::hit, and the coordinates where the actual collision occurred.

To do collection detection on arcs, the game calculates a list of points on the arc then draws straight lines between and tests if those straight lines make contact with anything. The game was correctly detecting the collisions with those straight lines, but then instead of storing the coordinates of the collisions, it just stored the coordinates of the end point of the straight line - which may or may not have been where the collision occurred. And so sometimes the end-point of those lines was inside the target, and sometimes it wasn't. The problem could be reduced by taking more points on the arc (so the lines are shorter); and doing that might still be a good idea to make the arcs more arc-like. But ultimately, we still need to store where the collision takes place - and that's what I've done.

Here's the fix.

Code: [Select]

diff --git a/src/Battlescape/TileEngine.cpp b/src/Battlescape/TileEngine.cpp
index 35214de..8d7fb9f 100644
--- a/src/Battlescape/TileEngine.cpp
+++ b/src/Battlescape/TileEngine.cpp
@@ -2755,29 +2754,31 @@ int TileEngine::calculateParabola(const Position& origin, const Position& target
  x = (int)((double)origin.x + (double)i * cos(te) * sin(fi));
  y = (int)((double)origin.y + (double)i * sin(te) * sin(fi));
  z = (int)((double)origin.z + (double)i * cos(fi) - zK * ((double)i - ro / 2.0) * ((double)i - ro / 2.0) + zA);
- if (storeTrajectory && trajectory)
- {
- trajectory->push_back(Position(x, y, z));
- }
  https://passes through this point?
  Position nextPosition = Position(x,y,z);
- int result = calculateLine(lastPosition, nextPosition, false, 0, excludeUnit);
+ std::vector<Position> contactPoint;
+ int result = calculateLine(lastPosition, nextPosition, false, &contactPoint, excludeUnit);
  if (result != V_EMPTY)
  {
  if (lastPosition.z < nextPosition.z)
  {
result = V_OUTOFBOUNDS;
  }
- if (!storeTrajectory && trajectory != 0)
+ if (trajectory != nullptr)
  { https:// store the position of impact
- trajectory->push_back(nextPosition);
+ assert(contactPoint.size() > 0);
+ trajectory->push_back(contactPoint[0]);
  }
  return result;
  }
+ if (storeTrajectory && trajectory != nullptr)
+ {
+ trajectory->push_back(nextPosition);
+ }
  lastPosition = Position(x,y,z);
  ++i;
  }
- if (!storeTrajectory && trajectory != 0)
+ if (!storeTrajectory && trajectory != nullptr)
  { https:// store the position of impact
  trajectory->push_back(Position(x, y, z));
  }


[Meridian]

Thanks!
I've opened a ticket in the tracker too: https://openxcom.org/bugs/openxcom/issues/1244

[Meridian]

Added to my fork... feel free to test it to speed up a fix in master.

https://github.com/MeridianOXC/OpenXcom/commit/4d37bae4c334e358a35de0cfa14d03ac4c716f4e

[Meridian]

Can you please have a look at this issue: https://openxcom.org/forum/index.php/topic,4058.msg70798.html#msg70798

Without this fix it works fine.
With it, it's not possible to throw objects (via clearly unobstructed trajectory).

[karadoc]

The problem is not the fix. The problem is that the collision point is not in the same tile as the target... it might legitimately be a problem with the hill itself.

Inside TileEngineValidate throw, this condition is what is failing.

Code: [Select]

if (test != V_OUTOFBOUNDS && (trajectory.at(0) / Position(16, 16, 24)) == (targetVoxel / Position(16, 16, 24)))

The collection point (`trajectory.at(0)`) is in layer 0, whereas the target point is in layer 1. It certainly looks as though we're targeting layer 1, but the ground of the hill is apparently barely still in layer 0.

It "works" in the old version because the old version didn't use the actual collision point, and so it essentially just flukes the right final tile; due to the same bug that we were fixing in the first place. (ie. it doesn't really hit the tile we were aiming out; but the bug says that it does.)

However! The fact that it is possible for the old version to fluke a value that's higher up than the contact point suggests there is another bug somewhere. I think there is a problem in the calculateLine function. It's returning a contact point that is not between the initial and final voxels. I'm looking into it right now.

[edit]
Ok. I've found and corrected the bug in TileEngine::calculateLine.

The problem is when the line is at a 45 degree angle with an odd number of steps, the "drift" step happens before the x step. That doesn't matter much, except that the x step is what is used to check that we've reached the destination; and so if the drift is happening first, then we can overstep the target voxel in the drift direction. eg. If you start at (0, 0), and target (1, 1), the game will check voxels in the following order:

Code: [Select]

start: (0,0)
drift: (0, 1)
x step: (1, 1)
drift: (1, 2)
(x step is at the target, and so the search is over. But we've already checked (1,2), which was outside of our range.)

Here's a patch to fix the bug.

Code: [Select]

diff --git a/src/Battlescape/TileEngine.cpp b/src/Battlescape/TileEngine.cpp
index cc4fd65..5fa6cb8 100644
--- a/src/Battlescape/TileEngine.cpp
+++ b/src/Battlescape/TileEngine.cpp
@@ -2652,8 +2652,9 @@ int TileEngine::calculateLine(const Position& origin, const Position& target, bo

        https://drift controls when to step in 'shallow' planes
        https://starting value keeps Line centred
-       drift_xy  = (delta_x / 2);
-       drift_xz  = (delta_x / 2);
+       https:// (round up, to prevent overflow drift at the end)
+       drift_xy  = (delta_x+1) / 2;
+       drift_xz  = (delta_x+1) / 2;

        https://direction of line
        step_x = 1;  if (x0 > x1) {  step_x = -1; }

Here's what I put in my commit log.

Code: [Select]

commit 1b132b82be31a341bacce7dfa6b281d7a43d25a8
Author: karadoc
Date:   Sun Sep 4 10:43:47 2016 +1000

    Fixed TileEngine::calculateLine to avoid checking outside the range.

    On 45 degree angles, the starting value of drift needs to be rounded up
    to avoid drifting further than the primary axis on the final step.

---

Unfortunately, this bug fix doesn't fix the issue you asked about. In fact, it makes it so that the same issue appears without the original arc collision fix too.

I know that you've reverted my original fix in your code as a result of this issue, but please think carefully about what's going on. The patches I've posted here (both the original fix and the fix in this post) are correcting real bugs, and the patches are simple enough that you can confirm how they work even without thorough testing.

So although the issue you have asked about only manifests after my fixes are applied, the fixes are not what is causing the issue. The issue is caused by some other problem which should be dealt with separately - certainly not by reverting the arc fix.

At some point I might look again to see how the target tile is decided, and see if that can be improved to correct the issue. But in the mean time, I'd suggest that the best way to fix the issue is to fix the hill. The actual collision points on the hill are in layer zero, whereas the hill appears to be in layer 1. That's the root of the issue.

[Meridian]

The problem is that the collision point is not in the same tile as the target... it might legitimately be a problem with the hill itself.
Inside TileEngineValidate throw, this condition is what is failing.

Code: [Select]

if (test != V_OUTOFBOUNDS && (trajectory.at(0) / Position(16, 16, 24)) == (targetVoxel / Position(16, 16, 24)))

The collection point (`trajectory.at(0)`) is in layer 0, whereas the target point is in layer 1. It certainly looks as though we're targeting layer 1, but the ground of the hill is apparently barely still in layer 0.

Yes, I got that far too.
I dismissed the idea of the problem with the hill itself... since the final point was not even between origin and target point.
You went further and (most probably) found a problem in calculateLine... I'll look at that too.

I know that you've reverted my original fix in your code as a result of this issue, but please think carefully about what's going on. The patches I've posted here (both the original fix and the fix in this post) are correcting real bugs, and the patches are simple enough that you can confirm how they work even without thorough testing.

Any fix, no matter how small can have side effects.
I'm not saying this is the case; and I hope it is not... just saying there is no such thing as "simple enough that you can confirm how they work even without thorough testing (resp. understanding)".

Sure on the "validateThrow" level... it is simple... but the function goes deeper and calls other functions, spanning hundreds of lines of (non-trivial) source code.
It's very likely there's either a bug or forgotten case somewhere or that you're having different assumptions than the author of the code.

That's why I chose the safe way and reverted back before the issue gets looked at.
It's nothing against you... just result of "thinking carefully about what's going on".

So although the issue you have asked about only manifests after my fixes are applied, the fixes are not what is causing the issue. The issue is caused by some other problem which should be dealt with separately - certainly not by reverting the arc fix.

Until there is a fix, or at least an explanation, I'll keep the arc fix reverted.
But don't worry... as a heavy bow user, I am personally interested that this fix is re-introduced.
You've done good job at bringing back the idea of checking the actual terrain to me (which I have incorrectly dismissed... because of that other unrelated bug).
I'll be looking for the terrain issue and if I find it, everything will be fine.

At some point I might look again to see how the target tile is decided, and see if that can be improved to correct the issue. But in the mean time, I'd suggest that the best way to fix the issue is to fix the hill. The actual collision points on the hill are in layer zero, whereas the hill appears to be in layer 1. That's the root of the issue.

As I said in the beginning, the root was known to me (after maybe 5 minutes of debugging).
It's the explanation that's elusive.
But maybe instead of writing a long answer I should've looked at that terrain first; maybe I'll find the issue with the terrain after 5 minutes

Now, what tool do people use to edit the terrain? I guess I should start with that...

[karadoc]

Sorry if I was a bit overly defensive in my previous post. I'm a bit tired. I didn't leave much mental resources for expressing myself properly. I agree that even small changes can have unforeseen consequences. I guess what I meant was that I couldn't see a problem with the previous changes, and so I wanted to approach this latest debugging from the point of view that the problem is probably somewhere else. I'm still not exactly what the problem is (because I don't yet know what determines where the "floor" of a tile is) - but I feel like I've got a strong enough understanding of the previous changes to be confident that they aren't the problem.

Since then, I haven't really learnt anything new. But I have spent a few hours wrestling with settings in an IDE, and stuffing around with git.  I'm not having a particularly good day.

[clownagent]

The reason for the the arcing shot problem might lie in the original UFO desert terrain map blocks (Taiga desert are the same). There, the hills are made of 'objects' without floor tiles on higher levels.  So the arcing shot probably wants to hit the 'floor' tile on the ground level, because there are no 'floor' tiles on the upper levels.
However, the ground level floor tile is blocked by the massive 'objects' above.

[Yankes]

For me changing terrain in out of question, original version handled this fine and new should too. Another this is that will require scraping and recreating lot of maps that none modders will want to do.

I would be very careful when changing `TileEngine::calculateLine`, this is used in lot of places and is most fundamental part of game logic.
In other places it work fine why do not work in this place?

[clownagent]

Sorry if I was a bit overly defensive in my previous post. I'm a bit tired. I didn't leave much mental resources for expressing myself properly. I agree that even small changes can have unforeseen consequences. I guess what I meant was that I couldn't see a problem with the previous changes, and so I wanted to approach this latest debugging from the point of view that the problem is probably somewhere else. I'm still not exactly what the problem is (because I don't yet know what determines where the "floor" of a tile is) - but I feel like I've got a strong enough understanding of the previous changes to be confident that they aren't the problem.

Since then, I haven't really learnt anything new. But I have spent a few hours wrestling with settings in an IDE, and stuffing around with git.  I'm not having a particularly good day.

Not sure if it helps, but there can be 4 different types of things on each tile: north wall, west wall, floor, object.
The type is defined by mcd entries.
-Floors are always at the bottom of the tile, but can exist on each level.
-Objects are on top of floors and can have a height. They can elevate units standing on them. In the problematic desert/taiga terrain the whole first level is filled by an object and the top part is so high that it is going into level two (I suppose). 
 

[Meridian]

All 3 of you (karadoc, clownagent and yankes) are probably right... but let's investigate more before jumping to conclusions.

[karadoc]

I wouldn't say that the original version handled it fine... it's was just a combination of two bugs and a bit of luck that made it seem to work. (And those bugs which resulted in the right behaviour here are the same ones that result in obviously wrong behaviour in other cases.) But on the flip side I do agree that this should be fixable without having to change the terrain, even if there is a mistake in the terrain.

I'll try to work out a solution, but I probably won't have time to look at it again properly until the weekend after next.

[karadoc]

This bug has been on my mind a bit; so I've been looking at it while eating dinner and such. Here's the best solution I've come up with so far. I've done very little testing of this, so I'm not totally certain that it's perfect. But it does fix the case we've been testing, and the logic of it seems sound enough to me. I expect that it will correctly in every case.

The only thing I don't like about the fix is that it does the same thing in two separate parts of the code. It's just one line, but I know that code duplication is evil. On the other hand, doing it 'properly' would require a little bit of restructuring, and I don't think it's really worth the bother. I reckon it's fine as is.

Here's the patch,

Code: [Select]

diff --git a/src/Battlescape/Projectile.cpp b/src/Battlescape/Projectile.cpp
index 8cd4410..9ffde7d 100644
--- a/src/Battlescape/Projectile.cpp
+++ b/src/Battlescape/Projectile.cpp
@@ -244,6 +244,11 @@ int Projectile::calculateThrow(double accuracy)
  deltas -= targetVoxel;
  _trajectory.clear();
  test = _save->getTileEngine()->calculateParabola(originVoxel, targetVoxel, true, &_trajectory, _action.actor, curvature, deltas);
+ https:// Adjust final voxel of throw to land on top of the collision point, rather than inside it.
+ if (_action.type == BA_THROW)
+ {
+ _trajectory.back().z++;
+ }
 
  Tile *endTile = _save->getTile(_trajectory.back().toTile());
  https:// check if the item would land on a tile with a blocking object
diff --git a/src/Battlescape/TileEngine.cpp b/src/Battlescape/TileEngine.cpp
index 5fa6cb8..a849544 100644
--- a/src/Battlescape/TileEngine.cpp
+++ b/src/Battlescape/TileEngine.cpp
@@ -3491,6 +3491,9 @@ bool TileEngine::validateThrow(BattleAction &action, Position originVoxel, Posit
  {
  std::vector<Position> trajectory;
  test = calculateParabola(originVoxel, targetVoxel, false, &trajectory, action.actor, curvature, Position(0,0,0));
+ https:// Adjust final voxel of throw to land on top of the collision point, rather than inside it.
+ trajectory.back().z++; https:// Note: this adjustment should be matched in Projectile::calculateThrow
+
  if (test != V_OUTOFBOUNDS && (trajectory.at(0) / Position(16, 16, 24)) == (targetVoxel / Position(16, 16, 24)))
  {
  if (voxelType)


and here's what I've put in my commit message.

Code: [Select]

commit 448f2113d4241f901d4da23f323a5c9710b95f56
Author: karadoc
Date:   Tue Sep 6 19:18:02 2016 +1000

    Adjusted final voxel of throw trajectories to fix a problem.

    Some maps are designed such that an object of height 23 is effectively
    the floor of the tile above. This is a problem for thrown objects
    because the object throw will automatically target the top tile, but the
    collision will always be at the top of the bottom tile (at height 23,
    whereas 24 is where the next tile starts). This results in a 'no arc of
    throw' message.

    To fix this, the final voxel of thrown objects is now increased by 1
    (always); so that the thrown object lands "on top" of the collision
    point rather than inside it.

(Am I the only one who writes explanations in the commit log?)

---
One final thing

I would be very careful when changing `TileEngine::calculateLine`, this is used in lot of places and is most fundamental part of game logic.
In other places it work fine why do not work in this place?

There is a logic problem with TileEngine::calculateLine which results in it checking 1 voxel too far in some particular cases. That's a pretty minor problem really, because 1 voxel at the very end of the line will almost never make any difference. But "almost never" is not the same as "never", and having identified the issue I think it's fair to say that it should be corrected. I'd encourage you (and anyone who is interested) to take a look at the fix that I provided and think about how it fixes the problem without messing up other stuff.

An alternative check is change the drift conditions from

Code: [Select]

if (drift_xy < 0)to

Code: [Select]

if (drift_xy < 0 && y != y1)
(and similarly for the xz drift)
I think that kind of fix is probably easier to understand but less elegant, in my view!


[edit]
I was just thinking about the phase "without messing up other stuff", and it occurs to me that the calculateLine fix would have messed up other stuff if we weren't making these other fixes. I guess what I really mean is that every function should do what it is meant to do. calculateLine should not check for collisions beyond the end point specified, regardless of what functions rely on that kind of erroneous behaviour. I don't ever want to deliberately keep a bug just to avoid causing a different problem. If fixing a bug causes a problem, that problem should be corrected as well. I think it's unwise to rely on particular oddities and past mistakes to produce desired behaviour. The bugs should all be fixed, and the desired behaviour should be restored using the corrected functions.

But I guess most of that is based on my own values, and I can certainly see that there is a kind of pragmatism in keeping certain bugs around for 'stability'.

[Meridian]

Thanks for the update.
I am also looking at this, but can spend only very little time on it now, so it goes slowly.

I think most of what has been said here is true and these are actual bugs.
The nature of the bugs however requires to proceed very carefully.

The fix you have provided will work in this case, but maybe there are other cases... for example object on level below will have height 21, not 23... which for the user is almost indistinguishable.
So instead of going one voxel up, I would probably leave the collision point as it is... and change the check of validity to accept both the target tile and one tile below as well.
This would not require any change in the "sensitive" methods.

I was also wondering, how these methods came to be... if Warboy wrote them from scratch... or if they were reverse-engineered. I almost believe they were reverse-engineered, because it's the "same" behavior as original. And if that's the case, I think the DEVs will not want to make any change there at all:
Just as examples:
1. same arc shot miss issue is in 1994 original ("best defense" against deep ones is just to stand diagonally to them... I remember as a kid they usually didn't kill my rookie aquanauts in no armor even though they stood right next to me and fired many times) ... which now makes sense.
2. as clownagent pointed out, it's not only new terrain that has this issue, but also some original terrain... which might even mean the original xcom developers "made this bug intentionally" so that it somehow works... but that's pure speculation.

I am now thinking how to check the various terrains (vanilla and terrain pack from hobbes) for these anomalies automatically. I'd like to see some statistics before deciding which "workaround" would be the best.

PS: and yes, in general I also think that bugs should be fixed, even if they cause other new issues... however I don't have access to source code of OXC and if I did bigger changes in OXCE+, I would have problems with merging later... that's why I am hesitant to do big refactorings and sometimes my changes look like "hacks/workarounds"... because they are.

PS2: Also, unrelated, that's why I am hesitant to merge bigger/complicated changes from other people into my branch... like for example FOV improvements from Stian. If it wasn't so damned good, I wouldn't take it purely because I don't understand it enough and wouldn't be able to fix merge conflicts later. Fortunately, Yankes took that change into OXCE as well... so the burden of merging will be on his shoulders 

[karadoc]

It's hard to know if there will still be annoying edge-cases where it still brakes. It's certainly conceivable there there will be. The code actually tells the thrown object to target a voxel 2 above the ground.

Code: [Select]

int Projectile::calculateThrow(double accuracy)
{
Tile *targetTile = _save->getTile(_action.target);

Position originVoxel = _save->getTileEngine()->getOriginVoxel(_action, 0);
Position targetVoxel = _action.target * Position(16,16,24) + Position(8,8, (2 + -targetTile->getTerrainLevel()));
So the problem could still occur. eg. If the ground was at a height of 22, it would target 24, which is at the next tile up, and the final trajectory voxel would still only be at 23; so we'd have the same problem. Based on that, an argument could be made that we should just add 2 to the final position rather than +1...

However, I'm confident that the +1 will work correctly. The main reason I'm confident is that I know that the original code only "worked" because the bug in calculateLine which overshot the target by 1 voxel. The fact that overshooting by just 1 voxel was enough for us to never encounter this problem suggests that simply adding 1 voxel will again protect us from encountering the problem.

It isn't a perfect solution, but it's good enough for me.

Checking both the bottom tile and the top tile is probably a safer option though.