If fact, this is a little more complicated !
The physics engine use 500 sub-steps.
In your example, collision occurs at sub-step 278 ( (800-11.254541-674.958088)/(879,552276-674.958088)*500 ).
Before collision, chip is at x = 788,712456528.
At step 276 it is at x = 789,121644904, but the engine move it immediately to a valid position (x<800-11.254541) so x at step 279 = 788,745459. Apply the remaining 221 steps (788,745459+(-204.594188*(221/500)) and … wait for it … 698,314827904.
That’s a key information! Thanks!
OK so if I want to have something real, I need to implement my engine with those 500 steps between each turn. I just hope it won’t break the performances 
How can you predict all interractions without using it ? I
That’s only linear algebra. Algorithms to predict the exact time and position of collision between circles moving without friction are easy to implement and not really costly. Also, it’s working whatever the velocities and sizes of objects are, which is probably the reason you chose these 500 steps ^^.
@Manwe as it seems we both did something similar, I guess finding the exact step isn’t that hard (it’s only discretising time).
Yeah, i agree, in this specific case, we could have done it this way. (It’s the morning here ! ^^ )
Hello. Thanks @loic_mangeonjean1 for usefull explanations. Thanks @Manwe for share your tests. Is it right to think, collision with 2 chips with different radius don’t follow the 500 sub-step engine and make new position calculation with both end positions ?
How does engine manage several collision within the same round (here perhaps 500 sub-step engine works again)? Engine works sub-step by sub-step to resolve each collision of each “entityCount” or engine loops range of “entityCount” ?
@Manwe Then you can forget about tree search lol, you couldn’t get even 1 level of depth, depending on what you explore though.
Re-implementing the full 500 steps engine is pretty much a waste of time because it will eat your 0.1s.
And it won’t change your AI’s behaviour, except in extremely rare case that do not matter in your final Elo.
I search through 6-7 levels of depth for some specific behaviours, using rough and horribly wrong approximations, and it still works pretty well in less than 10ms, which leaves me with plenty of time for future features.
Its not mandatory to implement “super_500_sub_steps_engine”. There are many vector-based collision detection methods, less resource-intensive. But the result will differ from engine, indeed.
Actually, it seems, that internal engine precision is more than 6-digit, so, anyway, there are no real way to code accurate model.
Also, as someone told in the chat a while ago, the goal of these challenges is to be creative, not to bruteforce a tree-search, thanks to the admins for choosing an appropriate time limit to prevent this from happening.
too complicated, lets be more practical…
since “entity with exactly the same size”, then [quote]entity1mass == entity2mass == mass[/quote]
then:
or:
for velocity vector:
where
[quote]normalVector = normalize(Vector(entity1.x - entity2.x, entity1.y - entity2.y))
relativeVelocity = Vector(entity1.vx - entity2.vx, entity1.vy - entity2.vy)
" * " - scalar multiplication
" · " - dot product
[/quote]
Order in substractions should depend on entity evaluated: for e1 => e1.XXX - e2.XXX, for e2 => e2.XXX - e1.XXX
Where am i wrong?
Hello
Be careful, the fact that the object movement is linear does not mean that the collision computation is linear too. My own research on the subject lead me to quadratic equations, not linear ones. Not so hard to solve… if you exclude the fact that an entity path is not a line but a series of parametrized segments, and is not necessarily cyclic.
So yes a clever algorithm is possible, but its not “just linear algebra”.
If you end up with quadratic equation, you probably didn’t go far enough. I mean, when two circles are both moving, you can look at their relative movement so one of the two circles is static (null vector). You then have a single speed vector, which is still linear in our case as there is no friction, thus only linear algebra to do. 
If there was any friction, it’d be a different matter and you’d indeed have to solve quadratic equations.
Hello NewBoo
The quadratic term does not come from the fact both entitities are
moving, but from the computation of the distance between them.
Suppose, as you said, one circle is not moving, hence, X(t) = 0 and Y(t) = 0.
You can express the coordinates of the second one with linear expressions X’(t) = Xa t + b, and Y’(t) = Y’a t + Yb. Right ?
Then you have to compute the distance betweent the two guys. Say we
have r and r’ for radius, then the condition for collision is :
(X(t)-X’(t))² + (Y(t) - Y’(t))² <= (r + r’)². There comes your
quadratic term. Using relative movement does not change anything.
Sure you can solve the collision detection like that, but this is unnecessarily complicated. Here are 2 interesting articles explaining how you can do the same with only linear algebra (and note that I’m talking about linear algebra, not linear equations):
Working directly with vectors is often way more powerful than breaking them down to their equations.
No more than the two articles you provide In fact, both of them, as well a what I suggest, end up with the same thing : solving a 2-degre polynom, hence having to compute at least one square root somewhere in the process (as it shows up pretty well in their code examples). They do not escape the quadratic term, unfortunately. They do not use only linear algebra.
Thanks for the links though 
Edit: I think you are confusing linear algebra and euclidean geometry.
As said : “x et y : la position de l’objet sur le tapis. (0, 0) = (haut, gauche).”
EN :
Is it possible for x and y to take the value 0 ? Reading this, I was certain x and y was the top-left coordinate of the chip. But I’m having trouble to calculate distance between two chips because of that. If I consider x and y are the center of the chip coordinates, thing seems to get better. Can you confirrm please ? The description is not clear.
Suggestion => You should include rules in your preview in debug mode 
FR :
A lire la description de x et y, on dirait qu’ils représentent les coordonnées haut-gauche du jeton. Mais cela mepose des problèmes pour calculer la distance entre deux jetons. Par contre, si je considère qu’ils représentent les coordonnées du centre les chose vont beaucoup mieux. Vous pouvez me confirmer svp ?
Suggestion => Vous devriez mettre des règles pour mieux s’y retrouver en mode debug
Oui, les coordonnées sont le centre du jeton.
L’indication (0, 0) = (haut, gauche) précise juste que la coordonnée (0,0) se trouve en haut à gauche du plateau et non en bas à gauche (axe des y inversé)
I’m mainly working with vectors which are part of linear algebra, but the pythagorean theorem can’t be avoided (and circles are easier to handle with geometry anyway) so in the end it’s a bit of both.
Nevertheless, I recognize that I’m sometimes a bit lost among the different branches of mathematics as they’re often interconnected 
Hi,
I get to the same conclusions but it give me very bad results… Do you find the problem ?
Thanks
Actually i doesnt do too much testing, but it seems work. Remember, that velocity vector V is “relative” between two entities (from e1 to e2). So you should divide it by 2, when setting velocity for each entity. And also check the direction - for e1 it should be reversed.
Something like that:
e1.dx = -V.x/2;
e1.dy = -V.y/2;
e2.dx = V.x/2;
e2.dy = V.y/2;