TD 5 - Shoot'em Up!



Votre opinion sur le cours d'aujourd'hui: Votre opinion sur le TD de la semaine derniere :

Introduction

Le but de ce TD est d'implementer une ebauche de jeu video First-Person Shooter (FPS) a la Doom, en vision subjective 2D 1/2. Plus precisement nous allons nous interesser au moteur graphique, base sur un lanceur de rayons en 2D. Pour representer le domaine du jeu en memoire nous utiliserons une triangulation de Delaunay 2D avec contraintes, ou chaque contrainte representera un morceau de mur et ou le reste des aretes servira a partitionner le domaine en cellules simples (en l'occurence des triangles), ce qui nous permettra de faire du lancer de rayons efficacement. Notez que les triangulations de Delaunay sont un choix parmi d'autres structures de donnees pour le lancer de rayons, comme les decompositions trapezoidales, les hierarchies de volumes englobants ou les Binary Space Partition trees.

couverture du jeu Doom
 Doom en action

Fig. 1 - Le jeu Doom (1993). A gauche, la jaquette du jeu. A droite, dans le feu de l'action.


Qu'est-ce que la 2D 1/2 ?

Le principe de la 2D 1/2 est simple : on a un observateur ponctuel positionne en un point p d'un domaine 2-dimensionnel D et oriente dans une direction d. L'idee est de synthetiser ce que voit l'observateur en scannant le domaine circulairement par un rayon r issu de p et en calculant, pour chaque  orientation du rayon, quel est le premier point d'intersection de r avec les obstacles. Ce point dans le domaine 2-dimensionnel genere un segment vertical dans la fenetre de vue de l'observateur. La longueur du segment inversement proportionnelle a la distance entre p et le point d'intersection. Voir la figure 2 pour une illustration.

Principe de la 2D 1/2
Fig. 2 - Principe de la 2D 1/2 : pour chaque rayon issu de la position de l'observateur (par exemple le rayon violet a gauche) on calcule la premiere intersection avec les bords du domaine (les aretes bleues sur la carte), qui genere un segment vertical (marque en violet) dans l'image de vue a droite. La taille du segment diminue avec la distance de l'observateur au point d'intersection.

