Meilleurs algo d'un test par bouding box

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).

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.


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...
                                                                                                                           

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...

Oui tout à fait, je sais pas quel pourrait être le gain sur le Z80, mais sur le 65xx tu peux voir plus haut, c'est pas négligeable ..
Et dommage que sur le Z80 l'indexation soit lente (il me semble), sinon on peut encore gagner en indexant le tableau plutôt que de passer par un pointeur .

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).

Pour ma part aucun intérêt a par me pénaliser, car c'est comme vingazole, le CPU ne voit que 16 bit d'adresse .
Donc l'idéal est de la mettre dans une bank mappée en permanence, ou en RAM

EDIT:Avec un écran en 256 pix, je pourrais faire du 190 cycles si X est aussi sur 8 bit , ça pourrait être pas mal non plus ..

Bon à mon tour :

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

8     move.w (a0)+, d0      ; d0 = player.x
8     move.w (a0)+, d2      ; d2 = player.y
12    move.l (a0)+, a0      ; a0 = player.box
4     move.w d0, d1         ; d1 = player.x
4     move.w d2, d3         ; d3 = player.y
8     add.w (a0)+, d0       ; d0 = player.x + box.xmin = player.xmin
8     add.w (a0)+, d1       ; d1 = player.x + box.xmax = player.xmax
8     add.w (a0)+, d2       ; d2 = player.y + box.ymin = player.ymin
8     add.w (a0)+, d3       ; d3 = player.y + box.ymax = player.ymax
68

.loop                       ; do {

// TEST on X coordinates

8     move.w (a1)+, d4      ; d4 = enemy.x
8     move.w (a1)+, d5      ; d5 = enemy.y
12    move.l (a1)+, a0      ; a0 = enemy.box
28

4     move.w d4, d6         ; d6 = enemy.x
8     add.w (a0)+, d6       ; d6 = enemy.x + box.xmin = enemy.xmin
4     cmp.w d1, d6          ; if (player.xmax < enemy.xmin)
10    bgt .no_collid        ;   no collision
26

8     add.w (a0)+, d4       ; d4 = enemy.x + box.xmax = enemy.xmax
4     cmp.w d0, d4          ; if (player.xmin > enemy.xmax)
10    blt .no_collid        ;   no collision
22

// TEST on Y coordinates

4     move.w d5, d6         ; d6 = enemy.y
8     add.w (a0)+, d6       ; d6 = enemy.y + box.ymin = enemy.ymin
4     cmp.w d3, d6          ; if (player.ymax < enemy.ymin)
10    bgt .no_collid        ;   no collision
26

8     add.w (a0), d5        ; d5 = enemy.y + box.ymax = enemy.ymax
4     cmp.w d2, d5          ; if (player.ymin > player.ymax)
10    blt .no_collid        ;   no collision
22

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

.no_collid
10    dbra d7, .loop        ; } while (numEnemies-)

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

Voici les calculs de cycle :

init: 116
loop min: 54
loop mean: 76
loop max: 134
end: 20/22


La valeur importante étant 134 cycles max par loop... bon voilà, je pense que tu commences à comprendre pourquoi le 68000 est imbattable   
Sachant que j'ai clairement pas été au bout des optimisations et que je suis en pure 16 bits sans compromis ni rien...

ohohoh, attend t'emballes pas trop   

expliques nous ce que tu as fait ???
Pourquoi une boucle ??

Ah oui, c'est du gerard majax ton truc, tu calcules toutes les collisions d'un coup c'est ça ??

vingazole a écrit:

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).

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.


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...
                                                                                                                           

Oui mais du coup c'est hyper chiant car ça signifie que tes bounding box doivent tous être dans la même page mémoire.
Pour le reste, oui ça me semble correct pour comparer.

TOUKO a écrit:ohohoh, attend t'emballes pas trop   

expliques nous ce que tu as fait ???
Pourquoi une boucle ??

