Meilleurs algo d'un test par bouding box

Page 4 sur 9 Précédent  1, 2, 3, 4, 5, 6, 7, 8, 9  Suivant

Voir le sujet précédent Voir le sujet suivant Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par fanoplusplus64K le Lun 3 Fév 2014 - 21:11

En parlant de ça , la version avec les additions précalculées, 176 cycles

Code:
   ;in :
   ;(HL) = xe(16),xe+le(16),ye(8),ye+he(8) enemy (6 aligned)
   ;(DE) = xp(16),xp+lp(16),yp(8),ye+hp(8) player (256 aligned)
   
   ;out :
   ;carry set if no collision
   ;carry reset if collision

   ;xp+lp<xe ?
   
   ld E,2         ;7 DE pointe sur xp+lp low
   
   ld A,(DE)      ;7 A = xp+lp low
   sub (HL)      ;7 xp+lp low - xe low
   inc E         ;4 DE pointe sur xp+lp hi
   inc L         ;4 HL pointe sur xe hi
   ld A,(DE)      ;7 A = xp+lp hi
   sbc (HL)      ;7 A = xp+lp hi - xe hi - carry
   ret c         ;5/11 pas de collision si xp+lp<xe
   
               ;section = 41
   
   ;xe+le<xp ?
   
   ld E,0         ;7 DE pointe sur xp low
   
   inc L         ;4 HL pointe sur xe+le low
   
   ex DE,HL      ;4 HL pointe sur xp low , DE pointe sur xe+le low
   ld A,(DE)      ;7 A=xe+le low
   sub (HL)      ;7 xe+le low - xp low
   inc E         ;4 DE pointe sur xe+le hi
   inc L         ;4 HL pointe sur xp hi
   ld A,(DE)      ;7 A=xe+le hi
   sbc (HL)      ;7 A=xe+le hi - xp hi - carry
   ret c         ;5/11 pas de collision si xe+le<xp
   
               ;section = 56 ;53
   
   ;yp+hp<ye ?

   
   ld L,5         ;7 HL pointe sur yp+hp   
   inc E         ;4 DE pointe sur ye
   
   ld A,(DE)      ;7 A=ye
   ld C,A         ;4 C=ye
   ld A,(HL)      ;7 A=yp+hp
   sub C         ;4 A=(yp+hp)-ye
   ret c         ;5/11
   
               ;section = 38
   
   ;ye+he<yp ?
   
   dec L         ;4 HL pointe sur yp
   inc E         ;4 DE pointe sur ye+he
   ld A,(DE)      ;7 A = ye+he
   sub (HL)      ;7 A = (ye+he)-yp
   ret c         ;5/11 pas de collision si xe+le<xp
   
   or A         ;4 reset carry
   ret            ;10
   
               ;section = 41
               
               ;total =176

fanoplusplus64K
Patient contaminé

Nombre de messages : 404
Date d'inscription : 16/01/2011

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Lun 3 Fév 2014 - 21:13

raaah le fano il déchire, bravo  Wink

Je referai la mienne pour voir si je peux pas encore réduire .

OK, donc tu changes la méthode pour avantager le 65xx avec des indexations gratuites...
Ce n'est pas fairplay ça !

Je change pas la donne, mais si on accepte les listes/tris prefait de stef je vois pas pk .


Dernière édition par TOUKO le Lun 3 Fév 2014 - 21:15, édité 1 fois
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Lun 3 Fév 2014 - 21:15

Oui, j'avais bien compris pour le report de CF, tu as écrit sub mais on comprenait bien que c'était un sbc d'après le commentaire:

Code:
sub (HL) ;7 hi(xp+lp)-carry-hi(xe)


Par contre je pense que le "or" ("or a", je suppose Wink) après le dernier "ret c" est inutile : la CF est forcément à zéro vu qu'on est après un "ret c", justement.

Ah ben du coup on peut se contenter d'un "ret" pour remplacer "ret c"+"ret", CF étant positionné par le "sub (hl)"...


Dernière édition par vingazole le Lun 3 Fév 2014 - 21:23, édité 1 fois
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Lun 3 Fév 2014 - 21:18