Pour intersecter un rayon avec le bord du domaine D, la methode naive consiste a regarder chacun des segments formant le bord de D et a tester l'intersection de ce segment avec le rayon. Cette methode a une complexite lineaire en le nombre total de segments formant le bord du domaine, ce qui beaucoup trop couteux (rappelez-vous qu'on lance un rayon par colonne dans l'image de rendu). Pour accelerer le processus  nous allons construire une partition de l'espace qui integre les segments du bord de D. Plus precisement, nous allons utiliser une variante de la triangulation de Delaunay 2D appelee triangulation contrainte. Le principe de cette construction est de respecter le critere de Delaunay local sur toutes les aretes, sauf sur celles qui sont marquees comme etant contraintes (affichees en bleu sur l'image de gauche dans la figure 2). Ainsi, un sommet et une face situes de part et d'autre d'une arete de contrainte sont autorises a ne pas respecter le critere de Delaunay. Ceci permet aisement de faire en sorte que la triangulation integre les aretes de contrainte, tout en gardant de bonnes proprietes d'aspect des faces, element essentiel pour le lancer de rayons.

La bibliotheque Jcg fournit une implementation de la triangulation de Delaunay 2D contrainte. En fait, c'est la classe Delaunay_2 du package triangulations2D qui fournit directement l'implementation, avec une methode public HalfedgeHandle<Point_2> insert(Point_2 p, Point_2 q) qui insere une nouvelle arete de contrainte [p,q] dans la triangulation. Le travail a effectuer se repartit comme suit  :
  1. Completer le squelette de la classe RayCast, en particulier la methode public HalfedgeHandle<Point_2> castRay (Ray_2 r, HalfedgeHandle<Point_2> e) qui retourne la premiere arete de contrainte intersectee par un rayon donne r, sachant que l'origine du rayon doit se trouver dans la face de la triangulation contenant la demi-arete e. Completer ensuite la methode public void castRays() qui lance tous les rayons necessaires a la generation de la vue de l'observateur et qui stocke les resultats dans le tableau double[] distancesToObstacles.
  2. Completer le squelette de la classe RayCastWindow, et en particulier la methode public void paint(Graphics graphics). Notez que la gestion de la creation de la fenetre et des evenements clavier est deja ecrite dans le squelette.
  3. Pour ameliorer le moteur graphique, ajouter la gestion des textures. Pour le plaquage de textures on remplacera simplement chaque segment vertical de couleur unie par un segment vertical pris dans l'image de texture stockee dans le champ textureImg.
Une fois ce travail realise vous pourrez vous amuser a ameliorer le moteur en ajoutant par exemple la gestion des collisions, l'utilisation de portes et de teleporteurs, l'afficchage de sprites representant les ennemis, etc. Le potentiel d'amelioration est infini, et vous vous rendrez vite compte qu'ecrire un bon moteur 3D necessite enormement de temps... pas etonnant que les moteurs de Id Software, la compagnie qui a cree Doom et Quake, se soient retrouves dans des dizaines de jeux Doom-like de l'epoque !

Installation des librairies

Avant de demarrer nous rappelons que la documentation de la bibliotheque Jcg est consultabe ici.

Il vous faut telecharger le jar de la derniere version de la librairie, disponible ici (et le source ici). Ajoutez simplement le jar au build path de votre projet.

Notez que nous n'aurons pas besoin de java3D aujourd'hui, puisque nous allons gerer l'affichage nous-memes en 2D 1/2.

1. Lanceur de rayons

Commencez par telecharger le fichier RayCast.java qui contient le squelette a completer de la classe RayCast. Il faut egalement telecharger Map.java qui contient la gestion de la fenetre de carte, ainsi que le fichier d'exemple de carte labyrinthe.edg. Notez que le format de ce fichier est tres simple : chaque ligne contient les coordonnees des deux sommets d'une arete de contrainte. C'est tout ! Il vous sera donc facile de creer d'autres fichiers de cartes. Notez toutefois un detail important : les aretes de contrainte ne peuvent s'intersecter qu'en leurs sommets. En effet, l'implementation des aretes de contrainte proposee dans la bibliotheque ne gere par les intersections entre contraintes, et en particulier la methode public HalfedgeHandle<Point_2> insert (Point_2 p, Point_2 q) risque tres fortement de boucler indefiniment et de generer un Stack Overflow si vous creez des contraintes qui s'intersectent en-dehors de leurs sommets. Pour le moment vous pouvez lancer le programme RayCast et voir s'afficher la carte de la figure 2 (gauche), avec les aretes de contrainte en bleu et le reste des aretes de Delaunay en noir. La plus grosse partie du travail, a savoir la construction de la triangulation contrainte, est deja faite.

Completez la methode public HalfedgeHandle<Point_2> castRay (Ray_2 r, HalfedgeHandle<Point_2> e) de la classe RayCast. Cette methode prend en entree un rayon r et une demi-arete e sur le bord de la face contenant l'origine du rayon, et elle retourne une HalfedgeHandle<Point_2> representant la premiere arete de contrainte intersectee par r. La methode doit retourner null quand il n'y a pas d'intersection. Deux remarques importantes :

Completez maintenant la methode public void castRays() qui localise la position de l'observateur dans la triangulation puis lance les rayons necessaires au rendu de la vue. pour chaque rayon lance, on reportera la distance de l'observateur au premier point d'intersection avec une arete de contrainte. En cas d'absence d'intersection (i.e. quand castRay retourne null), on reportera la valeur -1. Attention : pour le calcul de la distance n'utilisez pas la methode distanceToSegment, qui calcule en fait une autre quantite, a savoir la distance de l'observateur a l'arete de contrainte intersectee. Le resultat de la methode castRays sera stocke sous forme d'un tableau de distances a viewSize entrees, une pour chaque chaque rayon lance. Le tableau se nomme distancesToObstacles dans la classe RayCast.

L'ensemble des champs stockes dans la classe pour le lancer de rayons est defini et explicite au debut de la classe. Pour implementer la methode castRays vous aurez plus precisement besoin des champs suivants :
Ces variables sont deja initialisees, vous n'avez donc pas a vous preoccuper des valeurs a leur donner. Pour information, elles valent 600 pixels pour la largeur de l'ecran, et 45 degres d'angle total de vision (ce qui est standard dans ce genre de jeu, un angle plus grand impliquant une plus forte distortion et risquant de rendre l'utilisateur malade). Quant a l'observateur, il est situe initialement au point (-1.5, 1.2) et son regard est oriente a -45 degres (i.e. en diagonale en bas a droite). 

Note importante : quand on genere la scene vue par l'observateur, on fait l'hypothese que tous les rayons lances sont paralleles les uns aux autres. De ce fait, quand on regarde un mur de face, la hauteur du mur ne diminue pas en s'ecartant de l'axe de vue. Or, du fait qu'on lance des rayons circulairement, on introduit une distortion mesuree par le cosinus de l'angle entre la direction du rayon et l'axe de vue. Dans votre code il faudra donc compenser la distortion en multipliant la distance calculee par le cosinus de cet angle.