Ben je t'invite à lire le code... vu la vitesse à laquelle tu as répondu tu n'as pas lu le code de toute évidence. Tu devais, c'est hyper simple à comprendre l'assembleur 68000 (et j'ai bien commenté   )
Pourquoi une boucle ??? O_o ? ben parce-qu'on traite la collision entre ton 1 objet et X objets.

Ah oui, c'est du gerard majax ton truc, tu calcules toutes les collisions d'un coup c'est ça ??

C'est ce qu'on avait convenu ? et surtout ça représente un cas réel, auand tu testes si ton vaisseaux se prend les tirs ennemis par exemple.

Ok ,c'est bien ce qu'il me semblait, mais dans tes calculs tu oublies le plus important .
Certe ça fait mal au cul comme ça, mais au final tu fais bcp de tests pour rien, car dans mon algo de jeu je lance pas le test si le sprite n'est pas utilisé .

Ex tu réserves 20/25 sprites pour les ennemis et bullets, mais tu n'as que 10 sprites à l'écrans, toi tu vas faire ta boucle pour les 25, alors que moi juste pour les 10 .. 
C'est clair que si on fait des traitement par lot, le 68000 nous enfume .

Donc non au final c'est pas bon  

Hein ? ah bah non j'élémine les sprites en dehors de l'écran en amont    Mais là c'est un autre problème (clipping), si tu veux on pourra comparer la vitesse de clipping une autre fois :p

C'est clair que si on fait des traitement par lot, le 68000 nous enfume .

Ben déjà ce n'est pas forcément ce que tu sous entendais (car y'a beaucoup de tests à faire). Et puis bien sur que je fais un traitement par lot car dans un shoot c'est quand tu vas avoir beaucoup de tirs à l'écran que ça va devenir critique. S'il n'y a qu'un tir à l'écran ça ne risque pas de ralentir ! Je t'ai toujours expliqué que le 68000 exprimait toute sa puissance dans ce genre de cas mais j'ai vraiment l'impression que tu n'es pas capable de sortir de ta vision de programmer propre au 6502, qui est très... simple ! Et qui n'a rien à voir avec ce qu'on fait sur un 68000. Je vais pas non plus "désoptimisé" mon code pour te faire plaisir  

de plus dans ta liste, tu mets pas tout les sprites utilisés à la suite, bien sur tu peux le faire pour correspondre à ton algo, mais ça aussi ça coûte, ce que nous on a pas à faire, donc sur 60 frames, je pense pas que tu y gagnes .
et plus il y a de sprites réservé avec collision possible, plus ton algo sera coûteux .

Mais stef c'est ce que je te dis, là tu compte juste l'algo de traitement par lot, ok, mais y'a tout le reste en plus que tu dois mettre en forme pour que ça marche, que nous on a pas à faire .

Surtout qu'après faut reprendre tout ton tableau pour savoir qui entre en collision avec qui, etc ...
alors que moi tout est dans la même boucle .

Stef a écrit:

vingazole a écrit:

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).

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.


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...

Oui mais du coup c'est hyper chiant car ça signifie que tes bounding box doivent tous être dans la même page mémoire.

Oui mais 1 page=16 Ko sur SMS, ça laisserait un peu de marge, quand même...

Oui mais 1 page=16 Ko sur SMS, ça laisserait un peu de marge, quand même...

Exact, surtout que tu n'as pas 500.000 valeurs différentes de box .

TOUKO a écrit:Et dommage que sur le Z80 l'indexation soit lente (il me semble), sinon on peut encore gagner en indexant le tableau plutôt que de passer par un pointeur .

C'est une horreur, mieux vaut se servir de IX/IY comme registres normaux (avec pénalité)

TOUKO a écrit:de plus dans ta liste, tu mets pas tout les sprites utilisés à la suite, bien sur tu peux le faire pour correspondre à ton algo, mais ça aussi ça coûte, ce que nous on a pas à faire, donc sur 60 frames, je pense pas que tu y gagnes .
et plus il y a de sprites réservé avec collision possible, plus ton algo sera coûteux .

