Re: Mr ToutLeMonde et la programmation NES...

[Tryphon]

C'est pour ça que je ferais une table des 1/sqrt(x^2 + y^2) avant. Et sauf erreur, ça revient exactement au même que de faire une table des arctan(cos t)

[Invité]

C'est pour ça que je ferais une table des 1/sqrt(x^2 + y^2) avant. Et sauf erreur, ça revient exactement au même que de faire une table des arctan(cos t)

Les tables risquent d'être grosses avec tout ça .

[brokestudio]

Désolé je suis tout ça de loin, j'ai pas du tout le temps aujourd'hui. J'avais une piste hier soir, faut que j'approfondisse, mais je reviendrai vous tenir au courant, certainement demain.

Qu'est-il arriver aux 32 autres pages du topic ?!?!

[vincent2105]

Bon, l'apéro est passé par là, mais je vous montre mon début de solution, ça me fait plaisir    Je pense avoir une bonne piste, du moins j'ai testé quelques valeurs, et les resultats sont corrects (si on s'accorde une p'tite marge d'erreur ). Grosso modo, je calcule les valeurs à ajouter respectivement aux positions x et y du projectile à chaque frame. Mais il faudra que je lisse les valeurs obtenues sur 3 ou 4 frames car dans certains cas, une des 2 valeurs est trop élevée : on peut avoir des ratios x/y du genre : x1/y15 qu'il faudra que je ramène par exemple à x1/y5, x0/y5, x0/y5 et faire boucler.  Ensuite faudra determiner si on ajoute ou soustrait les valeurs obtenues.

Code:

  LDA position_x_tireur
  CMP position_x_cible
  BCC cible_a_droite
  
localisation_X:
  ;--------------------
cible_a_gauche:
  LDA position_x_tireur
  SEC
  SBC position_x_cible
  STA TEMP_vecteur_X
  JMP localisation_Y
  
cible_a_droite:
  LDA position_x_cible
  SEC
  SBC position_x_tireur
  STA TEMP_vecteur_X
  ;--------------------
localisation_Y:
;--------------------
  LDA position_y_tireur
  CMP position_y_cible
  BCC cible_en_bas
cible_en_haut:
  LDA position_y_tireur
  SEC
  SBC position_y_cible
  STA TEMP_vecteur_Y  
  JMP localisation_FIN
  
cible_en_bas:
  LDA position_y_cible
  SEC
  SBC position_x_tireur
  STA TEMP_vecteur_Y
  
localisation_FIN:
  ;----------------------------------------
 
boucle:  
  LSR TEMP_vecteur_X
  LDA TEMP_vecteur_X
  CMP #2
  BCC FIN
  
  LSR TEMP_vecteur_Y
  LDA TEMP_vecteur_Y
  CMP #2
  BCC FIN
  LDA TEMP_vecteur_X
  STA vecteur_X
  LDA TEMP_vecteur_Y
  STA vecteur_Y
  JMP boucle
FIN:
  
  RTS

[upsilandre]

C'est pour ça que je ferais une table des 1/sqrt(x^2 + y^2) avant. Et sauf erreur, ça revient exactement au même que de faire une table des arctan(cos t)

nan mais en fait on est con pourquoi pas juste une table qui prend en entrée le delta_x et delta_y qui sépare l'emeteur de la cible et qui en sortie te donne directement les valeurs d'incrementation x,y de ton projectile. quite a avoir une grosse table y a besoin d'aucun calcule
Ou sinon pour eviter d'avoir une grosse table on calcule juste le coef directeur (donc juste une division) et on s'en sert d'indexe vers une table qui te donne encore une fois directement les valeurs d'incrementations x,y.

[upsilandre]

Et si on veut aucune table et aucun calcule reste toujours la facilité de juste incrémenter le x,y du projectile a chaque frame tant qu'il est pas egale a celui de la cible initial et puis voila. La trajectoire sera alors decoupé en 2 phases, une phase a 45° et une phase en ligne droite, mais si ca colle avec la situation pourquoi pas.

[upsilandre]

Qu'est-il arriver aux 32 autres pages du topic ?!?!

coupé dans un autre topic en page 2

[Tryphon]

Ma faute, j'ai tapé trop vite (j'étais en pause) : je voulais parler d'une table des 1/sqrt(t) (pour éviter la division).

