Le Projet Doom

L'algorithme de reperage des murs

Les "anciens" algos

En 3D il existe deux catégories d'algorithmes d'affichages : Les méthodes bourines (du style algorithme du peintre et Z-buffer), où l'on affiche presque tous les polygones à afficher (on se contente d'en suprimer quelques-uns à l'aide de quelques critères simples), et où on les affiches de façon à ce que seuls ceux se situant sur le devant de la scène soient visibles. Mais il y a aussi des méthodes plus fines, comme le ray-tracing et son dérivé le ray-casting (et la méthode que je vais vous expliquer et que l'on pourait appeler propagation triangulaire), où l'on passe beaucoup de temps à savoir quels seront les polygones visibles afin de n'afficher que ceux là...

Chaque méthode à ses avantages et ses inconvenients mais sur HP une méthode "bourine" n'est même pas envisageable tellement elle est gourmande en calcul (sur un ordinateur ça passe parce qu'il y a des cartes 3D qui gèrent très bien ces méthodes). Il nous faut donc employer une méthode fine.

A ce jour tous les dooms existants utilisent une méthode proche du ray-casting, qui est une adaptation du ray-tracing en 2D (c'est d'ailleurs la méthode utilisée dans le vrai Doom je crois). Cela consiste à construire un plan du niveau de jeu, et à tracer des rayons depuis le point de vision selon plusieurs angles, jusqu'à ce qu'on rencontre un mur. On sait alors quels murs sont visibles et à quelle position, il ne reste plus qu'à les afficher...

Mon algorithme : la propagation tiangulaire

Pour cela on n'utilise plus vraiment un plan, mais on divise le monde en triangles : chaque angle d'un mur est le sommet d'un triangle. Les cotés des triangles correspondent soit à des murs soit à des espaces vides. L'idée est que l'on part du triangle sur lequel est le joueur, et on cherche la ou les arêtes visibles. Si l'arête est un mur, on recupère ses coordonées et on l'affiche, sinon, on passe au triangle adjacent, et là encore on recherche les arêtes visibles...

Revenons au problème des triangles : suposons que l'on ait analysé le triangle ABC sur l'image précédente, et que l'on ai remarqué que l'arête BC est visible et ne correspond pas à un mur. On va alors chercher à savoir ce que l'on voit entre les points B et C (je rappelles qu'un point corresponds à l'angle d'un mur donc on sait que des murs ne sont pas loins de ces points). On s'interesse alors au triangle adjacent BCD. Dans le triangle BCD on connait déjà l'arête BC puisqu'on vient de la traverser, on va donc s'interesser aux arêtes BD et CD (le nom des arêtes n'a pas été choisi au hasard !). Appellons O le point de vision. Puisqu'on ne s'interesse qu'à ce qui est visible entre B et C, l'arête BD n'est visble que si le point D est à droite de la demi-droite [OB). Et de même l'arête CD n'est visible que si D est à gauche de la demi-droite [OC).

On peut remarquer au passage que cet algo permet de gérer facilement le clipping en x (c'est-à-dire qu'il permet de savoir quelles parties de murs tiennent dans l'écran horizontalement) : pour cela il suffit de rajouter deux points virtuels O₁ et O₂, et l'on sait alors qu'un point X est visible si et seulement si la demi-droite [OX) est à droite de [OO₁) et à gauche de [OO₂).

Dans l'image d'exemple, on voit donc que l'arête BC est visible, bien que B et C ne le sont pas puisqu'ils se situent respectivement à gauche de [OO₁) et à droite de [OO₂). On s'interesse donc au triangle BCD, et plus particulièrement aux arêtes BD et CD (on sait qu'il y en a au moins une des deux visible). Or D n'est pas visible, puisque à gauche de [OO₁). La seule arête visible est donc DC. On la traverse pour s'interesser au triangle CDE. Comme E est visible les deux arêtes DE et EC sont visibles, on va donc les traiter les unes après les autres. On s'interesse donc à DE, qui ouvre sur le triangle DEF, et F est visible (on notera que pour tester la visibilité on n'utilise plus [OO₂) mais [OE) ). Donc les arêtes DF et EF sont visibles. Comme elles correspondent à des murs, on les affiches. On revient à l'arête EC qu'on avait laissée de côté, et on regarde le triangle CEG, etc... Au final on trouve que EH, GH et CG sont visibles et correspondent à des murs, et on les affichera.

Calcul de la visibilité d'un point