On s'était mis d'accord sur la structure pourtant c'est fou X'D
Et celle que j'ai proposé me semble tout à fait standard, où est le problème ?
Que proposes tu à la place ? Et je comprends même pas ce que tu dis sur la fin, bien sur que ça prend plus de temps de tester plus de collisions O_o, je me demande si tu as bien compris l'idée de l'algo que je proposais du coup    ?

C'est pas ce que je veux dire stef, on fait un test en condition réelle, donc faut rester un min cohérent je pense .
Si tu prends un alogo comme le tient, ok il est performant, mais on peut pas occulter le fait que tu vas passer du temps à traiter tout ça par la suite, et donc perdre tout le bénef ..
Chose que nous on n'aura pas à faire ..
Je pense pas être de mauvaise composition en pensant ça, ça me parait logique .
Si ce que tu gagnes d'un côté, tu le perds de l'autre ,où est l'intérêt ??

J'ai pas dit qu'on allait faire le test sur un jeu complet, mais si on essaye de coller à un vrai jeu, fait pousser la logique jusqu'au bout, enfin je pense .

Donc oui si on prend ton algo tel quel, juste comme ça, oui tu nous éclates, je pourrais jamais venir en dessous de 210/220 je pense en 16 bit .

Pour moi, si on doit comparer sur une fonction/routine, je pars du principe que tout le travail est dedans, si tu déportes des tris, et autres, à l'extérieur, chose que nous on fait pas , on peut pas parler de même chose .

Un truc m'échappe Touko, ta liste de boxes à tester , tu vas bien devoir la construire aussi sur PCE (ou alors tu vas tester à chaque fois dans ta routine qui gère ton enemi, ce qui est clairement sous efficient sur Z80 (et surement sur 68K) à mon idée) donc au final ça change quoi ?
Après , effectivement , si on veut comparer ce que tu as posté avec le code 68K, il faut garder la loop_max et le code qui calcule la box du player.

CAD, non c'est un tableau de constante, tu as juste un pointeur sur le début de ta box .

Après , effectivement , si on veut comparer ce que tu as posté avec le code 68K, il faut garder la loop_max et le code qui calcule la box du player.

C'est pas sur ça que je suis pas d'accord, puisque sa box du joueur est calculée, et reste dans les regs, donc pour moi c'est bon .

Avant il doit mettre tout ses sprites utilisées dans une liste, donc faire un tri, chose que je fais pas.
Mais une foi que ses calculs de collisions fait, il faut qu'il refasse une/plusieurs boucle(s) pour les traiter, les sprites à faire des tests de collision, ceux à déplacer, ceux qui sont en train d'exploser etc, alors que moi c'est traité dans la foulé .
Donc je pense qu'on peu pas comparer dans ce cas là .
Moi je parcoure ma liste, et en fonction de l'état des sprites, je fait telle ou telle action .

Ce qu'il va gagner d'un côté, il va forcement le perdre d'un autre, donc est ce que c'est valable ??

Je comprend bien ce que tu veux dire là
Effectivement, c'est difficile de comparer car quand tu as suffisament de registres, c'est souvent plus intéressant de traiter par lots, ça t'évite de recharger constamment tes données en mémoire.

TOUKO a écrit:C'est pas ce que je veux dire stef, on fait un test en condition réelle, donc faut rester un min cohérent je pense .
Si tu prends un alogo comme le tient, ok il est performant, mais on peut pas occulter le fait que tu vas passer du temps à traiter tout ça par la suite, et donc perdre tout le bénef ..
Chose que nous on n'aura pas à faire ..
Je pense pas être de mauvaise composition en pensant ça, ça me parait logique .
Si ce que tu gagnes d'un côté, tu le perds de l'autre ,où est l'intérêt ??

J'ai pas dit qu'on allait faire le test sur un jeu complet, mais si on essaye de coller à un vrai jeu, fait pousser la logique jusqu'au bout, enfin je pense .

Ben non là, la liste "enemies" que j'envoi en paramètres c'est la liste des sprites qui peuvent rentré en collision avec mon "player". Et tu verras que ma fonction retourne dés que j'ai collision ou si j'ai traité tout les sprites.