Mon "idée", c'était d'éviter le calcul de y/x, parce que ça casse la symétrie en x et y. Du coup, quand y est proche de 0, y/x sera proche de 0 et c'est bon, alors que quand x est proche de 0, y/x devient grand, on aura moins de chiffres significatifs et donc des erreurs en calculant l'arc tangente.

Après, si on veut se passer de tables, y'a des algos suffisamment véloces pour calculer avec une précision suffisante une racine carrée, même sur processeur 8 bits. C'est valble aussi pour l'arc tangente cela dit.

Encore une fois, au  niveau mathématique, les deux méthodes sont strictement équivalentes. Dans un cas on calcule 1/sqrt(x^2 + y^2), dans l'autre cos(arctan t) = 1/sqrt(1 + t^2).

[vincent2105]

Bon, bah elle s'en sort pas mal ma routine je trouve   ce sont des sprites 8x8, donc avec une cible en 16x16, pour moi, ça fera l'affaire.

[upsilandre]

ouai mais nan, tout le smilblick c'est justement d'avoir une vitesse linéaire bien défini
Et y a des choses qui me paraissent problématique dans ton code.

De toute facon la question a se poser c'est deja quelle quantité de table on s'autorise, c'est ca qui définie la suite car si on s'autorise une grosse table (de l'ordre de 64Ko) on a alors de loin la meilleur solution, aucun calcule, aucune ressource cpu et précision maximum mais ca serait pas raisonable, faut se limiter a des tables 256 .

[Invité]

Après les grosse tables c'est vraiment pour une diag maximale avec un X/Y de 256 pixels .
Ca peut facilement se réduire en faisant des compromis .
Surtout si le but n'est pas un projectile à tête chercheuse je pense que ce doit pas être compliqué à faire sans table(j'avais déjà fait la tête chercheuse dans mon shoot bonus) .

[vincent2105]

ouai mais nan, tout le smilblick c'est justement d'avoir une vitesse linéaire bien défini

Oui je sais, ça c'est mon challenge N°2, moi qu'était content d'avoir une trajectoire correcte 
Pour la vitesse linéaire, je pense pas que ce soit très compliqué dans mon cas. Bref, je continuerai ce soir ou demain.

[Stef]

Je pense au contraire que toute la complexité est là :p
D'où les propositions de Upsilandre et Tryphon (qui sont plus complexe à implémenter mais qui prennent cette donnée en compte)

[Tryphon]

Si t'as pas besoin d'une grosse précision, tu calcules juste la distance au carré (même pas la peine de calculer la racine) et suivant les valeurs tu divise ton vecteur par 2, 4, 8, 16, etc. Ca va très vite (ce ne sont que des décalages), et si tous les projectiles n'ont pas la même vitesse, c'est pas trop grave (ça peut même être sympa niveau gameplay).

Des trajectoires hyper-précises au sous-pixel, je m'en suis servi une seule fois pour faire un casse-brique y'a longtemps (faudrait d'ailleurs que je le reprenne, y'a pas de casse-brique funky sur MD à ma connaissance).

[vincent2105]

J'ai fait un pas en avant...  je me doute que c'est pas la manière la plus académique, mais pour l'instant je creuse mon idée jusqu'au bout, j'étudierai votre piste plus en détail par la suite    J'ai quelques bugs aussi.

[brokestudio]

OK, je prends enfin un moment pour expliquer mon approche des projectiles ciblés.

Tout d'abord les specs :
- pas besoin d'une précision à 360°, le jeu étant un platformer plutôt vif, je n'ai pas besoin de tirs ultra précis. Tant que c'est dans la direction du joueur ça me va
- performance ! Il faut que ça aille vite, si j'ai 3 ennemies à l'écran qui veulent tirer en même temps vers le joueur, plus l'écran qui scroll, plus le joueur qui tire, je ne veux pas de lag
- la vitesse est sur 16bits pour être plus précis (8.8 / pixel.subpixel)
- la vitesse des projectiles doit être constante peu importe la direction
- la vitesse des projectiles doit être (sensiblement) la même que la console soit PAL ou NTSC

Partant de là j'ai choisi de ne gérer que 32 angles différents.

Je suis parti de cette fonction : http://codebase64.org/doku.php?id=base:8bit_atan2_8-bit_angle, qui à partir des coordonnées X/Y du point de départ et du point d'arriver me donne l'angle beta alpha.



Travaillant sur une plateforme 8 bits, cette fonction nous renvoie l'angle sur un octet et les 360° sont ainsi représenté par 256 valeurs. Ce qui nous donne un pas de 360 / 256 = 1,40°.



Il reste au final à utiliser cette valeur comme index dans un tableau.

Pour ça j'ai créé un script (en PHP) qui me génère automatiquement les vitesses X/Y en fonction de l'angle et du type de console (PAL/NTSC).

Code:


$x          = 0;
$y          = 0;

$palSpeed   = 0x310;
$ntscSpeed  = 0x310*5/6;

$angle      = 0;
$angle_step = 360/32;

$xSpeeds = [];
$ySpeeds = [];
$angles     = [];

while ($angle < 360)
{
    $r = deg2rad($angle);
    $x = round( $palSpeed * cos ( $r ) );
    $y = round( $palSpeed * sin ( $r ) );

    $angles[]   = $angle;
    $xSpeeds[]  = dec2hex( $x & 0xFFFF, true, 4 );
    $ySpeeds[]  = dec2hex( $y & 0xFFFF, true, 4 );

    $angle += $angle_step;
}


Ce qui nous donne au final 4 tableaux qui ressemblent à ça :

Code:


bulletPalSpeedX:
    .word $0310,$0301,$02D4,$028C,$022A,$01B4,$012C,$0099
    .word $0000,$FF67,$FED4,$FE4C,$FDD6,$FD74,$FD2C,$FCFF
    .Word $FCF0,$FCFF,$FD2C,$FD74,$FDD6,$FE4C,$FED4,$FF67
    .word $0000,$0099,$012C,$01B4,$022A,$028C,$02D4,$0301

bulletPalSpeedY:
    .word $0000,$0099,$012C,$01B4,$022A,$028C,$02D4,$0301
    .word $0310,$0301,$02D4,$028C,$022A,$01B4,$012C,$0099
    .word $0000,$FF67,$FED4,$FE4C,$FDD6,$FD74,$FD2C,$FCFF
    .word $FCF0,$FCFF,$FD2C,$FD74,$FDD6,$FE4C,$FED4,$FF67

bulletNtscSpeedX:
    .word $028D,$0281,$025C,$021F,$01CE,$016B,$00FA,$007F
    .word $0000,$FF81,$FF06,$FE95,$FE32,$FDE1,$FDA4,$FD7F
    .word $FD73,$FD7F,$FDA4,$FDE1,$FE32,$FE95,$FF06,$FF81
    .word $0000,$007F,$00FA,$016B,$01CE,$021F,$025C,$0281

bulletNtscSpeedY:
    .word $0000,$007F,$00FA,$016B,$01CE,$021F,$025C,$0281
    .word $028D,$0281,$025C,$021F,$01CE,$016B,$00FA,$007F
    .word $0000,$FF81,$FF06,$FE95,$FE32,$FDE1,$FDA4,$FD7F
    .word $FD73,$FD7F,$FDA4,$FDE1,$FE32,$FE95,$FF06,$FF81


Côté assembleur, c'est plutôt simple, le seul truc auquel il faut faire attention, c'est que la fonction atan2 comme dit plus haut renvoie un angle sur 8 bits, et il ne nous en faut que 5 pour gérer nos 32 valeurs. Quelques shifts vers la droite suffiront.

Code:

       ; on prépare les coordonnées de départ et d'arrivée dans les variables x1/y1 et x2/y2
        lda enemyXpos
        sta x1
        lda playerXpos
        sta x2

        lda enemyYpos
        sta y1
        lda playerYpos
        sta y2

        ; fonction atan2 en lien plus haut qui nous retourne l'angle
        jsr getAngle

        ; on arrondit le résultat
        clc
        adc #$08

        ; on ne garde que les bits 3 à 7
        and #%11111000

        ; on shift à droite seulement deux fois vu qu'on index une table de word et non de byte
        lsr
        lsr

        ; on met le résultat dans Y pour pouvoir l'utiliser comme index
        tay

        lda tvSystem
        cmp #$01
        beq pal
    ntsc:

        lda bulletPalSpeedX+0,Y
        sta bulletxxspeed
        lda bulletPalSpeedX+1,Y
        sta bulletXxspeed

        lda bulletPalSpeedY+0,Y
        sta bulletyyspeed
        lda bulletPalSpeedY+1,Y
        sta bulletYyspeed

     jmp :+

    pal:

        lda bulletNtscSpeedX+0,Y
        sta bulletxxspeed
        lda bulletNtscSpeedX+1,Y
        sta bulletXxspeed

        lda bulletNtscSpeedY+0,Y
        sta bulletyyspeed
        lda bulletNtscSpeedY+1,Y
        sta bulletYyspeed

    :



