Rejoignez la communauté, réalisez vos jeux, gagnez de l’argent !

 

Ok le communiqué vient de Microsoft. L’information est relativement importante pour ne pas être occultée.

 


 


Résumé:


 


·         Xbox 360 est la première plateforme de jeu a décmocratiser le développement de jeu en permettant aux développeurs de,distribuer leurs jeux à une communauté de plus de 12 millions de joueurs abonnés au XBox Live, et de profiter des bénéfices financiers liés à leur productions.


·         Xbox LIVE Community Games est un nouveau service qui est service complémentaire et similaire au Xbox LIVE Arcade, ou aux système de vente de jeux en masse par l’intermédiaire de sa Console. Il fourni aux joueurs la selection des meilleurs jeux disponible pour sa console.


·         Xbox LIVE Community Games offre la possibilité aux membres de la communauté de participer à l’économie liée au monde du jeu vidéo.


·         La Xbox 360 est la première console permettant à n’importe qui de créer ses propres jeux et de partager le plaisir d’y jouer avec des millions de joueurs par l’intermédiaire du through Xbox LIVE Community Games.


·         La possibilité de partager ses productions sur la XBox360 est un nouveau concept révolutionnaire qui va changer la façon dont on mesure l’attractivité d’un jeu.


 


 


Présentation:


 


Vous avez joué aux jeux XBox 360 avec des millions d’autres joueurs par l’intermédiaire du XBox Live. Vous pavez parlez, échangé, dominé dans toute sorte de jeux. Imaginez maintenant le fait d’offrir à ces millions de joueurs la possibilité de jouer à vos propres productions ? Avez vous pensé au principe de gain financier lié au succès de votre jeu !


 


 


  


Comment ca marche ?


Le principe ? Simple. Le payement ? Cash.


En tant que Premium member dans le XNA Creators Club vous avez la possibilité de fournir un jeu complet pour la console XBOX 360 créé à l’aide du XNA Game Studio à la communauté du Creator Club  http://creators.xna.com pour faire tester votre jeu par les autres membres. Ceux-ci vont s’assurer que votre production est stable et digne d’être partagée. Dans ce cas vous devez définir un prix sous la forme de point (compris entre 200 et 800 points) que les joeuurs devront payer pour télécharger votre jeu. A partir du moment où le jeu a été testé et où un prix a été spécifié vous avez terminé. Votre jeu sera alors listé dans le XBox Live Marketplace (le marché du Xbox live) et vous aurez un bénéfice allant jusqu’à 70% des gains liés à la vente de votre jeu.


Votre jeu peut être mis en avant sur la XBox et par Microsoft au vu de son succès.


Imaginez la puissance de la communauté XBox Live : votre jeu dans les mains de millions de joueurs XBox 360 à travers la planète.


 


Comment commencer


Le lanchement officiel du Xbox LIVE Community Games ne se fera que plus tard dans l’année. Mais vous pouvez dors et déjà commencer à développer votre jeu dans cette optique à l’aide du XNA Game Studio et du XNA Creators Club Online community !



 


Pour commencer téléchargez le Xna Game Studio, l’outil de développement de jeu gratuit de Microsoft. Il est gratuit et il fonctionne avec Visual Studio ou Visual Studio Express qui est lui aussi gratuit. Si vous n’avez jamais réalisé de jeux auparavant, le site du XNA Creators Club offre un grand nombre d’exemples, de tutoriaux et videos pour vous aider et vous guider dans votre tâche. Lancez vous et créez le jeu de vos rêves !


 


Ensuite rejoignez la communauté du XNA Creator’s Club sur le site  http://creators.xna.com. Cette communauté de créateurs de jeux videos possède un grand nombre de membres qui, comme vous, débutant. Si vous développez un jeu pour la Xbox 360 et desirez devenir un membre Premium pour vendre votre jeu via le  Xbox LIVE Community Games vous devrez vous acquiter de la somme e $99 par an ou $49 pour 4 mois.


 


