pmdata's blog

De nombreux possesseurs de Falcon se demandent à quoi peut bien servir le blitter quand le 68030 de celui-ci est pratiquement aussi rapide pour afficher des sprites. Je dis que le blitter peut servir à cela, mais qu'en fait c'est un processeur qui peut avoir d'autres fonctions intéressantes si on sait l'utiliser (ce qui semble loin d'être le cas de tout le monde).

Il y a longtemps...

Rappelez-vous certains jeux d'arcade (surtout les shoot'em ups) sur ST où vous aviez superbement évité une cinquantaine de tirs adverses mais où le programme en avait décidé autrement. Ou bien d'autres jeux (de baston par exemple) où vous pouviez toucher votre adversaire sans voir réellement de contact. Tout ceci repose sur un fait unique : les collisions entre les sprites n'étaient pas précises. Pourquoi ? parce que cela nécessite un travail conséquent pour le processeur qui n'avait pas que cela à faire : 99 pourcents des jeux sur ST n'utilisent que le processeur central pour afficher les sprites, ce qui fait un boulot monstre dans un jeu d'arcade.

Blitter mon ami

Je vous propose donc ici d'utiliser ce pauvre petit processeur dans le but de tester la collision entre deux sprites quelconques, et ce au pixel près (eh oui !!). Le blitter permet toutes sortes de manipulations de mémoire: transfert, opérations logiques, décalages au pixel près. C'est la combinaison astucieuse de ces tâches qui nous permettra d'arriver à nos fins. Dans le cas présent, je me demandais si une opération logique simple me permettrait de savoir si oui ou non j'ai une collision. Réfléchissez: quelle fonction vous donne 1 si les deux opérandes en entrée sont égaux à 1, et zéro dans les autres cas? Vous avez trouvé? Non? Pas encor ? Allez: c'est le AND !!! Sachant cela, il suffit de faire un AND entre les deux sprites, et les zones à 1 seront les zones où il y a collision. Il n'y a plus qu'à programmer le blitter qui va nous faire ça gentiment et très facilement.

Le principe

Avant de commencer, regardez la figure 1 qui doit trainer quelque part par là, elle vous présente le travail à réaliser. Une remarque: qu'allons nous utiliser pour faire nos opérations ? Simple: pour tester tous les pixels d'un sprite, qu'y a-t-il de mieux que le masque de celui-ci? Nous allons donc utiliser les masques des sprites pour nos opérations; ce qui ne gêne personne, sauf ceux qui font des jeux en True Color (Y'en a au moins ?). Bon, tout le monde est prêt? On peut y aller?

x1,y1,w1,h1 sont les coordonnées et dimensions du sprite 1.
x2,y2,w2,h2 sont les coordonnées et dimensions du sprite 2.

Les rectangles englobants

Tout d'abord, nos sprites sont rectangulaires. Il faut donc commencer par tester si nos rectangles s'intersectent ou non. Si c'est le cas, on calcule les coordonnées de la zone d'instersection, dans chacun des sprites. On a intersection si le sprite 1 commence au milieu du sprite 2 (ou vice-versa), et ce horizontalement ou verticalement. La zone d'intersection se trouve entre la valeur la plus élevée du départ d'un des deux sprites (x1 ou x2 horizontalement), et la plus faible de la fin d'un des deux sprites (x1+w1 ou x2+w2 horizontalement).

cx=max(x1,x2)
cx2=min(x1+w1,x2+w2)
if (cx2<cx) stop:pas de collision
cy=max(y1,y2)
cy2=min(y1+h1,y2+h2)
if (cy2<cy) stop:pas de collision
cw=cx2-cx
ch=cy2-cy

La zone d'intersection

Maintenant que l'on a les coordonnées de la zone d'intersection (cx,cy,cw,ch), il faut calculer son emplacement relatif à chacun des deux sprites.

cx1=cx2=cy1=cy2=0
if (x1<x2) cx1=x2-x1
if (x2<x1) cx2=x1-x2
if (y1<y2) cy1=y2-y1
if (y2<y1) cy2=y1-y2

cx1,cy1,cw,ch est la zone d'intersection dans le sprite 1.
cx2,cy2,cw,ch est la zone d'intersection dans le sprite 2.

Nous avons maintenant tout ce qu'il nous faut, il n'y a plus qu'à faire les opérations logiques: il s'agit de trois opérations élémentaires (voir figure 2):

1. Copier la zone d'intersection du sprite 1 dans le buffer.
2. Faire un AND entre la zone d'intersection du sprite 2 avec le buffer.
3. Recopier avec un OR, le buffer dans un flag.

Le source

