Need help for corner case collisions in FB

Feedback & Bugs
#1

Hi, so I’m trying to implement the “physic engine” of FB, and I think that I’m nearly done, except for one corner case:

  • at the end of turn N, two entities are very close to each other, but not touching, so there is no collision. That’s fine. Then rounding takes place.
  • at the beginning of turn N + 1, because of the rounding, the two entities are overlapping, so there is an immediate collision at t = 0. And my engine fails to make correct predictions here.

Example: https://www.codingame.com/replay/171812647
At the end of turn 66, wizards 1 and 3 are not colliding but very close.
Indeed they are here before rounding:
1 Point 13839.99 03129.64 Vector +0005.80 +0024.64
3 Point 13872.01 03929.36 Vector -0017.80 +0280.36

Distance between their centers: 800.3594586069449 > 800, so no collision.

Then at the beginning of turn 67, I get in input as expected:
1 Point 13840.00 03130.00 Vector +0004.00 +0018.00
3 Point 13872.00 03929.00 Vector -0013.00 +0210.00

And now the distance between their centers is 799.640544244725 < 800
So there is then an immediate collision at t = 0

Unfortunately my engine, which is doing correct predictions in all other cases, is failing here, and by quite a lot (first line is my prediction, second one CG input of next turn):
1 Point 13989.00 03369.00 Vector +0112.00 +0180.00
1 Point 13981.00 03169.00 Vector +0106.00 +0030.00
3 Point 13852.00 03975.00 Vector -0015.00 +0034.00
3 Point 13860.00 04175.00 Vector -0009.00 +0184.00

I’d like to have some hints on how to handle this corner case, either from CG staff who could look at the referee code, or from players who solved it in their engine, thanks in advance :slight_smile:

Note : Magus discouraged me yesterday to handle these collisions at t = 0, and indeed I’m not sure the precision is worth the cost it’s going to induce in terms of performance, but I’d like to evaluate it before deciding to not handle them.

#2

Please show extracts from your code on how you calculate collision time, and how you decide which collisions are “considered” when looking for the next collision.
Our answer may be different depending on your method.

#3

Well my code is based on Magus’s CSB tutorial.
For collision at t = 0, there is not much to calculate in fact, since it’s just about checking the distances against radii like the example I gave above.
Maybe my issue is more in the handling of those specific “overlapping” collision than in their detection ?
I’ll share some pieces of code tonight as you asked.

#4

Here is the code for the collision detection. Since in my example the two wizards are already too close from each other at t = 0, it returns a collision between them. I think this is correct, as we can indeed see such a collision in the game UI.

private static EntitiesCollision getEntitiesCollision(Entity e1, Entity e2, double elapsedTime) {

		boolean wizardVsSnaffle = e1.type == EntityType.WIZARD && e2.type == EntityType.SNAFFLE;
		boolean snaffleVsWizard = e2.type == EntityType.WIZARD && e1.type == EntityType.SNAFFLE;

		if (wizardVsSnaffle && (((Wizard) e1).isHolding || ((Wizard) e1).grabCountDown > 0)) {
			return null;
		} else if (snaffleVsWizard && (((Wizard) e2).isHolding || ((Wizard) e2).grabCountDown > 0)) {
			return null;
		}

		// Square of the distance
		double dist = getDistanceSquare(e1.p, e2.p);

		// Sum of the radii squared
		double sr = 0;
		if (!wizardVsSnaffle && !snaffleVsWizard) {
			sr = (e1.getRadius() + e2.getRadius()) * (e1.getRadius() + e2.getRadius());
		} else {
			sr = minSnaffleGrabDistanceSquare;
		}

		if (dist < sr) {
			// Objects are already touching each other. We have an immediate collision.
			if (elapsedTime > 0) {
				return new EntitiesCollision(e1, e2, 0);
			} else {
				// It's a collision at the very beginning of the turn, rare cases...
				if (e1.type == EntityType.SNAFFLE && e2.type == EntityType.SNAFFLE) {
					// We'll ignore it if it's between two overlapping snaffles (see test015NoCollision)
					return null;
				} else {
					return new EntitiesCollision(e1, e2, 0);
				}
			}

		}

Now, about how to decide which is the next collision to consider, it’s almost as in Magus’s tutorial:

                                        EntitiesCollision col = getEntitiesCollision(e1, e2, elapsedTime);

					// If the collision occurs earlier than the one we currently have we keep it
					if (col != null && col.time + elapsedTime <= maxPlayTime && !previousCollisions.contains(col)) {

						if (firstCollision == null) {
							firstCollision = col;
						} else if (col.time < firstCollision.time) {
							firstCollision = col;
						} else if (col.time == firstCollision.time) {
							// We have a simultaneous collision. Except when it's a "mirror match", it'll only happen when a wizard cooldown resets and two (or more) snaffles are in its radius
							// In this case the wizard will grab the closest one
							if (col.e1.id == firstCollision.e1.id && e2.type == EntityType.SNAFFLE && firstCollision instanceof EntitiesCollision) {
								if (getDistanceSquare(col.e1.p, col.e2.p) < getDistanceSquare(firstCollision.e1.p, ((EntitiesCollision) firstCollision).e2.p)) {
									// The new one is closer, so take it instead
									firstCollision = col;
								}
							} else {
								firstCollision = col;
							}

						}

					}

Anyway, in my example it’s the only collision for the whole turn, so I don’t think this part of the code can be responsible for the issue I have.
My guess is that “something” is done by CG for overlapping entities before bouncing them, but I can’t figure out exactly what.

#5

I see nothing wrong in your code, because you have that lengthy if(dist < sr) condition.

My implementation for example only detects the exact moment when dist == sr. This is why I can not handle the situation you describe correctly.

Good luck understanding where the difference between your code and the servers comes from. I’d be interested to know when you find out :slight_smile:

1 Like
#6

Ok thanks for your reply.
Let’s see if another player or someone from CG can help :slight_smile:
On my 50 JUnits, I’ve only 5 failures all due to this tricky case, all other cases are working correctly.
By the way, this tricky case is not so rare, when I run a batch with CG Spunk I see it happening “at least once in a game” in maybe 5 or 10% of the games.

#7

In the engine, if the distance between two entities is negative, then we fix the positions by moving them in the opposite direction:

c1.position.add(normal.mult(-(-diff / 2 + EPSILON)))); c2.position.add(normal.mult(-diff / 2 + EPSILON)));

