Un pavé sur les pavages

Hello world.

Aujourd’hui, parlons de pavages ! Plus précisément, parlons de tout le travail qui a abouti aux pavages tels qu’ils sont actuellement implémentés et utilisés dans ma MML, ma petite bibliothèque mathématique, et dans Stream, mon projet de Tower Defense. L’idée de départ, les contraintes d’implementation, les applications dans le jeu, les bugs rencontrés, les solutions envisagées… Le tout en respectant l’ordre chronologique de développement.

Cet article a plusieurs buts. Bien sûr, le but principal est de présenter un peu ce que je fais, de parler du travail réalisé avec plus de détails que je n’ai pris le temps de le faire jusqu’ici. C’est aussi, pour ceux que ça intéresse, une invitation à regarder l’envers du décor. Enfin, c’est aussi pour moi l’occasion de prendre un peu de recul sur tout le travail effectué.

Au commencement, il y eut le carré

Car non, tout ne commença pas à Mænder Alkoor.

Un jour, il y a quelques mois, en réfléchissant à Stream, il m’est venu l’idée d’utiliser des pavages plus complexes que le trop classique pavage carré usuel. J’avais en tête d’essayer de voir ce que pouvaient donner des pavages hexagonaux ou triangulaires pour un Tower Defense. À l’époque, je n’avais même pas encore commencé à travailler sur ma MML, Stream n’était encore qu’une idée en l’air… Du coup, Avant de commencer à coder quoi que ce soit, documentation et réflexion. Direction Wikipédia, chapitre pavages réguliers et semi-réguliers.

Et là, j’ai découvert plein de chouettes pavages semi-réguliers dont je n’avais jamais entendu parler. Le pavage rhombitrihexagonal ! Le pavage carré adouci ! Dans la demi-mesure qui m’a toujours caractérisé, j’ai pris l’évidente décision de TOUS les implémenter, ne serait-ce que pour le plaisir de pouvoir générer des images les utilisant.

Mais déjà, cette décision faisait apparaître des contraintes techniques.

De l’impossibilité de tricher

Bien sûr, face à une tâche quelconque, le premier réflexe est d’essayer de tricher pour tout simplifier. Normal. L’exemple typique est bien sûr le traditionnel pavage carré déjà mentionné. Si l’on souhaite implémenter un jeu se jouant sur une classique grille carrée, il est parfaitement inutile de stocker en mémoire une verbeuse liste de carrés. En effet, il est beaucoup plus aisé de représenter les données du jeu comme une grande matrice : à chaque case de la matrice correspond une des cellules du pavage.

Cette simplification est suffisante car les coordonnées cartésiennes de chaque carré peuvent très facilement se déduire de sa place dans la matrice. Pour une taille de carré n, le carré que représente la cellule de la matrice à la rangée x et à la colonne y aura comme caractéristiques :

points (Ox + n *  x,      Oy + n *  y     ) (Ox + n * (x + 1), Oy + n *  y     ) (Ox + n * (x + 1), Oy + n * (y + 1)) (Ox + n *  x,      Oy + n * (y + 1))	voisins (x + 1, y    ) (x - 1, y    ) (x,     y + 1) (x,     y - 1)
Représentation matricielle d'un pavage carré.

Pour simplifier : il est possible d’abstraire chaque cellule d’un pavage carré avec un simple couple de valeurs (x, y). Cette information est suffisante pour générer trivialement tout ce qu’il faut savoir : les coordonnées du polygone, l’identité des cellules voisines…

On peut appliquer la même logique aux pavages hexagonaux et triangulaires, bien que de manière un peu moins intuitive. Il suffit de “décaler” un peu notre axe “vertical” : il reste possible d’exprimer un tel pavage via une matrice et de représenter chaque cellule via une simple paire de coordonnées.

Toutefois, ce procédé n’est applicable qu’à ces trois pavages, les trois pavages réguliers (triangulaire, carré et hexagonal), et ce pour une raison très simple : l’uniformité de leurs éléments. Tout élément est, respectivement, un triangle équilatéral, un carré, et un hexagone régulier.

Les pavages semi-réguliers, eux, sont “mixtes” : il y a plusieurs types de polygones réguliers différents dans le même pavage. Pour eux, la représentation matricielle devient beaucoup plus compliquée et contre-productive, voire impossible. Au final, donc, pas le choix : pour gérer tous ces pavages, il va me falloir générer tous les polygones. Impossible de tricher.

Comique de répétition

Du coup, comment faire pour générer un pavage ? La solution que j’ai retenue est, sur le papier, relativement simple : simplifier chaque pavage pour pouvoir le traiter comme un pavage “carré”. Pour chaque pavage, j’ai identifié et implémenté une méta-forme composée de polygones adjacents. Cette méta-forme ne devait répondre qu’à une seule exigence : être répétable horizontalement et verticalement.

Une fois cette méta-forme identifiée et implémentée, il me suffit de l’utiliser comme un patron et de la répéter pour générer un pavage. Le processus de génération devient alors le même pour tous les pavages :

• générer ce fameux patron en fonction des paramètres du pavage (point de départ, angle, paramètres de déformation) ;
• estimer le nombre de répétions nécessaires pour recouvrir l’intégralité de la forme englobante de référence ;
• itérer ; pour chaque polygone valide du patron, l’intégrer au résultat.

En pratique, le code ne génère pas une liste temporaire de polygones mais fournit une interface basée sur des itérateurs. D’autre part, le code fournit des informations supplémentaires pour chaque polygone. Par exemple, à chaque étape, le polygone généré indique auxquels des polygones précédents il est relié, information nécessaire à la génération du graphe.

Je ne détaillerai pas ici l’implémentation des polygones et des tests d’intersections : ce serait le sujet d’un article entier, surtout si je liste tous les bugs rencontrés… J’ai en effet choisi de refaire tout de zéro et à la main (NIH, vous dis-je !). Pour plus de détails, merci de consulter la (future…) documentation de la MML. :)

Le Bug Originel

Tout n’a bien sûr pas marché du premier coup : erreurs de compilation à rallonge et illisibles à cause des techniques de méta-méta-programmation employées (BOOST_PP ! Dem templatez !), fautes de frappes, confusion dans les coordonnées… Mais il y a eu bien assez vite un Bug majeur, celui qui nécessite de réécrire une partie du code.

Ce bug a été heureusement facile à détecter en raison d’un choix technique important en amont : mon choix de n’utiliser que des coordonnées entières dans Stream. Mon but était de m’éviter toutes les complications liées à la manipulation de valeurs réelles. C’était relativement illusoire, mais qu’importe. Ce bug aurait existé même en utilisant des valeurs réelles ; il aurait été simplement moins évident à détecter.

Le bug en question ? Un bug d’approximation et d’arrondi, bien sûr. Je définissais les coordonnées de chaque polygone du patron en fonction de celles des autres polygones, d’où accumulation des approximations. Du coup, certains polygones qui, en théorie, avaient une arête en commun (aux jonctions des patrons), finissaient par avoir des points légèrement différents. La solution a été aussi simple que fastidieuse : réécrire la génération des patrons. Dans la plupart des cas, je génère maintenant une grille de points, que j’utilise ensuite pour générer le patron. Calcul unique, points uniques, premier gros bug réglé. L’image ci-dessous montre la grille utilisée pour le pavage triangulaire.

Agrafés et greffés au graphe

Une fois tous mes polygones proprement générés, j’ai pu générer le graphe de déplacement utilisé en interne dans le jeu. Rien d’extravagant à ce niveau : le centre de chaque polygone est un noeud du graphe, les liaisons entre polygones en sont les arêtes. En associant plusieurs valeurs à chaque arête et en tenant à jour plusieurs cost maps, j’ai pu construire sur cette base le gameplay de Stream tel que je l’avais montré il y a maintenant quelques mois.

(Pour celleux que ça intéresse, j’utilise une variante de l’algorithme A* pour la génération de mes cost maps : le Lifelong Planning A*, une variante d’A* dans laquelle chaque appel réutilise les informations des précédents.)

Plus aucun problème majeur n’apparut pendant un certain temps. Mais, récemment, j’ai décidé d’implémenter un élément de gameplay important : l’influence des différents types de terrain sur le graphe des déplacements. Je n’envisage pour l’instant que deux types de terrains :

• des forêts qui ralentissent mais protègent les ennemis,
• des routes sur lesquelles les ennemis vont plus vite mais sont plus exposés.

L’implémenter paraissait simple : modifier les valeur des arêtes entre cellules. Chaque arête contient en effet toutes les informations nécessaires au calcul des chemins, dont bien sûr la distance séparant les cellules. Il suffit donc, dans le cas d’une forêt, d’augmenter la distance perçue entre les deux cellules ; dans le cas d’une route, de la réduire. Le calcul des chemins tiendra donc compte de la distance perçue et non de la distance réelle. Oui mais voilà : quid d’une arête qui va d’une cellule de route à une cellule de forêt ? Ça n’a pas de sens de voir des ennemis aller à la même vitesse sur leur demi-trajet de route et leur demi-trajet de forêt… Il m’a donc fallu ajouter des points intermédiaires au niveau des intersections entre arêtes et polygones, en conséquence de quoi chaque arête du graphe n’est plus contenue que dans une seule cellule et ne traverse donc plus qu’un seul type de terrain. Fin du problème, en apparence.

