Coders Strike Back

AI Battles
#42

Yes, it is :slightly_smiling:

#43

IIRC in the previous “physic” mp battle, there were 100 substeps between turns.

#44

Hi !

Can someone explain me (or give me links to correct explanations) of how I can understand and code how to go to the next checkpoint with a decent trajectory. (Currently I point to the checkpoint position minus my own speed vector, but clearly this is not great).

Thanks

#45

I’m experimenting with collisions and can’t quite figure them out. For example, if one pod stays put, and the second smashes right into it, in case of elastic collision I would expect that the first would to gain all the momentum, and the second one to stop still. But that’s not what happens. Say we have two pods at the distance 1000:

              1000
O------------------------------O

At time #0 they are standing still. I start accelerating the second one with the thrust 100. After one tick the position is:

            900         85
O-----------------------<---O

The distance is 900, the speed is 85, as expected. Now, on the next move they are supposed to collide. What happens?

180          911               23
<--O--------------------------O-->

Also, the left pod (the one that stood still) moved 98 to the left, and the right pod moved 87 also to the left.

Basically, I do not understand these three things:

  1. Why does the left pod have such a big speed after the collision? Even if all the speed of the right pod was transferred to it, it would still be just 157?

  2. Why did the right pod still move to the left after the pods have bounced? Especially, considering that its velocity in the end is in the opposite direction?

  3. How did the right pod gain any speed in the opposite direction if the pods have the same mass? It should have stood still in case of elastic and continue in the same direction in case of inelastic collision.

If anyone has figured out, how exactly collisions work in this game, please explain.

1 Like
#47

the idea is to approximate the trajectory with an equation, the simplest case may be a vertical parabola, (y=ax^2+bx+c), so with three incognitas (a,b,c) you need to solve the system for three points, p1(x1,y1), p2(x2,y2), and p3(x3,y3). so you have:

y1=ax1^2 + bx1 +c
y2=ax2^2 + bx2 +c
y3=ax3^2 + bx2 +c

those three points can be: your current position, next checkpoint, and following checkpoint.

However reality is much cruel, and for a good performance you will need a parabola with any axis, the formula is: ax^2 + bxy+ cy^2 +dx + ey + f =0. for solving this you will need three points and another three conditions, as the curvature ( inverse of radius) at each point.Concatenating this sort of trayectories usually is named as splines.

I found something about that topic here: http://www2.informatik.uni-freiburg.de/~lau/students/Sprunk2008.pdf

by the way, the solution to the vertical parabola is:

        c=-(- y3*x1*x1*x2 + y2*x1*x1*x3 + y3*x1*x2*x2 - y2*x1*x3*x3 - y1*x2*x2*x3 + y1*x2*x3*x3)/((x1 - x2)*(x1*x2 - x1*x3 - x2*x3 + x3*x3));
        
        b=(x1*x1*y2 - x2*x2*y1 - x1*x1*y3 + x3*x3*y1 + x2*x2*y3 - x3*x3*y2)/((x1 - x2)*(x1*x2 - x1*x3 - x2*x3 + x3*x3));
        
        a= -(x1*y2 - x2*y1 - x1*y3 + x3*y1 + x2*y3 - x3*y2)/((x1 - x2)*(x1*x2 - x1*x3 - x2*x3 + x3*x3));

Best of luck

#48

Thank you, this is very useful, I just have a few questions :

  • Suppose we know the parameters of the parabola, how do you make the pod follow this line ? Do you need to compute the tangent and output a point on this tangent ?

  • What do you mean by the curvature (or radius) at a given point ?

Thanks again, I’m gonna read this paper even though it seems a bit hard to apprehend :slight_smile:

#49

Congrats on making these observations. These can be explained by adding an undocumented minimum-impulse value in your code, which is applied when the speed difference on impact is below a certain threshold.

Be aware that this threshold is only applied to half of the total impulse applied to the pods.

I believe with your observations you now have enough information to evaluate the min-impulse and apply it in your simulations.

#50

I think I figured it out. Elastic collisions are defined by two laws: conservation of momentum (sum of mv vectors) and conservation of energy (sum of mv^2 scalars). In the game, the momentum is conserved (for the pods of the same mass, their sum of velocities is not affected by the collision). But it looks like there is a small additional energy value, presumably the energy of the force shields that pushes the other pod away.

