Devblog : améliorations 2.11 de la recherche en jeu

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 :

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 :

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 ici :) 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 :

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 :

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 :

Nous avons :

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 :

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.