[Devblog] Améliorations de la recherche en jeu

Répondre
Partager Rechercher
Améliorations 2.11 de la recherche en jeu (Source)

La recherche d’informations en jeu dans DOFUS n’a jamais vraiment été exploitée, peu de fonctionnalités proposaient d’en faire, les performances n’étaient donc pas un souci. Cependant, avec l’arrivée des Succès puis du Bestiaire, nous avons voulu vous offrir un outil de recherche rapide et performant vous permettant de retrouver les informations facilement.

Alors pour l’occasion, voici un article plus technique que d’habitude pour vous présenter cette nouvelle recherche !

Conditions des tests

Les relevés de performances sont effectués sur une machine ayant la configuration suivante :

  • Dual Core™ 64 Bits @ 3.00 Ghz
  • 4 Go RAM (DDR2 400 MHz)
  • Western Digital Caviar Black 500 Go
  • Windows 7 64 bits
  • Air 2.6, release mode
Pourquoi la recherche est lente

Jusqu’à la version 2.10, les recherches étaient effectuée en « brute force », c’est-à-dire en testant toutes les données. Cela ne pose pas forcement de problème si les données sont déjà en mémoire et si elles ne sont pas trop nombreuses (2 000 données différentes par exemple).

Dans l’interface de Succès mise en ligne en décembre, la recherche couvre le nom des succès et sa description. Bien, mais pas top. Typiquement, je suis certain que beaucoup de joueurs aimeraient savoir comment obtenir un Ambre du Tynril via les succès (si si). C’est pourquoi dans la version 2.11, Sili a rajouté la recherche sur les récompenses (titres, ornements et objets) ainsi que sur les objectifs.

Problèmes :

  1. Cela implique de rechercher dans des données qui ne sont pas présentes en mémoire.
  2. Par plus de commodité, on ne recherche pas un terme exact complet mais généralement une partie d’un terme (« Ambre » par exemple) : cela implique qu’il faudra rechercher parmi toutes les récompenses les objets ayant « Ambre » dans leurs noms.
Un rapide calcul, il y a 803 Succès donnant 567 objets en récompenses et 2246 objectifs de succès, soit pour le client DOFUS :

rercherche1.jpg

Un peu plus d’une seconde pour faire une recherche est déjà relativement long, d’autant que durant la recherche le client est complétements bloqué. On pourrait envisager de découper la recherche en plusieurs parties pour éviter de bloquer le client complétement mais on allongerait alors les temps de recherche.

On ne parle ici que de la recherche pour les Succès. Dans la nouvelle interface de Bestiaire les recherches sont plus complexes puisqu’on sonde les drops de tous les monstres ainsi que leurs noms en prenant en compte les drops sujets à conditions (objets de quête par exemple).

La recherche par « brute force » montrait ainsi ses limites, il fallait donc trouver un système plus rapide, moins coûteux en mémoire, plus beau, un truc de pgm (on m’indique que pgm est has-been, je me fais vieux).

Structure des fichiers de données

Les données du jeu sont stockées dans des fichiers binaires (entendre par là que ce ne sont pas des fichiers textes comme par exemple le format Xml ou Json). Nous allons nous intéresser à deux des types de fichiers de données de DOFUS :

  • Les données de jeu (les Objets, les Monstres, etc.)
  • Les données de langues (traductions)
Ces deux types de données sont dissociés afin d’éviter de devoir mettre à jour les fichiers de données de jeu lorsqu’un texte est modifié, cela accélère les temps de téléchargement.

Note aux curieux : Les formats de données décrits en dessous sont simplifiés : ils omettent certaines parties et l’ordre des blocs ne correspond pas forcément à la réalité.

Données de jeu

Ils sont composés de deux parties :

rercherche2.jpg
La partie Index permet de savoir où se trouve une donnée dans le fichier, cette partie est chargée dès le lancement du jeu.