Tout l'algo tourne donc autour de la question : "le point X est-il à gauche ou à droite de la demi-droite [OY) ?". Malheureusement cette question demande un calcul mathématique ou une approche géométrique coûteuse en temps de calcul... C'est ce qui me posait problème au départ. La solution que j'ai trouvé est basée sur les trois points suivants :

• D'une part je ne fait qu'un calcul par point au lieu de deux (alors qu'il y a deux tests par points).

• D'autre part le calcul que je fait est réutilisé plus tard pour l'affichage.

• Et finalement ce calcul est très rapide puisqu'il peut se faire en une 20aine d'instructions (moins de 200cycles car ce sont des intructions rapides).

Quel est ce calcul ? Eh bien il s'agit tout simplement de calculer l'abscisse (en pixels) du point à l'écran !!! C'est en fait un calcul très lourd (il faut faire quatre multiplications et une division), et c'est pour ça que je cherchais tout d'abord une autre solution, quand j'ai compris que c'était un calcul que je devais de toute manière faire pour l'affichage... Sauf que j'affiche moins de points que je n'en calcule, mais la différence n'est pas assez importante pour rendre l'algo inintéressant. J'ai de plus optimisé ce calcul. En voici le détail :

L'abscisse du point est connu par la projection du point (coordonnées 3D) sur l'écran (coordonées 2D). On utilise le fait que les rayons lumineux se propagent en ligne droite et le thèorème de Thalès pour trouver l'équation :

X_écran = (largeur de l'écran/2) * (X/Z) + (largeur de l'écran/2)

Où X est la distance du point par rapport à l'axe de vision (positif à droite, négatif à gauche), et Z la distance du point par rapport à l'axe orthogonal à l'axe de vision (positif devant, négatif derière). La largeur de l'écran étant constante (moi j'ai pris 128 pixels, ce qui simplifie les calculs et permet d'avoir 3 pixels libres pour afficher un indicateur quelconque), la multiplication est extrèmement simple. On notera aussi que cette formule correspond à un angle de vision de 45° de part et d'autre de l'axe de vision, ce qui corresponds à peu près au champ de vision humain et simplifie les calculs ;-)

Le premier problème qu'on rencontre est pour trouver X et Z. En effet on ne connait que X_P et Y_P, les coordonées du point dans la carte, X_O et Y_O les coordonées du point de vision dans la carte, et A l'angle que fait l'axe de vision avec l'horizontale de la carte (axe Ouest->Est). Pour ça on utilise les formules de rotation classiques :

X = (X_P - X_O) cos(A) - (Y_P - Y_O) sin(A)
Z = (X_P - X_O) sin(A) + (Y_P - Y_O) cos(A)

(Si A est mesuré dans le sens trigonomètrique, c'est-à-dire le sens contraire des aiguilles d'une montre). Comme vous pouvez le constater c'est un gros calcul complexe, nécessitant 4 multiplications. Bien sûr les sinus et cosinus sont trouvés grâce à des tables au lieu de les calculer (ce qui est d'autant plus faisable que le nombre d'angles possibles est limité. Dans la démo j'utilsai un pas de 2,5°, mais on peu très bien imaginer d'avoir 256 angles possibles). On notera aussi que ces cosinus et sinus sont les mêmes pour tous les points de la carte, on peut donc faire les multiplications en code généré, ce qui est certes plus dur mais aussi beaucoup plus rapide ! On peut donc calculer X et Z en un temps raisonnable (environ 150 instructions me parait envisageable). Notez aussi que Z sera réutilisé pour calculer la hauteur des murs.

Reste le problème de la division. En fait on va ruser, et faire en même temps la multiplication par (largeur de l'écran/2) et calculer l'octant dans lequel se trouve le point ! Vous allez voir que si le résultat est proche de celui d'une division l'algo utilisé n'est pas le même.

Diviser pour mieux régner

Je reviens à notre problème initial : on cherchait à savoir si un point P est à gauche ou à droite d'une demie-droite [OX). Pour cela une première estimation consiste à regarder dans quel cadran est situé le point P par rapport à O, et dans quel cadran se trouve la demi-droite, c'est-à-dire dans quel cadran se trouve le point X par rapport à O. En numérotant les cadrans 0 (Nord-Est), 1 (Sud-Est), 2 (Sud-Ouest) et 3 (Nord-Ouest), je peu avoir une première idée de la position du point par rapport à la demi-droite : soit C_P le numéro de cadran de P et C_X celui de X, donc de la demi-droite. Si C_P = C_X-1 alors je sais que le point est à gauche de la droite. Si C_P = C_X+1 alors je sais que le point est à droite de la demi-droite.
La chose interessante c'est que dans notre algo, le point X est toujours connu parce qu'il a été utilisé dans un autre triangle, on connait donc déjà la valeur de C_X ! Il n'y a donc que le calcul de C_P à faire pour chaque point.

Mais que se passe-t-il dans le cas ou C_P = C_X ou C_P = -C_X (comme on est dans un ensemble à 4 valeurs possibles, C_X-2 = -C_X) ? On ne sait pas encore de quel coté de [OX) se trouve P ! Eh bien on n'a qu'à rafiner, et au lieu d'utiliser des cadrans, on va utiliser des octants ! On va donc avoir désormais 8 valeurs possibles : 0 (Nord-Nord-Est), 1 (Est-Nord-Est), 2 (Est-Sud-Est), etc... jusqu'à 7 (Nord-Nord-Ouest). Et on saura que P est à gauche si O_X-4 < O_P < O_X, et à droite si O_X < O_P < O_X+4.
Ca marche dans plus de cas, mais on a encore le problème des cas O_P = O_X et O_P = O_X-4 = -O_X !
Comment faire ? Eh bien il suffit de diviser l'espace en régions encore plus petites, jusqu'à ce que ces régions soient trop petites pour discerner les points de l'écran (c'est-à-dire que 2 points appartenant à une même région sont forcement affichés dans l'écran à la même abscisse X_écran) ! On peut alors considérer que le point n'est pas visible et le foutre indiférement à droite ou à gauche selon ce qui nous arange le plus...

Très bien, mais comment faut-il diviser l'espace et combien de fois pour cela ? Jusqu'à present pour calculer O_P on avait juste besoin de savoir le signe de X, le signe de Z et si |X|<|Z|, ce qui est simple à calculer. Pour séparer encore en deux, on pourrait rajouter la séparation : 2|X|<|Z|, ce qui est assez simple à calculer aussi. Et puis pour encore diviser en 2 on pourait rajouter les séparations : 4|X|<|Z| et 4|X|<3|Z|... En généralisant, si on veut découper l'espace en 8*2ⁿ régions, il suffit des deux séparations sur les signes de X et de Z et des 2ⁿ séparations du style :
2ⁿ|X|<k|Z|, pour k allant de 1 à 2ⁿ.

Intéressons-nous au premier octant (0), le numéro de la partie de l'espace dans laquelle se trouve P est donné par (k-1) ! Si le point P est dans la partie q, alors on sait que :
q.Z <= (2ⁿ).X < (q+1).Z, et donc que q <= 2ⁿ.X/Z < q+1. On a un intervalle de valeurs pour 2ⁿX/Z !!!! Maintenant prenez n=6, on a donc 2ⁿ = 64 = (largeur de l'écran/2).
Et hop, le résultat qui tue : 64+q < X_écran < 65+q. Pour connaître X_écran, il suffit de connaître q, le numéro de la partie de l'espace contenant le point !!!! Bien sûr cette démarche peut se faire dans l'autre octant qui nous interesse : l'octant 7.

On sait donc maintenant comment diviser l'espace intelligement et combien de fois. Il ne reste plus qu'à trouver une méthode pour calculer q. Il en existe une qui donne la solution en log₂(2ⁿ) = n = 6 intérations, ce qui est très peu ! La voici (sans les tests pour savoir dans quel octant se trouve P, on suppose que X>0 et:Z>0) :

q <- 0
faire 6 fois : {
X <- X + X
q <- q + q
Si X >= Z
Alors q <- q + 1; X <- X - Z
}

Et voilà ! Comme la boucle est petite, qu'on ne la fait que 6 fois et que ça doit aller très vite, on peu même se payer le luxe de dérouler la boucle, on obtient à la fin 64 labels correspondants aux 64 valeurs de q, et on a juste à faire un LC q suivant le label, même pas besoin de calculer q ! Résultat : on fait six fois "X<-X+X", six tests et au pire six fois "X<-X-Z", soit au pire 18 instructions !!! C'est pas beau la vie ?

A suivre...

Bon allez c'est tout pour aujourd'hui, n'hésitez pas à me dire s'il y a des choses que vous ne comprenez pas, si vous voulez que je vous fasse d'autres dessins, ou même pour participer ;) : écrivez-moi ! Notez qu'il reste ancore plein de trucs à expliquer, l'affichage des sprites n'étant pas le moindre !