Même la version 16/8 est pas mal, 317 c'est wahou ..
Faudrait voir un codeur 65xx plus calé que moi pour voir ce qu'il arrive à faire, il est où manfred putin  tongue
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par fanoplusplus64K le Lun 3 Fév 2014 - 21:26

Je serai surtout curieux de voir ce que peux donner ce genre de routine sur un X80 de la gameboy.(autant pour moi , il ne s'agit pas du R800 des MSX)

vingazole a écrit:
Code:
sub (HL) ;7 hi(xp+lp)-carry-hi(xe)


Par contre je pense que le "or" ("or a", je suppose Wink) après le dernier "ret c" est inutile : la CF est forcément à zéro vu qu'on est après un "ret c", justement.
Bien vu, 9 cycles en moins !

Ce qui nous donne 290 cycles en 16/8 sans precalc et 167 en 16/8 avec precalc  smile 
Mention honorable pour notre bon vieux Z80  Wink


Dernière édition par fanoplusplus64K le Lun 3 Fév 2014 - 22:10, édité 2 fois

fanoplusplus64K
Patient contaminé

Masculin Nombre de messages : 404
Age : 41
Date d'inscription : 16/01/2011

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Lun 3 Fév 2014 - 21:36

et merde, il est ou mon X2   

Va falloir que je riposte lol ..
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Lun 3 Fév 2014 - 22:03

Tu en profiteras pour corriger le titre du topic...  Mr. Green
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Vetea le Lun 3 Fév 2014 - 22:55

Euh .. Je sais gérer pas mal de chose en programmation, mais la j'ai perdu pied dès les premières pages ...
Bonne chance !!
* s'en va sur la pointe des pieds ... *
avatar
Vetea
Docteur *
Docteur *

Masculin Nombre de messages : 4300
Age : 46
Localisation : Baillargues
Date d'inscription : 22/06/2012

http://www.rolango.fr/

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Lun 3 Fév 2014 - 23:54

La version avec les boxes précalculées, si elle est plus rapide, nécessite tout de même une première étape où on va calculer les boxes de chaque sprite. Ca signifie aussi qu'il faut de la mémoire pour les stocker... Du coup vous finissez par ne comparer que les boxes entre elle directement si j'ai bien compris =)

C'est effectivement intéressant pour gagner en vitesse, on a une boucle en O(N) pour le calcul des boxes et la collision (qui elle est plutot en O(N²)) devient plus rapide =)

Je vais faire la version avec boxes précalculées voir ce que ça donne mais à mon avis je ne gagne pas trop.


Dernière édition par Stef le Mar 4 Fév 2014 - 0:31, édité 1 fois
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 0:18

Donc ce coup ci en entrée on a la box player et les boxes ennemies :

Code:
8     lea    4(a7), a6      ; a6 point on parameters
12    move.l (a6)+, a0      ; a0 = player
12    move.l (a6)+, a1      ; a1 = enemies
12    move.l (a6), d7       ; d7 = numEnemies
4     subq.w #1,d7          ; d7 = numEnemies - 1 (prepare for DBCC instruction)
48

12+16 movem.w (a0)+, d0-d3  ; d0 = player.xmin... d3 = player.ymax
28

.loop                       ; do {

// TEST on X coordinates

4     move.l a1, a2         ; a2 point on enemy
8     cmp.w (a2)+, d1       ; if (player.xmax < enemy.xmin)
10    blt .no_collid        ;   no collision
22

8     cmp.w (a2)+, d0       ; if (player.xmin > enemy.xmax)
10    bgt .no_collid        ;   no collision
18

// TEST on Y coordinates

8     cmp.w (a2)+, d3       ; if (player.ymax < enemy.ymin)
10    blt .no_collid        ;   no collision
18

8     cmp.w (a2)+, d2       ; if (player.ymin > player.ymax)
10    bgt .no_collid        ;   no collision
18

.collid
4     move #1,d0            ; return 1
16    rts
20

.no_collid
8     add.l #8, a1          ; a1 point on next enemy
10    dbra d7, .loop        ; } while (numEnemies--)
18

