Codingame - La programmation hantée. Concours de fantômes dans la console fin Fevrier

[Monsieur Odd]

Cans 5 jours ca recommence. Des partants?

http://tof.canardpc.com/view/c0fa4fd...2024eaadbb.jpg

Je suis inscrit mais il va falloir que je trouve de la motivation parce que si je continue a me sentir comme actuellement, ca va pas etre glorieux.

[Naity]

Commwnt te sens tu actuellement?

[TarteAuxFleurs]

Bon, bah le nouveau challenge est un peu identique à celui de SF, sauf que l'on a 2 pods

[Monsieur Odd]

Commwnt te sens tu actuellement?

Débordé, pas vraiment envie de le lancer dans un truc de plus. Je regarderai mardi matin. Mes étudiants seront en exam et j'aurai rien à branler.

[Foudge]

Bon, bah le nouveau challenge est un peu identique à celui de SF, sauf que l'on a 2 pods

On ne peut plus "freiner", si ?

[Max_well]

Non, c'est surtout qu'on a un limitation sur le changement d'angle d'un tour à l'autre.
J'ai repris mon code à l'identique (Merci Naity ), et c'est plus holiday on ice :D

[Naity]

Non, c'est surtout qu'on a un limitation sur le changement d'angle d'un tour à l'autre.
J'ai repris mon code à l'identique (Merci Naity ), et c'est plus holiday on ice :D

Et plus de boost, mais un Shield a la place. Le fait d'avoir 2 pods ca ouvre quelques stratégies de grosse putasse. Enfin je vais déjà commencer par importer mon code, et tant qu'à faire, nettoyer un peu mes classes.

- - - Mise à jour - - -

Probablement !

T'as changé de pseudo?

[Naity]

Je me hais. Je galère encore (et toujours) sur des maths niveau collège.

Je cherche les coordonnées de Xr, en ayant les coordonnées de x1, x2 et x3. Xr et a une distance d de x2 sur la droite de la hauteur. Mon approche aurait été de calculer la position de H et d'en d´duire par bidouillage la position de Xr a d de distance de x2 sur le segment HX2... Mais je sèche

Un petit coup de pouce?

[Møgluglu]

Si tu poses v le vecteur de longueur 1 partant de x2 en direction de H:
v est orthogonal à x1x3, donc tu peux faire une rotation à 90, puis normaliser v. Une fois que tu as v, tu le multiplies par d et l'ajoute à x2.

// Rotation
v.x = x1.y - x3.y;
v.y = x3.x - x1.x;
if(merde_cest_pas_le_bon_sens) {
  v.x = -v.x;
  v.y = -v.y;
}
// Normalisation
invnorme = 1 / hypot(v.x, v.y);
v.x *= invnorme;
v.y *= invnorme;
// xr = x2 + d v
xr.x = x2.x + v.x * d;
xr.y = x2.y + v.y * d;

Tu noteras donc qu'il y a deux cas suivant de quel côté est x2 par rapport au vecteur x1x2... Tu peux calculer la condition merde_cest_pas_le_bon_sens à partir du signe du produit scalaire x1x3 * x1x2, avec seulement une chance sur deux de se planter.

[TarteAuxFleurs]

C'est quoi vous votre stratégie d’accélération ?
Moi je prends le symétrique de mon vecteur vitesse par rapport au vecteur moi-checkpoint, et je pousse dans ce sens !

[Naity]

Merci Mogluglu. Je vais voir si j'arrive a traduitre ca en resultats concrets. Je crois avoir pigé le principe, reste plus q'a implémenter "merde_cest_pas_le_bon_sens" et voir si ca marche

- - - Mise à jour - - -

C'est quoi vous votre stratégie d’accélération ?
Moi je prends le symétrique de mon vecteur vitesse par rapport au vecteur moi-checkpoint, et je pousse dans ce sens !

Presque pareil. Je prend le symétrique de mon vecteur de vitesse par rapport à moi-checkpoint, mais seulement si l'angle en compris entr +-89° et +-5° (valeurs calculées finement à l'aide du théorème du trial_and_error).

EDIT: C'est quoi ton profil CiG gbip?

[Møgluglu]

Vous avez cherché des solutions analytiques, pour avoir l'idée de la trajectoire optimale ?
Dans le cas où le vecteur accélération est libre mais de longueur constante (toujours au taquet), la trajectoire doit ressembler plus ou moins à une spline d'ordre 3, non ?
Et dans le cas où le changement d'angle est limité, c'est la dérivée de l'accélération qui est constante, ça doit faire passer à l'ordre 4. À la louche. Faut poser ça proprement, mais si c'est polynomial, alors il doit y avoir moyen de calculer la solution optimale (pour 1 pod tout seul, mais ça serait un bon début...).