Enfin, soumettez votre jeu au XNA Creators Club et regardez l’argent affluer !


 


 


Questions?


Si vous avez des questions sur la communauté, sur le XNA Game Studio, ou pour tout autre détail reportez vous à la FAQ.


 


 

Affichage de terrain par l’intermédiaire de la technique BILLOD

Terrain BilLOD


Si vous êtes un développeur de jeu vous avez forcement déjà travaillé sur l’affichage de terrain. Il s’agit généralement du point critique de tout jeu. Non pas parce que, conceptuellement parlant il est l’élément le plus important visible à l’écran mais parce qu’il est le principale facteur jouant sur les performances et la qualité de votre application. Il est donc important d’utiliser des techniques qui visent à réduire au maximum la charge supportée par votre jeu pour afficher le terrain tout en préservant sa qualité d’affichage.  Cet article présente justement une technique qui tente d’apporter une réponse à cette problématique en Xna.


Réalisant une étude de moteur de jeu destiné à aider les développeurs de jeux participants au concours Imagine Cup j’ai donc tout naturellement privilégié cet aspect important en cherchant un moyen d’afficher un monde 3D sans limite réelle de taille avec un niveau de détail acceptable.


Il existe nombre de techniques d’affichage de monde explicités par des articles intéressant. Ceux-ci sont souvent basés sur un compromis désagréable qui porte un choix entre la taille du terrain ou le niveau de qualité et s’accompagnent d’algorithmes rédhibitoires.


Cet article ne se présente pas comme la seule réponse possible à l’affichage de terrain en Xna mais entend juste apporter une solution efficace  fonctionnant pour cette technologie sachant que la plupart des exemples  existants sur le Web sont réalisés en DirectX et OpenGL.


Nous découperons notre étude en plusieurs phases :


·         D’abord nous décrirons la problématique posée par l’affichage de terrains et expliciterons le besoin d’optimisation.


·         Nous décrirons ensuite la méthode utilisée pour découper notre terrain en un QuadTree.


·         Nous expliciterons la façon dont nous réduisons le détail du terrain à distance tout en gardant au maximum son aspect à proximité.


·         Nous décrirons d’une manière plus technique l’implémentation de cette technique


·         Enfin nous verrons  les possibles optimisations offertes au lecteur.


 


La problématique


 


Imaginons que nous voulions modéliser une région de 10 km sur  10km avec un degré de détail sur 1 mètre (1 kilomètre = 1000 mètre). Nous avons donc (sans optimisation) une grille de 100000*100000 à afficher. Continuons dans le brutal en précisant que chaque vertex de la grille possède une taille mémoire égale à approximativement de 40 octets. On atteint alors  environ 4 gigas de données à afficher. Le matériel du joueur lambda actuel ne permet pas de manipuler de telles charges mémoire. Autre problème, un tel terrain modélisé en une grille statique demande le rendu de 200 millions de triangles par frame. Cette façon de procéder est un désastre. A partir du moment où la taille du terrain devient importante et  où l’on ajoute au terrain les ingrédients habituels d’un jeu, comme des modèles 3D, une interface utilisateur, des animations,  les performances d’un jeu ne peuvent plus suivre. C’est là ou la charge prise par le terrain pour son affichage prend toute son importance.


Il est donc important que la part de puissance CPU ou GPU prise par l’affichage du terrain soit la plus basse possible afin de garder du temps de traitement pour les autres besoins du jeu.  Les univers virtuels offerts par la plupart des jeux modernes sont gigantesques et ne peuvent plus être réalisé à l’aide d’une simple grille statique


Le besoin d’optimisation est donc clair. J’invite le lecteur à se rendre sur http://ww.vterrain.org pour découvrir quelques présentations de techniques autres que celle présentée ici.


Si nous avions un cahier des charges à respecter, nous aurions :


·         Garder l’aspect du terrain au maximum


·         Rendre la gestion du terrain par le code propre et accessible


·         Utiliser une technique efficace et simple et rapide.