Points névralgiques

Peu de temps après, j’ai implémenté la prévisualisation des plus courts chemins au sein de mon éditeur de niveaux. L’idée était de voir immédiatement ce que les changements apportés au niveau généré impliquaient au niveau du path-finding. J’ai commencé alors à voir émerger un très léger problème : certains chemins intuitivement équivalents étaient totalement ignorés par le path-finding. Le plus court chemin passait dans certains cas par un ou deux points précis, comme illustré ci-dessous. Les traits rouges représentent tous les plus courts chemins depuis la cellule verte jusqu’à la cellule rouge ; il peut y avoir, bien sûr, plusieurs chemins équivalents. C’est d’ailleurs le problème illustré dans l’image ci-dessous : il manque certains segments car le path-finder tient à passer par un point précis.

Après vérification, j’avais la confirmation que les points du pavage étaient correctement générés ; la distance théorique était la même pour les arêtes injustement ignorées et celles correctement incluses. J’ai finalement découvert que ce passage par un point unique ne se produisait qu’au moment de franchir un des axes du repère, au passage entre négatif et positif, quel que soit l’axe.

Au final, l’erreur venait bien de ces fameux points intermédiaires. En effet, la méthode d’arrondi utilisée dans toute ma MML était une méthode symétrique, du “round half away from zero” pour citer la terminologie de Wikipédia. Concrètement :

•  13.5 était arrondi à  14 ;
• -13.5 était arrondi à -14.

Mais cette symétrie était indésirable dans ce cas ; j’ai donc réglé le problème en calculant tous les points avec l’arrondi classique, le “round half up”. L’occasion pour moi de mieux apprécier l’insoupçonnée complexité d’une opération mathématique en apparence anodine.

Une fois ce petit détail corrigé, une fois les points intermédiaires correctement générés, tout semblait enfin bon, après plusieurs longues semaines à m’acharner sur le problème.

Nervous breakdown

Le fu. Le path-finder contourne bien l’infranchissable mur noir, mais il ne voit que le chemin qui le contourne par le haut et ignore royalement le chemin équivalent qui le contourne par le bas…

GOTO 10

Après m’être un peu arraché les cheveux, j’ai fini par comprendre d’où venait cette erreur… Et elle venait d’un problème loin en amont ; suffisamment loin, en fait, pour devoir repartir presque de zéro pour le résoudre. Le problème, comme toujours depuis le début était un problème d’arrondi. En raison des arrondis qui ont lieu lors de la génération de la grille du patron d’un pavage, même si ce patron est correctement répété dans le pavage généré, il peut y avoir en son sein un chemin indéniablement plus court qu’un autre.

Du coup, une première possibilité s’offrait à moi : renoncer à ma volonté de ne manipuler que des coordonnées entières, ne plus utiliser que des points aux coordonnées réelles et arrondir les résultats du path-finding à 0.0001 près pour éliminer les erreurs. Mais je m’y suis refusé. Une autre solution, pas réellement plus difficile, me forçait à revenir au point de départ et à améliorer ma génération de pavages. C’est ce que j’ai fini par faire, au final. À présent, j’associe à chaque lien entre polygones la distance théorique qui les sépare, plutôt que de calculer en pratique a posteriori la distance qui sépare les centres des cellules.

La tâche a été relativement fastidieuse. Pour vérifier la validité des valeurs implémentées, il m’a fallu faire quelques jolies images que voici. La première série avait pour but de vérifier la cohérence des informations : j’associais à chaque valeur réelle une couleur différente. Deux arêtes de la même longueur sont donc représentées par des traits de la même couleur (même longueur au bit près : je compare des valeurs de type double avec l’opérateur ==).

Avant	Après
Distances réelles : une douzaine de couleurs différentes.	Distances théoriques : trois couleurs.

La deuxième série m’a servi à visualiser la “plausibilité” des distances que je calculais. Chaque arête est dessinée avec une couleur correspondant à la différence entre la valeur théorique et la valeur réelle. Pas de différence, le trait apparaît noir, au delà de 10% d’erreur il apparaît totalement blanc. Inutile de vous les montrer : à présent, tout est noir !

But wait, there’s moar!

Et maintenant, j’ai de beaux pavages, et un path-finding qui marche correctement dessus. Il ne me reste plus qu’une toute petite étape mineure à terminer : en faire un jeu !

Au boulot, en avant, hardi, tout ça. :)