[Naity]

Vous avez cherché des solutions analytiques, pour avoir l'idée de la trajectoire optimale ?

Pas en ce qui me concerne. rOut a une approche assez propre a base de deceleration et de compensation de l'inertie avant d'arriver sur le checkpoint. J'ai une approche tres sale pour l'instant qui ne calcule n'y n'anticipe rien. Ceci dit, il y a effectivement moyen de mettre ca sous forme d'equation, mais ca risque d'etre chiant a reguer sachant que les enemis peuvent te faire violemment devier.

Apres, ya aussi ptet moyer d'utilier un vaisseau comme "belier" pour pousser le second '^^

[Møgluglu]

L'idée c'est que si tu connais la trajectoire optimale ou au moins certaines de ses caractéristiques, ça peut guider ta stratégie. Par exemple, plutôt que foncer droit sur le checkpoint, tu peux commencer à préparer ton virage vers le checkpoint suivant. Intuitivement, si tu as des checkpoints A->B->C je dirais que le checkpoint B correspond au point de corde du virage en allant de A à C. Donc au lieu de viser simplement une position, tu vises à la fois une position et un vecteur vitesse : je dois passer ce checkpoint avec tel angle et telle vitesse.

Après il doit y avoir un compromis entre prendre des virages très larges sans ralentir et les prendre plus serrés en parcourant moins de distance (et en éjectant les concurrents).

PApres, ya aussi ptet moyer d'utilier un vaisseau comme "belier" pour pousser le second '^^

Genius ! Ouais ça doit le faire, façon course de relais en alternant la fonction coureur/bélier à chaque checkpoint. Mais les deux pods doivent passer tous les checkpoints dans l'ordre quand-même ?

[rOut]

Il suffit qu'un pod finisse premier pour gagner. Je pense qu'une stratégie valable serait d'avoir un courreur et un attaquant qui va juste faire chier les pods concurrents.

Niveau stratégie personnellement j'ai juste fait du Monte Carlo (comme c'est subtil !). Pas eu trop le temps de me pencher sur le problème ce week-end.

[TarteAuxFleurs]

Merci Mogluglu. Je vais voir si j'arrive a traduitre ca en resultats concrets. Je crois avoir pigé le principe, reste plus q'a implémenter "merde_cest_pas_le_bon_sens" et voir si ca marche

- - - Mise à jour - - -



Presque pareil. Je prend le symétrique de mon vecteur de vitesse par rapport à moi-checkpoint, mais seulement si l'angle en compris entr +-89° et +-5° (valeurs calculées finement à l'aide du théorème du trial_and_error).

EDIT: C'est quoi ton profil CiG gbip?

Mon profil CiG
J'ai pas beaucoup de code dessus, et j'ai pas un énorme niveau (1A d'école d'ingé).

[Rao]

Je pense qu'une stratégie valable serait d'avoir un courreur et un attaquant qui va juste faire chier les pods concurrents.

C'est la stratégie qui a pas mal la cote sur le chat. Laisser un pod sur l'arrivée pour empêcher les autres de passer aussi.
Pas mal de discussion sur la physique du jeu aussi apparemment le coef de friction de 0.85 du précédent challenge est toujours d'actu.

[TarteAuxFleurs]

Ouais, et pour avoir une vitesse constante, la formule est : thrust = (3/17)*speed.
Je l'ai pas verifiée cependant.

[Naity]

C'est la stratégie qui a pas mal la cote sur le chat. Laisser un pod sur l'arrivée pour empêcher les autres de passer aussi.

Ca me parrait pas top comme strategie. Ca peut aider l'adversaire meme.

Je ne pense pas que les strategies offensives soient les meilleurs. Je developperai ce soir quand j'aurais acces a un ordi

- - - Updated - - -

Mon profil CiG
J'ai pas beaucoup de code dessus, et j'ai pas un énorme niveau (1A d'école d'ingé).

Chouette, je t'ajouterais a l'OP tt a l'heure.

Tkt pour le niveau, t'es pas le seul.

[TarteAuxFleurs]

Un gars du chat a donné les formules utilisées par le moteur pour calculer les positions :
x(n+1) = x(n)+vx(n)+T*cos(alpha)
y(n+1)=y(n)+vy(n)+T*sin(alpha)
vx(n+1) = (vx(n)+T*cos(alpha))*0.85
vy(n+1) = (vy(n)+T*sin(alpha))*0.85
Merci dk987.

