Le hack dans la recherche de chemin de StarCraft

La recherche du chemin des unités d'un jeu est une chose que les joueurs ne remarquent pas jusqu'à ce que cela ne marche plus de manière optimale, où même un souci mineur devient générateur de rage et un problème existentiel. Durant le développement de Starcraft, la recherche de chemin a plusieurs fois cessé de fonctionner.

Le développement de l'application traînait et il semblait qu'il n'allait jamais finir : le jeu était toujours à deux mois de sa sortie mais ne semblait jamais se rapprocher de sa mythique date de sortie. « Heureusement » - et j'utilise ce terme à bon escient - Blizzard avait de l'expérience à sortir des jeux en retard.

Bien que nous avions toujours eu des « objectifs » de date de sortie (« souhaits » serait sûrement un terme mieux adapté) nous essayions de ne pas les dévoiler publiquement à moins qu'il y avait une certitude que le jeu soit prêt au moment donné. La politique de Blizzard du « lorsque cela sera prêt » était vraiment un aveu dans la mesure où personne n'avait la moindre idée de quand nous l'aurions fini et que c'était un engagement de sortir des produits de qualité.

En tout état de cause, vers la fin du projet, nous avons eu une série de problèmes qui ont empêché le lancement du jeu. Comme pour tous les jeux lors des dernières étapes du développement, il y avait des anomalies à identifier et corriger. Le nombre de bogues identifiés était encore proche du millier.

La plupart de ces bogues étaient triviaux et ne demandaient que peu d'attention pour être corrigés. Dommage qu'ils n'étaient pas tous comme ça.

D'autres, comme un bogue au niveau de la synchronisation multijoueur, pouvaient survenir et demander une attention particulière de la part de plusieurs personnes dans l'équipe des programmeurs - quelquefois des semaines d'efforts pour un seul problème. D'autres développeurs de jeux ont reporté des expériences similaires avec des bogues de synchronisation. Ages of Empires et Supreme Commander.

Quelques bogues étaient liés au processus de développement lui-même. Le porte-nefs Protoss était souvent à la traîne derrière les autres unités, car il avait sa propre manière de faire… tout. À un moment donné le code du porte-nefs a été dérivé du code principal du jeu et a divergé au-delà de tout espoir de réintégration. En conséquence, à chaque fois qu'une nouvelle fonctionnalité était ajoutée aux unités, il fallait l'implémenter une seconde fois pour le porte-nefs. Et à chaque fois qu'un bogue était corrigé pour les autres unités, un autre similaire était également trouvé plus tard dans le code du porte-nefs, mais dans une version plus sournoise et difficile à corriger.

Mais le plus gros souci retenant Starcraft fut la recherche de chemin.

Ce n'était pas que la recherche de chemin ne fonctionnait pas du tout ; dans la plupart des cas cela marchait plutôt bien. Mais il y avait suffisamment d'anomalies pour rendre le jeu non délivrable.

Les unités du jeu pouvaient rester bloquées et s'arrêter sur le champ de bataille. Souvent, elles faisaient trop d'efforts pour trouver des chemins, avançant lentement ou bien tournant en boucle sans faire de progrès et parfois se retrouvant sur des bordures complètement bloquées. Des groupes entiers d'unités pouvaient se retrouver bloqués dans ce qui ressemblait à un voyage dans les métros en pleine après-midi.

Le problème était frustrant pour les joueurs, mais aussi rendait l'intelligence faible et en conséquence rendait impossible l'équilibrage des missions, ce qui, en plus, gâchait du temps consacré au design du jeu.

Bien que je n'ai jamais été un joueur de haut niveau, avant que le jeu ne sorte j'étais bon parce que j'avais découvert que les Goliaths étaient très puissants pour compenser leur pauvre capacité à trouver les chemins. Comme ils étaient plus larges que les autres unités terrestres ils avaient besoin de plus d'espace pour se déplacer et en positionnant astucieusement les Goliaths autour d'obstacles j'étais capable d'amener leur puissance de feu pour gérer des situations cruciales et vaincre des joueurs « macro » qui autrement m'auraient déchiré en lambeaux. Malheureusement mes compétences durèrent seulement un court moment jusqu'à ce que les Goliaths furent rééquilibrés. Soupir.

