Ceci est la version imprimable de Les moteurs de rendu des FPS en 2.5 D.

Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.

Les moteurs de rendu des FPS en 2.5 D

Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Les_moteurs_de_rendu_des_FPS_en_2.5_D

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

L'historique des moteurs de FPS

Dans les années 2000, le FPS a subit de nombreuses transformations. Des Fast-FPS d'antan, nerveux et aux maps non-linéaires et "labyrinthiques", ont été progressivement passé à des jeux plus lents, plus scénarisés, plus scriptés, aux maps plus linéaires. Sans doute que l'arrivée de la 3D a entrainé beaucoup de transformations dans le doamine du JV, le FPS a lui aussi été marqué par l'évolution technologique.

Mais les FPS datant d'avant l'arrivée de la 3D ont marqué leur époque pour leur gameplay très nerveux, très bourrin, avec une grande variété d'armes et de déplacements, et des maps complexes et non-linéaires, qu'on ne retrouve plus dans les jeux vidéos d'aujourd'hui. C'en est au point où les FPS d'antan sont actuellement appelés des Boomer-shooters, terme quelque peu cavalier auquel nous préférerons le terme de Fast-FPS, en opposition aux Slow-FPS d'aujourd'hui. Les fast-FPS, aussi appelés Boomer-FPS, regroupent de nombreuses sagas : les DOOM (sauf le 3), les Quake, les Unreal (sauf le 2), Duke Nukem en FPS, les Serious Sam, Heretic/Hexen, Marathon, Tribes, etc.

L'histoire du FPS est intimement lié à celle des moteurs graphiques. L'invention des premiers FPS va de pair avec la création des premiers moteurs capables de rendre respectivement de la 2.5D et ensuite de la 3D. Après tout, difficile de faire de la vue subjective si l'on ne sait pas effectuer un rendu en 3D en temps réel. La technologie a donc joué un rôle déterminant au début du FPS. Et nous allons étudier les moteurs de ces vieux jeux en 2.5D.

Un apercu des moteurs de jeux de l'époque

Les premiers FPS utilisaient des moteurs qui ne sont totalement en 3D, mais sont plus des jeux en 2,5 D, à savoir qu'ils mélangent des éléments purement 2D, avec un rendu 2D simule un rendu 3D. L'illusion de la 3D est rendu par des techniques assez diverses, dont nous parlerons dans les prochains chapitres. Pour résumer, il y a en gros deux techniques principales : le raycasting et le portal rendering. Les différents moteurs utilisent soit l'une soit l'autre, mais il arrive qu'ils utilisent les deux.

La grande famille des moteurs de rendu 2.5D des FPS est composée de plusieurs lignées. La première est celle des jeux IdSoftware, avec les moteurs des jeux Wolfenstein 2D et DOOM. Et contrairement à ce qu'on pourrait croire, les deux utilisent des moteurs très différents. Le premier moteur d'IdSoftware est celui de Wolfenstein 3D, mais aussi de ses prédécesseurs de la saga Catacomb (oui, Wolfenstein 3D n'est pas le premier FPS inventé, nous en reparlerons). Il n'a pas de nom, contrairement à son successeur, le moteur des jeux DOOM, appelé l'IdTech 1. Les moteurs de jeux suivants seront l'Idtech 2, 3, 4, respectivement utilisées pour Quake 1/2, puis Quake 3, et enfin DOOM 3. Bien qu'ils portent des noms similaires, ce sont des moteurs indépendants, batis sur des fondations totalement différentes. Le code source de tout ces moteurs a été rendu public, on sait comment ils fonctionnent.

Moins connu, le moteur Build a été utilisé pour les jeux de 3D Realms : Duke Nukem 3D, Blood, Shadow Warrior, mais aussi les jeux de la saga WitchHaven. Quelques jeux indés récents sont développés sur ce moteur, notamment le jeux Ion Fury développé par les anciens programmeurs de Duke Nukem 3D. Le code source a été rendu public, ce qui fait qu'on sait comment fonctionne le moteur. Il utilise la technique du portal rendering, dans sa forme la plus simple. Il n'implémente pas d'optimisations comme l'usage d'un BSP, comme le fait un DOOM pourtant sorti avant lui. Il est donc moins optimisé que DOOM, mais cela n'a pas posé problème car les jeux Build sont sortis quelques années après DOOM, dans une période où la technologie évoluait très vite et où les processeurs devaient très rapidement plus puissants.

Moins connu, il faut aussi citer les moteurs d'autres jeux plus confidentiels de l'époque. Et commençons par les trois jeux de la saga Marathon, développés par Bungie (les développeurs de Halo), qui disposaient de leur propre moteur de jeux. Les trois jeux sont sortis sur Macintosh, et n'étaient pas compatibles avec Windows. De là, on peut rapidement deviner qu'ils utilisaient un moteur de jeu fait maison, sur lequel on ne sait malheureusement pas grand chose. Le moteur était cependant assez puissant et avec beaucoup de fonctionnalités : support des escaliers, d'une gestion de la hauteur, plafonds et sols de hauteur variable, des ascenseurs, etc. Il était aussi possible d'avoir plusieurs pièces superposées.

La société Lucas Art, connue pour ses jeux Point'click, a développé deux FPS de son temps. Le premier est le jeu Star Wars : Dark Forces dans lequel on incarne un soldat de la résistance dans l'univers de Star Wars, le second est le FPS Outlaws se passant dans un univers de Western. Les deux jeux utilisaient un moteur de jeu fait maison, appelé le Jedi engine. Ce furent les deux seuls jeux à utiliser ce moteur, Lucas Arts ayant abandonné les FPS par la suite. LE fait que Outlaws soit sorti alors que Quake était déjà sorti n'a pas aidé ses ventes, la 3D venait d'arriver, il n'y avait plus besoin d'un rendu en 2.5D. Le moteur a été abandonné après cela. Le code source du moteur n'est pas disponible et n'a jamais été rendu public, mais quelques fans de ces jeux ont effectué de la rétro-ingénierie pour retrouver un moteur équivalent. Le moteur de jeu utilise la technique du portal rendering, la même que le moteur Build.

Les jeux de la saga Ultima Underwolrd étaient des jeux utilisant un moteur en quasi-3D. Il s'agit d'une série de FPS-RPG sortis un tout petit peu après Wolfenstein 3D. Des tentatives de reverse enginnering du moteur sont encore en cours. La seule chose que l'on sait est que les niveaux du jeu sont stockés en 2D, avec une organisation basée sur des tiles, mais que cette représentation était utilisée comme base pour un rendu en pure 3D. D'après les dires de Doug Church, un des programmeurs du jeu, voici comment fonctionnait ce moteur :

" However, let me second what Dan Schmidt said in the guestbook back in August about the description of the UW engine you guys have up on the page. Namely, UW _was not_ a raycasting engine. While UW did use a tilemap to store the world, that has nothing to do with the rendering model. In general, I'd suggest that the "world rep" and "rendering engine" be considered separate things when discussing game technology, because they very often are. In UW, we had a tile based world. The renderer used the tiles to explore the view cone and do a high level cull operation. From the list of visible tiles, we generated full 3d polygons, in the traditional XYZ sense, and handed them off to a rendering back end and rendered each poly in 3d as is. That is also how the 3d models like the ankh shrines or benches were done, which clearly aren't "raycast" model 3d objects. Now, in practice, many of our 3d primitives did things like normal checks first, and then chose which algorithim to rasterize with based on scale/normal/etc of the surface being rendered."

Source : ultima Underworld Viewer

Enfin, il faut aussi citer quelques FPS sortis sur Amiga, qui utilisaient leur propre moteur de rendu. Des jeux comme Alien Breed 3D et quelques autres étaient dans ce genre. Le code machine de ces jeux est disponible et a été rendu public, mais peu d'informations sont connues à ce jour sur le fonctionnement de leur moteur.

Paradoxalement, il a existé des moteurs de jeux en 3D avant même que les premiers moteurs de jeu en 2.5D n'apparaissent. Il faut notamment noter le Freescape 3D engine, datant de quelques années avant le premier moteur d'IdSoftware ! C'était un moteur de jeu entièrement en 3D.

Liste des moteurs de jeu en 2.5D et en 3D utilisés par les FPS au cours du temps.

Pour résumer, beaucoup de FPS en 2.5D ont existé et chaque entreprise utilisait plus ou moins son propre moteur maison. Le moteur de Wolfenstein 3D a été utilisé pour quelques productions, le moteur de DOOM aussi, le moteur Build n'a été utilisé que pour trois jeux, les autres moteurs n'ont été utilisés que par leur entreprise créatrice.

id Software : Wolfenstein, DOOM, Quake

id Software est une entreprise de jeux vidéo crée en 1991, par ses quatre membres fondateurs : John Carmack, John Romero, Tom Hall, Adrian Carmack (pas de liens familiaux avec John Carmack). Les deux premiers membres, les plus connus, ont décidé de quitter l'entreprise SoftDisk dans laquelle ils codaient des jeux vidéo, pour fonder leur propre studio de développement. Ils recrutèrent alors les deux autres membres. Le récit de la vie de cette entreprise, de la création jusqu'à environ 1996, est raconté dans le livre "Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture", publié en 2004, qui est la référence pour tout fan des jeux de cette entreprise.

John Carmack est le créateur des moteurs graphiques utilisés dans Wolfenstein 3D, DOOM, Quake et bien d'autres. Il est le programmeur principal, même si les autres membres étaient doués en programmation (Romero a appris à coder en autodidacte et a participé activement au développement de tous les jeux id Software. Il est reconnu pour être capable d'implémenter des idées autrefois publiées dans la littérature académique en rendu graphique, d'une manière qui fait que ces algorithmes peuvent tourner en temps réel. Romero est le level-designer principal des jeux, aux côtés de Tom Hall, Sandy Petterson, et d'autres membres qui ont participé à la création des jeux d'id Software.

Le tout premier jeu en vue subjective temps-réel d'id Software était Hovertank, un jeu de Tank en vue subjective qu'on trouve facilement en abandonware. Il a été le premier jeu à utiliser ce genre de rendu, et le moteur était très simpliste. Le gameplay est franchement pauvre et le jeu est clairement une démo technologique, qui permet de montrer ce que peut faire un moteur de raycasting simple. Il n'y a même pas de gestion des textures, chaque mur, sol et plafond a une couleur unie, sans détails.

Il a ensuite été amélioré pour le jeu Catacomb 3D et ses suites, qui sont restés confidentiels. Le moteur a été amélioré pour supporter des textures, rendant le jeu beaucoup plus agréable à l'oeil que son prédécesseur. Hé oui, Wolfenstein 3D n'était pas le premier FPS, contrairement à ce qu'on pourrait croire. Catacomb 3D eu trois suites, The Catacomb: Abyss est sorti en même temps que Wolfenstein 3D, The Catacomb: Armageddon est sorti la même année, The Catacomb: Apocalypse est sorti en 1993, après W3D.

Wolfenstein 3D, est souvent pris à tord comme le premier FPS, car il a marqué les esprits, bien plus que les Catacomb, qui sont restés très confidentiels. Après la sortie de Wolfenstein 3D, d'autres entreprises ont utilisé ce moteur, avec l'aval d'id Software et moyennement rémunération. En somme, dès le début du FPS, on avait ce système où un moteur de jeu créé par une entreprise était vendu à d'autres pour que ces dernières créent leurs propres jeux vidéos avec. Le moteur de Wolfenstein 3D a été réutilisé dans de nombreuses productions, dont voici la liste :

Blake Stone: Aliens of Gold
Blake Stone: Planet Strike
Corridor 7: Alien Invasion
Cybertag
Hellraiser
Operation Body Count
Rise of the Triad
Super 3D Noah's Ark

Beaucoup de ces jeux tombèrent dans l'oubli, parce qu'ils étaient de véritables catastrophes vidéoludiques à la qualité plus que mauvaise. De plus, l'arrivée de DOOM l'année suivante fit que le moteur de Wolfenstein 3D était devenu trop limité et obsolète (après seulement un an...). Seuls baroud d'honneur, les jeux "ShadowCaster" et "In Pursuit of Greed", de Raven Software, utilisaient une version améliorée du moteur de Wolfenstein 3D. Le moteur ajoutait un éclairage limité, des murs de taille variable, des sols pentus et des sols/plafonds texturés.

Wolfenstein 3D a ensuite été suivi par DOOM, puis par DOOM 2, deux jeux d'exception, dont le moteur était complétement différent de celui de Wolfenstein 3D. Le moteur de W3D utilisait une technique particulière de raycasting, mais pas le moteur de DOOM. Le développement de l'IdTech 1, le moteur de DOOM 1 et 2, a commencé peu après la sortie de Wolfenstein 3D et son histoire est assez intéressante.

John Carmack pensait à la base créer un moteur basé sur la technique dite du portal rendering, comme le fera Duke Nukem 3D quelques années plus tard. Mais John Romero, mappeur de l'équipe joua un mauvais tour à Carmack. Une des maps qu'il avait conçu ramait tellement que Carmack du retourner au travail et trouver une optimisation pour résoudre le problème. En parallèle de son travail sur le moteur de DOOM, Carmack travaillait en parallèle sur le portage de Wolfenstein 3D sur Super Nintendo. Mais la machine n'était même pas assez puissante pour faire tourner le jeu. Aussi, Carmack fi quelques recherches pour trouver une solution. Il découvrit dans plusieurs papiers de recherche la technique dite du BSP (Binary Space Partitioning), et décida de réécrire complétement le moteur de Wolfenstein 3D avec cette technique. La technique du raycasting était passée à la trappe au profit d'un système de portal rendering amélioré. Et c'est cette technique qui a été utilisée pour DOOM !

Les source ports

Les généralités : le rendu 2D

Les tout premiers First Person Shooters, comme DOOM, Wolfenstein 3D, et autres jeux des années 1990 avaient un rendu relativement simpliste et anguleux. Et contrairement à ce que voient nos yeux, le rendu n'était pas toujours en 3D. Le moteur de ces jeux disposait de deux méthodes de rendu assez simples :

un rendu purement 2D, pour le HUD, l'arme, les ennemis et les items ;
un rendu en 2.5D ou en 3D pour les murs.

Quelques moteurs utilisaient un moteur en 3D, avec rendu d'objets en polygones, comme le moteur d'Ultima Underworld, mais ils sont plus rares. Le rendu des murs est de loin la portion la plus compliquée du moteur. Aussi, nous allons d'abord parler du reste dans ce chapitre. Cependant, nous verrons que le rendu s'effectue ne plusieurs étapes, qui se font dans un ordre différent de celui du chapitre. L'ordre de ce rendu s'explique assez facilement quand on connait comme est effectué le rendu d'un jeu en 2 pure. Et je précise bien en 2D pure, car le principe de la 2.5D est assez similaire.

La base d'un rendu en pure 2D, comme un jeu Mario, superpose des images 2D pré-calculées les unes au-dessus des autres. Par exemple, on peut avoir une image pour l’arrière-plan (le décor), une image pour le monstre qui vous fonce dessus, une image pour le dessin de votre personnage, etc. On distingue généralement l'image pour l'arrière-plan, qui prend tout l'écran, des images plus petites qu'on superpose dessus et qui sont appelées des sprites. Le rendu des sprites doit s'effectuer de l'image la plus profonde (l'arrière-plan), vers les plus proches (les sprites qui se superposent sur les autres) : on parle d'algorithme du peintre.

Dans un FPS en 2.5D, l'idée est de calculer séparément une image pour l'environnement, le décor, une image avec les ennemis, une image avec l'arme en avant-plan et une autre image sur le HUD. Le HUD est à l'avant-plan et prédomine tout le reste, ce qui fait qu'il doit être dessiné en dernier. L'arme est située juste après le HUD, elle est tenue par le personnage et se situe donc devant tout le reste : elle est dessinée en second. Pour l'environnement et les ennemis, tout dépend de la pièce dans laquelle on est et de la position des ennemis. Mais il est plus pratique de rendre le décor et de dessiner les ennemis dessus, l'environnement servant d'arrière-plan.

Le rendu s'effectue donc comme ceci :

d'abord le rendu des murs, du plafond et du sol ;
puis le rendu des ennemis et items ;
puis le rendu de l'arme ;
et enfin le rendu du HUD.

Le rendu du HUD

Le HUD est simplement rendu en 2D, car le HUD est fondamentalement une structure en 2D. Il est mis à jour à chaque fois que le joueur tire (compteur de munitions), perd de la vie, prend de l'armure, etc. Il est idéalement rendu à la toute fin du rendu, son sprite étant superposé à tout le reste. La raison à cela est que le HUD est plein, et non transparent. J'explique.

Un HUD de FPS normal ressemble à ce qu'il y a dans le screenshot à droite : quelques chiffres et icônes superposées sur le reste du rendu. On voit l'icône pour la vie, sa valeur, idem pour l'armure et les munitions. Mais entre les icônes et les chiffres, on voit la scène, l'eau, la texture du sol, etc. Le HUD a donc des parties transparentes, dans le sens où seuls les chiffres et icônes sont visibles/opaques.

Mais dans Wolfenstein 3D, et dans d'autres jeux du même genre, on a la même chose que ce qui est illustré dans l'animation de droite. Le HUD est un gros rectangle qui prend tout le bas de l'écran. On peut bouger autant qu'on veut, le bas de l'écran associé au HUD reste le même. Le HUD n'a pas de transparence, les textures et l'environnement se se voient pas à travers. Avec cette contrainte, on peut dessiner le HUD et le reste de l'image séparément. Le HUD est donc rendu au tout début du rendu. Cela signifie aussi que l'image calculée est en réalité plus petite. Si le HUD prend 10% de l'écran, alors on a juste à dessiner les 90% restants. Sans cette contrainte, on doit calculer 100% de l'image, pour ensuite superposer un HUD partiellement transparent.

Le rendu de l'arme

Le rendu de l'arme est assez particulier. Tous les jeux vidéos, même récents, utilisent un rendu séparé pour l'arme et le reste du monde. Pour les jeux en 2.5D, c'est parce que c'est plus simple de procéder ainsi. Pour les jeux en 3D, la raison est que cela évite de nombreux problèmes. Si l'arme était en 3D et était calculée comme le reste du rendu, on aurait des problèmes du genre : l'arme passe à travers les murs quand on se rapproche trop d'eux. Il y a bien des exceptions, mais elles sont assez rares.

