Skip to content

Snake

L'objectif est de créer un jeu de snake minimaliste en exploitant la file construite avec deux piles dans le cours sur les files.

Les bases de la modélisation et de l'implémentation d'un jeu sont aussi abordées.

Modélisation

Un snake est une File de Coordonnées entières.

Cette file, c'est exactement celle que tu viens de construire avec deux piles : le snake en est la mise à l'épreuve. Pour le dessiner ou détecter une collision, on parcourt la file avec elements, sans la détruire.

alt text

La flèche rouge représente le vecteur directeur du snake. Ici, direction = (1, 0). On avance de 1 en x et de 0 en y.

Avant toute ligne de code, une décision commande tout le reste : une file a une entrée et une sortie, le serpent a une tête et une queue. Quel bout du serpent mets-tu à l'entrée ?

Choisir l'entrée et la sortie de la file

  1. Sur la grille, donne les coordonnées de la tête du serpent et celles de sa queue.
  2. Le serpent avance d'une case. Quelle case de la grille devient noire ? Quelle case redevient blanche ? Quel bout du serpent a gagné une case, lequel en a perdu une ?
  3. Une file n'ajoute qu'à son entrée et ne retire qu'à sa sortie. Où places-tu la tête ? Où places-tu la queue ?
  4. Écris l'état du snake de la grille, avec la notation du cours : > ... >, l'entrée à gauche, la sortie à droite.
Correction

La tête est en (4, 2), la queue en (1, 4). En avançant, la case (5, 2) devient noire et la case (1, 4) redevient blanche : la tête gagne une case, la queue en perd une. La tête est donc à l'entrée, la queue à la sortie : avancer, c'est enfiler la nouvelle tête puis defiler la queue.

> (4, 2), (3, 2), (3, 3), (3, 4), (2, 4), (1, 4) >

Exercices d'appropriation de la modélisation

  1. Écrire l'état du snake lorsqu'il aura avancé d'une case
    • Quelles primitives de file as-tu utilisées ?
  2. Écrire l'état du snake lorsqu'il aura avancé d'une case avec une pomme en (5,2)
    • Quelles primitives de file as-tu utilisées ?
  3. Lorsque le snake avance, donne la ou les conditions pour que le jeu soit terminé (gameover = True)
  4. Écrire les différentes valeurs du vecteur directeur selon qu'on avance en haut, à gauche, en bas, ou à droite.

Voici le code de départ du snake

from structures.lineaires import file
import random
import pyxel     # uv add pyxel

type Coord = tuple[int, int]   # Une coordonnée est un tuple constitué de deux ints
type Snake = file.File[Coord]  # Un snake est une file de coordonnées

# --- Constantes ---
W, H = 20, 20       # Largeur et Hauteur de la grille
STEP_FRAMES = 4     # Vitesse (Mise à jour toutes les 4 frames)


# --- État global --- Déclaration de toutes les variables --- 
serpent: Snake                  # File de coordonnées
tete: Coord                     # Tete du serpent
queue_supprimee: Coord | None   # Dernière queue du serpent supprimée
direction: Coord                # vecteur de déplacement du serpent
pomme: Coord                    # coordonnée de la pomme
score: int                      # score de l'utilisateur
game_over: bool                 # indicateur de game over
frames: int                     # compteur de frames (augmente de 1 dès que update est appelé)

# --- Initialisation ---
def reinit() -> None:
    """
    Initialisation de TOUTES les variables globales
    """
    global serpent, tete, direction, score, game_over, frames, queue_supprimee
    serpent = ...
    tete = ...
    ...........  # Initialiser le serpent avec sa tete
    direction = ......   # droite
    score = ......
    game_over = ......
    frames = 0    # Ne t'occupe pas de ça pour le moment
    queue_supprimee = ....
    # Il faut aussi spawner une pomme
    # on le fera grâce à une fonction spécifique qu'il faudra appeler ici

Deux fonctions outils, testables sans lancer le jeu

Ces deux fonctions ne dessinent rien et ne touchent à aucune variable globale : elles se testent donc immédiatement, sans ouvrir de fenêtre. Écris-les en premier, dans snake.py.

def prochaine_tete(tete: Coord, direction: Coord) -> Coord:
    """
    Coordonnée de la case suivante, sans toucher au serpent.
    """

def case_libre(occupees: list[Coord]) -> Coord:
    """
    Une case de la grille au hasard, parmi celles qui ne sont pas occupées.
    """

Leurs tests vont dans snake_test.py, dans le même répertoire :

# snake_test.py

from snake import H, W, case_libre, prochaine_tete


def test_prochaine_tete() -> None:
    assert prochaine_tete((4, 2), (1, 0)) == (5, 2)
    assert prochaine_tete((4, 2), (0, -1)) == (4, 1)
    assert prochaine_tete((0, 5), (-1, 0)) == (-1, 5)