[TarteAuxFleurs]

A prendre avec des pincettes bien sur.
Et si quelqu'un sait faire le symétrique d'un vecteur par rapport à un autre, je suis preneur.
Pour le moment, j'ai un truc comme ça :
(V1 et Axe 2 vecteurs)
V1sym = 2*scalaire(v,axe)*axe-v1
Mais ça donne pas des super résultats...

[Naity]

Genius ! Ouais ça doit le faire, façon course de relais en alternant la fonction coureur/bélier à chaque checkpoint. Mais les deux pods doivent passer tous les checkpoints dans l'ordre quand-même ?

En course de relais ca peut pas le faire, car les pods ne se partagent pas les checkpoints. Mais tu peux avoir un coureur et un "pousseur". Je pense qu'il y a moyen de gagner qqs 10aines de tours sur l'angle le plus petit entre 3 checkpoints. En l'etat, avec les limitation du systeme de "tournage", il faut anticiper / decelere / prendre un angle d'arrivee tres large (en y gaspillant de nombreux tours). Sachant que le bouclier semble renforcer l'inertie des ehicules de beaucoup et que les impacts sont vraiment violents pour devier un pod de sa trajectoire, il doit etre possible de les utiliser a son avantage.

Cas 1: Algo bourrin (pas a l'echelle)


Cas 2: Courbe optimale (pas a l'echelle)


Cas 3: Compensation dite "du belier"


Avantages: c'est beaucoup plus deterministe que de tenter d'handicaper l'adversaire (les deux vaisseaux peuvent communiquer entre eux, se synchroniser, hand- et booty-checker...) alors que de tenter d'handicaper l'adversaire reste pas top. Rester sur le checkpoint d'arriver peut meme avantager l'adversaire si le checkpoint suivant n'est pas dans la prolongation du precedent.

Une technique que j'imagine beaucoup plus chiante serait d'avoir un pod faisant le circuit a contresens ! Du coup avec une inertie importante allant a l'oppose du sens de la course. En activant le bouclier au bon moment y'a moyen de mettre 10-15 tours dans les dents de l'adversaire (estimation faite a l'aide du theoreme du pifometre) mais c'est beaucoup plus dur a coder / moins sur: Les comportements des vaisseaux enemis sont compliques a anticiper, et il faut un garde-fou pour eviter de se prendre son propere vaisseau dans la gueule (bonne chance avec la limite de 18 degres).

C'est les dernieres idees qui me sont passees par la tete. Je ne pense pas pouvoir els implementer, mais c'est toujours mieux de partager

- - - Mise à jour - - -

Et si quelqu'un sait faire le symétrique d'un vecteur par rapport à un autre, je suis preneur.

En copie/colle de mon code pas documente, le symetrique de speedVect par rapport a destVect. C'est probablement pas l'algo le plus efficace mais ca semble fonctionner:

double k = 1.0*(speedVect.X*destVect.X + speedVect.Y*destVect.Y)/(destVect.X*destVect.X + destVect.Y*destVect.Y);
Vector dotProduct = new Vector((int)Math.Round(k*destVect.X), (int)Math.Round(k*destVect.Y));        
int xDist = dotProduct.X - speedVect.X;
int yDist = dotProduct.Y - speedVect.Y;
Vector compensateVector = new Vector(speedVect.X + xDist*2, speedVect.Y + yDist*2);

En gros, je projette speedVect sur destVect, je calcul la distance entre speedVect et le vecteur projete dont j'ajoute le double a speedVect pour trouve le symetrique.

[rOut]

Haha forcément quand on ne fait pas d'erreur de calcul ça va beaucoup mieux :3

[Naity]

Haha forcément quand on ne fait pas d'erreur de calcul ça va beaucoup mieux :3

49.23

Beau gosse

[rOut]

C'est un peu redescendu quand même, soyons honnêtes.

Par contre je commence a avoir un assez bon framework pour travailler maintenant, je me suis même fait une version hors-ligne ou je joue tous les pods et qui génère des pngs avec des dessins de debug.

- - - Mise à jour - - -

D'ailleurs, la mécanique des collisions et en particulier du SHIELD est connue précisément ?

J'ai du code pour tenter de prédire les trajectoires en cas de collision, mais je ne suis pas sûr que ce soit correct. En particulier au niveau des vecteurs vitesse après collision.

- - - Mise à jour - - -

Le shield j'ai l'impression que ça fait plus que ajouter du poids, lorsque je calcule la somme des normes des deux vecteurs vitesse avant et après collision avec SHIELD activé, j'ai l'impression que ça ajoute genre 200 unités/s au total par rapport avec la version sans SHIELD qui a l'air de conserver la quantité de mouvement totale.

[ds108j]

Intéressant ce site, je m'inscris, et je regarde. Même si le développement ne fait pas complètement partie de mon job, j'en fais un peu de temps en temps.

[Naity]

pngs avec des dessins de debug.

On peut voir?

- - - Mise à jour - - -

Intéressant ce site, je m'inscris, et je regarde. Même si le développement ne fait pas complètement partie de mon job, j'en fais un peu de temps en temps.

Ouelkome. Si tu poste ton profil, je peux t'ajouter à l'OP. Et pas de soucis pour le job, on est qqs uns a n'avoir aucun background en info, mais on s'amuse quand même

[TarteAuxFleurs]

En course de relais ca peut pas le faire, car les pods ne se partagent pas les checkpoints. Mais tu peux avoir un coureur et un "pousseur". Je pense qu'il y a moyen de gagner qqs 10aines de tours sur l'angle le plus petit entre 3 checkpoints. En l'etat, avec les limitation du systeme de "tournage", il faut anticiper / decelere / prendre un angle d'arrivee tres large (en y gaspillant de nombreux tours). Sachant que le bouclier semble renforcer l'inertie des ehicules de beaucoup et que les impacts sont vraiment violents pour devier un pod de sa trajectoire, il doit etre possible de les utiliser a son avantage.

Cas 1: Algo bourrin (pas a l'echelle)
http://tof.canardpc.com/view/f09ffc0...11724079df.jpg

Cas 2: Courbe optimale (pas a l'echelle)
http://tof.canardpc.com/view/4a6d316...74100a5cbb.jpg

Cas 3: Compensation dite "du belier"
http://tof.canardpc.com/view/4ca3034...380b558dcf.jpg

Avantages: c'est beaucoup plus deterministe que de tenter d'handicaper l'adversaire (les deux vaisseaux peuvent communiquer entre eux, se synchroniser, hand- et booty-checker...) alors que de tenter d'handicaper l'adversaire reste pas top. Rester sur le checkpoint d'arriver peut meme avantager l'adversaire si le checkpoint suivant n'est pas dans la prolongation du precedent.

Une technique que j'imagine beaucoup plus chiante serait d'avoir un pod faisant le circuit a contresens ! Du coup avec une inertie importante allant a l'oppose du sens de la course. En activant le bouclier au bon moment y'a moyen de mettre 10-15 tours dans les dents de l'adversaire (estimation faite a l'aide du theoreme du pifometre) mais c'est beaucoup plus dur a coder / moins sur: Les comportements des vaisseaux enemis sont compliques a anticiper, et il faut un garde-fou pour eviter de se prendre son propere vaisseau dans la gueule (bonne chance avec la limite de 18 degres).

C'est les dernieres idees qui me sont passees par la tete. Je ne pense pas pouvoir els implementer, mais c'est toujours mieux de partager

- - - Mise à jour - - -



En copie/colle de mon code pas documente, le symetrique de speedVect par rapport a destVect. C'est probablement pas l'algo le plus efficace mais ca semble fonctionner:

double k = 1.0*(speedVect.X*destVect.X + speedVect.Y*destVect.Y)/(destVect.X*destVect.X + destVect.Y*destVect.Y);
Vector dotProduct = new Vector((int)Math.Round(k*destVect.X), (int)Math.Round(k*destVect.Y));        
int xDist = dotProduct.X - speedVect.X;
int yDist = dotProduct.Y - speedVect.Y;
Vector compensateVector = new Vector(speedVect.X + xDist*2, speedVect.Y + yDist*2);

En gros, je projette speedVect sur destVect, je calcul la distance entre speedVect et le vecteur projete dont j'ajoute le double a speedVect pour trouve le symetrique.

Merci pour ton code, je suis dessus

[rOut]

On peut voir?

- - - Mise à jour - - -



Ouelkome. Si tu poste ton profil, je peux t'ajouter à l'OP. Et pas de soucis pour le job, on est qqs uns a n'avoir aucun background en info, mais on s'amuse quand même

[TarteAuxFleurs]

Tu gères comment les cas où ton vecteur est derrière le vecteur destVect ? (quand tu es en train de reculer par rapport à l'objectif)