4+2   move #0,d0            ; return 0
16    rts
22

init: 76
test min: 22
test mean: 40
test max: 76
total per loop: 94
end: 20/22

Et si je traitais en appel unique (ce qui est moins interessant je trouve mais ça me permet de comparer à vos méthodes) ça reviendrait à ça : 8/24 + (22 * 4) + 20 soit 116 ou 132 cycles en tout selon le type d'initialisation.


Dernière édition par Stef le Mar 4 Fév 2014 - 1:08, édité 1 fois
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 0:57

fanoplusplus64K a écrit:Je serai surtout curieux de voir ce que peux donner ce genre de routine sur un X80 de la gameboy.(autant pour moi , il ne s'agit pas du R800 des MSX)

vingazole a écrit:
Code:
sub (HL) ;7 hi(xp+lp)-carry-hi(xe)


Par contre je pense que le "or" ("or a", je suppose Wink) après le dernier "ret c" est inutile : la CF est forcément à zéro vu qu'on est après un "ret c", justement.
Bien vu, 9 cycles en moins !

Ce qui nous donne 290 cycles en 16/8 sans precalc et 167 en 16/8 avec precalc  smile 
Mention honorable pour notre bon vieux Z80  Wink

290 sans precalcul c'est carrément pas mal, et le 167 avec non plus ! Bien joué :)
Je serais curieux de voir combien ça peut donner en loop (par sur que ca descende bcp plus).
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 1:04

TOUKO a écrit:Bon nouvelle routine avec calcul des box déjà calc dans tableau

Code:
tab_box_joueur[8];
tab_box_sprite[8];

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
; // debut test x'1
; // Test 1ere colone x'1 >= x2
; // Partie HIGH
5    lda _tab_box_joueur + 3
5    cmp _tab_box_sprite + 1
2/3  bne .suite_test_xprim2
; // Partie LOW
5    ldx _tab_box_joueur + 2
5    cpx _tab_box_sprite
2/3  bcc .fin_test

 .suite_test_xprim2:
; // Test 2ieme colone x'1 < x'2
; // Partie HIGH
5   cmp _tab_box_sprite + 3
2/3 bne .test_x_suite
 ; // Partie LOW
5   cpx _tab_box_sprite + 2
2/3 bcc .test_y
TOTAL 38 CYCLES

 .test_x_suite:
; // debut test x1
; // Test  x1 >= x2
; // Partie LOW
    lda _tab_box_joueur + 1
    cmp _tab_box_sprite + 1
    bne .fin_test
; // Partie HIGH
    ldx _tab_box_joueur
    cpx _tab_box_sprite
    bcc .test_y

; // Test  x1 <= x'2
; // Partie LOW
    cmp _tab_box_sprite + 3
    bne .fin_test
; // Partie HIGH
    cpx _tab_box_sprite + 2
    bcc .test_y
TOTAL 38 CYCLES
SOIT 38 * 2 = 76 CYCLES
 .fin_test:
    stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
    rts
 
; // TEST COLLISIONS EN Y
 .test_y:
 ; // idem test x
SOIT 38 * 2 = 76 CYCLES

TOTAL 76*2 = 152 CYCLES
 
.col_ok:
6   inc <collision     ; // Si collision ,alors collision <> 0
2   lda  #1                ; //si retour dans REG A
7   rts

 #endasm
}
161 CYCLES max si sortie dans registre en 16/8
165 cycles max si variables

min 25 si registre .
Mid 50 si registre


Y'a pas un problème avec ton code ? J'ai l'impression que tu fais trop de test ! D'ou ton nombre de cycle si élevé (au niveau du Z80) !
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 9:50

Stef a écrit:La version avec les boxes précalculées, si elle est plus rapide, nécessite tout de même une première étape où on va calculer les boxes de chaque sprite. Ca signifie aussi qu'il faut de la mémoire pour les stocker... Du coup vous finissez par ne comparer que les boxes entre elle directement si j'ai bien compris =)