This addition to energy becomes negligible on higher speed, but is noticeable when pods are moving slowly.

#51

Hi,

I notice that sometimes, i rematch the same opponent with the same parameters. Can it influence the rank?

#52

When the game will be available in the multiplayer section?

#53

Discussion continues here: https://www.codingame.com/forum/t/coders-strike-back-your-ideas/1338

#54

I’m working on a bot in the Coders Strike Back league (a bit late to the game). I have come across difficulty simulating the game in the following condition:

There are three pods very close together AND that the game’s rounding of positions happens to causes the two outer pods to overlap the middle pod. The center pod collides with the left pod, then immediately collides with the right pod. This is causing an infinite loop (or almost infinite) as the center pods bounces back and forth.

Has anyone encountered this issue? I don’t see the issue mentioned before, so maybe I’m off track here.

Any of the mods know how the game mechanics handles this issue?

#55

I have never encountered this situation. Here are my thoughts though :

  • The situation should be rare enough that it doesn’t matter if your simulation is not accurate when it happens. Any type of band-aid which prevents entering an infinite loop would do the trick.

  • Speaking of band-aids : all my calculations make the assumption that the pods are never overlapping at the beginning of a turn. In the case you describe, this means that I would detect the collision, but at a negative time. It is therefore rejected from the simulation. (I only calculate the time when the distance between the two pods is exactly 800, this means that when they are already overlapping it is not detected as a collision)

  • Another band-aid would be to reject simultaneous collisions. I believe that I used this type of of band-aid for PokerChipRace.

#56

Are you saying that the game simulation breaks down, or are you saying that you just don’t know how to model this for prediction in your AI? Can you share a replay link illustrating this situation?

  • danBhentschel
1 Like
#57

@pb4608, awesome reply.

  • Making the assumption that the pods never overlap is an idea I will try.
  • Yes, I was detecting negative collisions meaning that the pods overlapped due to positional rounding errors. While it may seem rare, it actually happens reasonably frequently at the beginning of the game when all pods are near each other. The minimum impulse exacerbates the issue, as a small tap/overlap can start a chain reaction.
  • Rejecting simultaneous collisions wont solve the problem, as they may not actually be simultaneous: three in a row, but only two overlap- the overlapping pods will collide and the middle pod will begin the endless bouncing.

I think that rejecting negative collisions is the way to go. Thanks.

@player_one, it is my simulation of the game where the problem arises, the actual game itself is fine.

#58

Just in case anyone has a similar problem (position rounding game output causing spurious collisions):

There are two types:
a) Two pods very near each other and are not about to collide, their positions have been rounded and the pods become overlapped. This situation can be ignored and no collisions need to be resolved.
b) Two pods very near each other and are about to collide, their positions have been rounded and the pods become overlapped. In this case, the collision should be resolved. I chose to resolve at t=0 and ignore the overlap.

Example:
Imagine pods have a radius of 2
Pod A at (0.6, 0.6) and
Pod B touching but not overlapping Pod A at (3.35, 3.35) [by Pythagoras to 3 significant figures]

Then the CodinGame engine prints these positions as:
Pod A (1, 1)
Pod B (3, 3)
And the pods are overlapping.
If the pods were moving toward each other, a collision should be resolved, otherwise ignore.

If you ignore all cases of overlap, you will be ignoring valid collisions, and if you have a visualizer for your own simulations, you will sometimes see pods enter each other.

I’m not sure how the CodinGame engine itself handles these cases, but this way seemed to make sense (the CodinGame engine will only have this issue when float/double truncation causing overlap, which is far more rare than the overlap caused by the game output’s integer rounding).

#59

Anyone have ideas on a simple bouncer/chaser bot to train against? I’m really struggling with this.

I read in the other forum thread about using target - 4*velocity as a point to aim at, but it’s quite vague what the target is in this scenario (the checkpoint or enemy racer?).

My current bot targets enemyRacer.pos + (checkpoint.pos - enemyRacer.pos) * 0.8, but it is not very good at all.

#60

in case some haven’t checked it, here is a document written by Magus about Coders Srike Back

1 Like
#62

I am having an issue understanding the logic of finding out the nextCheckpoint variable so I can make the pod slow down and start turning towards the checkpoint after the current checkpoint. writing in java.