Precision problems when calculating future positions of characters

Feedback & Bugs
#1

I don’t know if this could be considered a bug, but it’s causing me some errors when calculating future positions of the actors (in this case, Zombies). Check this example:

From this:

Code vs Zombies (A).jpg1598×904 518 KB

To this:

Code vs Zombies (B).jpg1595×899 509 KB

I am calculating the Zombie #2 new position as (6887,2459) which means the Zombie advances 399.3018908 units, but the system calculates the new position (as shown in the second image) as (6887,2458) which is a distance of 400.2811512 which is larger than the Zombie step size of 400 (you can also check this graphically at https://ggbm.at/FJNfnzve The line is a vector of length 400 with origin at (6806,2850)

This small (1 unit) difference causes my logic to think that the Zombie is still alive (according to my calculations) but the system reported new state considers the Zombie as death (as shown in the image) which in turn breaks all my future predictions.

Rounding causes lots of problems in this cases, mainly because the direction of the vector can and will affect the rounding direction. Maybe CG could share a standard algorithm so anyone can calculate this new position congruent with the system, so this won’t happen?

Thanks,
Oscar Nava aka “Monstruo”

#2

I believe the way this calculation is done on the CG’s side is by always rounding the results down, so when the true position should have been, say, (6887.356, 2458.754), the result will end up as (6887, 2458), which indeed means the zombies can occasionally step more than 400 units.

Source: One of the posts related to The Accountant contest, which I believe uses the same engine.

Edit: in fact, this behavior is specified explicitly in the Expert rules for the problem:
The coordinate system of the game uses whole numbers only. If Ash or a
zombie should land in a non whole coordinate, that coordinate is rounded
down.

#3

I agree with what you say, but to add more to this story, at first I was rounding down like stated until I found a situation in The Accountant where rounding down was resulting in a point a little farther than the 1000 step size, but the system had it “right”, a little lower than 1000 units, so I thought this should be taken “into account” :wink: and that worked well in TA, but this seems to be a little bit unstable since every now and then I find some situation where this happens.

I’ve resorted to comparing my forecast with the system results and reset when not equal but, in one hand, this is still more work to do in the 100ms time span, and in the other, I think this should be an exact result; the math is not that complex.

That’s why I suggested having a standard algorithm for this, one everybody can use and obtain the same results on both sides. What do you think?

Edit: I’ve checked again the Expert rules and, in addition to what you pointed out, it says: “For example, if a zombie were to move from X=0, Y=0 towards X=500, Y=500, since it may only travel 400 units in one turn it should land on X=282.843, Y=282.843 but will in fact land on X=282, Y=282.”. I think this is some sort of corner case where, when the character is traveling in a negative direction, rounding down in fact increases the distance traveled.

#4

In TA too, a agent could travel more with the rounding errors.
Move Ash from 2000,2000 to 0,0 will result in Ash in 1292,1292 (1001.2632 unit > 1000)

#5

I wish I had saved some example from TA but couldn’t find one; guess it will remain unknown if it was in fact an exception or just an unicorn :wink:

In any case, I’ve tried to find some algorithm that would in fact give me a position that is at the precise distance or just below, but I find the added complexity doesn’t justify the precision gain. It will suffice to know that the system will always round down, even when that would mean that the actor will move farther than it’s allowed.

Like I said above, this corner case causes both premises to conflict, that is, to round down and that the actor may only travel xx units; in this (corner) cases they can not both be true. I (wrongly) assumed that the second should prevail over the first.

Anyway, my concern isn’t to question the correctness of the system calculations, but that we both use the same algorithm.

Thanks a lot for your feedback! :grinning:

#6

Hi!

I did not had the chance to participate to Code vs Zombies so I take this calm period of the year as an opportunity :slight_smile:
I was rewriting the game engine in order to be able to predict score and zombies movement, and I am facing an issue I can’t explain…

In the test case “Horde” (number 17) I have one Zombie move I don’t understand.

This is the scenario:

Ash starts at position (3989,3259). Zombie number 3 starts at position (11060,253).
Closest human to zombie 3 is human 0 at position (3647,384) so Zombie 3 moves to (10660,270)
I move Ash to coordinate (4133 2397)
Closest human to zombie 3 is now Ash, so Zombie 3 is moving in position (10279, 384 )
I move Ash to coordinate (3502, 1796)
Closest human to zombie 3 is now human 0 at position (3647, 384).

Problem occurs here : zombie is moving to coordinate (9873, 383) when I would expect it goes to (9873, 384). I don’t understand why and how it can loss 1 in y since its target is perfectly aligned with its current coordinate…

Any idea anyone?

It should be easy to reproduce :
Simply order 4133 2397 then 3502 1796 in the “Horde” test case and you should see the issue with zombie 3.

#7

I didn’t look in the referee code, but I found this while scrolling:

public void moveTo(int tx, int ty, int speed) {
	double dir = Math.atan2(-ty + y, tx - x);
	if (distanceTo(tx, ty) <= speed) {
		x = tx;
		y = ty;
	} else {
		// Truncate
		x += speed * Math.cos(dir);
		y -= speed * Math.sin(dir);

		// Round
		// x = (int) Math.round(x + speed * Math.cos(dir));
		// y = (int) Math.round(y - speed * Math.sin(dir));
	}
}

Hope it helps :slight_smile:

#8

Hi!

Yes it indeed help! At least to explain why I have a different result.
In my case we have
atan2(0, -6632) which gives dir equals “almost” PI : 3.1415926535897931
The problem is with sin(dir) that returns… 1.2246467991473532 e-16

Due to the rounding we then have this shift of -1 in y.

I have a slight decrease of performances using atan2 + sin + cos versus my other implementation that normalize the vector of movement using a single call to sqrt and then adds it to the current position. In debug it is fine, I lost around 10%, but with optimization flags it’s a 2 times factor…

That’s fine for me, I’ll disable my check and keep my implementation :slight_smile:. A 1 rounding should not influence too much.