·         Respecter une approche QuadTree pour optimiser les performances


 


Le QuadTree


La première étape pour la réalisation de notre terrain est donc de le gérer par l’intermédiaire d’un QuadTree où chaque nœud possède 4 enfants. Le parcours d’un tel arbre est simple et prend en moyenne toujours le même temps : a chaque niveau, il n’y a au maximum que 4 tests à effectuer pour être « autorisé » à descendre au niveau inférieur.


Principe


Le QuadTree (souvent utilisé pour le rendu de terrain) apporte donc une réponse intelligente au problème d’optimisation. D’abord il ne permet de charger les données que lorsqu’elles sont nécessaires. Ensuite sachant la taille de la zone de terrain correspondant à un nœud est inversement proportionnelle a la profondeur de ce  nœud dans l’arbre, on limite par la même occasion le nombre de triangles à afficher. Nous expliciterons tout cela au fil de cet article.



Plus on s’enfonce dans l’arbre, plus la précision du détail affiché s’affine.


 


Au départ notre terrain ne fera qu’un seul nœud : le nœud racine. Celui-ci aura pour dimension la taille du terrain. Un nœud à l’écran correspond à une surface carré composée de 9 vertices :


1.       Nord


2.       Nord Est


3.       Est


4.       Sud Est


5.       Sud


6.       Sud Ouest


7.       Ouest


8.       Nord Ouest


9.       Centre



Un noeud se composé de 9 vertices


Le QuadTree se basera sur un heightfield (un tableau à deux dimension contenant l’ensemble des hauteurs Y de chaque vertex à l’écran). Chaque vertex de chaque nœud dans le QuadTree possède une hauteur dont la valeur est puisée dans le heightfield.


Au départ, seuls les sommets du  nœud sont visibles, soit : Nord Est, Sud Est, Nord Ouest, Sud Ouest. Son rendu correspond à peu près à l’image suivante :



Les vertices grisés sont les vertices visibles


A chaque mise à jour du terrain, pour chaque nœud actuellement visible, nous calculons la visibilité de chacun des vertices. Chaque mise à jour d’un nœud s’accompagne d’un redécoupage des triangles qui le composent. L’image suivante explicite quelques configurations possibles pour un nœud :


 



L’algorithme pour cette partie serait :


//Pour chacun des vertices Nord, Est, Sud, Ouest
If ( !Vertex.Visible && VertexTest())
                Vertex.Visible = true ;
Else if (Vertex.Visible && !VertexTest())
                Vertex.Visible = false;


Le test de cet algorithme prend en compte la distance à laquelle se trouve le vertex et le besoin croissant de détail à mesure que la camera s’approche de celui-ci. Nous reviendrons sur la nature de ce test plus tard.
Dans un second temps il est nécessaire de calculer la visibilité des enfants du nœud courant.  Un nœud se compose de quatre enfants comme l’image suivante le montre :



Nous avons ici affiché l’enfant Nord Est du nœud racine, puis l’enfant Sud Est de celui-ci, puis l’enfant Sud Est de ce dernier enfin l’enfant Nord Ouest de celui-ci.


Plus on pénètre profondément dans le QuadTree plus le maillage se resserre et permet d’afficher un terrain plus détaillé.


L’algorithme pour cette partie à ce stade de notre étude serait :


//Pour chacun des quatres enfants Nord West, Nord Est, Sud Ouest, Sud Est
If ( !Child.Visible && ChildTest())
                Child.Visible = true ;
Else if (Child.Visible && ! ChildTest())
                Child.Visible = false;


Là encore, le test de cet algorithme prend en compte la distance à laquelle se trouve l’enfant et le besoin croissant de détail à mesure que la camera s’approche de celui-ci. Nous reviendrons sur la nature de ce test plus tard.


Lorsqu’un enfant est visible, ses vertices et ses propres enfants sont soumis aux deux algorithmes que nous venons de voir. Nous sommes donc dans un principe de récursivité.