def test_case_libre() -> None:
    toutes = [(x, y) for x in range(0, W) for y in range(0, H)]
    assert case_libre([c for c in toutes if c != (7, 3)]) == (7, 3)

Le second test mérite un mot : en n'offrant qu'une seule case libre, il rend déterministe une fonction qui tire au hasard. C'est une manière courante de tester l'aléatoire.

Initialisation

  • Compléter la fonction reinit.
  • Créer la fonction spawn_pomme(), qui appelle case_libre et modifie les coordonnées de la pomme.

Avancer

Écris cette fonction après avoir répondu aux exercices d'appropriation ci-dessus.

def avancer() -> None:
    """
    Fait avancer le serpent d'une case dans la direction courante.

    Enfile la nouvelle tête. Défile la queue, SAUF si le serpent vient de
    manger la pomme, auquel cas il grandit d'une case.
    """

Les deux cas de la docstring correspondent exactement aux exercices 1 et 2 d'appropriation : tu as déjà écrit sur papier ce que la fonction doit produire.

Comme beaucoup de moteurs de jeu, pyxel va appeler automatiquement à chaque frame 2 fonctions à la suite:

  1. une fonction update(), chargée de:
    • Récupérer l'interaction utilisateur.
    • Mettre à jour l'état du jeu en conséquence.
  2. PUIS une fonction draw(), chargée de dessiner l'état du jeu.

Voici comment se lancera notre jeu (fin du fichier):

# -- Mise à jour régulière de l'état --
def update() -> None:
    """
    Appelée automatiquement par pyxel.
    si on appuie sur <R>, on réinitialise
    Si on appuie sur <Q, Z, S, D>, on met à jour la direction
    On avance
    """
    ...

# -- Dessin régulier après mise à jour --
def draw() -> None:
    """
    Appelée automatiquement par pyxel.
    Dessine le snake à l'écran.
    La seule fonction pyxel nécessaire est pset
    """
    ...


# -- Lancement --

def lancer_jeu() -> None:
    # Initialiser pyxel, le moteur graphique
    pyxel.init(W, H, title="Snake")
    # Initialiser l'état du jeu
    reinit()
    # lancer la boucle d'appels permanents à update puis draw
    pyxel.run(update, draw)  


if __name__ == "__main__":
    lancer_jeu()

Amélioration

Pour l'instant on ne peut pas écrire sur l'écran, les pyxels sont trop gros.

  • Modifier la fonction draw en considérant que chaque coordonnée du snake correspond en réalité à un carré de 10x10 pixels
    • W, H = 200, 200
    • TAILLE_CASE = 10
  • Modifier la fonction draw afin qu'un bandeau reste libre en haut afin d'afficher le score.

Bonus : faire passer draw en temps constant

Dans la version de base, draw parcourt toute la file à chaque image pour redessiner le serpent entier. C'est correct, et c'est ce qu'il faut écrire en premier : on n'optimise pas un dessin avant que le jeu marche.

Mais remarque ce qui change vraiment d'une image à l'autre : une case s'allume, la nouvelle tête, et une case s'éteint, la queue qui vient d'être défilée. Deux cases. Le reste de l'écran est déjà correct.

D'où l'idée : ne pas effacer l'écran, et ne redessiner que ces deux cases.

  • la queue retirée, en couleur de fond ;
  • la nouvelle tête, en couleur du serpent.

C'est très exactement pour cela que queue_supprimee existe dans le squelette : avancer y mémorise ce qu'elle a défilé, pour que draw sache quoi effacer.

Ce que ce bonus t'apprend, et qui dépasse le dessin

Ta file est faite de deux piles, et son defiler est annoncé en O(1) amorti : chaque élément ne bascule qu'une fois de entree vers sortie au cours de sa vie.

Or elements vide la file puis la reconstruit. Tout se retrouve dans entree, et le defiler suivant doit tout rebasculer. En appelant elements à chaque image, la version de base remettait donc l'amortissement à zéro à chaque image, et annulait l'avantage des deux piles.

Comptage des opérations élémentaires sur la file (empiler, dépiler, décalages) sur cent images, avec un serpent de 400 cases. Les deux pset du bonus n'y figurent pas : ils ne touchent pas la file, et ils sont deux quoi qu'il arrive.

file à tableau file à deux piles
version de base (elements à chaque image) 80 600 240 700, soit 3 fois plus
avec ce bonus (plus d'elements dans draw) 40 600 1 001, soit 40 fois moins

Sois honnête sur ce que tu verras : rien. Sur une grille de 20 par 20, à sept mises à jour par seconde, les deux versions sont aussi fluides l'une que l'autre, et aucun œil ne les départage. Le gain ne se voit pas, il se compte.

C'est le vrai enseignement de ce bonus : l'avantage d'une structure de données dépend de la façon dont on s'en sert. Une complexité ne s'énonce jamais dans l'absolu, toujours pour un motif d'usage donné. Retiens ça, c'est ce qui distingue quelqu'un qui connaît le nom des structures de quelqu'un qui sait en choisir une.