Voilà, ce n'est peut être pas parfait, peut être qu'il y a plus simple, mais ça me semble efficace et ça fonctionne pour moi.
Le tout prend 145 138 cycles et évidemment plus de ROM pour les tables de la fonction atan2.

A noter qu'il peut être intéressant de faire des tirs groupés en prenant la valeur de l'index +/- 1 ou +/- 2.

J'essaye de faire une vidéo dans la journée mais je ne promets rien.

[Tryphon]

Dans l'esprit, c'est ce que nous proposions, Upsilandre et moi.

Y'a une petit coquetterie j'ai regardé le code de la fonction atan2 : au lieu de tabuler atan(t), ça tabule atan(2^u), et au lieu de l'appliquer à t = y/x, ça l'applique à u = ln(y/x) = ln y - ln x. C'est malin (et ça respecte en partie la symétrie)

Par contre, il doit y avoir une vraie perte de précision, du fait qu'on code sur peu de chiffres une fonction compliquée (déjà, prendre le logarithme, puis la puissance, ça redonne pas tout à fait x avec aussi peu de précision). Mais pour un platformer, ce doit être suffisant en effet.

[Invité]

Voilà, ce n'est peut être pas parfait, peut être qu'il y a plus simple, mais ça me semble efficace et ça fonctionne pour moi.

Tant que ça fait ce que tu veux c'est l'essentiel(faut juste être sur que le projectile soit capable d'atteindre le joueur), et je trouve ta démarche bien vue, un bon compromis perfs/datas .  
145 138 cycles / tir, c'est vraiment que dalle dans une frame .

[vincent2105]

Merci Antoine d'avoir pris le temps d'expliquer ta solution 
Je vais pouvoir potasser ça.

[brokestudio]

Oops en fait c'est 138 cycles et non 145, j'avais amélioré la conversion 8bits => 5bits mais pas mis à jours le nombre de cycle.

Merci des retours et de rien Vincent, n'hésites pas si quelque chose n'est pas clair.

[vincent2105]

Bah en fait, rien que la vitesse sur 16bits, c'est quelque chose que je n'ai jamais abordé, donc faut que je me mette ça dans le crane déjà. On verra le reste ensuite. :)
Je me répète, je sais qu'il y a du beau monde sur le forum, et quand vous expliquez certaines choses, souvent ça fait pas TILT, du coup je passe à coté et je dois donner l'impression de ne pas écouter :/ Bref il me manque encore pas mal de bases ! Mais c'est une aubaine de discuter avec vous 

[Invité]

Ca fait pas tilt car il y a certaines choses que tu n'as pas encore abordées dans ta quette du dev nes,c'est tout 

[brokestudio]

Ah mais si tu veux qu'on discute des vitesses sur 16 bits y'a pas de souci hein :)
C'est plutôt simple d'ailleurs.

Tu as un octet pour le déplacement pixel par pixel qui est l'octet de poids fort, et un octet pour le déplacement par sous-pixel qui est l'octet de poids faible. Ce qui te permet de te déplacer de 0,5 pixel par exemple. L'octet de poids fort est utilisé pour l'affichage à l'écran, mais l'octet de poids faible n'est utilisé que pour le calcul.

Une vitesse de 1,0 pixel / frame = $0100
Une vitesse de 0,5 pixel / frame = $0080

Si par exemple ton personnage est au milieu de l'écran, sa position X est de $80.
Position qu'on va également passer sur 16 bits, donc $8000.

Si tu veux le déplacer de 0,5 pixel / frame, tu vas donc ajouter $0080 à sa position à chaque frame.

Code:


