Bloc-notes
Math Lycée
Info Lycée
Menu contextuel
Sokoban (Fiche élève)
[JEB303]

Le Sokoban est un jeu vidéo de puzzle inventé au Japon en 1982.

Un gardien d'entrepôt (divisé en cases carrées), le joueur doit ranger des caisses sur des cases cibles. Il peut se déplacer dans les quatre directions, et pousser (mais pas tirer) une seule caisse à la fois. Une fois toutes les caisses rangées, le niveau est réussi et le joueur passe au niveau suivant. Pour plus d'informations, consultez Wikipédia.

Partie A — Installation de Sokowiz

Le logiciel Sokowiz est un des nombreux programmes qui permet de jouer au Sokoban.
(a)
Installez Sokowiz sur votre système Ubuntu.
(b)
Lancez sokowiz et jouez une partie (une seule !!!).

Partie B — Codage d'un niveau de Sokoban

Divers programmes informatiques peuvent être conçus et réalisés autour du Sokoban :
  • programme pour jouer au Sokoban ;
  • interface graphique pour créer des niveaux de jeu ;
  • programme résolveur de niveaux ;
  • programme qui génère automatiquement des niveaux.

Une des premières questions qui se pose est de définir la façon de coder un niveau, c'est-à-dire de représenter ce niveau par un texte destiné à être lu par les programmes.

(a)
Proposez une méthode de codage et appliquez cette méthode pour encoder le niveau ci-dessus.
(b)
Les codages proposés sont-ils tous équivalents ? Quelles sont les qualités d'un bon codage ?
(c)
La page http://fr.wikipedia.org/wiki/Sokoban décrit un codage de niveaux appelé « format XSB ».

Un exemple de fichier au format XSB est disponible ici .

Étudiez ce codage. Quels sont ses avantages ?

Partie C — Programme d'analyse d'un niveau Sokoban

Dans cette activité notre objectif va être d'écrire un programme Python qui  :
  • lit le format XSB ;
  • analyse les niveaux ;
  • affiche certaines informations sur ces niveaux ;
  • détecte certaines anomalies éventuelles dans ces niveaux.

Le texte ci-dessous est une première version de ce programme. L'étude de ce texte va être pour nous l'occasion de nous familiariser avec le langage Python.

 1 #!/usr/bin/env python
 2 # -*- coding: utf-8 -*-
 3 
 4 """sokoban -- Analyseur de Jeu Sokoban  -- version 1
 5 
 6 Analyse une collection de niveaux du jeu Sokoban.
 7     Vérifie sa validité
 8     Fournit des informations sur cette collection.
 9 
10 Cette version affiche uniquement le nombre de caisses pour
11     chaque niveau.
12 """
13 
14 __author__ = 'Denis Pinsard'
15 __email__ = 'denis.pinsard@dichotomies.fr'
16 
17 #______________________________________________________________________________
18 def processLevel(lines):
19     """Analyse un niveau
20         `lines` est une liste qui contient les lignes du fichier XSB
21         associés à ce niveau
22         Affiche des informations sur ce niveau
23     """
24     # `nbBoxes` va contenir le nombre de caisses du niveau
25     nbBoxes = 0
26     # On parcourt toutes lignes du niveau
27     for line in lines:
28         # Pour chaque ligne, on parcourt tous les caractères de la ligne
29         for c in line:
30             if c in ['$', '*']:
31                 # Il s'agit d'une caisse (éventuellement sur une cible)
32                 nbBoxes = nbBoxes + 1
33     print 'Le niveau comporte', nbBoxes, 'caisses'
35 #============== PROGRAMME PRINCIPAL =======================
36 
37 # On lit le fichier XSB ligne par ligne.
38 # Le drapeau `readLevel` indique si on est en cours de lecture d'un niveau
39 
40 readLevel = False
41 # Le fichier passé en argument est ouvert en lecture ('r' signifie 'read')
42 levelSet = open('sokotest.xsb', 'r')
43 # On lit les lignes du fichier une par une
44 for line in levelSet:
45     if readLevel:
46         # La lecture d'un niveau est en cours
47         if line[0] in [' ', '#']:
48             # Suite du niveau
49             lines.append(line)   # Ajoute la chaîne `line` à la liste `lines`
50         else:
51             # Le niveau est entièrement lu
52             readLevel = False
53             # Analyse du niveau
54             processLevel(lines)
55     else:
56         # Pas de niveau en cours de lecture
57         if line[0] in [' ', '#']:
58             # Début d'un niveau
59             readLevel = True
60             print "_________________________________________"
61             # Création de la liste `lines` 
62             lines = [line]
63             # pour l'instant il n'y a que la première ligne dans `lines`
64         else:
65             # Toujours pas de niveau
66             pass
67 if readLevel:
68     processLevel(lines)    
69 # Fermeture du fichier 
70 levelSet.close()

Le texte ci-dessus possèdent deux finalités distinctes :
  • Être lu par une machine informatique afin de produire des effets.
  • Être lus par des humains afin que ceux-ci comprennent les effets qu'il produit et d'être en mesure de le modifier pour produire des effets différents.
Ces deux finalités sont les deux faces d'une même pièce. Un programme illisible par des êtres humains devient rapidement inutilisable.

«  Programs must be written for people to read, and only incidentally for machines to execute.  » -- Hal Abelson.

Du point de vue de la machine le texte ci-dessous est rigoureusement équivalent au texte précédent. Il produit les mêmes effets. Par contre du point de vue humain ce nouveau texte est illisible.

 1 def a(d):
 2  b=0
 3  for e in d:
 4   for c in e:
 5    if c in['$','*']:b=b+1
 6  print 'Le niveau comporte',b,'caisses'
 7 f=False
 8 g=open('sokotest.xsb','r')
 9 for e in g:
10  if f:
11   if e[0]in[' ','#']:d.append(e)
12   else:f=False;a(d)
13  else:
14   if e[0]in[' ','#']:f=True;print "_________________________________________";d=[e]
15 if f:a(d)    
16 g.close()

Un programme Python digne de ce nom se distingue par :
  • Une doctring principale (lignes 4 à 12) qui dit ce que fait le programme.
  • Une doctring pour chacune des fonctions qui dit ce que font ces fonctions
  • Des commentaires (précédés par le caractère '\#') qui aident à comprendre les instructions du programme.
  • Des noms de variables pertinents qui aident à comprendre la nature de l'information qu'elles désignent.
  • Une utilisation judicieuse et constante des espaces pour améliorer la lisibilité du texte (une espace avant et après le '=', une espace après la virgule mais pas avant, etc).

Le texte du programme ci-dessus peut être téléchargé .

Modifications à effectuer sur le programme :
(a)
Affichez le nombre de cibles.
(b)
Affichez un message d'erreur si le nombre de cibles n'est pas égal au nombre de caisses.
(c)
Affichez un message d'erreur si le pousseur manque ou si il y en a plusieurs.
(d)
Affichez pour chaque niveau du fichier, son numéro d'ordre dans le fichier.
(e)
Détectez si les caisses et les cibles sont bien dans la pièce où se trouve le pousseur.



Denis Pinsard -- Mis à jour le mardi 01 octobre 2013

Infos site
Visites

 0 visiteurs

 1 visiteur en ligne

Calendrier
^ Haut ^