C'est effectivement intéressant pour gagner en vitesse, on a une boucle en O(N) pour le calcul des boxes et la collision (qui elle est plutot en O(N²)) devient plus rapide =)

Je vais faire la version avec boxes précalculées voir ce que ça donne mais à mon avis je ne gagne pas trop.
C'est pourtant ce que tu fais avec ta routine par lot, tu déportes création/tris de ta liste sur le prog principal .
Un surcoût que tu as dans ton prog principal et que tu comptes pas .

en supprimant les calculs dans la routine de test je voulais justement montrer cela .

Y'a pas un problème avec ton code ? J'ai l'impression que tu fais trop de test ! D'ou ton nombre de cycle si élevé (au niveau du Z80) !
elle est faite à la va vite, j'ai rien optimisé, à part supprimer les calculs .

Mais bon si on se met à faire des trucs sur la boucle principale pour alléger artificiellement la routine on sort complètement du contexte .
Le but était de faire tout dans la routine de test de bounding box, et pas de déporter des calculs supplémentaires sur la boucle principale .

On devait prendre une routine, et tout faire dedans, là on sort du contexte, les routine 16/16 8/8 16/8 de base étaient pour moi les vraies routine représentatives, tout les traitements sont à l'intérieur .
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Mar 4 Fév 2014 - 9:58

TOUKO, dans ton algo cité par Stef tu marques "idem test x" pour le test en Y et tu comptes le même nombre de cycles, alors que tu es censé avoir des comparaisons de valeurs 8 bits  What the fuck ?!?
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 10:30

Oui en fait j'avais pas précisé que je faisais du 16/16 et non du 16/8
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Mar 4 Fév 2014 - 10:38

Ah d'accord, au temps pour moi salut


Dernière édition par vingazole le Mar 4 Fév 2014 - 10:43, édité 1 fois
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 10:42

en précalcul  16/16
Code:

CollisionTest_16()  ; // VERSION 3 X=16 bit Y=16 bit                  
{
 #asm
   .zp
      tab_box_joueur:      .ds 8   
      tab_box_sprite:      .ds 8
      
   .code
      
 ; // 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
; // debut test x'1
; // Test 1ere colone x'1 >= x2 & 2ieme colone x'1 < x'2
; // Partie HIGH
4    lda <tab_box_joueur + 3
4    cmp <tab_box_sprite + 1
2/3  bne .test_x_suite
4    cmp <tab_box_sprite + 3
2/3  bne .test_x_suite
; // Partie LOW
4    ldx <tab_box_joueur + 2
4    cpx <tab_box_sprite
2/3  bcc .fin_test
4    cpx <tab_box_sprite + 2
2/3  bcc .fin_test

TOTAL 32 CYCLES

 .test_x_suite:
; // debut test x1
; // Test  x1 >= x2 & Test  x1 <= x'2
; // Partie HIGH
    lda <tab_box_joueur + 1
    cmp <tab_box_sprite + 1
    bne .fin_test
    cmp <tab_box_sprite + 3
    bne .fin_test
; // Partie LOW
    ldx <tab_box_joueur
    cpx <tab_box_sprite
    bcc .test_y
    cpx <tab_box_sprite + 2
    bcc .test_y
  
TOTAL 32 CYCLES
SOIT 32 * 2 = 64 CYCLES

 .fin_test:
    stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
    rts
 
; // TEST COLLISIONS EN Y
 .test_y:
 ; // idem test x
SOIT 32 * 2 = 64 CYCLES
 
.col_ok:
2   lda  #1                ; //si retour dans REG A
7   rts

TOTAL 64*2 + 2 + 7 = 137 CYCLES
 #endasm
}

137 max
28 min


Dernière édition par TOUKO le Mar 4 Fév 2014 - 15:42, édité 4 fois
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Mar 4 Fév 2014 - 10:43