frame vitesse position
  0    $0080    $8000
  1    $0080    $8080     ; la position ne change pas, on est toujours à $80
  2    $0080    $8100     ; la position change cette fois et passe à $81
  3    $0080    $8100     ; de nouveau la position à l'écran ne change pas
  ... et on recommence


Au fil du temps tu te déplaces bien à 0,5px / frame.
Même exemple avec 0,25px / frame :

Code:


frame vitesse position
  0    $0040    $8000
  1    $0040    $8040     ; la position à l'écran ne change pas
  2    $0040    $8080     ; toujours pas
  3    $0040    $80C0     ; toujours pas
  4    $0040    $8100     ; 4ème frame, on se déplace enfin !
  ... et on recommence


Voilà pour la base, en espérant que ça soit clair, je ne suis pas toujours doué pour expliquer ...

[vincent2105]

TILT   

[Invité]

En gros la partie subpixel fonctionne comme un timer,que tu pourras facilement faire varier .

[upsilandre]

Dans l'esprit, c'est ce que nous proposions, Upsilandre et moi.

Y'a une petit coquetterie j'ai regardé le code de la fonction atan2 : au lieu de tabuler atan(t), ça tabule atan(2^u), et au lieu de l'appliquer à t = y/x, ça l'applique à u = ln(y/x) = ln y - ln x. C'est malin (et ça respecte en partie la symétrie)

Avec les CPU 8bit j'imagine qu'il vaut mieux etre a l'aise avec les logarithmes pour pouvoir faire des multiplication et division a base de table.
Et puis la table atan est bien calibré, elle va de $00 a $1f pour un octant  (donc sort des valeurs de $00 a $ff au final une fois le mask appliqué) donc ca exploite au mieux l'octet.
Partir de ce bout de code deja en 6502 ca me paraissait pas mal car il avait l'aire assez optimal. Tant que ca fait le job.

[upsilandre]

Voilà, ce n'est peut être pas parfait, peut être qu'il y a plus simple, mais ça me semble efficace et ça fonctionne pour moi.

Tant que ça fait ce que tu veux c'est l'essentiel(faut juste être sur que le projectile soit capable d'atteindre le joueur), et je trouve ta démarche bien vue, un bon compromis perfs/datas .  
145 138 cycles / tir, c'est vraiment que dalle dans une frame .

Et puis c'est 138 cycles juste pour l'initialisation du tire. ensuite ca consomme rien de plus que pour les autres sprite.
Donc y a aucune raison que ca consomme plus de 138 cycles par frame meme si y a plusieurs tires (faut empecher les tire simultané et une frame de décalage n'empeche pas de donner l'illusion de tire simultané)
Et donc ca fait a peu pret l'equivalent d'une scanline par frame donc c'est tres correct. C'est sans doute plutot la gestion des collisions qui fera varier le cout selon le nombre de tire.

[Invité]

Exact,et surtout les collisions avec le décors qui vont être les plus gourmandes en CPU .
Pour les sprites, avec un simple bounding box générique je suis à 170 cycles max / collision,ce qui est raisonnable je trouve, mais pas optimal  .

[vincent2105]

@brokestudio, une question : tu as choisi de n'avoir que 32 angles, mais qu'est ce qui t'empêchais  d'en avoir  64, 128 ou 256 ? Je me doute qu'il y a une raison, mais je n'arrive pas à voir où ça coince justement 


edit : y'a peut être un lien avec ce qu'a expliqué upsilandre ; mais c'est encore bien flou :/

Et puis la table atan est bien calibré, elle va de $00 a $1f pour un octant  (donc sort des valeurs de $00 a $ff au final une fois le mask appliqué) donc ca exploite au mieux l'octet.

[TotOOntHeMooN]

Voir même 16, pour pouvoir en stocker deux par octet.

[Invité]

une question : tu as choisi de n'avoir que 32 angles, mais qu'est ce qui t'empêchais  d'en avoir  64, 128 ou 256 ? Je me doute qu'il y a une raison, mais je n'arrive pas à voir où ça coince justement  

je pense que pour limiter la taille des tables, les angles sont codés sur 5 bits (au lieu de 8), donc 32 angles possibles .

Voir même 16, pour pouvoir en stocker deux par octet.

Ca peut le faire,in game le manque de précision passerait probablement inaperçu .