Séance 10 · Partie A · Projet

Mission Mars.

Un rover explore une grille inconnue, évite les rochers, collecte des échantillons et doit rentrer avant que sa batterie soit vide. Vous allez l’écrire de A à Z, avec tout ce que vous avez appris.

Durée : 2 séances · Objectifs : mener un projet du cahier des charges au programme final ; découper, tester, faire évoluer ; produire un code lisible qu’un camarade peut reprendre.

Méthode

Lire le cahier des charges et le reformuler avec vos mots.
Découper en fonctions avant d’écrire une ligne.
Construire par étapes, chacune testée, chacune fonctionnelle.
Assembler, jouer, corriger. Puis étendre.

Chaque étape ci-dessous est exécutable. Le code s’accumule : à la fin, vous avez le jeu complet.

01 / Cahier des charges

Ce que le programme doit faire

Le monde

Une grille de 8 × 8 cases.
Des rochers (#) infranchissables, placés au hasard.
Des échantillons (*) à collecter.
La base (B) en (0, 0), où le rover démarre.

Le rover

Une position (x, y) et une batterie (100 au départ).
Se déplace d’une case : N, S, E, O. Chaque pas coûte 3 %.
Ne peut pas sortir de la grille ni traverser un rocher.

La partie

À chaque tour, on affiche la carte et l’état, puis on lit une commande.
Commandes : n s e o, scan (montre les cases voisines, coûte 1 %), q (abandonner).
Passer sur un échantillon le collecte.
Victoire : revenir à la base avec tous les échantillons.
Défaite : batterie à 0 hors de la base.

Avant de continuer : quelles fonctions faut-il ? Notez-les sur papier.

02 / Conception

Découpage en fonctions

Fonction	Rôle	Entrées → sortie
`creer_carte(taille, nb_rochers, nb_echantillons)`	Construire le monde	→ liste de listes de caractères
`afficher(carte, rover)`	Montrer la situation	→ rien (affiche)
`deplacer(carte, rover, direction)`	Tenter un pas, gérer rochers et bords	→ booléen (réussi ?)
`scanner(carte, rover)`	Décrire les 4 cases voisines	→ rien (affiche)
`partie_terminee(carte, rover)`	Victoire, défaite ou rien	→ "victoire" / "defaite" / None
`jouer()`	La boucle principale	→ rien

L’état du jeu

Le rover est un dictionnaire : {"x": 0, "y": 0, "batterie": 100, "echantillons": 0}. La carte est une liste de listes : carte[y][x] (ligne puis colonne — attention à l’ordre !). Les fonctions reçoivent ces deux objets et les modifient sur place (séance 06 : les listes et dictionnaires sont mutables). deplacer renvoie un booléen pour que la boucle puisse dire « impossible ». partie_terminee ne fait que décider : elle est facile à tester.

03 / Étape 1

Créer et afficher le monde

import random

TAILLE = 8
VIDE, ROCHER, ECHANTILLON, BASE, ROVER = ".", "#", "*", "B", "R"

def creer_carte(taille, nb_rochers, nb_echantillons):
    carte = [[VIDE for _ in range(taille)] for _ in range(taille)]
    carte[0][0] = BASE
    libres = [(x, y) for x in range(taille) for y in range(taille) if (x, y) != (0, 0)]
    random.shuffle(libres)
    for x, y in libres[:nb_rochers]:
        carte[y][x] = ROCHER
    for x, y in libres[nb_rochers:nb_rochers + nb_echantillons]:
        carte[y][x] = ECHANTILLON
    return carte

def afficher(carte, rover):
    print("   " + " ".join(str(x) for x in range(len(carte))))
    for y, ligne in enumerate(carte):
        cases = [ROVER if (x, y) == (rover["x"], rover["y"]) else c for x, c in enumerate(ligne)]
        print(f"{y:2} " + " ".join(cases))
    print(f"Batterie {rover['batterie']} %  Échantillons {rover['echantillons']}")

random.seed(3)
carte = creer_carte(TAILLE, 10, 4)
rover = {"x": 0, "y": 0, "batterie": 100, "echantillons": 0}
afficher(carte, rover)

Points d’attention

La compréhension imbriquée crée une grille sans partager les lignes (un piège classique : [[VIDE] * 8] * 8 créerait 8 fois la même liste). On mélange les cases libres puis on prend les premières pour les rochers et les suivantes pour les échantillons : aucun risque de collision. random.seed(3) fixe la carte pendant le développement ; on l’enlèvera à la fin. Le rover n’est pas dans la carte : il est dessiné par-dessus à l’affichage. Ainsi la case sous lui reste intacte.

03 / Étape 2

Déplacer, avec les règles

import random
TAILLE = 8
VIDE, ROCHER, ECHANTILLON, BASE, ROVER = ".", "#", "*", "B", "R"
COUT_PAS = 3
DIRECTIONS = {"n": (0, -1), "s": (0, 1), "e": (1, 0), "o": (-1, 0)}

def deplacer(carte, rover, direction):
    """Tente un pas. Renvoie True si le rover a bougé."""
    dx, dy = DIRECTIONS[direction]
    nx, ny = rover["x"] + dx, rover["y"] + dy
    if not (0 <= nx < len(carte) and 0 <= ny < len(carte)):
        print("Bord de la zone : impossible.")
        return False
    if carte[ny][nx] == ROCHER:
        print("Un rocher bloque le passage.")
        return False
    rover["x"], rover["y"] = nx, ny
    rover["batterie"] -= COUT_PAS
    if carte[ny][nx] == ECHANTILLON:
        carte[ny][nx] = VIDE
        rover["echantillons"] += 1
        print("Échantillon collecté !")
    return True

# Tests
carte = [[VIDE] * 3 for _ in range(3)]
carte[0][1] = ROCHER
carte[1][0] = ECHANTILLON
rover = {"x": 0, "y": 0, "batterie": 100, "echantillons": 0}
assert deplacer(carte, rover, "e") is False and rover["x"] == 0      # rocher
assert deplacer(carte, rover, "n") is False                          # bord
assert deplacer(carte, rover, "s") is True and rover["echantillons"] == 1 and rover["batterie"] == 97
assert carte[1][0] == VIDE                                            # échantillon retiré
print("deplacer : OK")

Pourquoi un dictionnaire de directions ?

DIRECTIONS["n"] donne directement le vecteur de déplacement : pas de cascade de if. Ajouter les diagonales serait une ligne. Le y diminue vers le nord parce que la ligne 0 est en haut de l’affichage. On teste sur une carte minuscule construite à la main : c’est plus fiable qu’une carte aléatoire.

03 / Étape 3

Scanner et décider de la fin

VIDE, ROCHER, ECHANTILLON, BASE = ".", "#", "*", "B"
DIRECTIONS = {"n": (0, -1), "s": (0, 1), "e": (1, 0), "o": (-1, 0)}
NOMS = {"n": "nord", "s": "sud", "e": "est", "o": "ouest"}
COUT_SCAN = 1

def scanner(carte, rover):
    rover["batterie"] -= COUT_SCAN
    for d, (dx, dy) in DIRECTIONS.items():
        x, y = rover["x"] + dx, rover["y"] + dy
        if 0 <= x < len(carte) and 0 <= y < len(carte):
            contenu = {VIDE: "libre", ROCHER: "rocher", ECHANTILLON: "ÉCHANTILLON", BASE: "base"}[carte[y][x]]
        else:
            contenu = "hors zone"
        print(f"  {NOMS[d]:6}: {contenu}")

def echantillons_restants(carte):
    return sum(ligne.count(ECHANTILLON) for ligne in carte)

def partie_terminee(carte, rover):
    a_la_base = (rover["x"], rover["y"]) == (0, 0)
    if a_la_base and echantillons_restants(carte) == 0:
        return "victoire"
    if rover["batterie"] <= 0 and not a_la_base:
        return "defaite"
    return None

# Tests
carte = [[VIDE] * 2 for _ in range(2)]
carte[0][0] = BASE
assert partie_terminee(carte, {"x": 0, "y": 0, "batterie": 50}) == "victoire"
carte[1][1] = ECHANTILLON
assert partie_terminee(carte, {"x": 0, "y": 0, "batterie": 50}) is None
assert partie_terminee(carte, {"x": 1, "y": 0, "batterie": 0}) == "defaite"
assert partie_terminee(carte, {"x": 0, "y": 0, "batterie": 0}) is None   # à la base, batterie vide : pas perdu
print("partie_terminee : OK")
scanner(carte, {"x": 0, "y": 0, "batterie": 10})

Un cas limite à discuter

Batterie à 0, à la base, mais il reste des échantillons : ni victoire ni défaite selon notre fonction… mais le rover ne peut plus bouger. Le jeu serait bloqué. C’est le cahier des charges qui est incomplet, et c’est en écrivant les tests qu’on s’en aperçoit. Décision : à la base, la batterie se recharge à 100 (on l’ajoutera dans la boucle). Notez la décision dans un commentaire : les futurs lecteurs vous remercieront.

03 / Étape 4

Assembler : le jeu complet

import random

TAILLE, NB_ROCHERS, NB_ECHANTILLONS = 8, 10, 4
VIDE, ROCHER, ECHANTILLON, BASE, ROVER = ".", "#", "*", "B", "R"
COUT_PAS, COUT_SCAN = 3, 1
DIRECTIONS = {"n": (0, -1), "s": (0, 1), "e": (1, 0), "o": (-1, 0)}
NOMS = {"n": "nord", "s": "sud", "e": "est", "o": "ouest"}

def deplacer(carte, rover, direction):
    dx, dy = DIRECTIONS[direction]
    nx, ny = rover["x"] + dx, rover["y"] + dy
    if not (0 <= nx < len(carte) and 0 <= ny < len(carte)):
        print("Bord de la zone : impossible.")
        return False
    if carte[ny][nx] == ROCHER:
        print("Un rocher bloque le passage.")
        return False
    rover["x"], rover["y"] = nx, ny
    rover["batterie"] -= COUT_PAS
    if carte[ny][nx] == ECHANTILLON:
        carte[ny][nx] = VIDE
        rover["echantillons"] += 1
        print("Échantillon collecté !")
    if carte[ny][nx] == BASE:
        rover["batterie"] = 100          # décision : la base recharge
        print("Recharge à la base.")
    return True

def echantillons_restants(carte):
    return sum(ligne.count(ECHANTILLON) for ligne in carte)

def lire_commande():
    while True:
        c = input("Commande (n/s/e/o, scan, q) ? ").strip().lower()
        if c in DIRECTIONS or c in ("scan", "q"):
            return c
        print("Commande inconnue.")

def jouer():
    carte = creer_carte(TAILLE, NB_ROCHERS, NB_ECHANTILLONS)
    rover = {"x": 0, "y": 0, "batterie": 100, "echantillons": 0}
    tours = 0
    while True:
        afficher(carte, rover)
        fin = partie_terminee(carte, rover)
        if fin == "victoire":
            print(f"MISSION RÉUSSIE en {tours} tours !")
            return
        if fin == "defaite":
            print("Batterie vide loin de la base. Mission échouée.")
            return
        c = lire_commande()
        if c == "q":
            print("Mission abandonnée.")
            return
        if c == "scan":
            scanner(carte, rover)
        else:
            deplacer(carte, rover, c)
        tours += 1

jouer()

Jouer, puis relire

Une centaine de lignes, huit fonctions, une seule boucle. Relisez jouer() : elle se lit comme le cahier des charges. C’est le signe d’un bon découpage. Tout ce qui est « intelligent » est dans des fonctions testables ; la boucle ne fait qu’enchaîner. Sur votre PC, mettez ce code dans mission_mars.py et lancez-le dans un terminal : le jeu sera bien plus agréable qu’avec les fenêtres de saisie de cette page.

04 / Étendre

Extensions ★ — à faire dans l’ordre

Brouillard : n’afficher que les cases déjà visitées ou scannées (un ensemble set de tuples vues ; les autres cases s’affichent ?).
Coût variable : certaines cases sont du sable (~) et coûtent 5 % au lieu de 3.
Journal : enregistrer chaque commande et l’état dans mission.csv (séance 07). À la fin, afficher un résumé : distance parcourue, échantillons, batterie finale.
Sauvegarde : commande save qui écrit la carte et le rover en JSON, et reprise au démarrage si le fichier existe.

Indices

1 : vues = {(0, 0)} ; ajouter la position après chaque déplacement et les 4 voisines après un scan ; dans afficher, c if (x, y) in vues else "?". 2 : ajoutez un dictionnaire COUT = {VIDE: 3, "~": 5, ECHANTILLON: 3, BASE: 3} et remplacez COUT_PAS. 3 : ouvrir le fichier en mode "a" à chaque tour, ou garder une liste et tout écrire à la fin. 4 : json.dump({"carte": carte, "rover": rover}, f) — les listes de listes se sauvegardent telles quelles.

04 / Étendre

Extensions ★★ — de l’intelligence

Pilote automatique : commande auto qui choisit la direction menant à l’échantillon le plus proche (distance de Manhattan |dx| + |dy|), en évitant les rochers. Le rover peut se retrouver coincé : détectez-le.
Retour sûr : avant chaque pas, vérifier que la batterie suffit pour rentrer à la base (distance de Manhattan × 3). Si non, refuser et proposer le retour.
Tempête : chaque tour, 10 % de chance qu’une tempête coûte 5 % de batterie. Afficher un avertissement.

Indices

1 : min(echantillons, key=lambda p: abs(p[0]-rx) + abs(p[1]-ry)) pour la cible ; puis essayer d’abord la direction qui réduit le plus l’écart, sinon l’autre axe. Un compteur d’échecs consécutifs signale le blocage. 2 : la distance de Manhattan est une borne inférieure du vrai chemin (à cause des rochers) : la garantie n’est donc pas absolue. Comment faire mieux ? Séance 18 (plus court chemin dans un graphe).

04 / Étendre

Extension ★★★ — Esprit prépa : le rover autonome optimal

Écrire une fonction plan(carte, depart, arrivee) qui renvoie la liste des directions du plus court chemin en évitant les rochers (ou None s’il n’existe pas). Puis un pilote qui collecte tous les échantillons et rentre, en minimisant le nombre de pas total. Comparer votre solution à la force brute pour 4 échantillons (24 ordres possibles).

Questions : le plus court chemin entre deux points se calcule par un parcours en largeur (BFS). L’ordre optimal de visite des échantillons est le problème du voyageur de commerce : avec 4 échantillons, on peut tout essayer ; avec 20, il y a 2,4 × 10¹⁸ ordres. Que faire alors ?

Direction

BFS : une file (deque) de positions à explorer, un dictionnaire precedent pour reconstruire le chemin en remontant depuis l’arrivée. Séance 18 le détaille ; essayez d’abord seul, c’est l’un des algorithmes les plus importants qui existent. Pour le voyageur de commerce, une heuristique « le plus proche d’abord » donne souvent un résultat à 25 % de l’optimal ; les vrais robots utilisent des variantes plus fines. Ce problème est NP-difficile : aucun algorithme efficace connu, et prouver qu’il n’en existe pas vaudrait un million de dollars (problème P = NP).

05 / Bilan

Grille d’auto-évaluation

Critère	Vous
Le jeu complet fonctionne sur mon PC, dans un terminal	☐
Chaque fonction a un nom clair et fait une seule chose	☐
Les fonctions de logique (`deplacer`, `partie_terminee`) ont des tests qui passent	☐
Une saisie invalide ne fait jamais planter le programme	☐
Les constantes sont en haut du fichier, en majuscules	☐
J’ai réalisé au moins deux extensions ★	☐
Un camarade a pu lire mon code et l’expliquer	☐
J’ai tenté une extension ★★	☐

Pour présenter votre projet

Un projet se présente en trois minutes : ce qu’il fait (démo), comment il est construit (les fonctions, au tableau), ce qui a été difficile et ce que vous feriez ensuite. C’est exactement le format des oraux de projet en prépa et aux concours. Entraînez-vous.

Pour continuer

Fin de la partie A

Vous programmez. Vraiment. La partie B vous apprend maintenant à programmer bien : vite, juste, et en sachant pourquoi.

Ce qui vous attend

Séance 11 — Compter les opérations : pourquoi certains programmes sont mille fois plus rapides que d’autres.
Séance 12 — La récursivité : une fonction qui s’appelle elle-même.
Séances 13 à 15 — Les maths du roboticien : binaire, vecteurs, simulation.
Séance 16 — Les objets : modéliser un robot comme une chose qui a un état et des capacités.

← Séance 09 Sommaire Séance 11 : Complexité, recherche et tris →