Dis-moi, je suis en train de me documenter sur les opcodes du 6502 (à défaut de trouver quelque chose sur le 6280...), pour la soustraction normale il faut mettre C à 1 ("sec" ?) puis faire un "sbc" et pour la soustraction avec retenue il faut au préalable mettre C à zéro, c'est bien ça ? Et en cas de retenue on obtient C=0 (en fait le contraire de ce qu'on fait un z80). J'ai bon ou c'est la doc que j'ai lue qui est fausse ?
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 10:49

en precalcul 16/8

Code:
CollisionTest_16()  ; // VERSION 3 X=16 bit Y=8 bit                  
{
 #asm
 .zp
     tab_box_joueur: .ds 8
     tab_box_sprite: .ds 8
 
 .code
 
; // 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
; // debut test x'1
; // Test 1ere colone x'1 >= x2 & 2ieme colone x'1 < x'2
; // Partie HIGH
4    lda <tab_box_joueur + 3
4    cmp <tab_box_sprite + 1
2/3  bne .test_x_suite
4    cmp <tab_box_sprite + 3
2/3  bne .test_x_suite
; // Partie LOW
4    ldx <tab_box_joueur + 2
4    cpx <tab_box_sprite
2/3  bcc .fin_test
4    cpx <tab_box_sprite + 2
2/3  bcc .fin_test

TOTAL 32 CYCLES

 .test_x_suite:
; // debut test x1
; // Test  x1 >= x2 & Test  x1 <= x'2
; // Partie HIGH
    lda <tab_box_joueur + 1
    cmp <tab_box_sprite + 1
    bne .fin_test
    cmp <tab_box_sprite + 3
    bne .fin_test
; // Partie LOW
    ldx <tab_box_joueur
    cpx <tab_box_sprite
    bne .test_y
    cpx <tab_box_sprite + 2
    bcc .test_y
  
TOTAL 32 CYCLES
SOIT 32 * 2 = 64 CYCLES

 .fin_test:
    stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
    rts
 
; // TEST COLLISIONS EN Y
 .test_y:
 ; // idem test x mais sans partie HIGH
SOIT 32 CYCLES
 
.col_ok:
2   lda  #1                ; //si retour dans REG A
7   rts

TOTAL 64 + 32 + 2 + 7 = 105  CYCLES
 #endasm
}

105 max
min 28 (14 si je test y en premier)


Dernière édition par TOUKO le Mar 4 Fév 2014 - 15:54, édité 11 fois
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 10:50


C'est pourtant ce que tu fais avec ta routine par lot, tu déportes création/tris de ta liste sur le prog principal .
Un surcoût que tu as dans ton prog principal et que tu comptes pas .

Je ne suis vraiment pas d'accord avec cette remarque... c'est une implémentation comme une autre et je trouve que la mienne est bien plus logique pour le coup.
Les traitements que je fais en amont, tu dois les faire aussi mais d'une autre manière (y'a bien un moment ou tu testes si ton sprite est visible ou pas), surtout toi tu risques de te les taper bien plus souvent, justement au moment ou tu vas tester les collisions de ton sprite avec les autres par exemple.


elle est faite à la va vite, j'ai rien optimisé, à part supprimer les calculs .

Il n'y a pas que ça, il me semble que tu fais 8 tests 16 bits là où 4 suffisent...


Mais bon si on se met à faire des trucs sur la boucle principale pour alléger artificiellement la routine on sort complètement du contexte .
Le but était de faire tout dans la routine de test de bounding box, et pas de déporter des calculs supplémentaires sur la boucle principale .

Le but c'est de réussir à faire un bounding box rapide, c'est pas moi qui ait commencé à précalculer les boxes mais je trouve que c'était une bonne idée car la complexité du précalcule est insignifiante comparé au calcul des collisions en elle même. Toi tu penses toujours le petit cas pratique avec quelques sprites mais qui ne posera pas de problème de toute manière, le cas interessant c'est le cas critique, quand il faut en calculer beaucoup.


Dernière édition par Stef le Mar 4 Fév 2014 - 10:54, édité 1 fois
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par fanoplusplus64K le Mar 4 Fév 2014 - 10:51

Oulà , va falloir sortir le R800 pour suivre  MDR 

fanoplusplus64K
Patient contaminé

