Si on fait un grand bitmap qui représente les décors dont les endroits où le vaisseau pourra évoluer seront coloriés avec la couleur désignée transparante, comment peut gérer efficacement les déplacements du vaisseau dans ce bitmap?
 
Vous m'avez conseillé un bitmask la dernière fois que j'ai posé une question de ce genre, j'ai programmé un programme qui crée un bitmask à partir d'un bitmap, mais si on utilise une grande surface, la fonction qui va regarder si les pixels TRUE du vaisseau sont oui ou non au-dessus d'un pixel du décors TRUE prend beaucoup de temps.
 
N'y a-t-il pas une solution beaucoup plus rapide? Et on garde le bitmask pour gérer les collisions avec les vaisseaus ennemis en n'analysant qu'une petite partie de l'écran?

Une possibilite est d'utiliser, en plus du bitmask, des bounding boxes, en gros des boites englobant tes objets. En 2D, c'est simplement des rectangles.  
 
Donc le truc c'est de determiner des boites englobant les elements de ton decor. Comme ca pour tester l'intersection, tu regardes simplement si la bounding box de ton vaisseau intersecte les bounding boxes de ton decor (qui sont en petit nombre si c'est bien fait).  
Et c'est un test qui va tres vite (intersection de rectangles ).  
 
S'il n'y a pas d'intersection entre les bounding boxes (le cas le plus frequent), il n'y aura pas d'intersection entre les objets, puisque les objets sont inclus dans les bounding boxes.  
S'il y a intersection entre les bounding boxes, la par contre il faut regarder plus loin et utiliser le bitmask pour voir de maniere plus detaillee s'il y a intersection  
 
Une autre methode plus generale serait d'utiliser un quadtree, mais c'est un peu (beaucoup) plus complique a mettre en place.  
 

[edit]--Message édité par tgrx--[/edit]

C'est quoi exactement un quadtree?
 
Pour les boudings boxs, j'y ai pensé: donc en fait si deux boxs se superposent on test à l'aide du bitmask l'intersection des deux boxs, c'est ça?

Exactement.
 
D'ailleurs je ne comprends pas pourquoi le test de superposition de ton vaisseau avec le bitmask prend du temps.
 
Il prend tout l'ecran ton vaisseau ou quoi ??
Parce que s'il fait une taille x*y, ca fait jamais que x*y tests logiques, et ca va super vite normalement ??
 
Oublie le quadtree, je suis pas sur que ca soit vraiment utile.

Hop la. Stop arrêtez tout. Faut pas faire de la détection en scannant pixel par pixel (ou bit par bit) c'est beaucoup trop lent.
 
En fait, il faut que tu compare tes 2 bitmasks en utilisant un 'ET' sur des long (32 bits). Ensuite, tu regarde si la valeur est égale à 0 ou pas.
Si c'est 0 y'a pas de collision et tu continue tes tests sinon y'a collision et tu arrete le test.
 
 
Donc, pour une taille de x*y ça nous fait dans le pire des cas (x/32)*y tests à effectuer.
 
On peut aller plus vite encore en utilisant les registres du MMX.

Bien sûr, cette méthode impose que tu stocke tes bitmasks avec une taille horizontale qui soit un multiple de 32 (ou de 64 si tu utilise des routine MMX).

Attends je pige plus tout là...
 
J'ai un bitmask des décors "fixes" et un bitmask du vaisseau "non fixe".
 
Que veux-tu mettre en long là-dedans? J'ai que des valeurs booléennes donc faut que je fasse quoi? Et comment je compare les deux exactement?

Il ne faut que tu utilise des valeurs booléennes. Ton bitmask doit être composé de valeurs de type long. A chaque bit d'un long correspondra une valeur booléenne.
 
Ensuite, tu as un pointeur long sur le bitmask de ton vaisseau et un pointeur long sur le bitmask du décor qui se trouve sous ton vaisseau.
 
Tu fais le scan en effectuant un 'ET' sur les valeurs des pointeurs. Ensuite, tu compare le résultat du 'ET' avec 0.
Si le resultat est different de 0 alors collision, et on sort de la fonction de test.
Sinon tu continue ton scan jusqu'à ce que tu es scanné tout le bitmask du vaisseau.
 
Si tu as fini ton scan sans encombre c'est qu'il n'y a pas collision.

Tu pourrais m'aider avec les champs de bits dans mon autre poste qui traite ce sujet en particulier?
 
J'ai du mal à les utiliser et les infos que j'ai trouvé sont pas géniales et n'expliquent pas très bien...

Ah oui, je viens de me rendre compte qu'on peut pas faire de champs de bits plus grand que 32... Je pensais qu'on pouvait faire utiliser une plage mémoire aussi grande qu'on voulait... C'est chiant ce binz... Ca complique un peu tout.

on peut faire des champs de bits avec des
vector<bool>, et c'est effectivement des bits stoqués les uns après les autres.
 
Sinon y'a la méthode RLE scanline (c'est moi qui l'appelle comme ça)
 
de cette manière, on stoque pour le vaisseau pour chaque ligne une suite de valeurs donnant quand le vaisseau commence à être présent, et quand il ne l'est plus.
Imaginons que les 4 premiers pixels sont transparents, les 8 suivants opaques, puis 3 transparents, 2 opaques, et les 15 derniers transparents, on stoque
4,8,3,2,15
et on fait ça pour chaque ligne
 
Comme en général, les objets n'ont pas trop de trous, ça fait peu de valeurs, même si le sprite est grand.
 
Pour le décor, on fait pareil.
 
Le temps de test de collision devient indépendant de la taille et ne dépend plus que de la complexité du contour. C'est plus long à coder, mais ça s'exécute plus vite.
Sinon l'idée du quadtree est bonne et va vite. Mais pareil, l'implémentation peut en faire craquer plus d'un.
Courage.

Bon, j'ai finis d'écrire ma fonction créant un bitmask depuis un bitmap, enfin. Merci à tous ceux qui m'ont aidé, sans eux je crois que je serais encore entrain de galérer à trouver les conneries que j'ai codées.
 
Bon, j'ai fais des tests concernant le traitement d'un aire de x*y pixels donnés sur un seul bitmask de 1024*768 pixels.
 
Voilà les résultats:
 
_ pour une aire de 50*50 pixels: 0 ms
 
_ pour une aire de 100*100 pixels: 0 ms
 
_ pour une aire de 200*200 pixels: 10 ms
 
_ pour une aire de 500*500 pixels: 50 ms
 
_ pour une aire de 1024*768 pixels: 160 ms
 
 
Voilà, il ne faut donc pas abuser sur les zones à traiter par les bitmasks. De plus ce test ne réflète pas exactement les réels limites d'utilisation des bitmasks, car dans un jeu on traitera plusieurs bitmasks en même temps.
 
En conclusion, je pense que les bitmasks sont très précis, mais ne doivent être utilisé que le plsu rarement possible, il faut tout d'abord tester les spites avec des boudings box puis seulement s'il y a superposition de boundings box traiter la partie commune avec un bitmask.

Si, comme kizkool le mentionne, on fait les tests sur 32 bits, ce qui revient a stocker les bits dans un tableau de unsigned int et non plus un tableau de bool,
 
comparer une zone de 1024x768 revient a faire 1024x768/32 ET bit a bit, ce qui fait seulement 24576 operations en tout... et ca doit pouvoir se torcher en beaucoup moins que 160 ms... je pense facile < 1 ms.
 
PS : tu programmes sur quel processeur ?

Oki, faudra que j'essaie un jour. Mais pour le moment je vois pas comment mettre ça en oeuvre.

 
Sinon, je programme sur un P3 550@825.

Sinon, je mets pas mes valeurs dans un tableau de bool mais dans un tableau vector<bool>.