Rémy le Djinakh - Chasse aux Fromages

Rémy le Djinakh - Chasse aux Fromages est un jeu éducatif développé en Python avec PyGame qui illustre les concepts de Programmation Dynamique. Le jeu met en scène Rémy, un personnage qui ne peut se déplacer que vers la droite (→) ou vers le bas (↓), et dont l'objectif est de collecter un maximum de fromages dans une grille.

🎓 Objectifs Pédagogiques Comprendre les principes de la programmation dynamique

Résoudre un problème d'optimisation avec contraintes de déplacement

Analyser la complexité algorithmique (Θ(n²))

Visualiser les chemins optimaux vs les chemins parcourus

🎮 Concept du Jeu Le joueur contrôle Rémy qui commence en haut à gauche d'une grille et doit atteindre le coin inférieur droit en collectant un maximum de fromages. La contrainte principale : Rémy ne peut se déplacer que vers la droite ou vers le bas.

📐 Formule Récursive (Projet) C(i, j) = max(C(i-1, j), C(i, j-1)) + ExisteFromage(i, j) Conditions initiales :

C(1,1) = 0 (pas de fromage au départ)

ExisteFromage(i,j) retourne 1 si fromage présent, 0 sinon

sinon

🚫 Contraintes Imposées Déplacements limités : Uniquement → et ↓

Début/Fin fixes : Départ en (1,1), arrivée en (L,C)

Pas de fromage au départ : Case (1,1) toujours vide

Fromages consommables : Disparaissent après collection

Méthodes Principales Méthode Description Complexité ExisteFromage(i, j) Vérifie présence fromage à (i,j) O(1) compute_optimal_score_dp() Calcule score max par DP Θ(L×C) compute_optimal_path_dp() Reconstruit chemin optimal Θ(L+C) generate_strategic_grid() Génère grille avec pièges Θ(L×C) get_complexity_analysis() Retourne analyse complexité O(1)

🧠 Algorithme DP Détaillé def compute_optimal_score_dp(self) -> int: """ Calcule le nombre maximum de fromages via Programmation Dynamique. Formule: C(i,j) = max(C(i-1,j), C(i,j-1)) + ExisteFromage(i,j) """ L, C = self.rows, self.cols dp = [[0 for _ in range(C + 1)] for _ in range(L + 1)]

for i in range(1, L + 1):
    for j in range(1, C + 1):
        if i == 1 and j == 1:
            dp[i][j] = 0  # Cas de base
        else:
            top = dp[i-1][j] if i > 1 else 0
            left = dp[i][j-1] if j > 1 else 0
            dp[i][j] = max(top, left) + self.ExisteFromage(i, j)

self.dp_table = dp
self.max_score = dp[L][C]
return self.max_score

🛣️ Reconstruction du Chemin def compute_optimal_path_dp(self) -> List[Tuple[int, int]]: """ Reconstruit le chemin optimal à partir de la table DP. Utilise le backtracking depuis (L,C) vers (1,1). """ if not self.dp_table: self.compute_optimal_score_dp()

L, C = self.rows, self.cols
path = []
i, j = L, C

while i > 0 and j > 0:
    path.append((i, j))
    if i == 1 and j == 1:
        break
    # Choix direction précédente
    if i == 1:
        j -= 1  # Venue de gauche
    elif j == 1:
        i -= 1  # Venue du haut
    else:
        if self.dp_table[i-1][j] >= self.dp_table[i][j-1]:
            i -= 1  # Meilleur venait du haut
        else:
            j -= 1  # Meilleur venait de gauche

path.reverse()
self.optimal_path = path
return path

Structure des Fichiers

remy_game_v2/ │ ├── 📄 main.py # Point d'entrée + écran de démarrage ├── ⚙️ game_engine.py # Moteur principal du jeu ├── 🧮 grid_logic.py # Logique métier + algorithme DP ├── 🎨 ui_components.py # Composants graphiques modernes ├── ⚙️ config.py # Configuration + constantes └── 📖 README.md # Documentation (ce fichier)