with EPSILON=0.00001

Hope that helps.

1 Like
#8

Thanks a lot, I’ll fix my engine with this and see if I get 100% passed :slight_smile:

#9

Applying this correction fixed 2 of my 5 tests, which were wrong by “one pixel”, so it’s at least something :slight_smile:
However it didn’t helped to fix the 3 remaining ones, like the one I gave as example between the two wizards.

I was “feeling” that it would not solve it, since the discrepency between the prediction and the actual game was really big, both for the position AND the speed.
And the “espilonnesque” correction here only applies to the positions, which, even if it could have an effect on the upcoming collision, cannot correct the speed by as much as ~200…

Looking again at the values, it really looks like a +8 / +200 vector (before friction) is applied to the wrong entity (1 instead of 3):
1 Point 13989.00 03369.00 Vector +0112.00 +0180.00 (prediction)
1 Point 13981.00 03169.00 Vector +0106.00 +0030.00 (actual value)
3 Point 13852.00 03975.00 Vector -0015.00 +0034.00 (prediction)
3 Point 13860.00 04175.00 Vector -0009.00 +0184.00 (actual value)

If this vector would be applied to 3 instead of 1, all values would be good.

But if I had such a big obvious bug in my code, how would I correctly predict 99% of the other collisions and just fail in this case ?

#10

Ok I looked again at my example, and I had not realized that there was a late collision during turn 66 (starting at frame 130).
I modified a little bit the example to make it even simpler: the wizards won’t boost for turns 66 / 67. New replay: https://www.codingame.com/replay/172660816
So the scenario is in fact the following:

  1. At the beginning of turn 66 (frame 130), the wizards are here (none of them is boosting):
    1 Point 13824.00 02851.00 Vector +0016.00 +0279.00
    3 Point 13900.00 03903.00 Vector -0028.00 +0026.00

There is a very late collision during turn 66 at t = 0.9985879283014436, and the wizards are bouncing.
They have very little time to move after the bounce since it’s almost end of the turn, so they finish very close to each other (see in my first post distance between their centers is 800.35).
Then rounding takes place and their final position is:
1 Point 13840.00 03130.00 Vector +0004.00 +0018.00
3 Point 13872.00 03929.00 Vector -0013.00 +0210.00
This is correct as this is exactly what I get as input by CG in turn 67

  1. At the beginning of turn 67 (frame 132), they’re overlapping. As advised by Maxime, their position will be corrected. There is still no boost applied.
    Positions after the correction are then the following (speeds are not affected by the correction, only positions):
    1 Point 13839,99 03129,82 Vector +0004,00 +0018,00
    3 Point 13872,01 03929,18 Vector -0013,00 +0210,00

… and I don’t detect any collision with these values !
This seems “logic”, because they had already done their collision during the previous turn and there is no boost, so their speed are now moving them away from each other like always after a collision.

But… with no collision detected, the end result will still not match CG values:
1 Point 13844,00 03148,00 Vector +0003,00 +0014,00 (prediction)
1 Point 13844,00 03143,00 Vector +0003,00 +0010,00 (actual value)
3 Point 13859,00 04139,00 Vector -0010,00 +0158,00 (prediction)
3 Point 13859,00 04144,00 Vector -0010,00 +0161,00 (actual value)

In fact looking at wizard 3, with no collision and no boost, its final speed on Y should simply be 210 * 0.75 = 158 (that’s my prediction), but the fact that it’s more (161) seems to indicate that CG considers that there is a collision, which slows down 1 on Y and boosts 3 on Y.