Masculin Nombre de messages : 404
Age : 41
Date d'inscription : 16/01/2011

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 10:55

vingazole a écrit:Dis-moi, je suis en train de me documenter sur les opcodes du 6502 (à défaut de trouver quelque chose sur le 6280...), pour la soustraction normale il faut mettre C à 1 ("sec" ?) puis faire un "sbc" et pour la soustraction avec retenue il faut au préalable mettre C à zéro, c'est bien ça ? Et en cas de retenue on obtient C=0 (en fait le contraire de ce qu'on fait un z80). J'ai bon ou c'est la doc que j'ai lue qui est fausse ?
Alors pour la sous nomale tu fais un sec (c=1) puis sbc(c= dépend du résultat) .
pour addition c'est le contraire clc (c=0) -> adc(c = dépend du résultat)

Donc oui si tu veux directement faire une sous avec retenue tu fais un clc -> sbc

Si tu veux je peux t'envoyer la doc sur le 6280, tout les opcodes avec description et tout ..

Le but c'est de réussir à faire un bounding box rapide, c'est pas moi qui ait commencé à précalculer les boxes mais je trouve que c'était une bonne idée car la complexité du précalcule est insignifiante comparé au calcul des collisions en elle même. Toi tu penses toujours le petit cas pratique avec quelques sprites mais qui ne posera pas de problème de toute manière, le cas interessant c'est le cas critique, quand il faut en calculer beaucoup.
Le but était de tout avoir dans la routine pour comparer, si tu dépends de bcp de données externes pour faire ta routine comme avec ton tri, on peut plus calculer décemment car il faut voir avec ce qui tourne dans la boucle principale .
Je dis pas que ton approche est pas bonne , juste que la partie tris n'est pas quantifiable dans la routine, alors qu'elle impacte forcement ta boucle principale, comme avec le precalcul, qui impacte plus globalement que si il était dans la routine ..


Dernière édition par TOUKO le Mar 4 Fév 2014 - 11:25, édité 2 fois
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 10:57

TOUKO a écrit:en precalcul 16/8

Code:
char tab_box_joueur[8];
char tab_box_sprite[8];

CollisionTest_16()  ; // VERSION 3 X=16 bit Y=8 bit                  
{
 #asm
 .zp
 tab_box_joueur: .ds 8
tab_box_sprite: .ds 8
 
.code
 
; // 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
; // debut test x'1
; // Test 1ere colone x'1 >= x2 & 2ieme colone x'1 < x'2
; // Partie HIGH
4    lda <tab_box_joueur + 3
4    cmp <tab_box_sprite + 1
4    cmp <tab_box_sprite + 3
2/3  bne .test_x_suite
; // Partie LOW
4    ldx <tab_box_joueur + 2
4    cpx <tab_box_sprite
4 cpx <tab_box_sprite + 2
2/3  bcc .fin_test

TOTAL 28 CYCLES

 .test_x_suite:
; // debut test x1
; // Test  x1 >= x2 & Test  x1 <= x'2
; // Partie HIGH
    lda <tab_box_joueur + 1
    cmp <tab_box_sprite + 1
 cmp <tab_box_sprite + 3
    bne .fin_test
; // Partie LOW
    ldx <tab_box_joueur
    cpx <tab_box_sprite
 cpx <tab_box_sprite + 2
    bcc .test_y
  
TOTAL 28 CYCLES
SOIT 28 * 2 = 56 CYCLES

 .fin_test:
    stz <collision ; // Annule la collision si test negatif en mettant la var collision à 0
    rts
 
; // TEST COLLISIONS EN Y
 .test_y:
 ; // idem test x mais sans partie HIGH
SOIT 28 CYCLES
 
.col_ok:
2   lda  #1                ; //si retour dans REG A
7   rts

TOTAL 56 + 28 + 2 + 7 = 93  CYCLES
 #endasm
}

93 max
min 14 (si je teste y en premier)


Je comprends plus du tout ton code, tu fais 2 cmp à la suite O_o ? quel interet ??
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Mar 4 Fév 2014 - 10:57