On calcul les triangles composant un nœud en ne prenant pas en compte les parties occultés par les enfants :



On remarque ici que les vertices Nord et Est du parent sont partagés avec les vertices Nord Ouest et Sud Ouest de l’enfant.


Le principe de base du BilLOD est donc relativement simple. Vertices et enfants à afficher sont soumis à chaque mise à jour du terrain à un ensemble de tests qui déterminent leur visibilité. L’affichage de nœud se fait de manière récursive en parcourant le QuadTree du nœud racine à chaque nœud feuille de chaque branche.


Améliorations


Nous parlions précédemment du partage de vertices entre un enfant et un parent. L’image précédente illustrait ce point. Cette particularité peut être à l’origine d’un bug graphique assez désagréable illustré par l’image ci-dessous :


 



On y voit un espace entre deux nœuds qui laisse entrevoir le bleu du fond d’écran. Ce problème est dû à la non activation d’un vertex chez le nœud voisin. Explicitons ce problème en image. Schématiquement les nœuds concernés par ce bug sont les suivants :



Soit en réalité :



Le vertex Ouest de l’enfant rouge est activé mais pas le vertex Est de l’enfant jaune. Il y’a donc un delta entre les deux cotés communs des deux enfants. Pour résoudre ce bug il suffit simplement de valider le vertex est de l’enfant jaune :



Au final on obtient une continuité parfaite :



Imaginons maintenant que le vertex sud de l’enfant jaune devienne visible. Le nœud parent ne possède que deux enfants situés au nord ouest et au nord est. Activer ce vertex posera le même problème graphique que précédemment :



Malheureusement, contrairement au cas précédent, il n’y a pas d’enfant au Sud Ouest. Il est donc nécessaire de créer un enfant à cette position (bien que le « ChildTest » de notre algorithme pour cet enfant renvoie false) et de lui activer son vertex Nord :



L’ajout du vertex sud de l’enfant blanc à provoqué à la création de l’enfant Sud Ouest et l’activation du vertex Sud du nœud parent. Ce vertex Sud peut lui-même provoquer la modification des nœuds voisins. On assiste là à des effets en cascade qui ne sont pas vraiment contrôlable mais sont, fort heureusement, limités. L’image suivante montre l’impacte de l’activation de plusieurs enfants profondément dans le QuadTree en bas à droite du terrain.



On remarque que les nœuds situés à l’opposé du terrain sont impactés.


 


Activation/désactivation du nœud dans le QuadTree


 


Quelques années auparavant j’ai lu un excellent article d’une personne nommée Stan Melax auteur d’une technique ingénieuse permettant de calculer de manière dynamique l’aspect d’un modèle 3D à différent niveau de résolution. Les articles sur les meshs progressifs sont soumis aux mêmes lois que ceux sur les terrains : soit l’algorithme de réduction est trop compliqué, soit il est mal adapté. Stan Melax a trouvé une manière intelligente de résoudre ce problème. Il étudie le coût  de la disparition de chaque vertex en étudiant leur impacte sur la forme globale. Il est alors capable de réduire progressivement la résolution du modèle 3D en supprimant dans un ordre logique les vertices les moins impactant. Sa force réside dans le calcul du coût d’un vertex qui s’avère être une formule simple et efficace. Nous procéderons de la même manière.


La courbe, l’élément à retenir


Nous l’avons vu dans les deux algorithmes dédiés aux vertices et aux nœuds, un test est réalisé pour déterminer si un vertex ou un enfant doit être affiché ou non. La qualité du terrain affiché doit être fonction de la position de la caméra pour le confort du joueur. Plus une zone du terrain est proche de la camera plus elle doit être détaillé. Le but est aussi de préserver au maximum l’aspect du terrain au loin avec un minimum de vertices et de progressivement détailler lorsque la caméra s’approche.