L'instruction DBGE fait plusieurs choses à la fois :
- elle test si la condition GE (greater or equal) est faux, si c'est le cas :
  - elle décrémente D7 et si D7 != -1 alors branchement vers .loop

Bien sur le fait d'avoir bcp de registres aide pas mal, et dans un vrai traitement par lot, on se fait bouffer ,ça je le nie pas du tout, mais là le cas est spécial, alors si on considère seulement la routine, ok je peux rien dire, par contre si on parle de routine in-game, là c'est pas pareil .

Ben non là, la liste "enemies" que j'envoi en paramètres c'est la liste des sprites qui peuvent rentré en collision avec mon "player". Et tu verras que ma fonction retourne dés que j'ai collision ou si j'ai traité tout les sprites.

L'instruction DBGE fait plusieurs choses à la fois :
- elle test si la condition GE (greater or equal) est faux, si c'est le cas :
  - elle décrémente D7 et si D7 != -1 alors branchement vers .loop

Ok, c'est déjà mieux .
Reste que tu vas devoir te retraiter tout les sprites qui sont pas en collision,et que tu es quand même obligé de faire un tri au depart.
De traiter à part avec le test de collision, et à part ceux qui ont besoin d'un traitement spécifiques .

C'est toi qui a créé ce topic; le titre est : "Meilleurs algo d'un test par une bounding box".

Pour moi il ne s'agit évidemment pas de faire tous les traitements d'un jeu réel dans la boucle de cet algorithme, néanmoins si tout le monde applique le même algo -celui de Stef me parait pertinent- on pourra avoir des points de comparaison

Bon ok ,va pour ça alors, je pensais que l'algo devait être un algo in situ CAD de condition réelle,donc j'étais parti pour ça ..

Pour moi il ne s'agit évidemment pas de faire tous les traitements d'un jeu réel dans la boucle de cet algorithme, néanmoins si tout le monde applique le même algo -celui de Stef me parait pertinent- on pourra avoir des points de comparaison 

C'est pas sur qu'on puisse, puisque c'est propre au 68000 .

C'est pas la routine en soit qui me gène, c'est que pour fonctionner comme ça, elle nécessite un post traitement en amon qui coûte, alors que dans les notres non .

TOUKO a écrit:Bon ok ,va pour ça alors, je pensais que l'algo devait être un algo in situ CAD de condition réelle,donc j'étais parti pour ça ..

Pour moi il ne s'agit évidemment pas de faire tous les traitements d'un jeu réel dans la boucle de cet algorithme, néanmoins si tout le monde applique le même algo -celui de Stef me parait pertinent- on pourra avoir des points de comparaison 

C'est pas sur qu'on puisse, puisque c'est propre au 68000 .

Mais justement non, le prototype que j'ai défini pour la fonction de collision est très standard et représente au contraire un cas réel pour le jeu, rien à voir avec le 68000.
C'est ta manière de coder qui est bizarre X'D
Perso je ne m'amuse pas à traiter sprite par sprite, genre mon IA du sprite 1, mon clipping du sprite 1, mes collisions du sprite 1, mon affichage du sprite 1... ensuite sprite 2. C'est carrément sous efficient de travailler comme ça. Peut être que tu en as pris l'habitude car le 6502 pousse un peu à ça, mais même avec un 6502 tu as des pertes à travailler de cette manière (enfin c'est mon avis).

vingazole a écrit:C'est toi qui a créé ce topic; le titre est : "Meilleurs algo d'un test par une bounding box".

Pour moi il ne s'agit évidemment pas de faire tous les traitements d'un jeu réel dans la boucle de cet algorithme, néanmoins si tout le monde applique le même algo -celui de Stef me parait pertinent- on pourra avoir des points de comparaison

Je suis content qu'il y ai une tierce personne pour une fois

