Meilleurs algo d'un test par bouding box
+3
fanoplusplus64K
Stef
vingazole
7 participants
Page 1 sur 9
Page 1 sur 9 • 1, 2, 3, 4, 5, 6, 7, 8, 9 
Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 10:32
Bonjour, j'ouvre le sujet sur un test de collisions entre sprites via la technique des bounding box .
C'est kua cette technique ??
Simple dans un jeu tout le monde sait qu'il faut pouvoir détecter des collision entre les sprites, par exemple le joueur se fait toucher par un projectille .
On distingue 2 cathégories de techniques .
1- Par approximation, on définie une zone dans laquelle pourra avoir lieu la collision
2- Pixel perfect, on tests si 1 ou plusieurs pixels de 2 sprites différent se touchent .
La technique 2 est à éviter, car elle consomme bcp de CPU, et est très frustrante, mais elle peut être utilisé dans des style particuliers de jeux.
Ici on va retenir la seconde, par approximation .
Plusieurs techniques différentes ici, mais on va se consacrer à une en particulier, celle par bounding box .
Cette technique en plus d'être simple à programmer et rapide et peut être utilisée à tout type de jeux .
La technique est simple on défini une limite tout autour des sprites, cette limite de type carrée ou rectangle(une box/boite quoi) qui va être la zone dans laquelle tout autre boite qui va entrer sera considéré comme une collision .
Schéma rapide
Sprite 1 ==> Sprite2 <--->
On va définir 2 boite pour avoir cette representation
y1 y2
------ -------
x1 | ==>| x'1 x2 |<--->| x'2
------ -------
y'1 y'2
Les boite peuvent être augmentées ou diminuées selon la difficulté que l'on veut avoir .
Un boite large veux dire risque de collision plus importante qu'une petite boite .
Donc l'algo consiste en :
On a un sprite1 qui se déplace sur X/Y
On a un sprite2 qui se déplace sur X/Y
On teste si il y a une collision entre les 2
L'algo de base consiste à prendre la position X/Y du sprite1 et a ajouter à ces coordonnées les valeurs de la box pour avoir .
Les valeurs des box seront dans un tableau .
SPRITE 1
x1 + val1_box
x'1+ val2_box
y1+ val3_box
y'1+ val4_box
SPRITE 2
x2 + val5_box
x'2+ val6_box
y2+ val7_box
y'2+ val8_box
Le but de ce post est de voir la mise en oeuvre de cette technique sur différents processeurs.
pour le moment:
68000
Z80
6280/6502/65816
C'est ouvert à tout les CPU max 16 bit .
On peut autoriser l'ARM2 histoire de rigoler, mais pas plus .
Le but n'étant pas de troller, mais de voir comment on peut optimiser ce type de test sur des CPU aussi différents,
Et pourquoi pas des idées d'optimisations qui pourraient être mises en place peut importe le CPU.
Donc ici le code en assembleur, avec les cycles pris sur un test de collisions sur 16 bit.
C'est kua cette technique ??
Simple dans un jeu tout le monde sait qu'il faut pouvoir détecter des collision entre les sprites, par exemple le joueur se fait toucher par un projectille .
On distingue 2 cathégories de techniques .
1- Par approximation, on définie une zone dans laquelle pourra avoir lieu la collision
2- Pixel perfect, on tests si 1 ou plusieurs pixels de 2 sprites différent se touchent .
La technique 2 est à éviter, car elle consomme bcp de CPU, et est très frustrante, mais elle peut être utilisé dans des style particuliers de jeux.
Ici on va retenir la seconde, par approximation .
Plusieurs techniques différentes ici, mais on va se consacrer à une en particulier, celle par bounding box .
Cette technique en plus d'être simple à programmer et rapide et peut être utilisée à tout type de jeux .
La technique est simple on défini une limite tout autour des sprites, cette limite de type carrée ou rectangle(une box/boite quoi) qui va être la zone dans laquelle tout autre boite qui va entrer sera considéré comme une collision .
Schéma rapide
Sprite 1 ==> Sprite2 <--->
On va définir 2 boite pour avoir cette representation
y1 y2
------ -------
x1 | ==>| x'1 x2 |<--->| x'2
------ -------
y'1 y'2
Les boite peuvent être augmentées ou diminuées selon la difficulté que l'on veut avoir .
Un boite large veux dire risque de collision plus importante qu'une petite boite .
Donc l'algo consiste en :
On a un sprite1 qui se déplace sur X/Y
On a un sprite2 qui se déplace sur X/Y
On teste si il y a une collision entre les 2
L'algo de base consiste à prendre la position X/Y du sprite1 et a ajouter à ces coordonnées les valeurs de la box pour avoir .
Les valeurs des box seront dans un tableau .
SPRITE 1
x1 + val1_box
x'1+ val2_box
y1+ val3_box
y'1+ val4_box
SPRITE 2
x2 + val5_box
x'2+ val6_box
y2+ val7_box
y'2+ val8_box
Le but de ce post est de voir la mise en oeuvre de cette technique sur différents processeurs.
pour le moment:
68000
Z80
6280/6502/65816
C'est ouvert à tout les CPU max 16 bit .
On peut autoriser l'ARM2 histoire de rigoler, mais pas plus .
Le but n'étant pas de troller, mais de voir comment on peut optimiser ce type de test sur des CPU aussi différents,
Et pourquoi pas des idées d'optimisations qui pourraient être mises en place peut importe le CPU.
Donc ici le code en assembleur, avec les cycles pris sur un test de collisions sur 16 bit.
Dernière édition par TOUKO le Lun 3 Fév 2014 - 12:13, édité 4 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 10:34
Ma dernière version :
je pense que côté Z80 ces optimisations sont aussi valables .
- Code:
CollisionTest_16() ; // VERSION 2
{
#asm
; // Variables à initialiser avant l'appel de la fonction
; // sprite1 : sprite 1
; // ptr_hitbox_spr1 : tableau de collisions à 4 entrées du sprite 1
; // sprite2 : sprite 2
; // ptr_hitbox_spr2 : tableau de collisions à 4 entrées du sprite 2
; // TEST COLLISIONS EN X
; // Calcul x2
5 lda _pos_x2 ; // Ajout de val_x2 à x2
2 clc
7 adc [ ptr_hitbox_spr2 ]
4 sta <calc_pos + 2
5 lda _pos_x2 + 1
2 adc #0
4 sta <calc_pos + 3
29 CYCLES
; // Calcul x'2
5 lda _pos_x2 ; // Ajout de val_x2 + 1 à x2
2 clc
9 adc [ ptr_hitbox_spr2 ].1 ; // [ ptr_hitbox_spr2 ].1 => equivalent à ldy #1 + adc [ ptr_hitbox_spr2 ] , Y
4 sta <calc_pos + 4
5 lda _pos_x2 + 1
2 adc #0
4 sta <calc_pos + 5
31 CYCLES
; // Calcul x'1
5 lda _pos_x1 ; // Ajout de val_x1 + 1 à x1
2 clc
9 adc [ ptr_hitbox_spr1 ].1
2 tax
5 lda _pos_x1 + 1
2 adc #0
25 CYCLES
; // debut test x'1
; // Test 1ere colone x'1 >= x2
4 cmp <calc_pos + 3
2/3 bne .suite_test_xprim2
4 cpx <calc_pos + 2
2/3 bcc .fin_test
12 CYCLES
.suite_test_xprim2:
; // Test 2ieme colone x'1 < x'2
4 cmp <calc_pos + 5
2/3 bne .test_x_suite
4 cpx <calc_pos + 4
2/3 bcc .test_y
12 CYCLES
TOTAL 29+31+25+12+12 = 109 CYCLES
.test_x_suite:
; // Calcul x1
5 lda _pos_x1 ; // Ajout de val_x1 à x1
2 clc
7 adc [ ptr_hitbox_spr1 ]
2 tax
5 lda _pos_x1 + 1
2 adc #0
23 CYCLES
; // debut test x1,x2 et x'2 sont déjà calculés
4 and <calc_pos + 3 ; // Test 1ere colone x1 >= x2
4 eor <calc_pos + 5
2/3 bne .fin_test
4 cpx <calc_pos + 2 ; // Test 2ieme colone x1 < x'2
2/3 bcc .fin_test
4 cpx <calc_pos + 4
2/3 bcc .test_y
23 CYCLES
TOTAL 29+31+25+12+12+23+23 = 155 CYCLES
.fin_test:
stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
rts
; // TEST COLLISIONS EN Y
.test_y:
; // Calcul y'2
lda _pos_y2 ; // Ajout de val_y2 + 1 à y2
clc
adc [ ptr_hitbox_spr2 ].3
sta <calc_pos + 2
lda _pos_y2 + 1
adc #0
sta <calc_pos + 3
; // Calcul y2
lda _pos_y2 ; // Ajout de val_y2 à y2
clc
adc [ ptr_hitbox_spr2 ].2
sta <calc_pos + 4
lda _pos_y2 + 1
adc #0
sta <calc_pos + 5
lda _pos_y1 ; // Ajout de val_y1 à y1
clc
adc [ ptr_hitbox_spr1 ].2
sta <calc_pos
tax
lda _pos_y1 + 1
adc #0
cmp <calc_pos + 3
bne .suite_test_y2
cpx <calc_pos + 2
bcs .fin_test
.suite_test_y2:
; // Test 1ere ligne y1 >= y2
cmp <calc_pos + 5
bne .test_y_suite
cpx <calc_pos + 4
bcs .col_ok
.test_y_suite:
; // Calcul y'1 ,y2 et y'2 sont déjà calculés
lda _pos_y1 ; // Ajout de val_y1 + 1 à y1
clc
adc [ ptr_hitbox_spr1 ].3
tax
lda _pos_y1 + 1
adc #0
and <calc_pos + 3
eor <calc_pos + 5
bne .fin_test
cpx <calc_pos + 2
bcs .fin_test
cpx <calc_pos + 4
bcc .fin_test
TOTAL 29+31+25+12+12+23+23 = 155 CYCLES
TOTAL 155 * 2 = 310 CYCLES
.col_ok:
inc <collision ; // Si collision ,alors collision <> 0
rts
#endasm
}
je pense que côté Z80 ces optimisations sont aussi valables .
Dernière édition par TOUKO le Lun 3 Fév 2014 - 12:32, édité 8 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 10:37
Celui de stef sur 68000
- Code:
12 lea spr1, a0 [color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 lea hitbox1, a1 [color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 lea spr2, a2 [color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 lea hitbox2, a3 [color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
48[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
// TEST on X coordinates[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 0(a0), d0 ; d0 = spr1.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 2(a1), d0 ; d0 = spr1.x + box1.xmax = spr1.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 0(a2), d1 ; d0 = spr2.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 0(a3), d1 ; d0 = spr2.x + box2.xmin = spr2.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
48[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 cmp.w d0,d1 ; if (spr1.xmax < spr2.xmin)[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
10 bgt .no_collid ; no collision[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
14[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 0(a0), d0 ; d0 = spr1.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 0(a1), d0 ; d0 = spr1.x + box1.xmin = spr1.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 0(a2), d1 ; d0 = spr2.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 2(a3), d1 ; d0 = spr2.x + box2.xmax = spr2.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
48[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 cmp.w d0,d1 ; if (spr1.xmin > spr2.xmax)[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
10 blt .no_collid ; no collision[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
14[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
// TEST on Y coordinates[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 2(a0), d0 ; d0 = spr1.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 6(a1), d0 ; d0 = spr1.y + box1.ymax = spr1.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 2(a2), d1 ; d0 = spr2.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 4(a3), d1 ; d0 = spr2.y + box2.ymin = spr2.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
48[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 cmp.w d0,d1 ; if (spr1.ymax < spr2.ymin)[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
10 bgt .no_collid ; no collision[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
14[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 2(a0), d0 ; d0 = spr1.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 4(a1), d0 ; d0 = spr1.y + box1.ymin = spr1.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 move.w 2(a2), d1 ; d0 = spr2.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
12 add.w 6(a3), d1 ; d0 = spr2.y + box2.ymax = spr2.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
48[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 cmp.w d0,d1 ; if (spr1.ymin > spr2.ymax)[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
10 blt .no_collid ; no collision[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
14[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
.collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 move #1,d0 ; return 1[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
16 rts[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
.no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
4 move #0,d0 ; return 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
16 rts
Dernière édition par TOUKO le Lun 3 Fév 2014 - 11:10, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 10:37
- Code:
// TEST on X coordinates[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(spr1) // hl = spr1.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+hitbox1) // hl = hitbox1.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr1.x + hitbox1.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld b,h[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld c,l // bc = hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(spr2) // hl = spr2.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(hitbox2) // hl = hitbox2.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr2.x + hitbox2.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld d,b[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld e,c // de = bc[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
or a // cf = 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
sbc hl,de // hl = hl - de - cf[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
jr nc,no_collid // if (spr1.x + hitbox1.xmax <= spr2.x + hitbox2.xmin) no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
// ------------------[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(spr1) // hl = spr1.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(hitbox1) // hl = hitbox1.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr1.x + hitbox1.xmin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld b,h[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld c,l // bc = hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(spr2) // hl = spr2.x[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+hitbox2) // hl = hitbox2.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr2.x + hitbox2.xmax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld d,b[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld e,c // de = bc[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
or a // cf = 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
sbc hl,de // hl = hl - de - cf[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
jr c,no_collid // if (spr1.x + hitbox1.xmin > spr2.x + hitbox2.xmax) no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
// TEST on Y coordinates[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+spr1) // hl = spr1.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(6+hitbox1) // hl = hitbox1.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr1.y + hitbox1.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld b,h[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld c,l // bc = hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+spr2) // hl = spr2.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(4+hitbox2) // hl = hitbox2.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr2.y + hitbox2.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld d,b[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld e,c // de = bc[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
or a // cf = 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
sbc hl,de // hl = hl - de - cf[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
jr nc,no_collid // if (spr1.y + hitbox1.ymax <= spr2.y + hitbox2.ymin) no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
// ------------------[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+spr1) // hl = spr1.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(4+hitbox1) // hl = hitbox1.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr1.y + hitbox1.ymin[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld b,h[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld c,l // bc = hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(2+spr2) // hl = spr2.y[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ex de,hl // swap de,hl[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld hl,(6+hitbox2) // hl = hitbox2.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
add hl,de // hl = spr2.y + hitbox2.ymax[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld d,b[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
ld e,c // de = bc[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
or a // cf = 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
sbc hl,de // hl = hl - de - cf[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
jr c,no_collid // if (spr1.y + hitbox1.ymin > spr2.y + hitbox2.ymax) no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
.collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
scf // cf = 1[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
jr end[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
.no_collid[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
or a // cf = 0[color=#006600][font=Courier, CourierNew, sans-serif][/font][/color]
.end
Dernière édition par TOUKO le Lun 3 Fév 2014 - 11:09, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 10:48
Oui, sur Master System on a une résolution de 256x192 pixels, toutes les coordonnées sont donc sur 8 bits et ça évite toutes ces opérations sur 16 bits avec lesquelles le z80 a un peu de mal...TOUKO a écrit:sur 6280 :310 cycles, je pourrais gagner encore plus si on considère la taille de l'écran sur y qui est de 224, donc 8 bit et non 16 .
je pense que côté Z80 ces optimisations sont aussi valables .
Je remet ma routine en z80, vu que TOUKO me l'a toute salopée
- Code:
// TEST on X coordinates
ld hl,(spr1) // hl = spr1.x
ex de,hl // swap de,hl
ld hl,(2+hitbox1) // hl = hitbox1.xmax
add hl,de // hl = spr1.x + hitbox1.xmax
ld b,h
ld c,l // bc = hl
ld hl,(spr2) // hl = spr2.x
ex de,hl // swap de,hl
ld hl,(hitbox2) // hl = hitbox2.xmin
add hl,de // hl = spr2.x + hitbox2.xmin
ld d,b
ld e,c // de = bc
or a // cf = 0
sbc hl,de // hl = hl - de - cf
jr nc,no_collid // if (spr1.x + hitbox1.xmax <= spr2.x + hitbox2.xmin) no_collid
// ------------------
ld hl,(spr1) // hl = spr1.x
ex de,hl // swap de,hl
ld hl,(hitbox1) // hl = hitbox1.xmin
add hl,de // hl = spr1.x + hitbox1.xmin
ld b,h
ld c,l // bc = hl
ld hl,(spr2) // hl = spr2.x
ex de,hl // swap de,hl
ld hl,(2+hitbox2) // hl = hitbox2.xmax
add hl,de // hl = spr2.x + hitbox2.xmax
ld d,b
ld e,c // de = bc
or a // cf = 0
sbc hl,de // hl = hl - de - cf
jr c,no_collid // if (spr1.x + hitbox1.xmin > spr2.x + hitbox2.xmax) no_collid
// TEST on Y coordinates
ld hl,(2+spr1) // hl = spr1.y
ex de,hl // swap de,hl
ld hl,(6+hitbox1) // hl = hitbox1.ymax
add hl,de // hl = spr1.y + hitbox1.ymax
ld b,h
ld c,l // bc = hl
ld hl,(2+spr2) // hl = spr2.y
ex de,hl // swap de,hl
ld hl,(4+hitbox2) // hl = hitbox2.ymin
add hl,de // hl = spr2.y + hitbox2.ymin
ld d,b
ld e,c // de = bc
or a // cf = 0
sbc hl,de // hl = hl - de - cf
jr nc,no_collid // if (spr1.y + hitbox1.ymax <= spr2.y + hitbox2.ymin) no_collid
// ------------------
ld hl,(2+spr1) // hl = spr1.y
ex de,hl // swap de,hl
ld hl,(4+hitbox1) // hl = hitbox1.ymin
add hl,de // hl = spr1.y + hitbox1.ymin
ld b,h
ld c,l // bc = hl
ld hl,(2+spr2) // hl = spr2.y
ex de,hl // swap de,hl
ld hl,(6+hitbox2) // hl = hitbox2.ymax
add hl,de // hl = spr2.y + hitbox2.ymax
ld d,b
ld e,c // de = bc
or a // cf = 0
sbc hl,de // hl = hl - de - cf
jr c,no_collid // if (spr1.y + hitbox1.ymin > spr2.y + hitbox2.ymax) no_collid
.collid
scf // cf = 1
jr end
.no_collid
or a // cf = 0
.end
Dernière édition par vingazole le Lun 3 Fév 2014 - 11:09, édité 2 fois
vingazole- Infirmier
-
Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 10:58
Pour le X tu es obligé de considérer 16 bits car il faut considérer la position de ton sprite + sa taille (du coup ça fait plus de 256). Pour le Y effectivement 
Dernière édition par Stef le Lun 3 Fév 2014 - 10:59, édité 1 fois
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par fanoplusplus64K Lun 3 Fév 2014 - 10:58
Oui, sur l'axe des Y on peut effectivement travailler sur 8bits , par contre en X il faut compter avec le clipping (32 pixels seraient suffisants?)vingazole a écrit:Oui, sur Master System on a une résolution de 256x192 pixels, toutes les coordonnées sont donc sur 8 bits et ça évite toutes ces opérations sur 16 bits avec lesquelles le z80 a un peu de mal...
Par contre , je serai curieux de voir comment le 68K et le hu6280 se débrouillent pour aller chercher les coordonnées en mémoire dans un tableau.Pour le 68K comme pour le Z80 ça me semble assez simple, par contre sur le hu , tu travailles par page de 256 octets , non ?
fanoplusplus64K- Patient contaminé
- Nombre de messages : 597
Age : 48
Date d'inscription : 16/01/2011
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 11:02
Oui mais non pour les coordonnées X négatives ou supérieures à 256, je fais en sorte que ça n'arrive pas 
Dernière édition par vingazole le Lun 3 Fév 2014 - 11:03, édité 1 fois
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 11:03
@vingazole: dsl, c'est le copier/coller qui est pourri, il m'a copier du html ce con .
Oui, oui tout à fait ..
Après on peut tricher, vu que nos consoles (sauf MD) sont le plus souvent en 256 de large, on pourrait faire aussi du 8 bit sur X ..
Pour le X tu es obligé de considérer 16 bits car il faut considérer la position de ton sprite + sa taille (du coup ça fait plus de 256). Pour le Y effectivement
Oui, oui tout à fait ..
Après on peut tricher, vu que nos consoles (sauf MD) sont le plus souvent en 256 de large, on pourrait faire aussi du 8 bit sur X ..
Effectivement, mais une version 8 bit pourrait être sympa pour voir l'impact .Oui mais non pour les coordonnées X négatives ou supérieures à 256, je fais en sorte que ça n'arrive pas
Dernière édition par TOUKO le Lun 3 Fév 2014 - 11:07, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 11:05
Oui, je me doutais bien, les fonctions d'édition du fofo ne sont pas super, bonjour la galère dès que tu veux faire un peu de tabulationTOUKO a écrit:@vingazole: dsl, c'est le copier/coller qui est pourri, il m'a copier du html ce con .
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 11:06
Je reposte ma version 68000 ici car sur le post de Touko y'a un problème cde copier / coller qui rend le tout assez illisible :
68000: 316 cycles max.
- Code:
12 lea spr1, a0
12 lea hitbox1, a1
12 lea spr2, a2
12 lea hitbox2, a3
48
// TEST on X coordinates
12 move.w 0(a0), d0 ; d0 = spr1.x
12 add.w 2(a1), d0 ; d0 = spr1.x + box1.xmax = spr1.xmax
12 move.w 0(a2), d1 ; d0 = spr2.x
12 add.w 0(a3), d1 ; d0 = spr2.x + box2.xmin = spr2.xmin
48
4 cmp.w d0,d1 ; if (spr1.xmax < spr2.xmin)
10 bgt .no_collid ; no collision
14
12 move.w 0(a0), d0 ; d0 = spr1.x
12 add.w 0(a1), d0 ; d0 = spr1.x + box1.xmin = spr1.xmin
12 move.w 0(a2), d1 ; d0 = spr2.x
12 add.w 2(a3), d1 ; d0 = spr2.x + box2.xmax = spr2.xmax
48
4 cmp.w d0,d1 ; if (spr1.xmin > spr2.xmax)
10 blt .no_collid ; no collision
14
// TEST on Y coordinates
12 move.w 2(a0), d0 ; d0 = spr1.y
12 add.w 6(a1), d0 ; d0 = spr1.y + box1.ymax = spr1.ymax
12 move.w 2(a2), d1 ; d0 = spr2.y
12 add.w 4(a3), d1 ; d0 = spr2.y + box2.ymin = spr2.ymin
48
4 cmp.w d0,d1 ; if (spr1.ymax < spr2.ymin)
10 bgt .no_collid ; no collision
14
12 move.w 2(a0), d0 ; d0 = spr1.y
12 add.w 4(a1), d0 ; d0 = spr1.y + box1.ymin = spr1.ymin
12 move.w 2(a2), d1 ; d0 = spr2.y
12 add.w 6(a3), d1 ; d0 = spr2.y + box2.ymax = spr2.ymax
48
4 cmp.w d0,d1 ; if (spr1.ymin > spr2.ymax)
10 blt .no_collid ; no collision
14
.collid
4 move #1,d0 ; return 1
16 rts
.no_collid
4 move #0,d0 ; return 0
16 rts
68000: 316 cycles max.
Dernière édition par Stef le Lun 3 Fév 2014 - 11:08, édité 1 fois
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 11:07
Merci de les avoir remise
C'est clair, sur mon notepad++, tout est bien tabulé pour la lisibilité, et quand tu copie/colle, c'est le bordel .
Déjà que stef même avec des coms, il arrive pas à lire, si en plus c'est le bordel j'ai pas fini de l'entendre
Sinon vous utilisez quoi comme algo pour vos collisions en général, ce genre,avec une routine générique qui fonctionne quasiment tout le temps, ou vous faites des routines spécifiques a un jeu ???
Oui, je me doutais bien, les fonctions d'édition du fofo ne sont pas super, bonjour la galère dès que tu veux faire un peu de tabulation
C'est clair, sur mon notepad++, tout est bien tabulé pour la lisibilité, et quand tu copie/colle, c'est le bordel .
Déjà que stef même avec des coms, il arrive pas à lire, si en plus c'est le bordel j'ai pas fini de l'entendre
Sinon vous utilisez quoi comme algo pour vos collisions en général, ce genre,avec une routine générique qui fonctionne quasiment tout le temps, ou vous faites des routines spécifiques a un jeu ???
Dernière édition par TOUKO le Lun 3 Fév 2014 - 11:12, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 11:12
TOUKO a écrit:@vingazole: dsl, c'est le copier/coller qui est pourri, il m'a copier du html ce con .Pour le X tu es obligé de considérer 16 bits car il faut considérer la position de ton sprite + sa taille (du coup ça fait plus de 256). Pour le Y effectivement
Oui, oui tout à fait ..
Après on peut tricher, vu que nos consoles (sauf MD) sont le plus souvent en 256 de large, on pourrait faire aussi du 8 bit sur X ..Effectivement, mais une version 8 bit pourrait être sympa pour voir l'impact .Oui mais non pour les coordonnées X négatives ou supérieures à 256, je fais en sorte que ça n'arrive pas
Ah non pour le X c'est impossible de considérer seulement 8 bits, si ton sprite est en -5 tu fais comment ?? Tu dois de toute manière avoir une variable 16 bits pour stocker ses coordonnées sinon y'a un problème. En Y c'est suffisant, tu considère un offset de 32 et du coup tu rentres pile poil dans 8 bits.
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 11:14
Ah non pour le X c'est impossible de considérer seulement 8 bits, si ton sprite est en -5 tu fais comment ?? Tu dois de toute manière avoir une variable 16 bits pour stocker ses coordonnées sinon y'a un problème. En Y c'est suffisant, tu considère un offset de 32 et du coup tu rentres pile poil dans 8 bits.
Exact j'ai déjà eu ce soucis, mais tu peux t'arranger pour pas que ça arrive en organisant tes vagues d'attaque en conséquence (les vagues viennent toujours du haut ou du bas).
Ca ferra moins propre à l'écran surement, mais faisable .
C'est l'avantage quand c'est possible de pouvoir travailler en 8 bit, mon test de collision 8 bit est plus de 2x plus rapide .
Dernière édition par TOUKO le Lun 3 Fév 2014 - 11:21, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 11:19
Oui Stef, tu as raison si tu prend l'écran complet, mais comme je l'ai écrit je triche et je fais en sorte d'être dans le cas qui m'arrange (je fais sauter deux colonnes de tiles ) !
J'utilise bien 16 bits pour les X et les Y, mais c'est parce que je suis en virgule fixe 8.8, les tests de collision je les fais sur la partie entière de mes coordonnées (8 bits donc).
) !J'utilise bien 16 bits pour les X et les Y, mais c'est parce que je suis en virgule fixe 8.8, les tests de collision je les fais sur la partie entière de mes coordonnées (8 bits donc).
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 11:21
Et tu es environ à combien de cycles par rapport au test 16 bit ??
Ca rend pas bizarre à l'écran ??mais comme je l'ai écrit je triche et je fais en sorte d'être dans le cas qui m'arrange (je fais sauter deux colonnes de tiles
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 11:35
C'est pas hyper visible, je trouve... Regarde sur émulateur :
De toutes façons, sur ma vraie télé CRT l'affichage de la console est décalé vers la gauche (c'est les deux colonnes de gauche que j'ai viré) et ça me bouffe le côté gauche de l'écran sur certains jeux, alors...
De toutes façons, sur ma vraie télé CRT l'affichage de la console est décalé vers la gauche (c'est les deux colonnes de gauche que j'ai viré) et ça me bouffe le côté gauche de l'écran sur certains jeux, alors...
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 11:43
TOUKO a écrit:Ah non pour le X c'est impossible de considérer seulement 8 bits, si ton sprite est en -5 tu fais comment ?? Tu dois de toute manière avoir une variable 16 bits pour stocker ses coordonnées sinon y'a un problème. En Y c'est suffisant, tu considère un offset de 32 et du coup tu rentres pile poil dans 8 bits.
Exact j'ai déjà eu ce soucis, mais tu peux t'arranger pour pas que ça arrive en organisant tes vagues d'attaque en conséquence (les vagues viennent toujours du haut ou du bas).
Ca ferra moins propre à l'écran surement, mais faisable .
C'est l'avantage quand c'est possible de pouvoir travailler en 8 bit, mon test de collision 8 bit est plus de 2x plus rapide .
Ah oui bien sur tu peux faire ça mais dans le cas réel d'un jeu j'imagine que les coordonnées sont toujours en 16 bits, ne serait que pour gérer une partie "virgule fixe" sinon t'es vachement limité sur les mouvements des sprites.
Enfin bon tu peux t'amuser par commencer avec une version Y en 8 bits et ensuite pure 8 bits si tu veux pour gagner des cycles. Cependant je pense que vous pouvez déjà faire une version 16 bits plus rapide que celle que vous avez actuellement non ?
Sinon je pensais pour la structure de données, histoire d'avoir quelque chose de réaliste pour une situation "in-game", voici ce que je propose :
- Code:
struct Sprite {
int x;
int y;
struct BoundingBox *box;
}
struct BoundingBox {
int xmin;
int xmax;
int ymin;
int ymax;
}
Le but étant de pouvoir tester un la collision entre un objet et une liste d'objet, genre une fonction de ce style :
- Code:
int testCollision(Sprite *player, Sprite *enemies, int numEnemies);
Sachant que enemies est une liste de Sprite (tir ennemi ou vaisseau ennemi).
Le truc c'est qu'on peut soit retourner 1 s'il y a collision ou on retourne le nombre de collisions (pour gérer un niveau de vie). On va dire que ça dépend des cas, en tout cas ce genre de méthode me semble plus correspondre à une situation réelle.
Le but sera de donner le nombre min / moyen / max de cycle par collision testée, ça vous convient ?
- Code:
Sinon vous utilisez quoi comme algo pour vos
collisions en général, ce genre,avec une routine générique qui
fonctionne quasiment tout le temps, ou vous faites des routines
spécifiques a un jeu ???
Ca dépends de ton jeu mais en général tu fais soit de la bounding box ou de la circle box selon la forme de ton sprite. Après il est évident que pour un shoot ou tu peux avoir des salves de tirs ennemis et ami (genre Gynoug :p ) tu as intérêt à passer par des astuces.
Y'a plusieurs méthodes possibles, l'une d'elle consiste à positionner tes sprites dans une grille de 32x32 par exemple et ensuite de ne calculer les collisions en utilisant ce qui se trouve dans les cases adjacentes. Ca a un certain cout pour mettre en place la structure et la remplir mais tu t'y retrouves quand tu as vraiment beaucoup de collision à calculer.
Dernière édition par Stef le Lun 3 Fév 2014 - 11:53, édité 1 fois
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 11:53
Bien sur c'est pas top of the top en 8 bit, mais ça peut s'avérer utile si tu es trop light en ressource pour du 16,et bien entendu à condition que ce soit possible .Ah oui bien sur tu peux faire ça mais dans le cas réel d'un jeu j'imagine que les coordonnées sont toujours en 16 bits, ne serait que pour gérer une partie "virgule fixe" sinon t'es vachement limité sur les mouvements des sprites.
Oui, pour moi si j'utilise directement un index dans le tableau des valeurs des box, et non un pointeur, je pense arriver à 280 cycles (voire moins), pour le 16 bit .Enfin bon tu peux t'amuser par commencer avec une version Y en 8 bits et ensuite pure 8 bits si tu veux pour gagner des cycles. Cependant je pense que vous pouvez déjà faire une version 16 bits plus rapide que celle que vous avez actuellement non ?
C'est ce que j'utilise aussi, d'où les pointeurs, et les + x sur certaines variables .Sinon je pensais pour la structure de données, histoire d'avoir quelque chose de réaliste pour une situation "in-game", voici ce que je propose :
Par contre la struc bounding box non, car cela implique des valeurs de box jusqu'à 65536, donc pas réaliste .
Ou alors j'ai pas saisi ce que tu voulais stocker dedans .
C'est une idée, mais ça risque d'être chaud à définir ça le min/moyen non ??Le truc c'est qu'on peut soit retourner 1 s'il y a collision ou on retourne le nombre de collisions (pour gérer un niveau de vie). On va dire que ça dépend des cas, en tout cas ce genre de méthode me semble plus correspondre à une situation réelle.
Le but sera de donner le nombre min / moyen / max de cycle par collision testée, ça vous convient ?
Bon le min ce serai sans collision, mais le moy ??
Sinon pourquoi pas, ça peut être une bonne méthode pour tester sur un cas plus représentatif .
C'est probable que certains CPU sont pénalisés sur tout le test, mais s'avère bien meilleurs si les tests sont arrêtés avant terme, et comme les sprites dans un jeu (même un shoot) sont loin d'entrer tous en collision au même moment .
Après pour le retour j'ai mis une variable, car c'est pour mon jeu, rien ne vous empêche d'utiliser un registre .
@vingazole: je trouve vraiment joli ton projet .
Et je vois l'utilisation, effectivement dans ton cas ça pose aucun problème car tu as designé tes niveau en conséquence on dirait ..
Dernière édition par TOUKO le Lun 3 Fév 2014 - 12:05, édité 4 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 11:58
vingazole a écrit:C'est pas hyper visible, je trouve... Regarde sur émulateur :
https://www.youtube.com/embed/788AjBHtfGg?
De toutes façons, sur ma vraie télé CRT l'affichage de la console est décalé vers la gauche (c'est les deux colonnes de gauche que j'ai viré) et ça me bouffe le côté gauche de l'écran sur certains jeux, alors...
Ah c'est toi qui développe ce jeu ? C'est super beau je trouve pour de la Master System :)
Je l'avais déjà vu sur un autre forum (SMSPower peut être ?) et vraiment graphiquement j'avais trouvé ça très impressionnant sur le moment. En tout cas c'est prometteur, je te souhaite une bonne continuation =)
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 12:09
Bien sur c'est pas top of the top en 8 bit, mais ça peut s'avérer utile si tu es trop light en ressource pour du 16 .
Oui effectivement, tu peux toujours passer en 8 bits pour gagner un peu de temps, sur 68000 ça ne changera rien.
C'est ce que j'utilise aussi, d'où les pointeurs, et les + x sur certaines variables .
Par contre la struc bounding box non, car cela implique des valeurs de box jusqu'à 65536, donc pas réaliste .
Ou alors j'ai pas saisi ce que tu voulais stocker dedans .
En fait j'ai utilisé des int pour dire que c'était assez libre, vous pouvez utiliser du 8 bits pour la bounding box, ça me pose aucun problème. Pour les coordonnées X et Y en revanche je préfère du 16 bits mais vous pouvez faire 2 versions pour voir la différence
C'est une idée, mais ça risque d'être chaud à définir ça le min/moyen non ??
Bon le min ce serai sans collision, mais le moy ??
Sinon pourquoi pas, ça peut être une bonne méthode pour tester sur un cas plus représentatif .
C'est probable que certains CPU sont pénalisés sur tout le test, mais s'avère bien meilleurs si les tests sont arrêtés avant terme, et comme les sprites dans un jeu (même un shoot) sont loin d'entrer tous en collision au même moment .
Le min c'est que tu t'arrêtes au premier test, pour le moyen on peut prendre la moyenne entre le min et le max ou alors à la moitié des tests mais ça doit presque revenir au même en théorie. On se lance donc sur cette nouvelle version ? :)
Pour la structure du Sprite, j'ai mis un pointeur sur la bounding box car dans un jeu, beaucoup de sprite partage la même bounding box donc c'est plus réaliste. On pourrait avoir directement la boudind box en dur dans la structure du sprite mais ce n'est pas très représentatif de ce qui se fait en réalité (ça signifie qu'il faudrait recopier la bounding box pour chaque nouveau sprite, sans parler du supplément de mémoire).
Théoriquement le pointeur devrait être 32 bits car la bounding box étant constante elle peut être en ROM mais par simplification pour vous, on peut le considérer 16 bits (sinon ça va vous beaucoup vous pénaliser je pense).
Dernière édition par Stef le Lun 3 Fév 2014 - 12:17, édité 1 fois
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 12:13
Merci :)Stef a écrit:Ah c'est toi qui développe ce jeu ? C'est super beau je trouve pour de la Master System :)
Je l'avais déjà vu sur un autre forum (SMSPower peut être ?) et vraiment graphiquement j'avais trouvé ça très impressionnant sur le moment. En tout cas c'est prometteur, je te souhaite une bonne continuation =)
Je ne m'occupe "que" de la programmation, c'est ichigobankai le graphiste/level designer du projet.
En effet tu as dû voir notre jeu sur SMSPower, c'était notre participation au concours annuel de codage sur ce site en 2012.
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 12:18
effectivement, pour toi aucun intérêt ,autant rester en 16 ..Oui effectivement, tu peux toujours passer en 8 bits pour gagner un peu de temps, sur 68000 ça ne changera rien.
Mais dans le cas d'un jeu comme celui de vingazole, c'est utile, et ça se camoufle facilement, pour un shoot c'est plus délicat .
Ok, pas de soucis ..En fait j'ai utilisé des int pour dire que c'était assez libre, vous pouvez utiliser du 8 bits pour la bounding box, ça me pose aucun problème. Pour les coordonnées X et Y en revanche je préfère du 16 bits mais vous pouvez faire 2 versions pour voir la différence
Pour mon cas, ça va avoir un gros impact je pense, faut que je vois .
Ok, on peut faire ça ..Le min c'est que tu t'arrêtes au premier test, pour le moyen on peut prendre la moyenne entre le min et le max ou alors à la moitié des tests mais ça doit presque revenir au même en théorie.
Je vais rajouter ces premières valeurs sur l'algo déjà fait .
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 12:19
vingazole a écrit:Merci :)Stef a écrit:Ah c'est toi qui développe ce jeu ? C'est super beau je trouve pour de la Master System :)
Je l'avais déjà vu sur un autre forum (SMSPower peut être ?) et vraiment graphiquement j'avais trouvé ça très impressionnant sur le moment. En tout cas c'est prometteur, je te souhaite une bonne continuation =)
Je ne m'occupe "que" de la programmation, c'est ichigobankai le graphiste/level designer du projet.
En effet tu as dû voir notre jeu sur SMSPower, c'était notre participation au concours annuel de codage sur ce site en 2012.
Et bien félicitations, j'ai hate de voir le projet terminé ! Ca fait vraiment pro !
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 12:21
TOUKO a écrit:effectivement, pour toi aucun intérêt ,autant rester en 16 ..Oui effectivement, tu peux toujours passer en 8 bits pour gagner un peu de temps, sur 68000 ça ne changera rien.
Mais dans le cas d'un jeu comme celui de vingazole, c'est utile, et ça se camoufle facilement, pour un shoot c'est plus délicat .Ok, pas de soucis ..En fait j'ai utilisé des int pour dire que c'était assez libre, vous pouvez utiliser du 8 bits pour la bounding box, ça me pose aucun problème. Pour les coordonnées X et Y en revanche je préfère du 16 bits mais vous pouvez faire 2 versions pour voir la différence
Pour mon cas, ça va avoir un gros impact je pense, faut que je vois .Ok, on peut faire ça ..Le min c'est que tu t'arrêtes au premier test, pour le moyen on peut prendre la moyenne entre le min et le max ou alors à la moitié des tests mais ça doit presque revenir au même en théorie.
Je vais rajouter ces premières valeurs sur l'algo déjà fait .
Ca serait super cool si tu pouvais remettre ton algo au propre et bien indenté :)
Car j'avoue que du coup le premier, j'ai jamais pu bien le lire :p
Edit: je n'avais pas vu que tu avais reposté ton algo au clair, effectivement on comprend mieux maintenant
Sinon je vois que tu as compté 310 cycles, mais ça ne prend pas en compte le retour de fonction, ce que j'ai inclus dans mes 316 cycles (et le RTS est très couteux sur le 68000).Dernière édition par Stef le Lun 3 Fév 2014 - 12:28, édité 2 fois
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 12:24
Le pire c'est qu'il est bien indenté sous notepad++, mais quand je le copie, tout fou le camp 
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 12:32
j'ai un peu remis de l'odre aussi, le site ne semble pas aimer la tabulation, en remplaçant avec des espaces c'est mieux .
Le retour c'est 7 cycles en plus .
Donc ok je modifie .
Si je passe les box en 16 bit, c'est 42 cycles en plus max .
Le retour c'est 7 cycles en plus .
Donc ok je modifie
.Si je passe les box en 16 bit, c'est 42 cycles en plus max .
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par Stef Lun 3 Fév 2014 - 13:54
Non mais tu peux rester sur les box en 8 bits, y'a pas vraiment d'utilité à les avoir en 16 bits (à moins de gérer un meta sprite énorme mais on va écarter ce cas de figure peu probable :p).
317 cycles, haha 1 cycle de plus que ma méthode.
Bon sinon je vais essayer implémenter la fonction que j'ai décrit plus haut (et surement introduire quelques optimisations)
317 cycles, haha 1 cycle de plus que ma méthode.
Bon sinon je vais essayer implémenter la fonction que j'ai décrit plus haut (et surement introduire quelques optimisations)
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: Meilleurs algo d'un test par bouding box
par Invité Lun 3 Fév 2014 - 14:00
317 cycles, haha 1 cycle de plus que ma méthode.
eheh , j'ai ma bote secrète au cas où !!!
On compte l'appel à la fonction
Algo avec y sur 8 bit
- Code:
CollisionTest_16() ; // VERSION 3 X=16 bit Y=8 bit
{
#asm
; // Variables à initialiser avant l'appel de la fonction
; // sprite1 : sprite 1
; // ptr_hitbox_spr1 : tableau de collisions à 4 entrées du sprite 1
; // sprite2 : sprite 2
; // ptr_hitbox_spr2 : tableau de collisions à 4 entrées du sprite 2
; // TEST COLLISIONS EN X
; // Calcul x2
5 lda _pos_x2 ; // Ajout de val_x2 à x2
2 clc
7 adc [ ptr_hitbox_spr2 ]
4 sta <calc_pos + 2
5 lda _pos_x2 + 1
2 adc #0
4 sta <calc_pos + 3
29 CYCLES
; // Calcul x'2
5 lda _pos_x2 ; // Ajout de val_x2 + 1 à x2
2 clc
9 adc [ ptr_hitbox_spr2 ].1 ; // [ ptr_hitbox_spr2 ].1 => equivalent à ldy #1 + adc [ ptr_hitbox_spr2 ] , Y
4 sta <calc_pos + 4
5 lda _pos_x2 + 1
2 adc #0
4 sta <calc_pos + 5
31 CYCLES
; // Calcul x'1
5 lda _pos_x1 ; // Ajout de val_x1 + 1 à x1
2 clc
9 adc [ ptr_hitbox_spr1 ].1
2 tax
5 lda _pos_x1 + 1
2 adc #0
25 CYCLES
; // debut test x'1
; // Test 1ere colone x'1 >= x2
4 cmp <calc_pos + 3
2/3 bne .suite_test_xprim2
4 cpx <calc_pos + 2
2/3 bcc .fin_test
12 CYCLES
.suite_test_xprim2:
; // Test 2ieme colone x'1 < x'2
4 cmp <calc_pos + 5
2/3 bne .test_x_suite
4 cpx <calc_pos + 4
2/3 bcc .test_y
12 CYCLES
TOTAL 29+31+25+12+12 = 109 CYCLES
.test_x_suite:
; // Calcul x1
5 lda _pos_x1 ; // Ajout de val_x1 à x1
2 clc
7 adc [ ptr_hitbox_spr1 ]
2 tax
5 lda _pos_x1 + 1
2 adc #0
23 CYCLES
; // debut test x1,x2 et x'2 sont déjà calculés
4 and <calc_pos + 3 ; // Test 1ere colone x1 >= x2
4 eor <calc_pos + 5
2/3 bne .fin_test
4 cpx <calc_pos + 2 ; // Test 2ieme colone x1 < x'2
2/3 bcc .fin_test
4 cpx <calc_pos + 4
2/3 bcc .test_y
23 CYCLES
TOTAL 29+31+25+12+12+23+23 = 155 CYCLES
.fin_test:
stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
rts
; // TEST COLLISIONS EN Y
.test_y:
; // Calcul y'2
5 lda _pos_y2 ; // Ajout de val_y2 + 1 à y2
2 clc
9 adc [ ptr_hitbox_spr2 ].3
4 sta <calc_pos + 2
; // Calcul y2
5 lda _pos_y2 ; // Ajout de val_y2 à y2
2 clc
9 adc [ ptr_hitbox_spr2 ].2
4 sta <calc_pos + 4
5 lda _pos_y1 ; // Ajout de val_y1 à y1
2 clc
9 adc [ ptr_hitbox_spr1 ].2
4 sta <calc_pos
.suite_test_y2:
; // Test 1ere ligne y1 >= y2
4 cmp <calc_pos + 5
2/3 bne .test_y_suite
4 cmp <calc_pos + 4
2/3 bcs .col_ok
.test_y_suite:
; // Calcul y'1 ,y2 et y'2 sont déjà calculés
5 lda _pos_y1 ; // Ajout de val_y1 + 1 à y1
2 clc
9 adc [ ptr_hitbox_spr1 ].3
4 cpx <calc_pos + 2
2/3 bcs .fin_test
4 cmp <calc_pos + 4
2/3 bcc .fin_test
TOTAL 95 CYCLES
TOTAL 155 + 95 = 250 CYCLES
.col_ok:
6 inc <collision ; // Si collision ,alors collision <> 0
2 lda #1 ; //si retour dans REG A
7 rts
TOTAL 155 + 95 = 259 CYCLES / 263 CYCLE si variable
#endasm
}
259 cycles max si retour registre pour collision / 263 si retour variable .
97 min .
Bon sinon je vais essayer implémenter la fonction que j'ai décrit plus haut (et surement introduire quelques optimisations)
Ca commence à piquer ??
Dernière édition par TOUKO le Lun 3 Fév 2014 - 18:31, édité 1 fois
Invité- Invité
Re: Meilleurs algo d'un test par bouding box
par vingazole Lun 3 Fév 2014 - 14:34
Non, sur Master System il y a un système de pages/banques mémoire pour accéder à la totalité de la ROM, le cpu ne "voit" que des adresses 16 bits.Stef a écrit:Théoriquement le pointeur devrait être 32 bits car la bounding box étant constante elle peut être en ROM mais par simplification pour vous, on peut le considérer 16 bits (sinon ça va vous beaucoup vous pénaliser je pense).
Bon, je vais tâcher de faire une version multi-sprites avec les X sur 16 bits, les Y sur 8 bits et les coordonnées des hitboxes en 8 bits-non signé, ça me semble raisonnable pour une utilisation générale...
vingazole- Infirmier
- Nombre de messages : 4522
Age : 50
Localisation : Midian
Date d'inscription : 05/01/2012
Page 1 sur 9 • 1, 2, 3, 4, 5, 6, 7, 8, 9
Sujets similaires» Meilleurs jeux de baston ps1 et meilleurs Beat them all !
» [TEST] 2ème test éclair > WOLF FANG (saturn) > 5/6 suppos
» [TEST] Test Drive II The Duel - Super Nintendo
» [TEST] 1er test > KID DRACULA ( Game Boy ) !!!
» les meilleurs a-rpg de la ds ?
» [TEST] 2ème test éclair > WOLF FANG (saturn) > 5/6 suppos
» [TEST] Test Drive II The Duel - Super Nintendo
» [TEST] 1er test > KID DRACULA ( Game Boy ) !!!
» les meilleurs a-rpg de la ds ?
Page 1 sur 9
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