Pour parler simple, on mesure l’aspect d’un terrain à ses formes. On mesure une forme à ses courbes. La question est alors : comment définir une courbe ? Répondre à cette question permettrait de déterminer les emplacements du terrain où il faut garder un niveau détail important et ceux qui peuvent être dégradé.


Il existe un grand nombre de technique pour transformer une courbe en une fonction mathématique. Nous revenons dans ce cas à la problématique du départ : ne pas surcharger trop le processeur. Nous l’avons vu, il est nécessaire d’appliquer la formule trouvée à tous les vertices et à tous les enfants des nœuds. Une formule trop couteuse en instructions détériorera les performances de l’application.


La solution est en fait simple. Nous l’avons dit, notre terrain est découpé en nœuds appartenant tous à un arbre. Chaque courbe du terrain est donc constituée de nœuds qui sont en fait des surfaces carrés dont la taille varie



Le terrain est un ensemble de courbes visibles à l’écran. Chaque courbe est un assemblage de nœuds carrés collés côtes à côtes.


La normale, ordre de grandeur d’une courbe


Plus la courbe est importante, plus les nœuds qui la composent forment un angle important. Prenons pour exemple une courbe vue de profil :



On y voit ensemble de nœuds collés côte à côte. A l’endroit où la courbe est réellement importante on remarque que les nœuds forment un angle important. Au contraire à l’endroit où il n’y a pas de courbe mais une simple pente, les nœuds côtes à côtes ne forment pas d’angle mais semblent appartenir à un même plan. On le remarque encore plus si on affiche les normales de chacun des nœuds :



Nous sommes maintenant proches de trouver la formule ! Tous les lycéens savent que la fonction mathématique qui mesure l’angle entre deux vecteurs est le produit scalaire (dot product).



Le produit scalaire de deux vecteurs non nuls représentés par les vecteurs A et B est le nombre réel A.B.cos(θ) si l’angle θ représente l’angle formé entre les deux droites ayant pour direction ces deux vecteurs.


 


L’angle maximum que l’on peut trouver dans une courbe d’un terrain tel que nous le concevons tend vers les 90° (la valeur 90° ne pouvant être atteinte dans le mesure ou les nœuds ne peuvent se chevaucher). Cos 90 valant 0 on peut en déduire que plus la courbe formée par les vecteurs est importante plus leur produit scalaire s’approche de 0 (A*B*Cos(90) = A*B*0 = 0). Au contraire si la valeur du produit scalaire augmente, c’est que la courbe formée par les deux nœuds tend vers la « droite » (A*B*Cos(0) = A*B*1 = AB).  Voyons tout cela en image :



Le produit scalaire entre la normale du parent et celles des enfants va renvoyer ici une valeur clairement  différente de 0 : nous sommes sur une surface, certes inclinée, mais plane. Inutile de découper le nœud.


Prenons maintenant une courbe prononcée



L’angle entre les trois normales est plus prononcé. Le nœud originel (symbolisé par la ligne en pointillée noire) doit être découpé en sous-nœuds. On peut trouver dans cette façon de procéder une certaine logique : une surface plane se modélise facilement avec peu de polygones. Une surface courbée en demande beaucoup plus. Voici pour terminer la courbe en wireframe :



Plus la courbe est prononcée, plus notre technique utilise des primitives


 


Méthode d’activation


 


La méthode Child Test devra donc comparer la normale de l’enfant à tester avec celle du nœud auquel il appartient parent. Si l’angle entre les deux normales dépasse un seuil limite alors la méthode renvoie true.


 


Test de désactivation


La désactivation d’un enfant ne se fait que lorsqu’une série de facteurs est rencontré :


·         L’enfant n’a plus de vertices visibles


·         L’enfant n’a plus de sous-enfants


·         La méthode de Test renvoie false.


 


Activation/désactivation du vertex dans le nœud


 


De l’interpolé au réel