Tout d'abord, quelle taille va-t-on donner au buffer ? Un écran de 320x200 fait 64000 pixels, soit 8000 octets en 1 plan. Si vous avez des sprites gigantesques (genre gros monstre de fin de niveau), vous voyez que la place mémoire requise n'est pas énorme. J'ai pour ma part limité le buffer à 4000 octets, ce qui me paraît suffisant (soit une zone maxi de 160x200 à 320x100 approximativement). Pour vous simplifier la tâche, il s'agit de la taille du plus gros sprite.

La zone d'intersection étant positionnée à n'importe quel pixel horizontalement (et sûrement différente pour les deux sprites), il est nécessaire de décaler celle-ci dans les recopies que nous allons faire, pour les aligner dans le buffer au même pixel horizontal. Le blitter décale toujours les bits vers la droite, on n'a pas le choix. Si (sx(n) and 15) est différent de zéro, il faut décaler de 16-sx(n) pixels vers la droite (et donc décaler l'adresse destination de 1 mot vers la gauche au préalable). De même, si la zone d'intersection a une largeur nom multiple de 16 pixels, il faudra lire un mot en plus (une largeur de 33 pixels fait 3 mots à transférer). On effectue alors les deux recopies (simple pour le sprite 1, avec un AND pour le sprite 2).

Ensuite, comment savoir si j'ai des bits à 1 dans mon buffer? Et bien le blitter va nous le dire: il va nous recopier avec un OR, tous les mots du buffer faisant partie de la zone d'intersection dans un mot de 16 bits (COLFLAG dans le source). A la fin, si ce mot vaut zéro, alors c'est qu'il n'y a pas de collision, sinon c'est la fin du monde (votre vaisseau vient d'être touché par le missile ennemi qui vient de surgir du nuage rose derrière vous qui était invisible parce qu'il y avait du brouillard et qu'en bon pilote, vous n'avez pas allumé vos phares lasers spectro-condensés pour ne pas vous faire repérer par les plantes vertes de l'immeuble d'en face).

Certains se demandent sûrement pourquoi faire un OR dans le flag pour finir, et pas tester directement le contenu du buffer (ce qui est simple et rapide). Je leur dirai que comme la zone d'intersection n'a pas forcément une largeur multiple de 16 pixels, il leur faudrait auparavant vider le buffer avant d'y faire les recopies. Alors qu'avec le blitter, celui-ci masque directement les bits nécessaires à gauche comme à droite, et ne pose donc pas de problème. De plus, ce source était prévu à l'origine pour mon STE, et un 68000 sans cache a du mal à être plus rapide qu'un blitter. Cette routine marche parfaitement sur toute machine équipée d'un blitter. Mais sur mon Falcon, un autre problème est apparu: le cache de données...

C'est quoi le problème?

La routine écrit avec le blitter dans le mot COLFLAG. Ceci pose un problème quand le cache de données est activé. Le blitter travaille en effet en DMA. Le 68030, ayant mis COLFLAG à zéro au début de la routine, ne sait pas que ce dernier a été modifié par le blitter. Il faut donc désactiver le cache avant de tester le flag pour forcer le 68030 à lire COLFLAG en RAM et non dans son cache. Ainsi, le problème de cohérence cache/mémoire est résolu.

Une autre solution, est de placer COLFLAG quelque part où le 68030 n'utilise pas le cache de données, comme l'espace mémoire réservé aux différents coprocesseurs. Mais on ne peut pas se permettre d'écrire 16 bits comme ça n'importe où. Il se trouve que le blitter dispose de 16 registres de 16 bits inutilisés par notre test: il s'agit des registres de demi-teinte. Il suffit alors d'utiliser l'un de ces registres comme flag de collision, dans lequel le blitter ira écrire.

Si on essaie de tester le buffer au 68030, il faut le vider avant de faire le test. Il n'y a pas de problème quand la zone à vider est importante par rapport aux 256 octets de cache. Mais quand la zone d'intersection fait seulement 1 mot, il y a de grandes chances que ce dernier se trouve dans le cache et donc ici, vous aurez le même problème: le blitter écrit dans le buffer, qui est en partie dans le cache, et quand vous testez les mots du buffers, le 68030 croit qu'ils sont toujours à zéro... N'oubliez pas que les 68040 et plus ont un cache plus gros. Donc je pense que le meilleur moyen est d'invalider le cache le temps de faire le(s) test(s), ou bien d'utiiliser un des registres demi-teinte du blitter.

Pour finir

Pour conclure donc, le blitter n'est pas si mauvais que ça. Il est peut-être trop lent pour afficher des gros sprites en 640x480 en 8 plans, mais dans ce cas, il vaut mieux l'utiliser intelligemment. Le Falcon est une machine tout à fait homogène, dommage qu'il n'y ait pas (encore) de jeu à la hauteur de ce dernier. Alors faites nous-en! On n'attend que ça!

Sources et explication (Atari):
blitcol.zip (10 Ko)