Mais justement non, le prototype que j'ai défini pour la fonction de collision est très standard et représente au contraire un cas réel pour le jeu, rien à voir avec le 68000.
C'est ta manière de coder qui est bizarre X'D
Perso je ne m'amuse pas à traiter sprite par sprite, genre mon IA du sprite 1, mon clipping du sprite 1, mes collisions du sprite 1, mon affichage du sprite 1... ensuite sprite 2. C'est carrément sous efficient de travailler comme ça. Peut être que tu en as pris l'habitude car le 6502 pousse un peu à ça, mais même avec un 6502 tu as des pertes à travailler de cette manière (enfin c'est mon avis).

tu limites fortement les boucles en faisant sprites/sprites .

TOUKO a écrit:C'est pas la routine en soit qui me gène, c'est que pour fonctionner comme ça, elle nécessite un post traitement en amon qui coûte, alors que dans les notres non .

Pas obligatoirement , si les données du joueur sont stockées dans les registres , il peut très bien faire comme toi et faire le test de collision sans construire de liste.Il suffit que sa routine de gestion des enemis ne touche pas aux registres en question (si je ne me trompe pas ça l'obligerait à mobiliser 4 registres data sur les 8 ce qui me semble acceptable)

Oui Mais tu verrais là qu'on serait plus dans les même valeurs que celles qu'il à postées .

Car dans sa routine il traites seulement les sprites sensés entrer en collision , donc ça veut dire qu'a un moment il a séparé ceux là de ceux qu'il ne devait pas tester .

de plus si je dis pas n'importe quoi, plus il y a de collisions plus sa routine est lente ..
Car à chaque collision il fait 116+124+20/24, donc c'est très variable .

Pour donner raison à Touko sur la structure générale, il me semble que faire :

Code:

for (i=0; i<nbSprites; i++) {
   traitement1(sprite[i]);
   traitement2(sprite[i]);
              ...
   traitementN(sprite[i]);
}

doit être plus efficace que :

Code:

for (i=0; i<nbSprites; i++) traitement1(sprite[i]);
for (i=0; i<nbSprites; i++) traitement2(sprite[i]);
                            ...
for (i=0; i<nbSprites; i++) traitementN(sprite[i]);

C'est un peu ça l'idée .
Sa routine est super rapide, mais nécessite des traitements avant/après .
Les nôtres sont plus lentes, mais pas de traitement .

et comme je l'ai souligné plus haut :
de plus si je dis pas n'importe quoi, plus il y a de collisions plus sa routine est lente ..
Car à chaque collision il fait 116+124+20/24, donc c'est très variable, ajoutez ça aux traitements post/pré .

TOUKO a écrit:Car dans sa routine il traites seulement les sprites sensés entrer en collision , donc ça veut dire qu'a un moment il a séparé ceux là de ceux qu'il ne devait pas tester .

Tu es bien obligé de le faire à un moment ou un autre.Tu inclues ta routine de test dans la routine qui gère les enemis ce qui t'évites de devoir construire une liste.Il peut très bien faire pareil sans faire aucun traitement spécifique.ça ne change rien au fond du problème.

Justement tout dépend de ton implémentation interne.
Chaque traitement utilise ses propres variables et registres, du coup tu perds beaucoup à switcher de traitement. Pour moi le plus efficace c'est ça :

traitement1(sprites, num);
traitement2(sprites, num);
traitement3(sprites, num);

Quelque soit l'architecture...

Tu es bien obligé de le faire à un moment ou un autre.Tu inclues ta routine de test dans la routine qui gère les enemis ce qui t'évites de devoir construire une liste.Il peut très bien faire pareil sans faire aucun traitement spécifique.ça ne change rien au fond du problème.

Moi je procède comme suit, je dis pas que c'est forcement mieux, a vous de juger .
j'ai les stuctures de mes sprites (ennemis, bullets) en ram .
Un pointeur pointe sur le début de la liste .

Parcoure la liste jusqu'à la fin
si le sprite est inactif -> sprite suivant
si sprite = 1 -> test collision
    -> collision = 0 on déplace le sprite
  -> collision à 1 on initialise un pointeur de la struc vers fonction (explosion par exemple)
on lance la fonction alternative (explosion) du sprite

Passe au sprite suivant.