Conclusion:
For me we shouldn’t have a collision between 1 & 3 during turn 67, since it already occured during turn 66 (and they’re not boosting). But the values from CG seems to indicate that they consider a collision.
Is it a bug in CG’s engine ?
Am I completely wrong on my analysis ?

Edit: full test data here http://pastebin.com/tU8QkzkV

#11

When I calculate time to collision - i check do distance between 2 centers is smaller then sum of radiuses - if so my function return 0. So will return 0 - and 1st part - collision detection is OK.

Because time interval is 0 - it is no need to move all entiites - I’m just doing bounce.

Bounce is exactly as for normal collision. Only tricky is that impulse can be negative. In physical situation it is impossible - but in such collision - due to rounding - impulse can be negative. Any way - I calculate impulse, implement it to both entities. Next I compare my impulse with 100. So any way - next impulse will be positive (at least 100). So I implement this second impulse.

So now I have correct velocities (correct according to FB simulator). But still have overlaping entities.

So I move all entities by 1e-7 (or any walue). And return to detection next collisions.

I checked my simulator on 88 games. And I have had no difference in any collision. Only sometimes difference in rounding (when correct possition is around 0.5). Per average I have 1 such difference (rounding of 0.5) per game.

In this 88 games I have had I big difference. It was in situation that due to rounding - my wizard have had 2 snaffles in time 0. I do not know FB rule to decide which snaffle catch. In one situation it was snaffle with bigger ID, in another game - snaffle with smaller ID.

#12

Hi, thanks for your message.
Is your code able to predict the correct CG values in my example ?

I had implemented the “position correction” before anything else, unlike you who implemented after the immediate bounce at t = 0.
It’s true that Maxime didn’t told us the exact sequence and when exactly the correction is applied.
But anyway in my example in my opinion there is no sense in having a collision during turn 67, since it already occured during 66 so the speeds are now moving the wizards away from each other. So wether the correction is applied before or after bouncing should not make a difference.
Just to be sure I tested with the way you implemented it, still not able to get the correct CG values.

Finally, about the use case where a wizard has two snaffles to grab, from my testing I concluded that he grabs the closest one, nothing to do with IDs.

#13

In this 88 games I have had I big difference. It was in situation that due to rounding - my wizard have had 2 snaffles in time 0. I do not know FB rule to decide which snaffle catch. In one situation it was snaffle with bigger ID, in another game - snaffle with smaller ID.

I found that the wizard catches the snaffle which is closer to it’s center in such cases.
Can someone else confirm?

#14

Yes, my code predicts the corect CG values in your example.

Before final rounding my prediction is:

so after rounding I have exactly CG values.

You example is exactly this “nonphysical” situation I talked about in my previous post. Collision with negative impulse. Speaking in another words - situation when before collision entities move apart. So it is absolutely “nonphysical”. I do not know is it planned or is it an error - but actually it works this way.

When you implement “position correction” before everything - you code detects only “physical” collisions - and correctly do not detect this “nonphysical”. So it is the reason you have problem with around 50% of overlaps - I think that probablility of overlaping is similar for “physical” and “nonphysical” case .

I agree and disagree simultanously with Magus concernng the simulator. For sure such details are not imporant for any bot above first 10 positions, and in contest - probably above 1st 3 positions. But my current bot - without spells - have 3% win rate with Magus one - and in all cases I think I win due to Magus’s bots error in overlaping cases. For sure simply adding spells or better fitness function will give me much better winrate then 3 wins in 100 matches - but without good simulator I have had 0 wins :slight_smile:

If you interested in I can post my C++ code for bounce calculation (it is not based on Magus one and is rather simple - 5 lines).

1 Like
#15

Thanks. I have not found it. :slight_smile: So now my simulator have only problem with rounding in some *.5 cases :slight_smile:

#16

I round entity x,y coordinates and vx, vy only at end of every game round.
I’m using this method:


The method in the question is fast and good enough for Fantastic Bits.

public static long round(double d) {
    if (d > 0) {
        return (long) (d + 0.5d);
    } else {
        return (long) (d - 0.5d);
    }
}
#17

Ok thanks, I finally got it right (at least for this use case).
The order I do the things now is:

  1. detect immediate overlapping collision
  2. then correct positions (if you do 2 then 1, you may miss on detecting the collision)
  3. then bounce, by applying the “negative” impact vector once (it’s going to make the entities even more overlapping !!!), then a second time with a “positive” minimal 100 impulse

What happens is that the impulse of the collision in my example was ~95, so the bounce is essentialy doing -95 then +100, and here you get the ~5 difference between the prediction I had without collision, and the actual values with this strange collision (for both the position and the speed).

“Physically” speaking, for me it doesn’t make any sense, especially because the bounce was already performed at the previous turn, but I’ll just follow JFB on this one:

All right, so I’ll stop with this topic, I may open a corner case #2 one :slight_smile: as I already saw other strange things (wrong prediction without even a collision, wrong prediction just on one side and not the other, etc…)