Ah oui, je veux bien pour la doc Wink


Quand tu fais ça :

Code:
   lda <tab_box_joueur + 3
   cmp <tab_box_sprite + 1
   cmp <tab_box_sprite + 3

Le résultat de la comparaison du milieu est perdue, non ? Ou alors le 6280 est très différent des autres cpu dans le fonctionnement de ses comparaisons ?


Dernière édition par vingazole le Mar 4 Fév 2014 - 11:04, édité 1 fois
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 11:04

vingazole a écrit:Ah oui, je veux bien pour la doc Wink


Quand tu fais ça :

Code:
   lda <tab_box_joueur + 3
   cmp <tab_box_sprite + 1
   cmp <tab_box_sprite + 3

Le résultat de la comparaison du milieu est perdue, non ? Ou alors le 6280 est très différent des autres cpu dans le fonctionnemennt de ses comparaisons ?
effectivement, je suis peut être allé un peut vite là  scratch 
Je vais revoir ça ..

J'envoie la doc sur ta boite . Wink

EDIT: ok  c'est bon pour la doc .
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par vingazole le Mar 4 Fév 2014 - 11:11

Doc bien reçue ! Merci TOUKO thumleft
avatar
vingazole
Infirmier

Masculin Nombre de messages : 4011
Age : 43
Localisation : Les Herbiers (85)
Date d'inscription : 05/01/2012

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 11:14

De rien .
Si tu arrives à comprendre (normalement oui venant du Z80), dis moi ce que tu en penses, en bien ou en mal  Wink 
Si c'est un type de cpu difficile à comprendre, ou coder .

Par contre le 6502 à certains opcode plus rapides (en général 1 cycle en moins).

Ok j'ai corrigé, effectivement je me suis emballé trop vite .

EDIT: j'ai refait une correction, j'avais une erreur dans le comptage des cycles .
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par fanoplusplus64K le Mar 4 Fév 2014 - 12:28

TOUKO a écrit:Si tu veux je peux t'envoyer la doc sur le 6280, tout les opcodes avec description et tout ..
Je suis preneur aussi, je t'avais envoyé un mail il y a quelques temps à ce propos mais je crois que tu ne l'as pas reçu/vu.

fanoplusplus64K
Patient contaminé

Masculin Nombre de messages : 404
Age : 41
Date d'inscription : 16/01/2011

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 13:20

fanoplusplus64K a écrit:
TOUKO a écrit:Si tu veux je peux t'envoyer la doc sur le 6280, tout les opcodes avec description et tout ..
Je suis preneur aussi, je t'avais envoyé un mail il y a quelques temps à ce propos mais je crois que tu ne l'as pas reçu/vu.
Dsl fano il me semble pas avoir vu de message pour ça, je t'envoie ça de suite  Wink
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par TOUKO le Mar 4 Fév 2014 - 13:43