La gestion de la visibilité des vertices ne suit pas la même logique que celle décrite précédemment. Ici il n’est pas question de courbes  mais de delta.  Seuls les vertices situés sur les cotés d’un nœud sont à tester. Soit Nord, Est, Sud, Ouest. Lorsqu’un nœud est créé, ceux-ci ne sont pas visible. Situé entre deux vertices sommets on peut déduire leur hauteur facilement. Voici un exemple de nœud vu de coté :



 


On y voit les vertices Nord Ouest et Sud Ouest activé (visibles)) et le vertex Ouest  désactivé.


Ce dernier semble être sur la droite parcourant les deux sommets. En fait il n’en est peut être rien. Pour l’heure nous avons interpolé (déduit) sa position (Si Sud Ouest est à une hauteur de 10 et Nord Ouest à une hauteur de 20, on peut raisonnablement penser qu’Ouest sera à une hauteur de 15). Pourtant en réalité  il se trouve peut être à une position tout autre :



On y voit une distance delta qui sépare la position du vertex Ouest interpolée de sa position réelle. Cette différence de hauteur mesure le degré de réalité du nœud actuellement affiché avec une version plus détaillée.


Afficher le nœud avec seulement les 4 vertices sommets affichés ne rend donc pas bien compte de la réalité du terrain affiché par le nœud.


Méthode d’activation


La méthode d’activation est ici très simple, il nous suffit de déterminer la valeur delta (une simple différence de hauteur) et de déterminer si elle dépasse un seuil.


Test de désactivation


La désactivation d’un vertex ne se fait que lorsqu’une série de facteurs est rencontré :


·         Le vertex n’appartient pas à un nœud enfant


·         La méthode de Test renvoie false.


 


 


 


Détail Progressif


 


C’était l’un des prérequis de notre technique : nous devons optimiser l’affichage en fonction de la position de la caméra ; le détail doit progressivement s’atténuer à mesure que l’on s’en éloigne. Pour l’heure nos deux fonctions de tests (pour les vertices et les enfants de nœuds) ne prennent pas en compte la position de la caméra et la position de l’élément à tester.


 


Détail progressif pour le QuadTree


Pour l’heure la méthode de test se base sur l’ouverture de l’angle formé par la normale d’un enfant avec son parent.  Cette façon de procéder n’est pas forcement pertinente à distance.


Si un angle de quelques degrés est visible lorsqu’on est proche des nœuds qui le composent, cet angle n’est pas forcement détectable à distance. Il n’est donc pas nécessaire d’activer l’enfant.


Voici l’implémentation de cette méthode de test :


private bool ChildTest(Vector3 childNormal, BoundingBox boundingBox, Vector3 cameraPosition)


{


    //by default, the four childs of the root node are visible.


    if (this.Depth < 1)


        return true;


 


    //get the closest point to the camera and check the distance


    float distanceCameraToPoint = Vector3.Distance(GetBoundingBoxClosestPointToPoint(boundingBox, cameraPosition), cameraPosition);


    //compute the dot product between parent normal and child normal


    float dotprod = 1 – Vector3.Dot(childNormal, this.CenterVertex.Value.Normal);


 


    //check with the threshold


    return (distanceCameraToPoint / this.ParentTree.QuadTreeDetail) < (dotprod);


}


Par défaut les nœuds situés au sommet de l’arbre sont rendus visibles. Nous déterminons ensuite la distance entre la position de la caméra et le point le plus proche de celle-ci dans la boundingbox englobant l’enfant. Le produit scalaire est ensuite calculé. Nous testons alors si la division de cette distance par un seuil paramétrable  est inférieure au produit scalaire.


Il est à noter que cette méthode de test peut très bien être adaptée pour soumettre le QuadTree à une autre technique d’optimisation.


 


Détail progressif pour le vertex


La encore, la méthode de test pour les vertices ne prend pas en compte la distance à la caméra. Nous devons déterminer si la distance entre la position réelle du vertex et sa position interpolée dépasse un seuil paramétrable.