La recherche de chemin était difficile - bien qu'il y eut des algorithmes bien choisis pour diriger les unités, ils étaient handicapés par quelques mauvaises décisions faites au cours du projet.

Dans un ancien article de ce blog, j'ai fait allusion aux difficultés dans la recherche de chemin. Starcraft a été développé à partir du moteur de Warcraft, qui affiche les terrains à partir d'un moteur de tuiles optimisé pour dessiner des tuiles de 32 x 32 pixels constituées de seize carrés de 8 x 8 pixels. J'avais architecturé Warcraft de cette manière, car ça avait bien marché pour nos titres sur Super Nintendo et Genesis. Ces consoles de jeux avaient un support matériel pour dessiner des tuiles 8 x 8, mais le comportement était facile à émuler sur PC.

Comme le point de vue de la caméra de Warcraft I et II était presque une vue de haut en bas, les cotés des objets (forêts, terrain, bâtiments) du jeu étaient soit horizontaux, soit verticaux. Donc la représentation de moteur de rendu du monde comme une carte carrée de tuiles conduisait à des algorithmes simples de recherche de chemin. Dans ces jeux, chaque tuile de 32 x 32 pixels était traversable ou non. J'ai montré quelques bordures de tuiles traversables dans l'image ci-dessous en vert. Quelques-unes apparaissent traversables mais ne le sont pas ; en dessous vous pouvez voir que le dessin de la caserne ne remplit pas la zone 48 x 48 sur laquelle elle est placée, laissant deux tuiles apparemment traversables qui en fait ne le sont pas (en rouge).

Mais au milieu du projet, l'équipe des développeurs a changé Starcraft en vue isométrique pour rendre le jeu visuellement plus attractif (détails dans cet article). Mais le moteur de terrain n'a pas été réécrit pour utiliser des tuiles isométriques, seuls les artworks ont été redessinés.

Le nouveau point de vue de la caméra était un succès au niveau de l'apparence mais pour faire marcher correctement la recherche de chemin il était nécessaire d'augmenter la résolution de la carte des chemins : maintenant chaque tuile 8 x 8 était soit passable soit non passable, augmentant la taille de la carte des chemins d'un facteur 16. Tandis que cette résolution plus fine permettait un plus grand nombre d'unités sur la carte, cela signifiait également que la recherche de chemin sur la carte allait nécessiter davantage de temps de calcul pour parcourir le plus grand espace.

La recherche de chemin était maintenant plus compliquée, car les passages en diagonale dessinés dans les images découpaient les tuiles de manière inégale, rendant difficile de savoir si la tuile devait être traversable ou non. S'assurer que toutes les tuiles étaient correctement marquées demandait beaucoup d'efforts.

De plus, l'éditeur de carte de StarCraft était horriblement difficile à écrire à cause des nombreux cas particuliers provoqués par le découpage en diagonale de la carte de tuiles carrées. Écrire le correctif spécifique pour les tuiles a nécessité des mois de programmation.

Contrairement à Diablo, qui utilisait un moteur de rendu isométrique, l'équipe de développement a gardé l'ancien moteur bien que de nouveaux problèmes avec cette approche continuaient d'être découverts de semaine en semaine.

Cette image montre comment un pont était fait de tuiles 8 x 8 ; plusieurs sont montrées en vert. Le point de vue presque isométrique du modèle 2D se découpe de manière irrégulière à travers les tuiles, laissant les côtés du pont en forme d'escalier, comme vous pouvez voir au niveau de la ligne rouge qui découpe chaque tuile en formes irrégulières.

