Position dans un classement à chaque passage de checkpoint ?

Bonjour, je développe un jeu de course en ligne dans lequel mon serveur doit renvoyer aux joueurs la position (1er, 2e, 3e...) de tous les joueurs.

La position sur le circuit est déterminé par des checkpoints ainsi pour le moment, dès qu'un joueur passe un checkpoint je parcours tous les joueurs pour compter le nombre de joueur qui ont déjà franchit ce checkpoint ce qui me donne la position du joueur.

Mais il faut encore que je vérifie si un autre joueur avait déjà cette position et la modifier le cas échéant...


Pensez vous que j'utilise la bonne méthode ou voyez vous plus simple et qui demanderait moins de calcul ?

Merci

Pourquoi ne procèdes-tu pas exactement comme dans le monde réel ?

Tu fais n objets dans un tableau correspondant à chacun de tes concurrents, tu les tries en mémoire dans l'ordre où ils sont alignés au départ, et chaque fois qu'un concurrent dépasse un autre, tu permutes les deux objets dans ton tableau. Ainsi il sera toujours trié et tu seras toujours où tu en es toi-même.

Il est très aisé de calculer la position d'un élément dans son tableau, donc tu peux considérer cette info comme disponible pratiquement sans calcul. En outre, au moment exact où tu franchis un checkpoint, par définition, tout ceux qui sont derrière toi ne l'ont pas encore franchi, et tout ceux qui sont devant l'on déjà franchi. Ton rang est donc forcément au nombre de concurrents qui ont franchi la ligne (toi compris).

Citation:

---

Ton rang est donc forcément au nombre de concurrents qui ont franchi la ligne (toi compris).

---

Oui c'est ce que je disais il faut que je compte le nombre de concurrents ayant déjà franchi le checkpoint, c'est ce que j'aimerai éviter dans un soucis d'optimisation (peut etre que je chipote un peu).

Ca me fait penser que si je crée également un tableau contenant pour chaque checkpoint le nombre de joueurs l'ayant franchi je n'ai pas besoin de reconmpter à chaque fois qu'un concurrent en passe un !



Donc pour résumer voila la procédure:
-création d'un tableau (A) de nConcurrent contenant la position des concurrents au départ
-création d'un tableau (B) de nConcurrent contenant le numéro des concurrent dans l'ordre de départ
-création d'un tableau (C) de nCheckpoint contenant le nombre de concurrents ayant franchi chaque checkpoint

-a chaque franchissement on ajoute 1 au tableau C pour le checkpoint franchi ce qui nous donne directement la position du concurrent
-si le concurrent change de position on récupère le concurrent dont il prend la place dans le tableau B pour inverser
-on stocke les nouvelles positions dans le tableau A

Je ne pense pas m'etre trompé.

Merci

Je ne suis pas sûr que tu m'aies bien lu.

Citation:

---

Envoyé par supergrey

Oui c'est ce que je disais il faut que je compte le nombre de concurrents ayant déjà franchi le checkpoint, c'est ce que j'aimerai éviter dans un soucis d'optimisation (peut etre que je chipote un peu).

---

Non. Je disais que ta propre position dans la course est forcément égale au nombre de personnes ayant franchi le point au moment où te le franchis toi-même. Il n'y a donc aucun calcul à faire.

Citation:

---

Ca me fait penser que si je crée également un tableau contenant pour chaque checkpoint le nombre de joueurs l'ayant franchi je n'ai pas besoin de reconmpter à chaque fois qu'un concurrent en passe un !

---

Citation:

---

Donc pour résumer voila la procédure:
-création d'un tableau (A) de nConcurrent contenant la position des concurrents au départ
-création d'un tableau (B) de nConcurrent contenant le numéro des concurrent dans l'ordre de départ
-création d'un tableau (C) de nCheckpoint contenant le nombre de concurrents ayant franchi chaque checkpoint

---

Là encore, tu t'embêtes pour franchement pas grand chose.

Même en prenant le cas le plus complet, c'est-à-dire le cas d'un circuit à plusieurs checkpoints, chacun d'eux pouvant être franchi une fois par tour, il suffit de compter pour chaque concurrent, le nombre de checkpoints qu'il a franchi jusqu'ici en faisant un +1 à chaque fois qu'il en franchit un.

Le nombre de checkpoints franchis est égal au numéro du dernier franchi. Dans le cas d'un circuit, il suffit de faire un modulo n sur ce nombre pour le retrouver.

Citation:

---

Non. Je disais que ta propre position dans la course est forcément égale au nombre de personnes ayant franchi le point au moment où te le franchis toi-même. Il n'y a donc aucun calcul à faire.

---

Ben oui on est d'accord il faut donc soit compter le nombre de personne qui l'ont franchit soit faire un tableau (le tableau C que je propose).

Pour le reste j'ai beau relire ce que tu dis je ne vois pas comment faire autrement, sans mes 3 tableaux il ne me semble pas possible d'éviter une fois de temps en temps un parcours de tous les checkpoint ou tous les joueurs pour déterminer le classement...

L'idée est de « garder sa chambre bien rangée » :-) Il faut classer les données en temps réel à chaque fois qu'un changement se produit.

Tu fais un seul tableau de joueurs. Le type des éléments de ce tableau est une structure contenant deux éléments :

• Le numéro de dossard du joueur (et encore, c'est limite optionnel) ;
• Le nombre de checkpoints qu'il a franchi.

C'est la position dans ce tableau qui définit le rang de chaque joueur dans la course. Lorsqu'un joueur dépasse un autre, c'est qu'il étaient déjà forcément consécutifs. Il suffit de permuter les deux cases adjacentes du tableau pour mettre à jour automatiquement les rangs de tes concurrents.

Chaque joueur conserve une référence sur l'élément qui lui est propre, soit en utilisant un tableau de pointeurs ci-dessus si tu programmes en C, soit directement avec une référence si tu codes en Java. Cette liste de langage est non-exhaustive, naturellement.

Chaque fois qu'un joueur franchit un checkpoint, il incrémente son propre compteur. Tu n'as même pas à parcourir le tableau pour cela : le joueur possède sa propre référence et si ce n'est pas le cas, si tu connais quand même son rang, tu peux t'en servir comme indice de tableau.

De cette manière, tu n'as pas besoin des checkpoints pour connaître le rang de tes joueurs. Le tableau étant automatiquement trié et le restant tout au long du jeu, il suffit de le lire dans l'ordre et de t'arrêter au joueur qui t'intéresse pour connaître tous les joueurs qui sont devant.

Le problème qu'il s'agit d'un jeu en 3d et que déterminer qu'un joueur "dépasse un autre joueur" serait trop complexe à calculer. Je pourrais me dire qu'au moment ou il franchis un checkpoint je regarde celui devant lui dans le classement et celui derrière lui pour savoir si il a doublé ou été doublé mais il peut très bien avoir doublé 2 personnes (ou plus) entre 2 checkpoints.
Je comprends à peu près la méthode que tu proposes mais finalement si je compte tu utilises un tableau de structure à 2 éléments et un tableau de pointeur, je crois que c'est équivalent à mes 3 tableaux, après je vais effectivement peut etre utiliser une structure et des pointeurs pour simplifier mais le compte est bon.

Citation:

---

Envoyé par supergrey

Je comprends à peu près la méthode que tu proposes mais finalement si je compte tu utilises un tableau de structure à 2 éléments et un tableau de pointeur, je crois que c'est équivalent à mes 3 tableaux, après je vais effectivement peut etre utiliser une structure et des pointeurs pour simplifier mais le compte est bon.

---

Non, ce n'est pas ce que j'ai dit.

J'ai dit que tu peux − et devrait − utiliser une approche objet pour décrire tes joueurs mais ce n'est pas une obligation. Tu peux ne conserver que le nombres de checkpoints franchis et faire par conséquent un tableau d'entiers ordinaires, plutôt que de structures. Je n'utilise qu'un seul tableau. L'utilisation de pointeurs dans ce tableau ne relève que de l'implémentation.

Tu utilises donc une approche « par cantons », comme pour les trains, pour classer tes joueurs, mais le principe est le même. Tu démarres avec un tableau de joueurs triés selon leur rang. Chaque fois qu'un joueur franchit un checkpoint, tu examines la case juste avant la sienne et si le compte de checkpoints franchis est inférieur au sien, tu permutes les cases et tu recommences. De cette manière, tu ne fais les comptes qu'au moment où quelque chose change et, à ce moment, tu ne passes en revue que les quelques joueurs qui sont immédiatement devant, pas l'ensemble des concurrents.

Ensuite, pour faire un état de la course à un moment donné, il te suffit de parcourir linéairement le tableau en une seule fois, du début à la fin, sans faire aucun calcul.

Je ne vais pas revenir sur l'utilisation de pointeur et de structure qui sont je suis d'accord préférentielles, mais qui ne change rien au principe global de l'algorythme de classement que je recherche.

Mais je comprends ce que tu dis par rapport au fait qu'un joueur peut doubler plusieurs personne d'un coup, il suffit effectivement de faire une boucle tant qu'il a un joueur devant lui avec moins de checkpoints franchis.
On a finalement 2 tableaux: 1 tableau d'entier représentant pour chaque joueur sa position et un tableau d'entier représentant le nombre de checkpoint franchis pour chaque joueur et classé du 1er au dernier.
Ainsi lorsqu'un joueur franchis un checkpoint on a sa position dans le premier tableau on incrémente donc son nombre de checkpoint, on le fait remonter dans le classement avec un bouclage (au besoin) et on met à jour sa position.

Je pense que je suis bon ?

Citation:

---

Envoyé par supergrey

Je ne vais pas revenir sur l'utilisation de pointeur et de structure qui sont je suis d'accord préférentielles, mais qui ne change rien au principe global de l'algorythme de classement que je recherche.

---

Si. Ça change tout (ou presque). Cela t'évite d'avoir à maintenir en parallèle plusieurs tableaux différents, ce qui est en soi une forme de redondance. Et ça te permet de faire évoluer ton programme sans remettre en cause ce que tu as déjà écrit.

Citation:

---

On a finalement 2 tableaux: 1 tableau d'entier représentant pour chaque joueur sa position et un tableau d'entier représentant le nombre de checkpoint franchis pour chaque joueur et classé du 1er au dernier.

---

Non, il n'y a qu'un seul tableau, pour la bonne raison que si tu connais le nombre de checkpoints par chaque joueur, alors tu connais forcément leur classement. Tu n'as pas besoin de sauver celui-ci de manière explicite dans un second tableau. À la place, tu maintiens trié le premier. C'est alors la place de chaque joueur dans le tableau qui te donne son classement dans la course. Exemple :

Code:

---

1 2 3 4 5 6

+---------------+---------------+---------------+---------------+----- | Bob | Tom | Sam | Joe | … | | | | | | 9 | 6 | 3 | 2 | … | checkpoints | checkpoints | checkpoints | checkpoints | … +---------------+---------------+---------------+---------------+-----

---

Ce tableau étant trié, et le restant au cours du temps puisque que tu le mets à jour à chaque checkpoint franchi, alors on voit très bien que :

• Bob occupe la première case et est donc le premier du classement ;
• Tom occupe la deuxième case et est donc le deuxième du classement ;
• Sam occupe la troisième case et est donc le troisième du classement ;
• Joe occupe la quatrième case et est donc le quatrième du classement.

Citation:

---

alors on voit très bien que

---

Oui mais que fais ton cerveau si je te demande la position de Sam par exemple, il regarde la premiere case, puis la deuxieme, puis arrive enfin sur la bonne case, il faut donc bien parcourir avec cette méthode...

Citation:

---

Envoyé par supergrey

Oui mais que fais ton cerveau si je te demande la position de Sam par exemple, il regarde la premiere case, puis la deuxieme, puis arrive enfin sur la bonne case, il faut donc bien parcourir avec cette méthode...

---

Si tu relis plus haut, tu verras que chaque joueur est censé conserver sa propre référence vers l'objet qui l'intéresse. Et cette référence est généralement suffisante pour en déduire sa place dans le tableau, sans avoir à faire de boucle.

Si tu affiches un chart général de la course, tu n'as pas besoin de rechercher les joueurs. Tu transmets le contenu du tableau entier.

Enfin, si tu veux obtenir les informations d'un joueur particulier, tu es de toutes façons obligé de le rechercher à la main puisqu'il n'y a pas de relation d'ordre a priori entre les différents joueurs (au départ, ils se valent tous). Donc faire une recherche dans ce tableau où dans un autre revient au même.

Tu peux cependant faire un index ou une table de hachage si tu veux faire une recherche sur des critères particuliers, mais cela n'a de sens que si tu as vraiment beaucoup de joueurs. Autrement, le coût en ressources (mémoire et temps de calcul), même minime, sera supérieur à ce que tu gagneras au moment de la consultation.

Je préfère avoir une référence vers le classemeent du coté du tableau des joueurs et une référence vers les joueurs du coté de tableau de classement comme ça je n'ai jamais besoin de parcourir toute une liste et sachant que mon tableau de joueur est en fait une grosse structure avec plein de variable il peut m'etre utile d'avoir acces à une de ces variable.

Aussi pendant le jeu je ne peux pas envoyer tout le classement d'un coup je n'envoi donc que le nombre de checkpoint franchis au moment ou un checkpoint est franchi, il peut y avoir un décalage entre les client et le serveur mais ca ne se joue que sur quelques dixièmes de secondes et à la fin j'envoi le classemeent serveur.

Merci pour toutes ses explications, à ta place j'aurais abandonnée avant.