2 routines de tri pour 65xx
2 participants
Page 1 sur 2
Page 1 sur 2 • 1, 2
2 routines de tri pour 65xx
Je viens d'optimiser 2 routines de tri sur 65xxx, Si ça peut aider:
Elles sont toutes les 2 très rapide
- 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
Invité- Invité
Re: 2 routines de tri pour 65xx
C'est quoi le premier comme algo ? (je parle pas 65O2 couramment )
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.
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- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
C'est marqué
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 .
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 .
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 .
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) .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.
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
Invité- Invité
Re: 2 routines de tri pour 65xx
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.
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- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
Oui si tes éléments ne bougent pas trop il est plus rapide.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 ?
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 .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.
Invité- Invité
Re: 2 routines de tri pour 65xx
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 )
('tain c'est vieux tout ça )
Tryphon- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
Héhéhé, bah oui('tain c'est vieux tout ça )
Mais pour un BTU par exemple t'as pas le choix .
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.mais y'a d'autres cas pathogènes qui apparaissent.
Ici en plus ça prend 35/60 octets,et si je vois que j'ai besoin de mieux, je verrai .
Dernière édition par Touko le Lun 14 Jan 2019 - 21:57, édité 1 fois
Invité- Invité
Re: 2 routines de tri pour 65xx
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 ?
T'es sur un BTU ?
Tryphon- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
Non, mais j'en ai un de prévu .T'es sur un BTU ?
Ah ça peut être intéressant, tu aurais le nom ou l'algo quelque part ??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.
Après faut voir avec une petite liste ce que ça donne .
Invité- Invité
Re: 2 routines de tri pour 65xx
Raah, là non (et j'ai du taf encore à finir).
Tu peux me le rappeler régulièrement, si tu vois que j'oublie ?
Tu peux me le rappeler régulièrement, si tu vois que j'oublie ?
Tryphon- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
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).
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- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
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 .
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
Invité- Invité
Re: 2 routines de tri pour 65xx
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.
Il me semble qu'on en avait parlé d'ailleurs.
Tryphon- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
Quick sort est plus complexe, et utilise aussi énormément la pile .
Invité- Invité
Re: 2 routines de tri pour 65xx
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- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
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
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
L'indexation est plus rapide qu'avec des pointeurs sur 65xxx, c'est pour ça que je fais comme ça .
Invité- Invité
Re: 2 routines de tri pour 65xx
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
Même sur 6502, avec une structure type "liste chainée" ça serait (un peu) plus rapide
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
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 )
(mais le code était pas forcément simple à lire , je ne le posterai pas je pense )
Invité- Invité
Re: 2 routines de tri pour 65xx
Mais tu utilises quel algo ?
Tryphon- Docteur *
- Nombre de messages : 26166
Age : 47
Localisation : Un peu plus à l'Ouest
Date d'inscription : 23/07/2016
Re: 2 routines de tri pour 65xx
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 )
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
(et puis c'est pas un tri en faite )
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
Invité- Invité
Re: 2 routines de tri pour 65xx
Oui c'est encore mieux, si tu as peu d'éléments c'est une très bonne idéeKannagi 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 )
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 .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 !
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 .
Invité- Invité
Re: 2 routines de tri pour 65xx
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)
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- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
Ce n'est pas une astuce, mais une utilisation optimale des 65xxx,vu que l'indexation de tableau est son point fort .Bien sur tu peux recourir à des astuces de ce genre
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.
Invité- Invité
Re: 2 routines de tri pour 65xx
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
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.
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
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- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
Si tu veux, mais plutôt qu'astuce, je dirai plutôt bonnes pratiques pour cette architecture .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.
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 .mais qui est clairement moins élégant / pratique sur pleins d'aspects
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 .
Tu détermines comment si un sprite à changé ??, tu as un flag dans ta struct ??Sinon voici la fonction qui me permet de trier mon sprite quand je change son depth :
Invité- Invité
Re: 2 routines de tri pour 65xx
Si tu veux, mais plutôt qu'astuce, je dirai plutôt bonnes pratiques pour cette architecture .
Certes 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- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Re: 2 routines de tri pour 65xx
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 ??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).
Invité- Invité
Re: 2 routines de tri pour 65xx
Un bout de code vaut mieux qu'un (long) discours :
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
Et puis bon ainsi c'est simple et clair, le code est très facile à comprendre
- 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
Et puis bon ainsi c'est simple et clair, le code est très facile à comprendre
Stef- Interne
- Nombre de messages : 5087
Age : 45
Localisation : Sevres
Date d'inscription : 04/04/2007
Page 1 sur 2 • 1, 2
Sujets similaires
» [ECH] livre BASIC plus 80 routines sur Commodore 64 contre autre livre c64
» Quels outils pour créer des graphismes et sprites 2D pour ANDROID
» A SUPPRIMER SVP -> [ESTIM] pour vente DRAGNO EGG boite etc pour Nec Pc Engine HuCard
» [Don] Code pour la Béta de Elders Scroll Online pour ce weekend
» [ESTIM] pour vente DRAGON EGG boite etc pour Nec Pc Engine HuCard
» Quels outils pour créer des graphismes et sprites 2D pour ANDROID
» A SUPPRIMER SVP -> [ESTIM] pour vente DRAGNO EGG boite etc pour Nec Pc Engine HuCard
» [Don] Code pour la Béta de Elders Scroll Online pour ce weekend
» [ESTIM] pour vente DRAGON EGG boite etc pour Nec Pc Engine HuCard
Page 1 sur 2
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum