2 routines de tri pour 65xx

Page 1 sur 2 1, 2  Suivant

Aller en bas

2 routines de tri pour 65xx

Message par Touko le Lun 14 Jan 2019 - 20:30

Je viens d'optimiser 2 routines de tri sur 65xxx, Si ça peut aider:
Code:
Insertion_Sort8()
{
 #asm
 Insert_Sort_8:
        ldy <nb_entrees
 
  .l1:
        tya
        tax
        lda _tab_entrees , X
        sta <val_temp1
 
  .l2:
        inx
        cmp _tab_entrees , X
        bcs .l3
        lda _tab_entrees , X
        sta _tab_entrees - 1 , X
        lda <val_temp1
        bra  .l2
 
  .l3:  
        sta _tab_entrees - 1 , X
        dey
        bpl .l1
      
        rts          
 #endasm
}

Code:
/* Pas compatible 6502 */
Bubble_Sort8()
{
 #asm
     dec <nb_entrees
 
  .bubble_sort8:  
     cly
 
     clv                   ; // TURN EXCHANGE FLAG OFF (V = 0)
 
     ldx <nb_entrees       ; // FETCH ELEMENT COUNT
 
  .nxtel:    
     lda _tab_entrees , Y       ; // FETCH ELEMENT
     cmp _tab_entrees + 1 , Y   ; // IS IT LARGER THAN THE NEXT ELEMENT?
     bcc .chkend
     beq .chkend
 
  ; // YES. EXCHANGE ELEMENTS IN MEMORY
     pha                        ; // BY SAVING BYTE ON STACK.
     lda _tab_entrees + 1 , Y   ; // THEN GET NEXT BYTE AND
     sta _tab_entrees , Y  
     pla                        ; // PULL BYTE FROM STACK
     sta _tab_entrees + 1 , Y  
 
   ; // TURN EXCHANGE FLAG ON (V = 1)
     lda #%01000000
     bit #%01000000
 
  .chkend:
     iny
     dex                        ; // END OF LIST?
     bne .nxtel                 ; // NO. FETCH NEXT ELEMENT
 
  ; // YES. EXCHANGE FLAG STILL OFF?
  ; // NO. GO THROUGH LIST AGAIN
     bvs .bubble_sort8
 
  ; // YES. LIST IS NOW ORDERED
    rts          
 #endasm
}

Elles sont toutes les 2 très rapide


Dernière édition par Touko le Mer 16 Jan 2019 - 12:26, édité 11 fois
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Lun 14 Jan 2019 - 21:25

C'est quoi le premier comme algo ? (je parle pas 65O2 couramment Razz)

Le deuxième c'est un tri à bulle (c'est marqué), c'est très efficace quand le tableau est "presque" trié, ce qui est souvent le cas (genre tu tries des sprites, y'a peu de chances que l'ordre soit très différent d'une frame sur l'autre).

Par contre, pour des données aléatoires, c'est bof (complexité moyenne en n²).

Y'a une variante où tu compares 2 éléments lointains (il te faut donc deux index), puis tu resserres l'écart progressivement, qui est beaucoup plus rapide. Mais je me souviens plus de son nom. Si ça t'intéresse, dis-le moi, je dois avoir ça dans un coin...

Sinon t'as le quicksort ou le tri fusion, mais c'est peut-être très chiant à coder en asm, et puis surtout ça n'a de sens que pour de grosses listes.
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Lun 14 Jan 2019 - 21:34

C'est marqué  Razz

Le premier est un insertion sort et le second un bubble .
C'est plus en utilisation pour un jeu, et non pour une applie, donc pour gérer un Y order de 0 à 255 .

Donc oui si tu dois gérer des tables aléatoires et avec bcp d'éléments tu utiliseras des algos prévus pour .

Sinon t'as le quicksort ou le tri fusion, mais c'est peut-être très chiant à coder en asm, et puis surtout ça n'a de sens que pour de grosses listes.
Le quick sort pour des listes déjà triée ou partiellement triées surtout avec peu d'éléments est pas bon(trop lent) .
J'ai fais plusieurs tests avec plusieurs algos, et ce sont les 2 qui marchent très bien pour un jeu 8/16 bits .
L'insertion est le plus polyvalent, dans le cas d'une liste triées ou aléatoire avec un NB d'éléments < 128 .