Le tout est bien expliqué dans cette vidéo Youtube sur la chaine de "Scrotum de Poulpe" (ca ne s'invente pas, je sais) :

Le "problème" des mains dans les FPS.

Sur les anciens jeux comme Wolfenstein 3D, DOOM, Duke Nukem et autres, l'arme utilise la technique des sprites qui sera vu dans la section suivante.

Le rendu des ennemis et items

Les objets sont rendus avec de simples images placées au-dessus du décor, qui ne sont ni plus moins que des sprites. Le meilleur moyen pour s'en rendre compte étant de tourner autour d'un objet : la forme de l'objet ne change pas du tout. Les objets sont de simples pancartes sur lesquelles on plaque une image.

Les ennemis sont généralement animés : ils bougent, ils sont "stun" quand on tire dessus, ils peuvent tirer des projectiles, ils ont une animation de mort, etc. Et il y a une animation pour chaque action. Pareil pour certains objets de l'environnement : pensez aux fameux barils explosifs qui explosent quand on tire dessus ! Le tout est illustré ci-contre, avec quelques exemples. Reste à la simuler avec des sprites. Pour cela, rien de plus simple : chaque animation est toujours la même, elle correspond à une succession de sprites qui est toujours identique. Il suffit de dérouler la bonne succession de sprite et le tour est joué !

L'ordre de dessin des sprites

Le rendu des sprites se fait une fois que l'environnement a été dessiné, c'est à dire après les murs, le sol et les plafonds. Les sprites des ennemis et items sont donc superposé sur l'arrière-plan calculée par l'étape précédente. Cependant, certains sprites peuvent se recouvrir : il faut impérativement que le sprite le plus proche soit affiché au-dessus de l'autre. Pour cela, les sprites sont superposés suivant l'algorithme du peintre : on commence par intégrer les sprites des objets les plus lointains dans l'image, et on ajoute des sprites de plus en plus proches. Faire cela demande évidemment de trier les sprites à rendre en fonction de la profondeur des objets/ennemis dans le champ de vision (qu'il faut calculer).

Le cas le plus simple est le sprite de l'arme, qui est dessiné en tout dernier, car il est le plus proche du joueur.

Un autre point est qu'il ne suffit pas de superposer un sprites d'item ou d'ennemi pour que cela fonctionne. Cela marche dans un jeu en pure 2D, mais la 3D impose de gérer la profondeur. Rappelons que plus un objet/ennemi est loin, plus il nous parait petit, plus il est petit à l'écran. Les sprites doivent donc être mis à l'échelle suivant la distance : rapetissés pour les ennemis lointains, et zoomés pour les ennemis proches. Pour cela, on utilise une relation mathématique très simple : la loi de Thalès.

La mise à l'échelle des sprites

Dans un jeu vidéo, et comme dans le monde réel, si on multiplie la distance d'un objet par deux, trois ou quatre, celui-ci devient respectivement deux, trois ou quatre fois plus petit. Dit autrement, un objet de hauteur H situé à une distance D aura une hauteur perçue identique à celle d'un objet de hauteur double/triple/quadruple situé deux/trois/quatre fois plus loin. En clair, pour un objet de hauteur $h_{1}$ , situé à une distance $d_{1}$ , et un autre objet de hauteur $h_{2}$ et de distance $d_{2}$ , les deux auront la même hauteur perçue :

{\frac {h_{1}}{d_{1}}}={\frac {h_{2}}{d_{2}}}

Tout sprite est une image, avec une résolution. Elle a un certain nombre de pixels à l'horizontale, un autre à la verticale. La taille verticale en pixel du sprite dépend du sprite, mettons qu'elle est égale à 50 pixels de large pour 60 de haut. Il s'agit de la taille réelle du sprite déterminée lors de la conception du jeu (aussi bien en vertical et horizontal). Nous allons noter sa taille en vertical comme suit : $T_{s}$ .

Cette taille correspond à une distance précise. Pour un sprite 50 pixels de large pour 60 de haut, le sprite aura la même taille à l'écran à une certaine distance, que nous allons noter $D_{s}$ .

Maintenant, d'après la relation vue plus haut, on peut calculer la taille affichée à l'écran du sprite, notée H. Pour cela, il suffit de connaitre la distance D, et on a la relation :

{\frac {T}{D}}={\frac {T_{s}}{D_{s}}}

On peut la reformuler comme suit :

T=D\times {\frac {T_{s}}{D_{s}}}

Quelques multiplications, et le tour est joué. Le terme ${\frac {T_{s}}{D_{s}}}$ peut même être mémorisé à l'avance pour chaque sprite, ce qui économise quelques calculs.

Le moteur de Wolfenstein 3D

Le moteur de Wolfenstien utilisait toutes les techniques du chapitrre précédent pour rendre ses graphismes. Mais il nous reste à voir comment il faisait pour rendre les murs, le plafond et le sol, et les environnements en général. Tout le reste est réalisé avec des sprites, mais pas l'environnement en 2.5D.

Le ray-casting : l’algorithme général

Pour les murs, la 3D des murs est simulée par un mécanisme différent de celui utilisé pour les objets et ennemis. Le principe utilisé pour rendre les murs s'appelle le ray-casting. Il s'agit d'un rendu foncièrement différent de celui des sprites. Formellement, le ray-casting est une version en 2D d'une méthode de rendu 3D appelée le lancer de rayons. Mais avant de détailler cette méthode, parlons de la caméra et des maps de jeux vidéo.

La map et la caméra

Une map dans un FPS en 2.5D est un environnement totalement en deux dimensions, dans lequel le moteur d’un jeu vidéo place des objets et les fait bouger. Cette scène est, en première approche, un simple rectangle. Un des coins de ce rectangle sert d’origine à un système de coordonnées : il est à la position (0, 0), et les axes partent de ce point en suivant les arêtes.

Dans cette scène 2D, on place des murs infranchissables, des objets, des ennemis, etc. Les objets sont placés à des coordonnées bien précises dans ce parallélogramme, pareil pour les murs. Le fait que la scène soit en 2D fait que la carte n'a qu'un seul niveau : pas d'escalier, d'ascenseur, ni de différence de hauteur. Du moins, sans améliorations notables du moteur graphique. Il est en fait possible de tricher et de simuler des étages, mais nous en parlerons plus tard. Pour donner un exemple, voici un exemple de map dans le jeu libre FreeDOOM :

Outre les objets proprement dit, on trouve une caméra, qui représente les yeux du joueur. Cette caméra est définie par :

une position ;
par la direction du regard (un vecteur) ;
le champ de vision (un angle) ;
un plan qui représente l'écran du joueur.

L'algorithme de raycasting : du lancer de rayon simplifié

Le ray-casting colorie une colonne de pixels à la fois sur l'écran. Pour cela, on émet des lignes droites, des rayons qui partent de la caméra et qui passent chacun par une colonne de pixel de l'écran.

Illustration de l'agorithme de Ray-casting.

Les rayons font alors intersecter les objets, les items, mais aussi les murs, comme illustré ci-contre. Le moteur du jeu détermine alors, pour chaque rayon, quel est le point d'intersection le plus proche. Les coordonnées du point d'intersection sont calculées à l'aide d'un algorithme spécialisé, qui varie selon la méthode de raycasting utilisée.

Une fois le point d'intersection connu, on peut alors déterminer la distance de l'ennemi/item/mur. Rien de plus simple : il suffit de récupérer la coordonnée de ce point d'intersection, celle du joueur, et d'appliquer le théorème de Pythagore. Si le joueur est à la position de coordonnées (x1 ,y1), et l'intersection aux coordonnées (x2, y2), la distance D se calcule avec cette équation :

D=(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}

La position du joueur est connue : elle est initialisée par défaut à une valeur bien précise au chargement de la carte (on ne réapparait pas n'importe où), et est mise à jour à chaque appui sur une touche de déplacement. On peut alors calculer la distance très simplement. Une fois la distance connue, on peut déterminer la taille des sprites, des murs, et de tout ce qu'il faut afficher.

Le rendu de l'environnement : murs, sol et plafond

Le rendu du sol et des plafonds est assez simple et est effectué avant tout le reste. Le sol a une couleur bien précise, pareil pour le plafond. Elle est la même pour tout le niveau, elle ne change pas quand on change de pièce ou qu'on se déplace dans la map. Le sol et le plafond sont dessinés en premier, et on superpose les murs dessus. Le dessin du sol et du plafond est très simple : on colorie la moitié haute de l'écran avec la couleur du plafond, on colorie le bas avec la couleur du sol, et on ajoute les murs ensuite.

Passons maintenant au rendu des murs. Et il faut maintenant préciser que le rendu est simplifié par plusieurs contraintes. La première est que l'on part du principe que tous les murs ont la même hauteur. En conséquence, le sol et le plafond sont plats, les murs font un angle de 90° avec le sol et le plafond. La seconde contrainte est que le regard du joueur est à une hauteur fixe au-dessus du sol, généralement au milieu de l'écran. Cela garantit que le plafond est situé au sommet de l'écran, le sol est en bas de l'écran, et les murs sont au milieu. Mais cela implique l'impossibilité de sauter, s'accroupir, lever ou baisser le regard. À partir de ces contraintes et de la carte en 2D, le moteur graphique peut afficher des graphismes de ce genre :

Le mur est centré au milieu de l'écran, vu que le regard est au milieu de l'écran et que tous les murs ont la même hauteur. Par contre, la hauteur du mur perçue sur l'écran dépend de sa distance, par effet de perspective. C'est comme pour les sprites : plus ils sont loin, plus ils semblent petits. Et bien plus un mur est proche, plus il paraîtra « grand ». La formule pour calculer la taille d'un mur à l'écran est la même que pour les sprites : on utilise le théorème de Thalés pour calculer la taille du mur à l'écran.

Vu qu'on a supposé plus haut que la hauteur du regard est égale à la moitié de la hauteur d'un mur, on sait que le mur sera centré sur l'écran. Les pixels situés au-dessus de cet intervalle correspondent au plafond : ils sont coloriés avec la couleur du plafond, souvent du bleu pour simuler le ciel. Les pixels dont les coordonnées verticales sont en dessous de cet intervalle sont ceux du sol : ils sont coloriés avec la couleur du sol.

La taille du mur est calculée pour chaque colonne de pixel de l'écran. Ainsi, un même mur vu d'un certain angle n'aura pas la même taille perçue : chaque colonne de pixel donnera une hauteur perçue différente, qui diminue au fur et à mesure qu'on s'éloigne du mur.

La correction d'effet fisheyes

L'algorithme utilisé ci-dessus donne ce genre de rendu :

Le rendu est assez bizarre, mais vous l'avez peut-être déjà rencontré. Il s'agit d'un rendu en œil de poisson (fish-eye), assez désagréable à regarder. Si ce rendu porte ce nom, c'est parce que les poissons voient leur environnement ainsi. Et certaines caméras ou certains appareils photos peuvent donner ce genre de rendu avec une lentille adaptée.

Pour comprendre pourquoi, imaginons que nous regardions un mur sans angle, le regard à la perpendiculaire d'un mur plat. Les rayons du bord du regard parcourent une distance plus grande que les rayons situés au centre du regard. Si on regarde un mur à la perpendiculaire, les bords seront situés plus loin que le centre : ils paraîtront plus petits. Prenons un joueur qui regarde un mur à la perpendiculaire (pour simplifier le raisonnement), tel qu'illustré ci-dessous : le rayon situé au centre du regard sera le rayon rouge, et les autres rayons du champ de vision seront en bleu.

Pourtant, nous sommes censés voir que tous les points du mur sont situés à la même hauteur. C'est parce que les humains ont une lentille dans l'œil (le cristallin) pour corriger cet effet d'optique, lentille qu'il faut simuler pour obtenir un rendu adéquat.

Pour comprendre quel calcul effectuer, il faut faire un peu de trigonométrie. Reprenons l'exemple précédent, avec un regard perpendiculaire à un mur.

Or, vous remarquerez que le rayon bleu et le rayon rouge forment un triangle rectangle avec un pan de mur.

Pour éliminer le rendu en œil de poisson, les rayons bleus doivent donner l'impression d'avoir la même longueur que le rayon rouge. Dans un triangle rectangle, le cosinus de l'angle a est égal au rapport entre le côté adjacent et l'hypoténuse, qui correspondent respectivement au rayon rouge et au rayon bleu. On en déduit qu'il faut corriger la hauteur perçue en la multipliant par le cosinus de l'angle a.

Les textures des murs

Le ray-casting permet aussi d'ajouter des textures sur les murs, le sol, et le plafond. Comme dit précédemment, les murs sont composés de pavés ou de cubes juxtaposés. Une face d'un mur a donc une hauteur et une largeur. Pour se simplifier la vie, les moteurs de ray-casting utilisent des textures dont la hauteur est égale à la hauteur d'un mur, et la largeur est égale à la largeur d'une face de pavé/cube.

En faisant cela, chaque colonne de pixels d'une texture correspond à une colonne de pixels du mur sur l'écran (et donc à un rayon lancé dans les étapes du dessus).

Reste à trouver à quelle colonne de texture correspond l'intersection avec le rayon, et la mettre à l'échelle (pour la faire tenir dans la hauteur perçue). L'intersection a comme coordonnées x et y, et est située soit sur un bord horizontal, soit sur un bord vertical d'un cube/pavé. On sait que les murs, et donc les textures, se répètent en vertical et en horizontal toutes les lmur (largeur/longueur d'un mur).

En conséquence, on peut déterminer la colonne de pixels à afficher en calculant :

le modulo de x avec la longueur du mur, si l'intersection coupe un mur horizontal ;
le modulo de y avec la largeur d'un mur si l'intersection coupe un mur vertical.

Le raymarching de Wolfenstein 3D

Le ray-casting est très gourmand en calculs, surtout pour les ordinateurs de l'époque. Aussi, pour Wolfenstein 3D, la map a quelques contraintes pour rendre les calculs d'intersection plus simples. Déjà, la carte est un labyrinthe, avec des murs impossibles à traverser. Les murs sont fixes, on ne peut pas les changer à la volée.

Mais surtout : tout mur est composé en assemblant des polygones tous identiques, généralement des carrés de taille fixe. La totalité des lignes du niveau qui délimitent les murs sont perpendiculaires, leurs semgnets sont tous orientés nord-sud ou ouest-est. Si elle respecte ces contraintes, on peut la représenter en 2D, avec un tableau à deux dimensions, dont chaque case indique la présence d'un mur avec un bit (qui vaut 1 si le carré est occupé par un mur, et 0 sinon).

De telles contraintes permettent de fortement simplifier l’algorithme de raycasting, au point où il en est méconnaissable. Sans cela, Wolfenstein 3D n'aurait pas réussit à tourner sur les PCs de l'époque. Dans ce qui suit, nous allons détailler l'algorithme général de raycasting, avant de voir comment il a été modifié pour Wolfenstein 3D.

L'algorithme de calcul d'intersection

En faisant ainsi, le calcul des intersections est grandement simplifié. L'idée est de partir de la position du joueur et de sauter d'une unité de distance. L'unité de distance est la largeur/longueur d'une case de la map, d'un carré. On part donc de la position du joueur et on se déplace d'une unité en suivant la direction du rayon : cela demande juste de faire une addition vectorielle. Là, on vérifie si le point se situe dans un mur ou non. Si c'est le cas, on calcule le position de l'intersection entre le rayon et le carré du mur en question. Si ce n'est pas le cas, on poursuit d'une unité supplémentaire.

Pour résumer, on avance pas par pas à partir de la caméra, et on s'arrête quand on est dans un mur. Cette idée est très simple, mais elle rate certaines intersections avec des géométries de murs un peu tordues. Aussi, le moteur de Wolfenstein 3D utilisait une autre méthode. Avec elle, les coordonnées du point d'intersection sont calculées à l'aide d'un algorithme nommé Digital Differential Analyser, décrit en détail dans ce lien :

Lode's Computer Graphics Tutorial, Raycasting.

L'application des textures

Les calculs pour appliquer des textures sont grandement simplifiés avec le raymarching. Pour se simplifier la vie, les moteurs de ray-casting utilisent des textures dont la hauteur est égale à la hauteur d'un mur, et la largeur est égale à la largeur d'une face de pavé/cube. En faisant cela, chaque colonne de pixels d'une texture correspond à une colonne de pixels du mur sur l'écran (et donc à un rayon lancé dans les étapes du dessus). La seule difficulté est de trouver à quelle colonne de texture correspond l'intersection avec le rayon, et la mettre à l'échelle (pour la faire tenir dans la hauteur perçue).

L'intersection a comme coordonnées x et y, et est située soit sur un bord horizontal, soit sur un bord vertical d'un cube/pavé. On sait que les murs, et donc les textures, se répètent en vertical et en horizontal toutes les lmur (largeur/longueur d'un mur). En conséquence, on peut déterminer la colonne de pixels à afficher en calculant :

le modulo de x avec la longueur du mur, si l'intersection coupe un mur horizontal ;
le modulo de y avec la largeur d'un mur si l'intersection coupe un mur vertical.

Sources

Pour en savoir plus sur les moteurs de ce jeu, je conseille vivement la lecture du Black Book rédigé par Fabien Sanglard, et ses articles de blog :

Le portal rendering

Jeux build, jedi engine.

Pour en savoir plus sur le build engine, je conseille fortement la lecture des articles du blog de Fabien Sanglard :

Le peu d'information publique vulgarisée sur le Jedi Engine est disponible via ce lien :

Dark Forces (DOS) Rendering, Part I

Le DOOM engine

Autres sources

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.