Les microbes reviennent ... douououcement ....

[babaorhum]

Bonjour à tous,
Je ne sais pas pourquoi mais le "jeu de la vie" m'a toujours faciné ... voir ces populations évoluer, ces figures se créer ...
Je peux proposer un petit détour par wiki, article très sympa a lire et relire, pour se remettre un peu tout ca en mémoire ! (on trouve pleins d'autres trucs en passant par Google aussi)

Revenons à nos pockets ... (les machines, pas l'admin !)

Récemment doté d'un PC-1600, j'ai voulu lui implémenter le jeu de la vie - disons "microbes" sur un pocket !

J'ai choisi de travailler directement en mode graphique dans un carré de 30x30 :

- la machine calcule le premier "carré" à gauche (ca ressemble à un code barre 2D !!)
- puis calcule la nouvelle génération dans le nouveau carré, celui de droite,
- a la fin du calcul, la nouvelle génération est recopiée dans le carré de gauche et ca recommence à l'étape ci avant.

Avec ce système, tout se passe sur l'écran, pas de variable nécessaire pour mémoriser les 900 cellules !

Code : Tout sélectionner

 10 REM   ***BABACROBES***
   20 CLEAR :CLS :WAIT 0:RANDOM 
   40 N=0:R=1:Y=0:X=0:WAIT 100
   45 CURSOR 5,1:PRINT "*** MICROBES ***":CURSOR 10,2:PRINT "by baba"
   60 CLS :WAIT 0
   70 CURSOR 13,0:PRINT "Generation 1":GOSUB 1000
   75 GOSUB 700:CURSOR 13,0:PRINT "calcul ...":GOSUB 1500
   80 GOSUB 1300:R=R+1
   85 GOSUB 700:CURSOR 13,0:PRINT "Recopie":GOSUB 1500
   90 GOSUB 1200:GOSUB 1500
  100 GOTO 75
  700 REM   ****CLEARAFF****
  710 FOR I=1 TO 3
  720 CURSOR 13,I:PRINT "            " : REM 12 SPACE
  730 NEXT I : RETURN
 1000 REM  ***INIT***
 1010 FOR J=1TO 30:FOR I=1TO 30
 1020 A=RND 2-1
 1030 IF A=1THEN PSET(I,J):N=N+1
 1050 NEXT I:NEXT J:RETURN 
 1200 REM  ****COPIE****
 1210 FOR J=1TO 30:FOR I=1TO 30
 1220 PRESET(I,J):IF POINT (I+40,J)THEN PSET(I,J)
 1230 PRESET(I+40,J)
 1240 NEXT I:NEXT J:RETURN 
 1300 REM   **NEXTGEN***
 1301 Y=0:X=0
 1305 FOR J=1TO 30:FOR I=1TO 30
 1390 F=POINT (I-1,J)+POINT (I+1,J)+POINT (I,J-1)+POINT (I,J+1)
 1400 F=F+POINT (I-1,J-1)+POINT (I-1,J+1)+POINT (I+1,J-1)+POINT (I+1,J+1)
 1410 IF POINT (I,J)AND (F<2OR F>3)THEN PRESET(I+40,J):N=N-1:X=X+1:GOTO 1450
 1420 IF NOT POINT (I,J)AND F=3THEN PSET(I+40,J):N=N+1:Y=Y+1:GOTO 1450
 1430 IF POINT (I,J)AND (F=2OR F=3)THEN PSET(I+40,J):GOTO 1450
 1440 IF NOT POINT (I,J)AND F<>3THEN PRESET(I+40,J)
 1450 NEXT I:NEXT J:RETURN 
 1500 REM  ***AFFDATA***
 1510 CURSOR 13,1:PRINT "Gen : ";R
 1520 CURSOR 13,2:PRINT "Pop : ";N
 1530 CURSOR 13,3:PRINT "+";Y;" -";X
 1540 RETURN 

Tout est écrit en basic "de base" et c'est là le problème ... c'est lent !! je sors mon chrono, de base aussi :

Génération 1 (routine ligne 1000) : 40 secondes
Génération 2 (routine ligne 1300) : env 3 minutes 30" !!!!
Recopie (routine ligne 1200) : 25 secondes

Et c'est là que vous intervenez !!!

Qui peut m'aider à écrire ces routines en assembleur ?
J'y connais quasi rien ...

Edit du 22/03 : petit correctif sur le code (retrait d'un morceau inutile)

[Gilles59]

Excellent !

Mais je ne serai pas t'aider pour l'assembleur... Si quelqu'un se lance je suivrai cela avec intérêt

je me demande (en restant en basic) si tu ne gagnerais pas du temps en travaillant avec des chaines ou des tableaux et afficher à la fin ?

reste qu'en assembleur, c'est typiquement le genre de programme ou tu peux multiplier la vitesse par.... beaucoup !! (100,1000, plus?)
mais faut voir comment l'écran graphique est codé car çà peut vite devenir très compliqué

[babaorhum]

Merci Gilles !

Ce pgm doit marcher aussi sur les PC-13XX ... mais encore bien plus lents ... voir aussi sur PB-700 et 770 avec quelques ajustements.
pour le tableau mémoire, le pb c'est la taille pour 900 variables (et encore j'ai limité, au début je voulais faire évoluer ma vie dans un 75x30 ...) - on a que des réels de 8 octets sur nos bécanes ... ca fait 7 ko pour un seul tableau de 900 variables - sauf erreur - et il en faut 2 ....

Faut travailler en byte et donc en mémoire système ... Pour faciliter l'accès aux graphiques, peut être qu'il existe des macros instructions intéressantes ...

[remy]

ben non, tu as besoin de 900 variables BOOLEENNES. Donc tu as besoin de 900/8 octets= 113 octets. Ça sera plus rapide que les POINT qui font un appel au processeur graphique (un HD61102).

[Gilles59]

Pourquoi pas un tableau de 30 chaines de caractères de longueur 30 ?

"000001100101010010000011100101"
"000110010101001000001110010100"
etc.

ca ferait ~ 900 octets (et beaucoup de 'déchets' puisque moins de 120 octets suffiraient en théorie)

et si le basic permet des truc du style MID$(...) = "0" ca peut etre rapide ?

A voir suivant les possibilités du langage. Par ex sur une HP48..50 l'utilisation d'entiers binaires qui vont jusque 64 bits si je me souviens bien.

[destroyedlolo]

Ce pgm doit marcher aussi sur les PC-13XX ... mais encore bien plus lents

Non, car sur 13xx, quant tu affiches qq chose, tout ce qui se trouve en dessous est effacé, genre si t'affiche "GEN : 2, les 3e et 4e lignes sont effacées ... C'est débile car ça vient uniquement du basic, y'a aucune raison technique à ça.

Ce n'est pas la seul aberration, car instructions graphiques comme GPRINT sont aussi TRES lentes : elles affichent / efface les points un par un en appelant les primitives de PSET et PRESET pour chaque point alors qu'il est tellement plus rapide de faire des décalages ... c'est ce que je faisais dans mes jeux et il y a un facteur de 20 ou 30 !

[remy]

Ce n'est pas la seul aberration, car instructions graphiques comme GPRINT sont aussi TRES lentes : elles affichent / efface les points un par un en appelant les primitives de PSET et PRESET pour chaque point alors qu'il est tellement plus rapide de faire des décalages ... c'est ce que je faisais dans mes jeux et il y a un facteur de 20 ou 30 !

Ils ont fait ça car le GPRINT peux se positionner sur n'importe quelle ligne (0-31) et pas uniquement aligné sur les 4 ligne de texte. C'était donc plus compliqué d'adresser potentiellement plusieurs zones mémoire et ont donc décidé de passer par les PSET/PRESET.
Je suis d'accord qu'ils auraient pu tester l'alignement sur les lignes de texte pour écrire directement dans la mémoire vidéo.

[destroyedlolo]

Ils ont fait ça car le GPRINT peux se positionner sur n'importe quelle ligne (0-31) et pas uniquement aligné sur les 4 ligne de texte. C'était donc plus compliqué d'adresser potentiellement plusieurs zones mémoire et ont donc décidé de passer par les PSET/PRESET.

Ils ont surtout utilisé la solution de facilité

Dans mes jeux, j'avais au début Xreg = le pattern que je voulais afficher. Ensuite, je décalais bit par bit et octet par octet et je stockais les débordements sur Yreg que je décalais aussi (ça tombe bien, les instructions de décalage tiennent compte de la carry donc le tout est très léger).
A la fin, je me retrouvais dans Xreg le resultat de la ligne courante et dans Yreg la ligne suivante (par ligne, j’entends au sens contrôleur video du terme, donc sur 8 bits de haut sur chaque ligne).
Enfin, il suffisait de faire un OR de ces registres vers la mémoire vidéo pour afficher (vers la fin, je faisais même des filtres avec AND donc j'avais une image complète ... on peut même avoir un gabarie sur un 3e "registres" pour tester les collisions.
Et comme la routine qui calcul l'adresse vidéo tien aussi compte des dépassements de l'écran physique (une ligne fantôme en bas, une autre en haut), on peut déciner ce que l'on veut où l'on veut.

Ca allait TRES TRES vite. Bon, malheureusement, j'ai pommer ces soft depuis, mais l'excellent ChangerMKII présent sur mon site utilise cette méthode, enfin juste les OR.

Ils auraient pu faire de même avec GPrint et on aurait eu alors la possibilité de faire des vrais BLOBs même en BASIC

Niveau optimisation, ils auraient utilisés des switch/case à la place des tables de pointeurs pour exécuter les token basic, on y aurait gagner beaucoup ... surtout que le CPU n'est pas prévu pour gérer les pointeurs de fonctions. C'est encore plus prégnant sur les machines à banques comme le 1360 où le CPU perd sont temps à basculer d'une banque à l'autre.

M'enfin, ils ne se sont sans doute jamais douté qu'il y aurait des malades pour pousser ces machines dans leurs retranchements

[ledudu]

@Babaorhum, C'est sympa. Ce sont de vieux souvenirs.

Juste un truc, pourquoi recopier de droite à gauche
Pour gagner 25s à chaque fois, tu peux générer un coup à droite un coup à gauche, non ?

[babaorhum]

Merci à tous,

@Gilles : en passant par les chaînes de caractère - j'ai essayé sur l'écran "texte" 26x4 du PC-1600 - c'est encore plus lent ... Je me suis rabattu sur les PSET et PRESET car j'ai l'impression que ces instructions sont proches du hard et donc rapides ...

@Rémy : Voui, le besoin est bien de variables booléennes, qui n'exitent pas en basic. Une solution est peu être de "poker" les valeurs en mémoire sous forme d'octets - je n'ai pas essayé mais j'ai un peu peur du temps que va mettre le basic pour extraire les "bits" utiles dans les octets - Mais je vais essayer, ca me fera un bon exercice de manipulation de poke et de peek !

@Lolo : ton site est toujours dans mes références et je suis loin d'en avoir tout décortiqué - si toutefois tu retrouves des traces de tes travaux en LM, sache qu'il n'est pas inutile de les diffuser ... même en 2013 (!!) - Et merci au tandem Rémy/Lolo pour soulever un peu le clavier et voir les entrailles de nos machines et leur conception, toujours passionnant !

@Ledudu : Ton conseil est tout à fait judicieux - En fait la phase de recopie n'est pas la plus pénible ... on est même content de voir quelque chose de passer un peu rapidement à l'écran (plus d'une ligne traitée par seconde !). Mais je garde en tête si j'arrive à booster un peu la chose.

Je vais essayer le stockage des lignes sous forme de deux tableaux d'octets (je vais donc sûrement passer à un format 32x32 = 128 octets plus adapté) - développer les routines pour travailler en mémoire et faire l'affichage à la fin du calcul. On verra si je gagne du temps. Quelques soirées sans télé en perspective !

Et si vous avez des billes sur l'organisation de la mémoire vidéo du 1600, je suis preneur ! (sur mon apple 2e de quand j'étais jeune, la mémoire vidéo était entrelacée, toutes les 40 lignes si je me souviens bien, c'était l'enfer à programmer)

[destroyedlolo]

Une solution est peu être de "poker" les valeurs en mémoire sous forme d'octets - je n'ai pas essayé mais j'ai un peu peur du temps que va mettre le basic pour extraire les "bits" utiles dans les octets

Mais pourquoi descendre au niveau du bit ? Ca va rajouter du traitement et du temps de calcul.
Non, si tu reste avec ta matrice de 30x30, tu réserves simplement une zone de 900 octets : s'il est nul, cellule vide, s'il est non nul, cellule plaine.
C'est du gachi niveau mémoire, mais c'est clairement le plus efficace, y compris je pense niveau temps de calcul par rapport à un stockage en tableau basic ou en chaine de caractère.
Sinon, si tu veux resté niveau bits (je ne considère ici que les colonnes, pour les lignes l'adressage est évident):

• chaque bit a une adresse de 0 à 30 (A)
• l'octet correspondant à l'adresse A/8
• le bit dans l'octet est A modulo 8 (modulo qu'il faudra sans doute coder)
• donc son poids est 2^(A modulo

En basic, ça va prendre pas mal de temps (d'où ma proposition de resté au niveau de l'octet). Mais c'est hyper simple en assembleur vu que le tout se résume à faire des décalages et des masques.

@Lolo : ton site est toujours dans mes références et je suis loin d'en avoir tout décortiqué - si toutefois tu retrouves des traces de tes travaux en LM, sache qu'il n'est pas inutile de les diffuser ... même en 2013 (!!) -

Même si je les retrouve, je doute que les K7 soient encore lisibles. Mais j'ai donné l'algo, reste plus qu'à coder si qq'un est intéressé, c'est très simple

Il y a quelques temps, j'avais envie de refaire un jeu pour le 1350 comme à la bonne époque. Mais l'envie est retombée et j'ai plein d'autres projets en route. Peu être un jour

[Marge]

Bravo Babaorum !

Toujours passionnant, ce jeu de la vie.

Il a existé plusieurs versions pour HP-97, et j'aimerais (un jour) tester une version unidimensionnelle sur HP-19c.

Ah, je n'ai pas regardé ton pgm en détail, mais tu considères le plateau de jeu comme fini ou comme un tore ?

[jvernet]

En BASIC, je ne suis pas sur que

Code : Tout sélectionner

 1390 F=POINT(I-1,J)+POINT (I+1,J)+POINT (I,J-1)+POINT (I,J+1)

soit beaucoup moins rapide que

Code : Tout sélectionner

 1390 F=P(I-1,J)+P(I+1,J)+P(I,J-1)+P(I,J+1)

ou P est le tableau 30x30 qui stocke les microbes.

Il ne faut pas descendre au niveau du bit, manipuler des bits sera plus lent que des octets
Ca existe, DEFINT P en BASIC PC1600 ? Sinon, DIM P(30,30) va réserver bien plus que 900 Octets !

[ledudu]

Code : Tout sélectionner

DIM P(30,30)*1

900 octets

[jvernet]

Code : Tout sélectionner

DIM P(30,30)*1

900 octets

Non, le PC-1600 ne prend pas cette expression (ERROR 1).
Sous Pockemul, DIM P(30,30) ne change pas MEM, curieux... Mais je ne me souviens jamais comment cette bestiole gère sa mémoire.