Dernière édition par Touko le Lun 14 Jan 2019 - 21:38, édité 1 fois
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Lun 14 Jan 2019 - 21:38

Ah oui merde, j'avais pas vu pour le 1er

Le deuxième doit quand même être plus efficace, même pour un jeu, non ?

Edit : j'avais pas vu ta remarque du bas. C'est étonnant, j'aurais pensé que le tri bulle serait en général plus véloce, même pour de petites listes.
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Lun 14 Jan 2019 - 21:39

@Tryphon a écrit:Ah oui merde, j'avais pas vu pour le 1er

Le deuxième doit quand même être plus efficace, même pour un jeu, non ?
Oui si tes éléments ne bougent pas trop il est plus rapide.

Edit : j'avais pas vu ta remarque du bas. C'est étonnant, j'aurais pensé que le tri bulle serait en général plus véloce, même pour de petites listes.
Tant que ta liste reste partiellement triées (à définir ce que l'on entend par partiellement), le bubble reste le meilleurs choix,sinon ses perfs s'écroulent .
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Lun 14 Jan 2019 - 21:48

Le problème du bubble, c'est les petits éléments qui descendent lentement. C'est pourquoi je te parlais d'une variante qui évite ce problème. Tu peux aussi faire un bubble alterné (en allant de gauche à droite puis de droite à gauche) pour accélérer la descente des petits, mais y'a d'autres cas pathogènes qui apparaissent.

('tain c'est vieux tout ça )
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Lun 14 Jan 2019 - 21:52

('tain c'est vieux tout ça )
Héhéhé, bah oui  Wink 
Mais pour un BTU par exemple t'as pas le choix .

mais y'a d'autres cas pathogènes qui apparaissent.
Voilà, y'a pas mal d'algos bien meilleurs, mais ils sont tous pour de grosses listes(ou des éléments > 8 bits) , sur nos consoles on va trier quoi, 40/50 éléments maxi.
Ici en plus ça prend 35/60 octets,et si je vois que j'ai besoin de mieux, je verrai . Cool


Dernière édition par Touko le Lun 14 Jan 2019 - 21:57, édité 1 fois
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Lun 14 Jan 2019 - 21:56

Non, la variante dont je te parle est pour le même genre de listes que le tri à bulles. Par contre, il n'est pas aussi rapide que le Quick Sort, ou le tri fusion. Mais plus que le tri à bulle classique.

T'es sur un BTU ?
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Lun 14 Jan 2019 - 21:58

T'es sur un BTU ?
Non, mais j'en ai un de prévu .

Non, la variante dont je te parle est pour le même genre de listes que le tri à bulles. Par contre, il n'est pas aussi rapide que le Quick Sort, ou le tri fusion. Mais plus que le tri à bulle classique.
Ah ça peut être intéressant, tu aurais le nom ou l'algo quelque part ??
Après faut voir avec une petite liste ce que ça donne .
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Lun 14 Jan 2019 - 22:03

Raah, là non (et j'ai du taf encore à finir).

Tu peux me le rappeler régulièrement, si tu vois que j'oublie ?
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 8:20

Pas de soucis, rien ne presse .  Wink
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mar 15 Jan 2019 - 10:12

L'insertion sort est, je pense, le plus efficace pour ce genre de cas mais il faut une structure qui s'y prête bien (une liste chainée), j'ai d'ailleurs du mal à suivre l'algo de Touko (il manque pas des trucs dans le code ?? genre y'a un STA sans rien derrière et y'a d'autres trucs qui m'échappent).

C'est celui que j'utilise dans SGDK pour implémenter la gestion du Z-order sur les sprites. J'avais un quicksort avant (que j'ai même passé en assembleur) et c'était incomparablement plus lent car comme le dit Touko, le QuickSort n'est pas efficace pour une liste qui est déjà quasiment triée.
Quand tu gères le Z-order sur plusieurs sprites tu n'as que peu de changement sur l'ordonnancement de la liste entre 2 frames du coup l'insertion sort marche très bien. Il a aussi un autre avantage, c'est que tu peux juste trier le sprite au moment où tu modifies son depth (ce que je fais), tu dilues ainsi le temps de tri (pas besoin de faire un tri total à chaque frame) :)

Sinon la réponse à votre question est surement là dedans :
https://www.toptal.com/developers/sorting-algorithms

Comme on peut le voir, l'insertion sort est imbattable pour une liste quasiment triée (par contre il n'est pas très efficace pour un tri global).


Dernière édition par Stef le Mar 15 Jan 2019 - 11:21, édité 1 fois
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 11:14

J'ai remis les fonctions dans des balises code, c'est moins lisible et l'indentation est merdique, mais au moins tout est là .
Ca a merdé au copier/coller.

Sinon pour mes tests , ma routine bubble est bien plus rapide que l'insertion si la liste est triée ou quasiment,l'insertion est bien plus rapide si la liste est aléatoire, par contre ses perfs sont aussi très bonnes si la liste est triée ou quasiment après faut voir en situation laquelle est la plus rapide pour un projet donné .
J'ai juste fait un comparatif sur une liste déjà triée pour avoir un aperçu .


Dernière édition par Touko le Mar 15 Jan 2019 - 11:30, édité 1 fois
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Mar 15 Jan 2019 - 11:29

Il y a beaucoup de variantes du QuickSort qui fonctionnent aussi très vite sur une liste déjà triée (en modifiant le choux du pivot).

Il me semble qu'on en avait parlé d'ailleurs.
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 11:31

Quick sort est plus complexe, et utilise aussi énormément la pile .
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Mar 15 Jan 2019 - 11:33

Oui, je pense aussi que c'est overkill ici. C'est surtout pour dire que la limitation sur les listes déjà triées peut-être corrigée.
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mar 15 Jan 2019 - 12:04

@Touko a écrit:Sinon pour mes tests , ma routine bubble est bien plus rapide que l'insertion si la liste est triée ou quasiment,l'insertion est bien plus rapide si la liste est aléatoire, par contre ses perfs sont aussi très bonnes si la liste est triée ou quasiment après faut voir en situation laquelle est la plus rapide pour un projet donné .
J'ai juste fait un comparatif sur une liste déjà triée pour avoir un aperçu .

C'est bizarre normalement l'insertion sort est la plus rapide si la liste est déjà triée ou presque (une seule passe et c'est réglée).

Edit: J'ai enfin compris ton algo d'insertion sort et je pense que tu y gagnerais beaucoup en perf avec une liste chainée, là sur un tableau effectivement c'est pas du tout efficace car tu dois recopier tout le tableau à chaque fois Wink
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 12:07

L'indexation est plus rapide qu'avec des pointeurs sur 65xxx, c'est pour ça que je fais comme ça .
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mar 15 Jan 2019 - 12:25

Non mais là c'est surtout que tu trie un tableau tout simple, donc l'insertion sort n'est pas très efficace car à chaque "insertion" tu n'as pas d'autres choix que de faire un décalage de tout le tableau !
Même sur 6502, avec une structure type "liste chainée" ça serait (un peu) plus rapide Wink
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Kannagi le Mar 15 Jan 2019 - 12:47

Le seul tri que j'utilise c'est pour le zorder et comme je connais le nombre d'objet à trier , je déplie ma boucle :p
(mais le code était pas forcément simple à lire , je ne le posterai pas je pense Mr. Green  )
Kannagi
Kannagi
Patient contaminé

Masculin Nombre de messages : 477
Age : 30
Localisation : Marseille
Date d'inscription : 18/08/2014

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Tryphon le Mar 15 Jan 2019 - 13:04

Mais tu utilises quel algo ?
Tryphon
Tryphon
Docteur *
Docteur *

Masculin Nombre de messages : 13814
Age : 42
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Kannagi le Mar 15 Jan 2019 - 13:43

Le truc c'est qu'il à pas de nom mon tri , alors je vais l’appeler le Tri Kannagi
(et puis c'est pas un tri en faite Razz )
Le principe est simple , je compare mon élément avec tout les autres , quand celui ci est plus grand j’incrémente mon registre (pour éviter les doublons , je compare aussi s'il sont égaux à certaine condition) et à la fin ben j'ai ma valeur qui indique où je dois mettre mon élément.

Niveau code ça donne ça : https://paste.ofcode.org/JMkB9xg2yEMDzdWkpA8Ct3

Sur PS1 (vu qu'il faut trier tout les triangles) je ne fait pas une comparaisons avec tout les élément (encore heureux) , je regarde juste si il n'y a pas d'élément occupé (donc avec le même z) , du coup c'est un tableau avec beaucoup de 'trou' (enfin ça dépend de combien en affiche de triangle) vu qu'ici z varie entre 0 et 4095.

Cela donne : https://paste.ofcode.org/nazC5DBSdW6VENqvKyLPW5


Dernière édition par Kannagi le Mar 15 Jan 2019 - 14:51, édité 1 fois
Kannagi
Kannagi
Patient contaminé

Masculin Nombre de messages : 477
Age : 30
Localisation : Marseille
Date d'inscription : 18/08/2014

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 14:27

@Kannagi a écrit:Le seul tri que j'utilise c'est pour le zorder et comme je connais le nombre d'objet à trier , je déplie ma boucle :p
(mais le code était pas forcément simple à lire , je ne le posterai pas je pense Mr. Green  )
Oui c'est encore mieux, si tu as peu d'éléments c'est une très bonne idée  Wink

Non mais là c'est surtout que tu trie un tableau tout simple, donc l'insertion sort n'est pas très efficace car à chaque "insertion" tu n'as pas d'autres choix que de faire un décalage de tout le tableau !
Pas besoin tu utilises un tableau Y en plus de ta structure de sprites qui est mis à jour au même moment que les sprites .
L'indice correspond à ton num de sprites,et rien n'empêche de faire une concordance avec un tableau en parallèle qui contient l'indice du sprite correspondant .
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mar 15 Jan 2019 - 14:59

@Touko a écrit:Pas besoin tu utilises un tableau Y en plus de ta structure de sprites qui est mis à jour au même moment que les sprites .
L'indice correspond à ton num de sprites,et rien n'empêche de faire une concordance avec un tableau en parallèle qui contient l'indice du sprite correspondant .

Bien sur tu peux recourir à des astuces de ce genre (au final tu tries un tableau mais tu appliques le tri sur 2 tableaux à la fois), c'est juste que c'est pas hyper élégant comme façon de faire (ça t'oblige aussi à dupliquer les Y ou les stocker dans un tableau à part) Razz
Et au final ça fait pas mal d'overhead comparé à une gestion type liste chainée mais bon c'est peut être plus facile de faire ainsi avec de l'assembleur sur ce CPU en particulier...

Sinon voici la fonction qui me permet de trier mon sprite quand je change son depth :

Code:
static void sortSprite(Sprite* sprite)
{
    // previous sprite
    Sprite* const prev = sprite->prev;
    // next sprite
    Sprite* const next = sprite->next;
    Sprite* s;

    // current sprite depth
    const s16 sdepth = sprite->depth;

    // find position forward first
    s = next;
    while(s && (s->depth < sdepth)) s = s->next;
    // position changed ? --> insert sprite after s->prev (as s is pointing on 'next')
    if (s != next) moveAfter(s?s->prev:lastSprite, sprite);
    else
    {
        // try to find position backward then
        s = prev;
        while(s && (s->depth > sdepth)) s = s->prev;
        // position changed ? --> insert sprite after s
        if (s != prev) moveAfter(s, sprite);
    }
}


J'utilise pour des raisons de pratique une liste chainée double (précédent et suivant), la fonction moveAfter(..) permettant de déplacer un sprite derrière un autre (comme un déplacement dans une liste chainée). La fonction a une complexité assez faible (O(N) avec N le nombre de sprite mais on est souvent en dessous car la liste est quasi déjà triée) et elle va être appelée uniquement lorsqu'on change le depth du sprite (souvent lié à sa position Y).
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 16:18

Bien sur tu peux recourir à des astuces de ce genre 
Ce n'est pas une astuce, mais une utilisation optimale des 65xxx,vu que l'indexation de tableau est son point fort .
Un accés à un pointeur indexé coûte 7 cycles,contre 5 pour un accès en RAM et 4 en ZP (sur le hu6280).
Tu organises tes données de façon à ce qu'elles soient indexées pour aller le plus vite possible.
Si je code une structure de sprites elle aura cette tête:

SPR_Pos_Y:   .ds XX
SPR_Pos_X_Low:   .ds XX
SPR_Pos_X_Hig:    .ds XX
SPR_Pattern_Low:  .ds XX
SPR_Pattern_Hig:   .ds XX
etc ...

; // Tableau pos Y et de num de sprites temporaires pour tri 
pos_y_temp:    .ds XX
num_spr:         .ds XX

; // XX est le nombre d'entrées maxi

Donc par exemple, le sprite du joueur serra le sprite d'indice 0, et donc chaque tableau d'indice 0 contient les datas de ton sprite, les données de l'indice 1, concernent le sprite 1, etc ...
Le tri se ferra sur le tableau pos_y_temp(mis à jour en même temps que les sprites) et je mettrai l'indice des sprites dans num_spr lors du tri,ensuite je créerai ma liste DMA pour la MAJ de la SAT via num_spr.
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mar 15 Jan 2019 - 17:10

Oui je sais, mais si c'est un peu une astuce d'organisation des données pour se plier à l'architecture particulière du CPU.
C'est le fameux "tableau de structures" vs "structure de tableaux" que t'impose un peu le 65xx mais qui est clairement moins élégant / pratique sur pleins d'aspects  Confused

Perso j'en viendrai à ce genre d'organisation de mes données *uniquement* si j'ai vraiment des soucis de performance car vraiment je trouve que c'est pas pratique du tout (pas de réelle structure de données). Mais réellement le plus gênant c'est surtout ces registres d'index 8 bits, heureusement sur 65816 on passe en 16 bits.
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mar 15 Jan 2019 - 17:52

Oui je sais, mais si c'est un peu une astuce d'organisation des données pour se plier à l'architecture particulière du CPU.
Si tu veux, mais plutôt qu'astuce, je dirai plutôt bonnes pratiques pour cette architecture .

mais qui est clairement moins élégant / pratique sur pleins d'aspects  
Elégant, non ça ne l'est pas c'est sur, pratique par contre ça l'est pour un habitué, puisque c'est une façon naturelle de voir les données sur ce type de CPU .
Un incrément/décrément d'un indice est autrement plus simple et rapide que changer une adresse qui nécessite une addition/soustraction pour moi .
Après forcement sur le 68k tu vas privilégier les pointeurs qui sont surement plus pratiques que l'indexation(si c'est possible) .
Et puis la SAT de la PCE n'a pas de link, donc j'ai pas réellement d'intérêt à utiliser les listes chainées pour le moment(je dis pas que je ne l'utiliserai pas) .
Et techniquement ça fonctionne comme une structure,dont l'indice est le pointeur,rien ne m'empêche dedans d'y ajouter un tableau donnant l'indice du sprite suivant pour les chaîner .

Techniquement la structure sera vu comme ça:

spr 0

SPR_Pos_Y , 0
SPR_Pos_X_Low , 0
SPR_Pos_X_Hig , 0
SPR_Pattern_Low , 0
SPR_Pattern_Hig , 0
...

spr 1

SPR_Pos_Y , 1
SPR_Pos_X_Low , 1
SPR_Pos_X_Hig , 1
SPR_Pattern_Low , 1
SPR_Pattern_Hig , 1
...

spr 2

SPR_Pos_Y , 2
SPR_Pos_X_Low , 2
SPR_Pos_X_Hig , 2
SPR_Pattern_Low , 2
SPR_Pattern_Hig , 2
....

etc ...

donc :
SPR_Pos_Y , X
SPR_Pos_X_Low , X
SPR_Pos_X_Hig , X
SPR_Pattern_Low , X
SPR_Pattern_Hig , X

au lieu de (sur une structure classique) :
ptr_struct->SPR_Pos_Y 
ptr_struct->SPR_Pos_X_Low 
ptr_struct->SPR_Pos_X_Hig 
ptr_struct->SPR_Pattern_Low
ptr_struct->SPR_Pattern_Hig 

L'indexation est ultra efficace si tu dois toucher des éléments non contigus dans ta structure
par exemple SPR_Pos_Y et SPR_Pattern_Low/Hig, tu y accèdes directement sans aucune opération supplémentaire . 
Sinon voici la fonction qui me permet de trier mon sprite quand je change son depth :
Tu détermines comment si un sprite à changé ??, tu as un flag dans ta struct ??
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mer 16 Jan 2019 - 9:53

Si tu veux, mais plutôt qu'astuce, je dirai plutôt bonnes pratiques pour cette architecture .

Certes Wink mais en terme de programmation c'est pas super bonne pratique si j'ose dire, surtout si tu veux mixer avec un langage plus haut niveau (style C) mais c'est vrai qu'ici c'est rarement le cas.

Un incrément/décrément d'un indice est autrement plus simple et rapide que changer une adresse qui nécessite une addition/soustraction pour moi .
Après forcement sur le 68k tu vas privilégier les pointeurs qui sont surement plus pratiques que l'indexation(si c'est possible) .
Et puis la SAT de la PCE n'a pas de link, donc j'ai pas réellement d'intérêt à utiliser les listes chainées pour le moment(je dis pas que je ne l'utiliserai pas) .
Et techniquement ça fonctionne comme une structure,dont l'indice est le pointeur,rien ne m'empêche dedans d'y ajouter un tableau donnant l'indice du sprite suivant pour les chaîner .

Oui je sais pourquoi on organise ses données ainsi sur 65xx et en réalité tu pourrais le faire sur 68k aussi en placant tes data dans les 32KB haut de la mémoire ou sur la pile (et donc l'adressage avec un offset 16 bit est suffisant pour toucher les différents tableaux), tu y gagnerais aussi en performance grâce à la post incrémentation gratuite... mais on a recours à ce genre d'astuce uniquement si on est au taquet en performance car c'est pas super élégant.
Pour la liste chainée, ce type de structure est interessant quand tu veux avoir une gestion dynamique de tes sprites (ce qui est mon cas forcément pour que ça soit un minimum flexible) mais effectivement avec une allocation complètement statique ça n'a pas vraiment d'intérêt.
Après je comprends que sur ce genre de machine, on est quand même un peu contraint par l'architecture du CPU. C'est justement ce que j'aime sur le 68000, il est très polyvalent et quelque soit ta manière de coder tu ne vas pas te prendre de méchantes pénalités.

Tu détermines comment si un sprite à changé ??, tu as un flag dans ta struct ??

J'ai une méthode setDepth(...) pour le sprite, c'est cette fonction qui va appeler le sortSprite(..) si jamais le depth est effectivement modifié (si la valeur donnée reste la même il n'y a pas besoin de trier). D'ailleurs c'est l'une des rares choses qui est appliqué immédiatement (le tri) là où habituellement j'utilise un flag pour mettre à jour plus tard (sur le SPR_update() qui met à jour tout mes sprites).
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Touko le Mer 16 Jan 2019 - 10:33

J'ai une méthode setDepth(...) pour le sprite, c'est cette fonction qui va appeler le sortSprite(..) si jamais le depth est effectivement modifié (si la valeur donnée reste la même il n'y a pas besoin de trier).
Tu gardes donc une copie de tes positions pour comparer aux nouvelles ?? (ou j'ai pas compris), mais pk pas mettre un flag ??, par exemple le bit 15 de la position Y à 1 si elle est modifiée ??
Touko
Touko
Docteur *
Docteur *

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

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Stef le Mer 16 Jan 2019 - 14:10

Un bout de code vaut mieux qu'un (long) discours :

Code:
void SPR_setDepth(Sprite *sprite, s16 value)
{
    // depth changed ?
    if (sprite->depth != value)
    {
        // set depth and sort sprite (need to be done immediately to get consistent sort)
        sprite->depth = value;
        sortSprite(sprite);
    }
}

Tu vas me dire que c'est un peu lourd de tester à chaque fois qu'on a effectivement changé la valeur de depth mais franchement c'est gratuit en comparaison d'un sort inutile Wink
Et puis bon ainsi c'est simple et clair, le code est très facile à comprendre Wink
Stef
Stef
Infirmier

Masculin Nombre de messages : 4684
Age : 39
Localisation : Sevres
Date d'inscription : 04/04/2007

Revenir en haut Aller en bas

Re: 2 routines de tri pour 65xx

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 1 sur 2 1, 2  Suivant

Revenir en haut


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