Routine normale sans précalc 16/8
Code:
/* FONCTION DETECTION COLLISION X 16 bit, Y 8 bit */
CollisionTest_16_8()                      
{
   #asm
             .zp
      pos_x1:      .ds 2
      pos_x2:      .ds 2
      pos_y2:      .ds 2
      pos_y1:      .ds 2
         
         .code
   ; // 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
   4   lda    <pos_x2         ; // Ajout de val_x2 à x2               
   2   clc
   7   adc    [ ptr_hitbox_spr2 ]                  
   4   sta    <calc_pos + 2      
   4   lda    <pos_x2   + 1
   2   adc   #0
   4   sta   <calc_pos + 3

   ; // Calcul x'2
   4   lda    <pos_x2         ; // Ajout de val_x2 + 1 à x2      
   9   adc    [ ptr_hitbox_spr2 ].1      
   4   sta    <calc_pos + 4      
   4   lda    <pos_x2   + 1
   2   adc      #0
   4   sta      <calc_pos + 5   
54 CYCLES

   ; // Calcul x'1
   4   lda    <pos_x1      ; // Ajout de val_x1 + 1 à x1                     
   9   adc    [ ptr_hitbox_spr1 ].1               
   2   tax
   4   lda    <pos_x1   + 1      
   2   adc   #0      
   
   ; // 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
87 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      
      
     .test_x_suite:       
   ; // Calcul x1                     
   4   lda    <pos_x1            ; // Ajout de val_x1 à x1               
   2   clc
   7   adc    [ ptr_hitbox_spr1 ]            
   2   tax
   4   lda    <pos_x1   + 1
   2   adc   #0      
120 CYCLES
   
   ; // debut test x1,x2 et x'2 sont déjà calculés      
   4   and   <calc_pos + 3            ; // Test 1ere colone x1 >= x2   MSB       
   4   eor   <calc_pos + 5
   2/3   bne   .fin_test
      
   4   cpx   <calc_pos + 2            ; // Test 2ieme colone x1 < x'2 LSB
   2/3   bcc   .fin_test
   4   cpx   <calc_pos + 4
   2/3   bcc   .test_y      
   
142 CYCLES
    .fin_test:
   2   cla   ; // Annule la collision si test negatif en mettant la var collision à 0      
   7   rts
   
   ; // TEST COLLISIONS EN Y
     .test_y:             
   ; // Calcul y'2
   4   lda    <pos_y2            ; // Ajout de val_y2 + 1 à y2               
   9   adc    [ ptr_hitbox_spr2 ].3      
   4   sta    <calc_pos + 2   
      
   ; // Calcul y2
   4   lda    <pos_y2            ; // Ajout de val_y2 à y2         
   2   clc
   9   adc    [ ptr_hitbox_spr2 ].2                  
   4   sta    <calc_pos + 4               
      
   4   lda    <pos_y1            ; // Ajout de val_y1 à y1
   2   clc
   9   adc    [ ptr_hitbox_spr1 ].2                     
      
   4   cmp   <calc_pos + 2
   2/3   bcs    .fin_test
57 CYCLES
+9   
     .suite_test_y2:      
   ; // Test 1ere ligne y1 >= y2            
   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
   4   lda    <pos_y1            ; // Ajout de val_y1 + 1 à y1               
   9   adc   [ ptr_hitbox_spr1 ].3                  
   
   ; // TEST POIDS FAIBLES LSB
   4   cmp   <calc_pos + 2
   2/3   bcs   .fin_test
   4   cmp   <calc_pos + 4
   2/3   bcc   .fin_test      
   
TOTAL 88 CYCLES   
     .col_ok:      
      lda   #1         ; // Si collision ,alors collision <> 0
      rts
TOTAL 142 + 88 + 2 + 7 = 239 CYCLES

   #endasm   
}

239 cycles max
90 Min (65 si je teste y en premier)

On peut encore descendre de 10/15 cycles je pense dans le max si je remplace les pointeurs par des tableaux indexés .
Je peux aussi gratter pas mal de cycles si on considère l'écran < 512 ..
avatar
TOUKO
Docteur *
Docteur *

Masculin Nombre de messages : 12137
Age : 44
Localisation : LE MANS/MARSEILLE
Date d'inscription : 08/07/2010

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Stef le Mar 4 Fév 2014 - 18:25

TOUKO a écrit:Routine normale sans précalc 16/8
...
239 cycles max
90 Min (65 si je teste y en premier)

On peut encore descendre de 10/15 cycles je pense dans le max si je remplace les pointeurs par des tableaux indexés .
Je peux aussi gratter pas mal de cycles si on considère l'écran < 512 ..

C'est assez marrant de voir que le 6502 (ou dérivé) est plus lent quand on utilise des pointeurs plutot que des tableaux indexés là où la logique attend plutot le contraire O_o...
Enfin du coup, comment tu fais pour traiter un tableau le plus rapidement possible ? T'es bien obligé d'utiliser un pointeur quand même ?

Bon sinon 68000 win  Mr. Green
avatar
Stef
Infirmier

Masculin Nombre de messages : 3598
Age : 38
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: Meilleurs algo d'un test par bouding box

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 4 sur 9 Précédent  1, 2, 3, 4, 5, 6, 7, 8, 9  Suivant

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum