Classements des joueurs

[php_addict]

bonjour

je vais entreprendre le codage du classement des joueurs de mon projet. j'ai bien fais une recherche sur le forum mais sans réellement avoir trouvé mon bonheur.

je me pose pas mal de questions....

dans le cas d'un nombre important de joueurs (ne me demandez pas combien j'en sais rien ) :

quelle stratégie adopter?

- mettre un champs "classement" dans la table joueur ?
- ou alors faire une table classement ?

deuxième point: classer les résultats de la table joueur ou de la table classement...

vaut t il mieux utiliser un système de cache de fichier ?
ou trier la table à la volée?

dans le cas d'un cache de résultats: à quels problèmes risque je d'être confronté?

merci de m'avoir lu...

bonne fin d'apres midi

[Sephi-Chan]

Tout dépend de tes critères de tri. Est ce que tu donnes des points à un joueur au moment où il effectue les actions ?

Si ton jeu se déroule en parties, est-ce que tu veux garder un historique des anciennes parties (le problème est le même pour un jeu où un joueur peut jouer plusieurs parties en parallèle), etc.

En gros, ta question est trop vague pour pouvoir y répondre comme ça.


Sephi-Chan

[Foxglove]

D'autres questions :
- A quelle fréquence les classements sont consultés ?
- A quelle fréquence les classements changent (c'est presque la même question que Sephi-chan) ?
- Affiches-tu le classement complet (ce qui est probablement pénible quand tu as beaucoup de joueurs) ou une partie du classement ?

[php_addict]

Tout dépend de tes critères de tri. Est ce que tu donnes des points à un joueur au moment où il effectue les actions ?

des points seront attribués à chaque resolution d'action (attaque, etc...)

est-ce que tu veux garder un historique des anciennes parties

toutes les actions à resoudre des joueurs sont loggées dans une table en attendant leur resolution,et une fois resolues les entrées ne sont pas effacées (log des actions resolues)

- A quelle fréquence les classements sont consultés ?

aucune idée pour le moment, mais il se peut que les classements soit souvent consultés (en accès libre donc)

- A quelle fréquence les classements changent (c'est presque la même question que Sephi-chan) ?

très souvent, à chaque resolution d'action

- Affiches-tu le classement complet (ce qui est probablement pénible quand tu as beaucoup de joueurs) ou une partie du classement ?

une partie du classement, par exemple:
- les 20 resultats autours de la position du joueur dans le classement
- et possibilité de voir le haut du classement, le bas, etc...
- il y aura donc plusieurs page de resultats (10 ou 20 par pages...à definir + tard...

classer des resultat de requete n'est pas un probleme, mais c'est le volume à classer et la frequence de classement qui m'inquietent...

merci de vous pencher sur mon cas

[Foxglove]

La solution que tu recherches doit-elle être une solution SQL ou pas ? Est-ce que tu veux que ça soit ton SGBD qui se débrouille avec le tri, ou bien PHP ?

Si tu privilégies PHP, tu peux t'en sortir (même sur un gros volume de données) avec des hashtables (ou des tables SQL), des tableaux triés (par PHP) et des recherches dichotomiques. Je ne pense pas que tu aies besoin de structures plus complexes que des tableaux triés pour le classement, car les classements vont être modifiés/consultés dans le désordre.

Si tu privilégies SQL, je passe mon tour

J'attends ta réponse pour détailler davantage (si besoin).

[php_addict]

Si tu privilégies PHP, tu peux t'en sortir (même sur un gros volume de données) avec des hashtables (ou des tables SQL), des tableaux triés (par PHP) et des recherches dichotomiques. Je ne pense pas que tu aies besoin de structures plus complexes que des tableaux triés pour le classement, car les classements vont être modifiés/consultés dans le désordre.

j'avoue que je ne connais pas les concepts dont tu parles: hashtables et recherches dichotomiques...

effectivement je pensais à une solution MySQL du genre SELECT, ORDER et LIMIT .

[Foxglove]

hashtables

Dans un tableau tu associes une valeur à chaque index. t[0] vaut "a", t[1] vaut "b", t[2] vaut "c". Si tu veux rechercher un élément, tu dois parcourir toutes tes cases.

Dans une hashtable, tu associes une valeur à un hash, c'est-à-dire à une clé. Par exemple, tu peux dire qu'il y a deux clés : voyelles et consonnes. Si tu veux ajouter "a" dans ta hashtable, tu vas la mettre dans la case t[voyelle]. Si tu veux ajouter "b", tu le mets dans t[consonne]. Si tu veux ajouter "c", problème car il y a déjà quelqu'un dans t[consonne]... La solution utilisée par les hashtables est de pouvoir mettre plusieurs éléments dans une même case. On a donc :
t[voyelle] = {a, e, i, o, u}
t[consonne] = {b, c, d, f, g, ...}

A quoi ça sert ? Toute à l'heure, pour chercher une lettre dans un tableau, tu devais examiner toutes les cases. Maintenant, pour rechercher une lettre dans une hashtable, tu dois juste regarder t[voyelle] (donc 5 cases) si la lettre recherchée est une voyelle, et t[consonne] (donc 21 cases) si c'est une consonne.

En suivant ce principe, j'imagineais le truc suivant dans ton cas. Je suppose que tu as pleins de joueurs différents, disons 100 000. Les classements vont de 0 à 20 000 par exemple. Je découpe les classements en "paquets" de 1000, ça me fait 20 paquets. Le premier paquet c'est les classemets de 0 à 999, le deuxième de 1000 à 1999, etc.

Si je veux connaître les 20 classements autour d'un joueur donné, je regarde son score : 3375 par exemple. Je prend le quatrième paquet (contenant les scores de 3000 à 3999), je trie ce paquet, et je prend les 20 classements qui m'intéressent. J'aurais pas à trier 100 000 valeurs, à moins que les 100 000 joueurs aient un classement compris entre 3000 et 3999... En fait, j'espère que les classements sont bien répartis, et dans ce cas j'aurais que 5000 valeurs à trier (et si c'est toujours trop, j'ai qu'à faire plus de 200 paquets au lieu de 20 paquets).

Bon, il peut arriver que le paquet que je considère ne contienne pas tous les classements voulus. Ca arrive si le joueur a 3000 pile par exemple. Il faut que j'aille chercher des valeurs dans le paquets du dessous. Bon, mais c'est pas très grave, l'intérêt est que tu sais à peu près où sont les valeurs que tu recherches sans avoir à tout parcourir.

recherches dichotomiques

La recherche dichotomique, ça sert à retrouver rapidement une valeur dans un tableau trié.

Je reprends l'exemple de tout à l'heure. J'ai un paquet avec 5000 scores. Je sais que le joueur a 3375. S'il faut que je parcoure les 5000 scores pour trouver le score du joueur, c'est dommage, ça me fait perdre du temps (ok, trier ça m'a fait perdre plus de temps, mais une fois qu'on a trié, on va garder le tableau trié, on va pas le retrier à chaque fois non plus).

La recherche dichotomique, c'est comme quand tu recherches un nom dans l'annuaire. Tu fais pas les pages une par une dans l'ordre. Tu ouvres à peu près au milieu, tu regardes si tu es trop loin ou pas assez loin, et tu recommences.

Sur un dictionnaire de 100 000 pages, tu peux retrouver n'importe quel nom en regardant au plus 17 pages. C'est super efficace.

J'espère que c'est plus clair ?

Maintenant, c'est pas forcément la méthode la plus efficace de refaire ce genre de trucs en PHP. Ton SGBD fait lui aussi des opérations super efficaces lui aussi. Il fait pas ses recherches n'importe comment, et il a des méthodes très rapides pour trier, etc. Maintenant, elles sont pas forcément adaptées à tes données (à leur fréquence de changement, à l'intervalle de valeurs, etc), et il faut bien le connaître pour savoir s'il va supporter la charge. A mon avis, tant que tu as moins de 10000 valeurs, n'importe quelle méthode (même une mauvaise) marchera sans problème.

[Sephi-Chan]

Les Hashtable (souvent appelés hash) sont ce qu'on appelle parfois des tableau associatif, en opposition aux tableaux indexés.

$sword = array('attack' => 10, 'defense' => 0); // PHP

sword  = { :attack => 10, :defense => 0 }       // Ruby

sword  = { attack: 10, defense: 0 };            // Javascript, et oui, c'est un objet !

Sephi-Chan

[Foxglove]

Je me permets d'ouvrir une petite parenthèse philosophique.

Le nom de tableau associatif m'embête un peu. Il est souvent utilisé pour hashtable, mais bon... Un tableau associatif, c'est comme un tableau sauf que les clés ne sont pas forcément des entiers, mais peuvent être n'importe quoi. C'est bien ça non ? On associe une clé à une valeur. En tout cas, c'est la manière dont je le comprends.

Avec cette définition, on masque la notion de "hash". On a l'impression que dans chaque case, on n'a qu'une seule valeur. Dans la case "attaque", j'ai la valeur 10. Dans la case "défense", j'ai la valeur 0.

Je crois que c'est un abus de langage, et qu'il vient du fait que les tableaux associatifs sont implémentés grâce à des hashtables. Comment permettre à n'importe quel truc d'être une clé ? En transformant cette clé en un entier (grâce à un "hash"), et en utilisant un tableau normal.

J'utiliserais plutôt "table de hachage" s'il fallait franciser.

Je m'excuse pour cette parenthèse philosophique, mais comme il est minuit, je me suis dit que je pouvais philosopher

PS : Ca m'embête d'autant plus qu'en Perl ils ont fait l'abus... Les tableaux associatifs sont représentés par "%", qui ressemble à un "H" (selon l'inventeur du Perl). Bon, si même Perl est contre moins, c'est que c'est peut-être juste dans ma tête tout ça

[niahoo]

effectivement je pensais à une solution MySQL du genre SELECT, ORDER et LIMIT .

honnêtement, je pense que faire confiance au SGBD pour ça est la meilleure solution. Il sera bien plus rapide pour faire des tris que PHP (mais je peux me tromper).

Tu peux par exemple lancer chaque requête de classement toutes les 10 minutes. Si t'as 10 requêtes, t'en fais une par minute pour pas tout balancer en même temps, avec un cron et tu stockes ça dans un cache. Ici, ne pas oublier d'afficher aux joueurs la date/heure de mise à jour des données pour pas qu'il s'étonne que son classement n'ait pas bougé après une super action de ouf etc..

Et pour les requêtes centrées autour d'un joueur, du genre "les 10 devant moi, les 10 derriere", ben pareil, celle là tu la lance quand le joueur demande, mais tu le limites avec un cache de x minutes.