La partie Définition indique comment sont stockées les données, par exemple pour pouvoir dé-sérialiser (autrement dit lire, plus d’informations icismile.gif un Objet, nous avons besoin de savoir que chaque donnée va contenir un identifiant unique, un nom, un niveau, etc.

La dernière partie contient toutes les données sérialisées les unes à la suite des autres.

Lorsqu’on souhaite accéder à une donnée en particulier, on regarde dans l’index où elle se trouve, puis on va dans la dernière partie pour la dé-sérialiser.



Données de texte

Comme indiqué un peu plus haut, les données textes qui nécessitent d’être traduites sont séparées des données de jeu. Les données de jeu font simplement références aux textes via un identifiant numérique. En contrepartie de la souplesse du système, l’accès aux données textes est plus lent car il faut lire deux fichiers (données de jeu + données textes).

Le fichier des textes est ordonné de la façon suivante :

recherche3.jpg
La partie Index permet de savoir où se trouve une donnée dans le fichier, cette partie est chargée dès le lancement du jeu.

La dernière partie contient toutes les données textes les unes à la suite des autres.

Pour accéder à un texte, comme pour les fichiers de données, on regarde simplement dans l’index où elle se trouve dans le fichier.

Principe

Pour accélérer la recherche, il ne faut plus avoir besoin de dé-sérialiser les données (ce qui implique de lire tous les champs) et il faut ordonner les données de façon différente. Mais puisque le jeu a toujours besoin d’accéder rapidement données, nous allons devoir ajouter de nouvelles parties dédiés à la recherche.

La structure des fichiers de données de jeu devient donc :

recherche4.jpg

Nous sommes partis du principe que les recherches ne se font que sur un seul champ de donnée (le niveau d’un objet par exemple) : cette approche nous permet d’optimiser la structure du fichier. Si on souhaite faire une recherche multicritère, on lancera simplement plusieurs recherches.

Prenons par exemple un objet avec les champs suivants : nom, niveau et type (arme, bouclier, etc.). Puisque nous souhaitons effectuer une recherche que sur un seul champ nous n’avons pas besoin des autres. Donc nous avons ajouté un bloc de donnée par champ :

Au lieu d’avoir :

recherche5.jpg


Nous avons :

recherche6.jpg

Chaque champ a son propre bloc de données, qui contient les valeurs possibles pour ce champ et les objets qui ont cette valeur.

On remarquera deux choses dans cette nouvelles façon d’organiser les données :

  • Lorsque plusieurs objets ont la même valeur pour un champ donné, ils sont regroupés
  • Les valeurs sont triées par ordre décroissant
Cette nouvelle façon d’organiser les données permet de faire des recherches sans pour autant avoir besoin de lire tous les champs d’une donnée, ce qui permet un gain de temps considérable.

Il faut ensuite distinguer deux types de recherche :

La recherche d’une valeur en particulier

Exemple : trouver les objets de niveau 29

C’est le cas le plus simple et le plus rapide. On peut optimiser la recherche car nous n’avons pas besoin de parcourir toutes les valeurs possibles. Une fois la valeur trouvée, on peut arrêter de chercher. Dans un tel cas de figure, il est possible d’utiliser des algorithmes de recherche tels que la recherche dichotomique puisque les données sont rangées dans l’ordre.


La recherche d’une chaine de caractères


Exemple : trouver les Objets dont le nom contient un « e »

Dans l’exemple illustré plus haut, il faudra trouver « Cuivre », « Ecaliseur » et « Pain doré »

C’est là que les ennuies reviennent pour deux raisons :

  • Il faut parcourir toutes les valeurs de textes puisqu’on ne recherche pas une valeur précise : cela rend la recherche plus longue.
  • Il ne faut tenir compte ni des accents ni des majuscules : les majuscules ne posent pas de soucis car Flash sait les gérer nativement. Il n’en est pas de même avec les accents, il faut le coder soi-même.
De prime abord, coder la non prise en compte des accents peut sembler relativement trivial mais en réalité avec nos contraintes (traiter des milliers de chaines de caractères) cela ralenti très fortement la recherche.

Après avoir tenté plusieurs approches, la seule solution viable est de préparer les textes sans accents à Ankama et donc de dupliquer tous les textes avec accents (a titre d’information, sur les 80 000 textes français utilisés par Dofus, plus de 40 000 contiennent des accents).

Cela peut sembler aberrant mais dans la mesure où tous les fichiers sont ensuite compressés pour l’updater, cet ajout ne représente qu’un méga en plus et fait gagner de précieuses millisecondes aux joueur (et « le temps, c’est des kamas » comme me le répète mon dopeul Enu avant de mourir).

Coût

Et tout cela pour la modique somme de 5,8 Mo en plus à téléchargé par rapport à la version 2.10, en comprenant les données de jeu et de textes.

Résultat

Si on reprend le tableau du début :

recherche7.jpg

Soit un gain de 4300%, c’est-à-dire une amélioration non négligeable.

En réalité, les interfaces ne réagiront pas aussi vite à vos recherches, car une fois que les données qui correspondes à vos critères sont trouvées, il faudra quand même dé-sérialiser les données et les charger en mémoire. Mais malgré cela les temps de réponse seront bien meilleurs qu’avant la version 2.11

On arrive à la fin de cet article, si vous lisez ces lignes, trois cas, soit je vous ai perdu en route et vous avez sauté à la fin, soit comme moi vous aimez tenter de résoudre ce genre de problème.




J'aime ce genre d'articles, vive la transparence

Dernière modification par Lifescythe ; 29/04/2013 à 19h56.
*Je pensais qu'ils allaient annoncer une amélioration de la Recherche de Groupe *

J'ai pas tout lu, mais question communication ça fait plaisir.
C'est vrai que la recherche prend son temps parfois.

Ça serait bien s'ils pouvaient détailler d'autres sujets autant que celui-ci (surtout ceux jugés plus important par la communauté).
[mylife]
Aha c'est rigolo, notre prof de Visual Basic nous a demandé de faire exactement la même chose pour améliorer nos structures de données y a une semaine :

"Bande de p'tits cons, vous faites n'importe quoi ! Utilisez plusieurs tableaux de données plutôt qu'un tableau de structures !" "Vous vous foutez du monde ! Vous avez déjà tout oublié de ce que je vous ai appris ! Sinon, reparlons de ma femme..."
[/mylife]

Très intéressant sinon, merci des infos.
C'est toujours interessant de comprendre la réflexion et les moyens mis en oeuvre pour aboutir à un resultat.

La plupart des gens critiquent lorsqu'ils n'aiment pas une Maj, ou quand il y a des Bugs. Et ils estiment long de devoir attendre 2 ou 3 mois... alors qu'ils ne savent strictement rien du temps que prend un developpement, les recherches, etc.

Si Ankama communiquerait plus sur ses processus, il y aurait surement moins de discours stupide de la part des joueurs à chaque annonce de MaJ. Et ça eviterait surement toute les niaiseries comme la pétition qui a été faite.

edit: c'est le stagiaire qui s'est amusé ^o^ à 420 euros par mois yabon
J'ai pas compris énormément sur le principe, mais juste les grandes lignes. C'est sympathique.

Par contre je comprend pas trop l'intéret de communiquer la dessus. . Non je rale pas, je vois pas ce qu'ils essayent de dire derrière a part "on a divisé par 43 le temps de recherche pour 6Mo de fichiers a télécharger en plus".

Puis sinon j'espère que vous vous etes pas tapés a la main les textes sans accents . Si vous voulez un p'tit programme pour tout mettre sans accent, cherchez sur le net.
C'est vraiment chouette ce genre de petit plus !

Un que j'attends depuis longtemps par contre, c'est d'améliorer le transfert des ressources en banque... Question lag on est pas mal aussi...
Bon, en gros, ils nous expliquent que les structures de données adaptées a ce qu'on veut en faire, c'est bien. Bref, ils ont récemment embauche un jeune qui a fait des études propres d'informatique, et pas "seulement" (dit sans aucune animosité) d'infographie.

Bref, ça fait plaisir de voir que, parfois, les trucs qu'on se tue a dire a nos étudiants, ça peut servir
Citation :
Publié par feuby
Par contre je comprend pas trop l'intéret de communiquer la dessus. . Non je rale pas, je vois pas ce qu'ils essayent de dire derrière a part "on a divisé par 43 le temps de recherche pour 6Mo de fichiers a télécharger en plus".
"Dis dis chef, mon truc sur la recherche, je peux faire un devblog dessus? hein? je peux?"

(Si y'avait pas eu de schémas incompréhensibles pour le commun des mortels, les réactions auraient été "voila bien la preuve que Dofus est programme avec les pieds tiens, s'ils sont capables de l'accélérer par un facteur 43... pompafric toussa toussa")
Citation :
Publié par ShosuroPhil
Bon, en gros, ils nous expliquent que les structures de données adaptées a ce qu'on veut en faire, c'est bien. Bref, ils ont récemment embauche un jeune qui a fait des études propres d'informatique, et pas "seulement" (dit sans aucune animosité) d'infographie.

Bref, ça fait plaisir de voir que, parfois, les trucs qu'on se tue a dire a nos étudiants, ça peut servir

J'ai tellement explosé de rire...

Surtout combiné a ton second message, ca fait un peu "programmé avec les pieds" mais dit subtilement.
Citation :
Publié par ShosuroPhil
Bon, en gros, ils nous expliquent que les structures de données adaptées a ce qu'on veut en faire, c'est bien. Bref, ils ont récemment embauche un jeune qui a fait des études propres d'informatique, et pas "seulement" (dit sans aucune animosité) d'infographie.

Bref, ça fait plaisir de voir que, parfois, les trucs qu'on se tue a dire a nos étudiants, ça peut servir
Cela fait tellement longtemps que les joueurs ne se rappellent plus de mon pseudo pré-Ankama. Je ferais rectifier demain avec mon pseudo officiel, mais ça fait plaisir de se faire prendre pour un stagiaire x).
Citation :
Publié par MrFourbasse
Cela fait tellement longtemps que les joueurs ne se rappellent plus de mon pseudo pré-Ankama. Je ferais rectifier demain avec mon pseudo officiel, mais ça fait plaisir de se faire prendre pour un stagiaire x).
Quand j'ai lu son post, j'ai prié très fort pour que tu le vois
Citation :
Je ferais rectifier demain avec mon pseudo officiel, mais ça fait plaisir de se faire prendre pour un stagiaire x).
Ah ces srams toujours invisibles ^^.

C'est normal que je ne trouve pas de lordsotheuses ou de crache boulette lors de mes recherches ???

Tu as encore beaucoup de visites sur myavatar ?

Je veux des filtres de classement

Dernière modification par psonlu ; 29/04/2013 à 22h54.
Citation :
On arrive à la fin de cet article, si vous lisez ces lignes, trois cas, soit je vous ai perdu en route et vous avez sauté à la fin, soit comme moi vous aimez tenter de résoudre ce genre de problème.
y a que moi que ça perturbe?

sinon cool le message global du ticket, pour le contenu, c'est trop complexe pour moi, surtout à cette heure
Répondre

Connectés sur ce fil

 
1 connecté (0 membre et 1 invité) Afficher la liste détaillée des connectés