Un démineur en python pour la NumWorks


Accueil > Projets > Un démineur en python pour la NumWorks

Par Robert Vincent en février 2020

Souvenir de jeunesse

J’ai découvert la programmation sur une désormais antique Casio 9960GT, propulsé par son CPU 8 bits à 4,3 MHz.

Lycéen et autodidacte, j’ai alors entrepris de programmer un démineur et cela fut passionnant.

Le processeur de cette génération de calculatrice était tellement lent et l’accès à la mémoire encore plus lent que chaque test logique prenait un temps considérable.

Le démineur codé et parfaitement fonctionnel se montrait ainsi d’une lenteur remarquable au premier lancement lors de l’affichage de la couche graphique.

Quelques caractéristiques de ce démineur :

  • 5 niveau de difficulté
  • un plateau de jeu de 14 cases par 7, soit 98 cases en tout.
  • L’initialisation de la couche graphique prenait à elle seule plus de 30 secondes
  • La navigation était fluide, mais la fonction découverte pouvait prendre une bonne dizaine de seconde.

Concernant la lenteur de la calculatrice, l’allemand Marco Kaufmann écrit sur son site web en 2004 (traduction de Fedyna Kevin ) :

Beaucoup de gens ont certainement été agacés par la lenteur de leurs programmes sur le Casio CFX, mais cela n’est pas dû à l’ordinateur, mais SEULEMENT à l’inadéquation du Casio Basic : d’une part, il s’agit juste d’un langage d’interprétation, qui est en partie peu mis en œuvre (surtout dans l’affichage graphique, on pourrait gagner un peu plus de vitesse si l’interprète n’exécutait pas un rafraîchissement de l’affichage après CHAQUE commande graphique, mais si vous deviez l’appeler séparément). Si vous pouviez programmer le Casio CFX directement en assembleur (ce qui est probablement possible SANS), vous seriez surpris de la performance, car : Sur le plan purement matériel, le Casio CFX pourrait certainement rivaliser avec une GameBoy ! ! source

Sur une NumWorks, en Python

20 ans plus tard, l’idée est donc de coder un nouveau démineur, en python, et de le faire tourner sur la calculatrice à la mode du moment : une NumWorks, propulsé par un CPU ARMv7 à 100 / 200 mhz, donc probablement plus de 50 fois plus rapide que celui de mon antique Casio.

Mes élèves de seconde étant tous équipés de cette calculatrice, ils pourront s’amuser en silence quand les cours sont trop ennuyeux, et cela montrera aux futurs élèves de la spécialité NSI les possibilités de la calculatrice et la souplesse du langage python.

L’objectif est de sortir ce démineur pour la sortie officielle de la version 13 de Epsilon, le logiciel sous licence CC BY-NC-SA de la calculatrice NumWorks.

La version 13 de Epsilon introduit beaucoup d’améliorations et de nouveautés à l’application Python, celle qui nous intéresse particulièrement et le getkey, la capacité de la calculatrice dans un script python à détecter si une touche est pressée.

Le site tiplanet.org ayant déjà bien documenté cette fonctionnalité, on dispose donc déjà des codes associés aux touches :

Créer une interface graphique

Pour faire un démineur, on a besoin d’un tableau de n lignes et p colonnes dans lequel on va afficher une mine, un drapeau ou un chiffre.

Il faut donc s’adapter à la résolution de l’écran, et la principale contrainte à prendre en compte est la taille d’affichage des chiffres.

Puis on les met en couleur

et enfin on code les mines et le drapeau.

  1. #codage des couleurs
  2. co=color
  3. f,h,n = 255,127,0
  4. c=[co(f,f,f), co(45,125,210), co(151,204,4), co(238,185,2), co(244,93,1), co(215,65,167), co(n,n,n), co(n,n,n), co(n,n,n),
  5.    co(h,h,h),co(192,192,192),co(96,96,96),co(253,236,185)]

Télécharger

  1. def terrain(): #Affiche la grille
  2.   fill_rect(8,21,300,200,c[9])
  3.   for y in range(21,243,20):
  4.     for x in range(8,309):
  5.       set_pixel(x,y,c[10])
  6.   for x in range(8,320,20):
  7.     for y in range(21,222):
  8.       set_pixel(x,y,c[10])

Télécharger

  1. def cl(x,y):
  2.   fill_rect(9+20*x,22+20*y,19,19,c[0])
  3.  
  4. def drapeau(x,y):
  5.   fill_rect(17+20*x,26+20*y,3,9,c[12])
  6.   fill_rect(17+20*x,36+20*y,3,3,c[12])
  7.  
  8. def mine(x,y): # Ce code ne sera pas retenu pour la version finale.
  9.   cl(x,y);
  10.   fill_rect(12+20*x,36+20*y,13,4,c[9])
  11.   fill_rect(14+20*x,34+20*y,9,2,c[11])
  12.   fill_rect(17+20*x,32+20*y,3,2,c[5])

Télécharger

Une matrice pour stocker les mines

Le plus simple est de stocker les mines dans une matrice 10x15.

Pour cela on défini une matrice en python et on la rempli de 0.

  1. m = [[0 for y in range(10)] for x in range(15)]

puis un script génère des bombes, codées 999 dans la matrice.

  1. def gvt(): #fonction renommée depuis ...
  2.   b = 20
  3.   while b>0:
  4.     x, y = randint(0,14),randint(0,9)
  5.     if m[x][y]!=999:
  6.       m[x][y]=999
  7.       b-=1
  8.       for p in range(max(0,x-1),min(15,x+2)):
  9.         for q in range(max(0,y-1),min(10,y+2)):
  10.           if m[p][q]!=999:m[p][q]+=100  

Télécharger

Le script ci-dessus a deux fonctions, il place les 20 mines puis "calcule" pour chaque case le nombre de bombes dans les 8 cases autour.

Ainsi, la matrice contient à ce stade uniquement des entiers :
soit des 0 (0 bombes dans les 8 cases environnantes), soit des multiples de 100, soit des 999.

Question : Pourquoi 100 et pas 1 pour indiquer qu’il y a une bombe ?

Réponse : Car on va utiliser cette matrice pour y stocker une information importante, à savoir si la case a été découverte ou pas.

m[i][j] La case (i,j) contient Dans les 8 cases autour de la case (i,j) il y a case découverte
999 1 mine on ne sait pas non sinon (...)
342 0 mine 3 mines oui
300 0 mine 3 mines non
42 0 mine 0 mine oui
1 0 mine 0 mine en cours de découverte
0 0 mine 0 mine non

Calcul du nombre de mines de chaque case

En parcourant l’article Wikipédia sur le démineur lors de la rédaction de ce compte rendu, j’y ai découvert que j’ai construit intuitivement l’un des deux algorithmes classiques pour le calcul des nombres des différentes cases du démineur.

Sur mon antique Casio 9960GT, j’utilisais l’algorithme par case :

explorer tableau par case
si case est vide
nombre := compter_mines(case.voisinage)
case.valeur = nombre<

et sur la numworks, j’ai construit une version légèrement adapté de l’algorithme par mine :

// Placement de la mine
explorer mine.voisinage par case
si case est vide
incrémenter case.valeur

Dans une première version en python, j’utilisais la partie décimale pour y stocker le 42 ou le 0.01, ainsi cela donnait 1,42 si il y a une mine dans le voisinage et que la case est déjà découverte, mais ceci posa un problème, le test :

  1. if 1.42-round(1.42)==42

ne marchait pas, car python ne dispose pas d’un moteur de calcul exact sur les réels.
Le résultat du calcul 1.42-1 en python est 0.419999999999999

Par ailleurs, stocker en réel et non un entier est susceptible de consommer plus de mémoire, donc le stockage de l’information sous la forme d’entier est préférable pour les tests conditionnels.

Une fonction pour les découvrir toutes !

A partir de la matrice, on peut exécuter un script qui révèle les positions et vérifie que tout fonctionne correctement :

  1. def verif():
  2.   for x in range(15):
  3.     for y in range(10):
  4.       if m[x][y]==666:
  5.         mine(x,y)
  6.       elif m[x][y]>0:
  7.         chiffre(x,y)

Télécharger

La fonction chiffre elle a pour objectif d’afficher le nombre de bombes autour :

  1. def chiffre(x,y):
  2.   cl(x,y)
  3.   nb[1]+=(m[x][y]%100!=42)
  4.   i=m[x][y]-m[x][y]%100
  5.   m[x][y]=i+42
  6.   if i>=100:v=int(i/100);draw_string(str(v),13+20*(x),23+20*(y),c[v],c[0])
  7.   deminage()

Télécharger

pas à pas de la fonction chiffre :

- cl(x,y) éclairci la case
- nb[1] s’incrémente de 1 si la case n’a pas déjà été découverte, c’est le compteur de la victoire
- Si la valeur m[x][y] contenait Z00 elle sera désormais de Z42, Z étant un entier entre 0 et 8.
- On affiche la valeur de Z, avec une couleur adaptée.
- On exécute le script deminage(), qui calcule le score et vérifie si l’on a gagné.

Le plus difficile à coder est la fonction de découverte de proche en proche, si on dévoile une case ne contenant aucune mine, et pas de mine non plus dans les 8 cases alentours, il faut faire un "script récursif" de traitement et de découverte de ces cases.

Au départ cela ne marche pas

Enfin si mais de manière aléatoire

et puis une fois debug, tout fonctionne de manière fluide et efficace :

La fonction decouvre() est la suivante :

  1. def decouvre(x,y):
  2.   i=1
  3.   while i>0:
  4.     chiffre(x,y)
  5.     for p in range(max(0,x-1),min(15,x+2)):
  6.       for q in range(max(0,y-1),min(10,y+2)):
  7.         if m[p][q]>=100:chiffre(p,q)
  8.         elif m[p][q]==0:m[p][q]+=1
  9.     i=0
  10.     for p in range(15):
  11.       for q in range(10):
  12.         if m[p][q]%100==1:i=1;x=p;y=q;p=14;q=9

Télécharger

Elle est appelée par la fonction marche() :

  1. def marche(x,y):
  2.   if m[x][y]>=999:explose()
  3.   elif m[x][y]>=100:chiffre(x,y)
  4.   else:decouvre(x,y)

Télécharger

Ainsi la fonction découverte n’est appelée que si on "marche" sur une case sans mine, et que les 8 cases aux alentours ne contiennent également aucune mine.

Elle teste les 8 cases du voisinage, affiche le chiffre de celles qui doivent afficher un chiffre. Si les cases contiennent un 0, il devient 1 et devra être traité par le script ultérieurement.

Ce fonctionnement n’est pas optimal en temps de calcul, mais il ne crée aucun nouvel objet en mémoire. Il n’est pas vraiment non plus récursif au sens python pour éviter là encore de consommer trop de mémoire.

Une précédente version ajoutait les coordonnées des cases à traiter dans une liste, mais cette liste grossissait et pouvait saturer la mémoire.

Piloter un drone sur un terrain miné

Il ne reste plus qu’à coder la navigation dans l’écran, c’est à dire l’interaction entre l’affichage et le clavier de la calculatrice.

  1. a,r,t,l,k,s=set_pixel,fill_rect,draw_string,range,keydown,sleep
  2. p=[[6,5],[7,5]]
  3.  
  4. def survol():
  5.   x, y = p[1][0], p[1][1]
  6.   v = m[x][y]
  7.   gps(x,y)
  8.   # t(str(int(v/100)),20,2)
  9.   x, y = p[0][0], p[0][1]
  10.   v = m[x][y]
  11.   if p[1][0]!=x or p[1][1]!=y:
  12.     if (v-42)%100==0:gps(x,y,0)
  13.     else:gps(x,y,9)
  14.   del p[0]
  15.  
  16. def gps(x,y,i=6):
  17.   r(9+20*x,22+20*y,19,2,c[i])
  18.   r(26+20*x,22+20*y,2,19,c[i])
  19.   r(9+20*x,22+20*y,2,19,c[i])
  20.   r(9+20*x,39+20*y,19,2,c[i])
  21.  
  22. def drone():
  23.   while not k(6):
  24.     if k(0):p.append([max(p[0][0]-1,0),p[0][1]])
  25.     if k(3):p.append([min(p[0][0]+1,14),p[0][1]])
  26.     if k(1):p.append([p[0][0],max(p[0][1]-1,0)])
  27.     if k(2):p.append([p[0][0],min(p[0][1]+1,9)])
  28.     if k(4):marche(p[0][0],p[0][1])
  29.     if k(17) or k(16):drapeau(p[0][0],p[0][1])
  30.     if k(52):nb[2]=0;nb[0]=22;minage(nb[0]);s(1)
  31.     if k(45):nb[0]=min(nb[0]+5,90);minage(nb[0]);s(1)
  32.     if k(46):nb[0]=max(nb[0]-5,10);minage(nb[0]);s(1)
  33.     if len(p)>1:survol();s(0.120)

Télécharger

La fonction survol() déplace le curseur, en rétablissant l’affichage de la case précédemment survolée à l’aide de la fonction gps().

la fonction drone() attend que l’utilisateur appuie sur une touche du clavier.

Touche Code touche Action
Flèche haut 1 se déplacer
Flèche bas 2 se déplacer
Flèche gauche 0 se déplacer
Flèche droite 3 se déplacer
OK 4 marcher sur la case
Clear ou Tolbox 17 Afficher un drapeau
Maison 6 quitter la boucle
+ 45 ajouter 3 mines et recommencer la partie
- 46 enlever 3 mines et recommencer la partie
EXE 52 recommencer la partie avec les paramètres par défaut

Le nombre de mine par défaut est fixé à 19 pour un plateau de 150 cases, soit un ratio de 12.7%.

Le démineur de Microsoft sur Windows 10, appelé Minesweeper propose des ratios de 11,1%, 15%, et 20% respectivement pour les modes faciles, moyen et difficile.

Le nombre de mine qu’il est possible de placer est un nombre dans la liste :
13, 16, 19, 22, 25, ..., 40 mais une petite astuce mathématiques permet de choisir n’importe quel entier entre 8 et 42 pour désigner le nombre de mine.

Oui n’importe quel nombre entier entre 11 et 42 alors que l’interface et l’utilisation des touches [+] et [-] ne permet que d’ajouter ou d’enlever 3 mines...

Epsilon version 13.2.0

La sortie de la version 13.2.0 d’Espilon, le logiciel qui anime la NumWorks permet de faire tourner sans problème ce démineur.

Si dans la version 13.0.0 et 13.1.0 le démineur ne fonctionnait pas à cause d’une affectation insuffisante de mémoire pour l’exécution des scripts python, la version 13.2.0 résout ce problème qui n’est plus qu’un mauvais souvenir.

Ainsi, la NumWorks est l’une des calculatrice la plus rapide lors de l’exécution des scripts Python, et que pour un prix d’achat de 79€ elle n’a clairement aucune concurrence dans cette gamme de prix.

Omega, un firmware alternatif pour votre numworks

Le logiciel de la NumWorks est libre et ouvert, ce qui est très appréciable et on peut même dire admirable dans l’univers très fermé des calculatrices.

Ainsi, tout le monde peut accéder au code source, le lire, le modifier et le redistribuer en respectant les conditions imposées par la licence CC BY-NC-SA.

Une équipe de passionné a donc décidé de développer un firmware alternatif, et il l’ont appelé Omega. Ils intègrent différentes amélioration, et poussent les developpeur du firmware stock à s’améliorer sans cesse.

Pour tester ce démineur, tu dois :

  • Soit mettre à jour ta calculatrice en version 13.2.0 au minimum.
  • Soit installer le firmware Omega.
Installer Lien hypertexte
1. Installer Le firmware Omega en quelques clics
1. Ou mettre à jour Epsilon en quelques clics
2. Installer le démineur worshop
Bonus : L’application polynome 4.0 Ko worshop

Version 1.2

Une nouvelle version de ce démineur est sortie le 18 avril 2020, elle intègre un menu graphique python développé en interne pour cette occasion.

Le script du démineur pèse désormais 8.42ko, et le démineur peut désormais être paramétré par un menu graphique, interactif et intuitif.

De nouvelles options ont été ajoutées :

  1. Le choix du graphisme : Flat vs Classique
  2. Un mode triche à tester avec la touche MAJ de l’ordinateur ou Shift sur la calculatrice.

Pour jouer, il faut télécharger sur votre calculatrice :

Soit le script demine.py
Soit les scripts demine_se.py et menu.py.

La version "(...)_se" désigne une édition spéciale, allégée du menu qui est appelé depuis un autre script. Ainsi, le code du menu est mutualisé, ce code occupe donc moins de place car l’espace de stockage des scripts sur la calculatrice est limité.

Amusez vous bien !

Quelques dernières remarques

Si tu souhaites réagir à cet article, tu es invité à le faire sur ce forum :
[tiplanet.org] Un démineur en python pour la NumWorks

Tu y trouvera des discussions pointues sur l’utilisation de la mémoire lors de l’éxécution d’un script Python, et il n’est pas impossible que tu y trouves un deuxième démineur codé par un de mes plus brillants élève en algorithmique : Arthur Jacquin

Entre le script initial et le script proposé en ligne à cet instant, de nombreuses réécritures portions du code ont été réécrites, mais les explications de cet article restent valables.

Poursuivre la lecture : Un démineur en python pour la NumWorks

Mots-clés