Comme le projet était toujours à deux mois de sa sortie, il était inconcevable de disposer de suffisamment de temps pour concevoir un nouveau moteur de terrain et rendre la recherche de chemin plus facile. Donc le code de la recherche de chemin devait fonctionner. Pour pouvoir gérer tous les cas particuliers, la recherche de chemin explosa en une gigantesque machine à états qui implémentait toutes sortes de hacks « sors-moi d'ici » spécialisés.

S'il y avait un problème majeur avec la recherche de chemin, c'était que les récolteurs (VCS Terran, drone Zerg et sonde Protoss) se retrouvaient bloqués en essayant de récolter des cristaux (renommés par la suite « minéraux ») et du gaz Vespene, et ils étaient paralysés. Lorsqu'un joueur était occupé à gérer une bataille ou à construire une base secondaire, les récolteurs de retour à la maison se bloquaient, arrêtant la récolte de minéraux. Lorsqu'ensuite le joueur s'en rendait compte, sa stratégie de construction était détruite due à un manque de ressources.

Le problème de base avec la récolte de ressources est que les joueurs veulent maximiser le nombre de récolteurs travaillant sur chacun des minéraux pour optimiser leurs revenus en ressources. Ces récolteurs se déplacent entre les minéraux et leur base donc ils rentrent constamment en collision avec les autres récolteurs se déplaçant dans des directions opposées. En mettant suffisamment de récolteurs dans un espace plutôt petit il est tout à fait possible que certains se retrouvent bloqués et incapables de bouger jusqu'à la récolte complète des minéraux.

Je m'étais porté volontaire ou bien on m'avait demandé de regarder de plus prêt le problème ; je ne me souviens plus après toutes ces années. Après avoir étudié intensivement le code de la recherche de chemin, il n'y avait pas moyen que je sois suffisamment intelligent pour simplement « résoudre le problème ». En conséquence j'ai mis en place un hack très moche.

Pendant que certains développeurs peuvent devenir obsédés à trouver la solution la plus pure, abstraite, propre et même sublime à un problème, il arrive des moments où des sacrifices doivent être faits. S'ils sont bien faits, personne ne remarque les compromis diaboliques qui ont été faits, comme c'est le cas des hacks compilés par Brandon Sheffield dans l'article Dirty Coding Tricks.

Mon idée était simple : à chaque fois que des récolteurs se déplacent pour récolter ou ramener des ressources, ils ignorent les collisions avec les autres récolteurs dans la même situation autres unités. En éliminant les collisions entre les unités pour les récolteurs, ils ne se retrouvent plus bloqués lorsqu'ils sont nombreux et ils peuvent travailler efficacement.

Il est possible d'observer ce comportement en sélectionnant un groupe de récolteurs qui récoltent des cristaux et de lui dire de s'arrêter. Ils vont alors immédiatement se répartir pour trouver des tuiles non occupées.

Ce comportement est évident si vous faites attention, mais généralement, il passe inaperçu, ça ne surprend pas, bien que des joueurs professionnels et créateurs de cartes s'en rendent compte.

En gros, ça marche, ce qui est l'un des meilleurs types de hack.

Alors qu'il restait encore beaucoup de travail pour finir le jeu, ce hack était ce qui nous a permis de lancer le jeu sans passer un temps phénoménal à récrire une grande partie du code.

L'équipe de développement était capable de contourner quelques autres problèmes dans la recherche de chemin et de simplement ignorer le reste, bien que le Dragon Protoss en particulier a fini avec une mauvaise réputation, car, étant la plus grosse unité terrestre, il échouait également fréquemment à trouver son chemin correctement.

Le résultat final fut que la recherche de chemin était suffisamment fonctionnelle, et on a tous appris une leçon difficile à propos des espoirs et des souhaits comme outils de planification.

Merci à Patrick Wyatt de nous avoir permis de traduire son article que vous pouvez consulter en version originale sur son site.

Merci à LittleWhite pour sa relecture et àWinjerome et f-leb pour leur correction orthographique.