Voici la méthode de test :


 


        public bool VertexTest(Vector3 vertexPosition, Sides side, Vector3 cameraPosition)


        {


            //get the distance between interpolated height position and real height position


            float lengthToTest = this._realToInterpolatedVertexHeight[(int)side];


            //get the distance from the camera position to the vertex position


            float distanceCameraToPoint = Vector3.Distance(vertexPosition, cameraPosition);


 


            //check with the threshold


            return lengthToTest * this.ParentTree.VertexDetail > distanceCameraToPoint;


        }


 


Le delta entre les deux vertices (interpolé et réel) est stockée en mémoire. Nous la rapatrions. Nous déterminons ensuite la distance entre le vertex et la caméra. Un test est alors effectué pour déterminer si le delta conjugué au seuil dépasse la distance à la caméra. Tout comme précédemment cette méthode de test peut très bien être adaptée pour soumettre le les vertices de chaque nœud à une autre technique d’optimisation.


Un terrain à différents niveau de détail, de gauche à droite : 7500, 3000, 1500, 300 150 vertices


 


 


Code et optimisation


 


Le code donné avec cet article est volontairement sommaire pour des raisons de compréhension et de …manque de  temps J


Son but est de tester la technique Billod décrite ici de manière simple et lisible sans chercher en aucune manière tout type d’optimisation.


Description des classes « métier »


Quatre classes sont réellement métier :


·         Terrain


·         QuadTree


·         QuadNode


·         TerrainVertex


Terrain est un conteneur de QuadTrees. Il représente le terrain dans sa globalité.


QuadTree représente une portion de terrain. C’est un conteneur de QuadNodes.


QuadNode représente un nœud. C’est un conteneur de TerrainVertex.


TerrainVertex représente un vertex.


La majeure partie du traitement se situe à l’intérieur de la classe QuadNode. Celle-ci dispose de deux méthodes importantes : Initialize et Update.  La méthode Initialize s’occupe de charger le node avec toutes les informations liées à sa position dans le QuadTree. Elle rend visible les 4 sommets, elle détermine les nœuds voisins (pour le partage de vertices). Elle calcule en outre, les deltas, les normales, les boundingbox.


La méthode Update effectue les tests sur les quatres vertices « cotés » (Nord, Est, Sud, Ouest) et sur les quatre enfants potentiels (Nord Ouest, Nord Est, Sud Ouest, Sud Est).


C’est la classe QuadTree qui initialise le premier node et débute le traitement sur l’arbre. Toutes les x secondes (paramétrable) elle lance un update asynchrone sur tous les nœuds instanciés pour mettre à jour l’arbre en fonction de la position de la caméra.


L’instanciation d’un QuadTree se réalise en précisant la taille de celui-ci, sa profondeur et sa location :


QuadTree tree = new QuadTree(treeDepth, rootNodeSize, location);


 


La structure TerrainVertex contient le vertex à afficher. Un vertex peut être partagé sur plusieurs nœuds.


Le code de ces quatre classes importantes a été simplifié à l’extrême et largement commenté. S’il reste des points noirs n’hésitez pas à me contacter.


 


Thread Update


Une solution simple et rapide à implémentée à été choisie pour la mise à jour du terrain. Un backgroundWorker est lancé au démarrage de l’application et s’occupera de la mise a jour du terrain de manière asynchrone.


Cette façon de procéder évite tout ralentissement du jeu lors de l’update. Les données d’affichages (VertexBuffer et IndexBuffer) sont stockées dans une pile et utilisé dans la méthode Render. Dans l’exemple fourni avec cet article, nous n’effectuons un Update que toutes les 4 secondes.


 


Optimisations


En dehors des améliorations portant sur le code, voici quelques pistes pour augmenter la qualité du rendu et la puissance de la technique Billod.


Plusieurs optimisations sont possibles :


·         Nous effectuons deux parcours de l’arbre à chaque Update (l’un pour mettre à jour l’arbre, l’autre pour extraire la liste triangles à afficher). Il y’ peut être un point à améliorer ici.


·         Le backgroundWorker pour un jeu Xna  n’est pas un choix judicieux. Un thread normal encapsulé dans une gestion adaptée serait plus efficace.


·         La mise à jour toutes les 4 secondes n’est pas forcement la meilleure solution. Il y’a plusieurs autres pistes possible : mettre à jour que lorsque la caméra est déplacée. Prévoir les déplacements du joueur et mettre à jour en conséquence. Enfin, il faut savoir que l’état final d’un arbre ne s’obtient pas en un seul Update. Il est peut être préférable dans certains cas d’attendre la version finale de l’arbre en appelant la méthode Update autant de fois qu’il le faut avant de générer les données d’affichage.


·         Eviter les generics dans les jeux. Par manque de temps j’ai utilisé en plusieurs endroits des classes génériques (pour la gestion des listes/queues). Les listes ne sont pas aussi rapides qu’un array…


·         Interpoler les transitions. Lorsqu’un nœud est découpé ou fusionné, ou bien lorsqu’un vertex change d’état (visible/caché), la transition est visible à l’œil nu. Il peut être utile de découper cette transition en plusieurs étapes progressive pour adoucir les changements visuels.


·         S’appuyer sur la classe Terrain. Pour l’heure nous n’affichons qu’un seul Arbre. La classe terrain peut être un sérieux tremplin pour tenter de gérer plusieurs arbres qui seront liés les un aux autres. Cette façon de procéder permettrais de réaliser des horizons à l’aide de QuadTree tellement éloignés qu’ils en seraient réduit à quelques vertices.


·         Nous chargeons le HeightField en entier dès le départ en analysant une image en noir et blanc (plus la couleur lue est noire, plus l’altitude est faible.). C’est une façon efficace de procéder pour réaliser un exemple ce l’est moins dans le cadre d’un jeu affichant un monde d’une très grande taille. Il serait peut être judicieux de stocker l’array de hauteur dans un fichier et de ne lire que ce que le QuadTree a besoin à chaque Update. Ceci libérerait la mémoire.


·         Le code source n’a pas été optimisé pour des raisons de lisibilité. A vous de restaurer un code rapide et efficace !


 


Le programme d’exemple


 


Ce programme n’est qu’un rapide exemple d’implémentation du terrain Billod. Les classes métier sont toutefois rapidement adaptables au besoin de chacun. Le projet est réalisé en Xna 3.0. Il est toutefois adaptable au 2.0.


Les commandes pour interagir avec le monde sont :


·         Souris : Cliquer pour tourner la caméra.


·         Touches fléchées : déplacement de la caméra dans la direction courante.


·         Touche W : Mode Wireframe On/Off.


·         Page Haut / Page Bas : Seuil de test des enfants.


·         Touche left Shift + Touches fléchées : déplacement rapide.


·         Touche left Alt + Touches fléchées : déplacement lent.


Le test du terrain Billod se fait simplement en se déplaçant sur le terrain et en étudiant l’évolution du terrain.


Vous pouvez réutiliser le code source à votre guise. Je demande juste de me référencer dans vos « credits » J


 


Références / Remerciements


Le site de Stan Melax : http://www.melax.com/.  Quelqu’un de très pragmatique à l’origine du technique de Progressive Mesh très intelligente sur laquelle je me suis basé.


Continuous LOD Terrain Meshing Using Adaptive Quadtrees par Thatcher Ulrich. Une méthode assez proche de la mienne mais plus orientée vers la recherche de deltas. C’est l’une des rares méthodes sur le web utilisable dans un jeu. La technique Billod possède un QuadTree assez similaire à son « Adaptive QuadTree ». Sa gestion du heightfield étant bien plus intelligente que la mienne.


La page d’Hugues Hoppe : http://research.microsoft.com/~hoppe/. L’un des maîtres du terrain rendering. Tout est bluffant mais illisible pour le néophyte et pas forcement adapté au monde du jeu vidéo.


Virtual Terrain Project: http://www.vterrain.org/. Le site incontournable regroupant un ensemble de publications autour de la gestion de terrain.