2. Rendu de la scene vue par l'observateur

Telechargez maintenant le fichier RayCastWindow.java, qui contient le squelette de la classe RayCastWindow. Cette classe ouvre une fenetre graphique, dans laquelle sa methode public void paint(Graphics graphics) doit generer la scene vue par l'observateur. C'est cette methode qu'il vous faut maintenant completer. Notez que pour eviter le scintillement nous utilisons un double buffer, donc vous devez absolument utiliser la variable bufferGraphics et non la variable graphics pour le dessin. Actuellement la methode paint le sol et le ciel dans le double buffer, puis il copie ce dernier d'un coup sur l'ecran. Il vous reste a peindre les murs au milieu. Pour cela vous scannerez le tableau distancesToObstacles calcule precedemment dans la classe RayCast, et pour chaque entree vous genererez un segment vertical d'abcisse l'indice de l'entree dans le tableau, et de longueur l'inverse de la distance. Le facteur d'echelle a appliquer a la longueur du segment est donne par le champ sceneZoom de la classe RayCastWindow. Enfin, la position verticale relative du segment doit etre 1/3 en-dessous de l'horizon (stocke dans le champ horizon) et 2/3 au-dessus.

Pour tester votre code, commentez les lignes suivantes dans la methode main de la classe RayCast :
Map map = new Map(r);
Collection<TriangulationDSFace_2<Point_2>> facesDel = r.del.finiteFaces();
LinkedList<Point_2[]> trianglesDel = new LinkedList<Point_2[]>();
for (TriangulationDSFace_2<Point_2> f : facesDel)
	trianglesDel.add(new Point_2[]{f.vertex(0).getPoint(), f.vertex(1).getPoint(), f.vertex(2).getPoint()});
Collection<HalfedgeHandle<Point_2>> cEdgesDel = r.del.constraintEdges();
LinkedList<Point_2[]> cSegmentsDel = new LinkedList<Point_2[]> ();
for (HalfedgeHandle<Point_2> e : cEdgesDel)
	cSegmentsDel.add(new Point_2[]{e.getVertex(0).getPoint(), e.getVertex(1).getPoint()});
map.addTriangles(trianglesDel);
map.addFatSegments(cSegmentsDel);
et decommentez celle-ci :
RayCastWindow f = new RayCastWindow (r);
Si tout se passe bien vous, devriez maintenant voir apparaitre la scene telle que vue par le joueur, avec a peu pres le meme rendu que dans la figure 2.

3. Plaquage de texture

Nous allons maintenant ameliorer le rendu en plaquant une texture sur les murs. Telechargez tout d'abord le fichier de texture stone_wall.jpg, puis enlevez les commentaires a la ligne 
textureImg = ImageIO.read(new File(textureFileName));
du constructeur de la classe RayCastWindow. Ainsi votre code chargera l'image de la texture dans le champ textureImg de la classe RayCastWindow, ou bien il generera une exception si le fichier n'est pas present.

Pour plaquer la texture, il suffit de remplacer dans la methode paint de la classe RayCastWindow l'affichage des segments verticaux : au lieu d'afficher un segment uni, il faut afficher un segment pris dans la texture (pour cela vous pourrez afficher le segment pixel par pixel). Il faut faire attention a deux choses :
Si vous avez bien suivi les consignes ci-dessus, vous devez obtenir un resultat similaire a celui-ci :

Rendu avec texture


Ce resultat n'est pas acceptable pour au moins trois raisons :
Ces phenomenes ont une meme cause : le decalage dans la texture pour afficher un segment donne est toujours calcule par rapport au bord gauche de la fenetre de rendu, au lieu de l'etre par rapport au bord gauche du mur ou se trouve le segment. Pour y remedier, dans la methode castRays de la classe RayCast vous devez completer egalement le tableau distancesToObstaclesBound qui code, pour chaque rayon lance, la distance du point d'intersection au sommet de l'arete intersectee le plus a gauche dans le champ de vision de l'observateur. Ensuite, dans la methode paint de la classe RayCastWindow il vous suffit de calculer pour chaque abcisse le decalage dans la texture correspondant a la distance au bord gauche du mur ou votre segment se trouve. Ici encore une mise a l'echelle s'impose, en multipliant la distance au bord gauche par la valeur textureScale stockee dans la classe RayCastWindow.

Le resultat a obtenir est illustre ci-dessous, ou l'on voit d'une part que la texture ne se distort plus verticalement, et d'autre part que les jointures entre murs contigus sont maintenant bien visibles du fait qu'en changeant de mur le decalage dans la texture change egalement :
 
Plaquage de texture reussi