TD6 : Lemmings

L’objectif de ce TD est d’étudier la gestion des IA des personnages d’un jeu de tactique/gestion. Nous allons présenter la mise en place d’une machine à états permetant à un personnage d’effectuer successivement différentes actions afin de suivre un scénario.

Introduction

Présentation

Phénomène vidéoludique de l’année 1991, Lemmings est plébiscité pour son concept singulier, à la fois simple et ingénieux mélangeant jeu de gestion et jeu de casse-tête. Le joueur doit guider vers la sortie des dizaines de lemmings ceci dans des niveaux truffés de dangers mortels ceci afin d’en sauver un maximum ! Ce ne sera pas facile, et beaucoup n’y arriveront pas : chute, explosion, lave… La vie d’un lemmming est particulièrement aléatoire.

Heureusement des aptitudes sont disponibles, elles sont représentées par des icônes au bas de la fenêtre de jeu. Le joueur peut cliquer sur un icône et ensuite attribuer l’aptitude en question à un lemming en cliquant dessus. Voici les différents aptitudes présentes dans le jeu :

Climber – capable d’escalader les parois verticales

Floater – chute avec un parasol lui évitant de s’écraser au sol !

Blocker – s’immobilise et empêche les autres lemmings de passer

Bomber – explose après un compte à rebours de cinq secondes en détruisant une partie des murs

Builder – échafaude un escalier de 12 marches qui sera emprunté par ses collègues

Basher – creuse à l’horizontale

Digger – creuse sous ses pieds

Miner – creuse en diagonale

Le jeu comprend 30 niveaux de plus en plus complexes. A chaque niveau, le joueur dispose de certaines aptitudes en quantité limitée afin de contourner les différents pièges. Ainsi, le jeu se tranforme en énigme où il faut trouver quelle aptitude utiliser, sur quel lemming et à quel moment/endroit. Pour réussir un niveau, il faudra sauver un minimum de lemmings en utilisant les aptitudes disponibles.

Pour mieux visualiser le gameplay voici un extrait des niveaux introductifs présentant les différentes aptitudes :

Digger

Blocker

Voici les vidéos pour les autres aptitudes :

Floater

Miner and Climber

Basher

Bomber

Builder

Test

Vous pouvez tester le jeu en réel sur cette page

Choisissez : 4 - VGA

Choisissez : 2 - High Performance PC

Choisissez : 1 player

ESC : pour récupérer le curseur de la souris

Les lemmings

Parenthèse animalière, le nom du jeu et le look des personnages sont inspirés des véritables lemmings minuscules rongeurs que l’on trouve dans les régions arctiques. Mi-souris, mi-marmottes, ils ont la force de survivre dans un milieu où le sol est en permanence gelé. Ils passionnent les habitants et les chercheurs car leur population suit un cycle de 4 ans, alternant une phase de surpopulation où l’on peut voir des groupes de lemmings traverser des lacs gelés à la course avec une phase de quasi-instinction de l’espèce. Ce phénomène mystérieux reste inexpliqué mais il continue à animer de nombreuses légendes. Si vous voulez en savoir plus sur les lemmings, rien de mieux que de consulter leur page sur l’office de la faune du Canada.

Mise en place

Téléchargez le projet Lemmings.zip et dézippez-le.

Au lancement du programme, vous obtenez ceci :

Le projet est incomplet. Quelques remarques :

Le décor semble complet

Les lemmings apparaissent et chutent dans le vide

Aucune gestion de collision ne semble active

Une fois les 10 lemmings disparus, plus rien ne se passe

Notions clefs

Gérer une animation

Nos lemmings effectuent une multitude d’actions. Ils creusent, ils marchent, ils grimpent… Pour produire un rendu graphique sympathique, les graphistes dessinent une animation sous forme d’une suite de sprites. Ci-dessous, nous vous présentons la série associée à l’action « creuser le sol », elle se lit de gauche à droite.

Il y a plusieurs actions et chacune comporte plusieurs sprites. Ainsi pour les lemmings, on dispose d’environ 250 sprites d’animation. Plutôt que de stocker chaque sprite dans un fichier, on préfère stocker l’ensemble dans une grande image appelée « sprite sheet », comme par exemple pour le personnage de Sonic ci-dessous :

Tester une animation dans Piskel

Vous pouvez visualiser et éventuellement corriger cette animation grâce à l’éditeur en ligne Piskel.

Téléchargez l’animation creuse.png

Dans Piskel, cliquez sur l’icône Import sur la droite :

Choisissez : Import From Picture

Dans la boite de dialogue, choisissez l’option Sprite Sheet et entrez les valeurs 30x28 pour indiquer la taille de chaque sprite. Remarquez que le logiciel découpe alors chaque sprite par un rectangle orange :

Nous revenons à l’interface principale, vous remarquez les différentes images de l’animation numérotées dans la colonne de gauche. Au centre se trouve l’éditeur de l’image en cours, on peut modifier les pixels ou la recaler s’il y a un problème de centrage.

Dans la zone de test d’affichage en haut à droite, nous voyons l’animation qui se déroule :

Nous vous laissons regarder les tutoriaux en ligne pour prendre en main Piskel si vous êtes intéressés.

Utiliser une Sprite Sheet

Nous vous fournissons une planche simplifiée de sprites pour le jeu Lemmings. Chaque sprite est stocké dans un carré 30x32 et chaque animation occupe une ligne. Lorsqu’il n’y a plus de sprites à charger, une case rouge est présente :

Voici la fonction qui charge la ligne d’animation numéro id et qui retourne une liste de sprites :

Pour gérer une animation, nous utilisons la ligne suivante :

compteur = int( pygame.time.get_ticks() / 100 )

Ainsi, toutes les 0.1 secondes, la valeur de compteur augmente de 1. Cette valeur nous indique le sprite à afficher parmi les sprites de l’animation. Ainsi, nous allons afficher le sprite donné par :

ListeSprites[compteur%len(creuse)]

En utilisant cette ligne, lorsque la variable compteur progresse de 3 à 10, avec len(creuse)=4 par exemple, l’indice va varier ainsi : 3, 0, 1, 2, 3, 0, 1, 2, 3… De cette façon, une animation avec 15 sprites dure 1.5 secondes.

Gérer des personnages

Fini la tranquillité de l’aquarium où il n’y avait que quelques poissons à gérer, avec le jeu Lemmings, on passe à la vitesse supérieure. En effet, on doit pouvoir gérer une centaine d’individus. On va donc utiliser une liste Python dans laquelle nous allons stocker nos lemmings. Comment représenter un personnage ? Nous pouvons utiliser un concept très plébiscité dans le monde du jeu vidéo : les dictionnaires. Ils fournissent les mêmes facilités que l’objet avec l’aspect dynamique en plus. Ainsi, un lemming est créé de la manière suivante :

lemming = { }
lemming['x'] = 250    # position
lemming['y'] = 100
lemming['vx'] = -1    # vitesse
lemming['vy'] = 0
lemming['etat'] = ETAT.Marche  # action courante

On stocke ensuite ce personnage dans les listes des lemmings au moyen de la commande « append » :

lemmingsLIST  = []
lemmingsLIST.append(lemming)

Ainsi dans la fonction d’affichage de notre jeu, nous allons trouver :

AfficheEcranJeu :
        Afficher le fond
        Pour chaque lemming dans la liste des lemmings
                lemming courant => fais ton affichage
        Afficher le score
        ...

Python nous fournit une syntaxe tout à fait simple pour parcourir une liste :

for onelemming in lemmingsLIST:
        xx = onelemming['x']
        yy = onelemming['y']
        screen.blit(…,(xx,yy))

A ce niveau, il faut bien saisir que onelemming est un lemming de la liste. Lorsque l’on rentre dans la boucle, onelemming correspond au premier lemming de la liste. Ensuite, une fois l’opération blit effectuée, onelemming est mis à jour par l’instruction for, il correspond alors au 2ème lemming dans la liste et ainsi de suite jusqu’au dernier. La variable onelemming va désigner à tour de rôle chaque lemming de la liste.

Gestion des transitions et des états

Un lemming a une intelligence et doit se comporter différemment en fonction de ce qu’il se passe dans le jeu. Pour gérer cela, nous utilisons une machine à états, ce qui rend la gestion du jeu un peu plus complexe. Par exemple, lorsqu’il marche et qu’il se retrouve au-dessus du vide, le lemming passe en mode « chute ». Lorsqu’il chute, on incrémente un compteur pour estimer la hauteur de sa chute et lorsqu’il touche le sol deux options sont possibles : soit le compteur est trop important et il s’écrase au sol et passe en état « dead » sinon il survit et repasse à l’état « marche ».

Ainsi, dans la fonction gérant la logique du jeu, pour un lemming donné, nous devons effectuer deux traitements pour gérer sa machine à états :

Déterminez s’il y a une transition : analysez l’état courant et l’environnement

Appliquez l’action associée à l’état courant

Prenons un exemple avec trois états et leurs transitions : Dead, Chute, Marche et une variable fallcount indiquant le nombre de pixels parcourus depuis le début de la chute du lemming. En représentant les états par des ronds et les transitions par des flèches, nous obtenons le schéma des transitions suivant :

Voici les actions effectuées dans chaque état :

Dead : pas grand-chose à faire ! Éventuellement un compteur pour faire disparaître le sprite 10 secondes plus tard.

Chute : le lemming tombe y = y - 1 et on incémrente la variable de comptage : fallcount = fallcount + 1

Marche : le lemming avance : x = x + vx

Afin de gérer les états, chaque lemming embarque son paramètre [“etat”]. Cependant, il est dangereux de représenter les états par des chiffres, en effet, pour des raisons de lisibilité, vous allez rapidement vous mélanger. Un programmeur averti va préférer utiliser des noms de variable :

# Liste des états
EtatMarche = 1
EtatChute  = 2
EtatStop   = 3
EtatDead   = 4

Pour faciliter le Débogage, on pourra encore améliorer la lisibilité en écrivant :

# Liste des états
EtatMarche = 'EtatMarche'
EtatChute  = 'EtatChute'
EtatStop   = 'EtatStop'
EtatDead   = 'EtatDead'

Ainsi, au lieu d’écrire lemming[“Etat”] = 200 ce qui est peu lisible, on écrira : lemming[“etat”] = EtatChute ce qui est bien plus clair. Pour gérer les transitions comme pour gérer les actions, nous utilisons le mot clef match :

match lemming.Etat:
   case EtatMarche:
      actionMarche(lemming)
   case EtatChute:
      actionChute(lemming)
   case EtatStop:
      actionStop(lemming)

Vous pouvez encore alléger le code en utilisant une version plus élégante basée sur les dictionnaires :

def actionMarche(lemming):
   ...
def actionChute(lemming):
   ...

ActionToPerform = { EtatMarche:actionMarche, EtatChute:actionChute }

# et plus tard dans le code, on trouvera :
lemming = { 'Etat':EtatMarche }
...
ActionToPerform[lemming['Etat']](lemming)

Note

Évidemment, lors de la gestion de l’affichage, l’état courant va nous permettre de choisir quelle animation afficher.

Gestion des scénarios

On entend par scénario un regroupement d’états dans notre diagramme. Ainsi, pour le scénario Bomber, on construit un enchaînement d’états/actions :

Etat Attendre

Etat Explose

Etat Dead

Il n’est pas évident d’identifier quels sont les états d’un scénario. Mais dans ce jeu, c’est assez simple, car ils sont chacun associés à une animation. Ainsi dans l’état Attendre, le lemming reste figé en tapant du pied, ensuite dans l’état Explose, une animation avec une petite onde de choc se produit et pour finir dans l’état Dead, il reste au sol éventuellement.

Les scénarios sont très communs dans le monde des jeux de gestion/simulation, par exemple, on peut envoyer un bucheron ramasser du bois :

Se déplacer jusqu’à l’arbre le plus proche

Couper l’arbre

Retourner au chateau

Déposer le bois

Transition : recommencer le cycle s’il reste des arbres dans la forêt

Ajouter des états

En ajoutant de nouveaux scénarios (creuser, bloquer…), nous allons créer de nouveaux états et de nouvelles transitions. Afin de faciliter la conception du jeu, nous faisons en sorte que chaque scénario ne puisse être activé que par une transition depuis l’état Marche. Nous obtenons donc un schéma en étoile comme celui-ci :

Note

Ce choix peut paraître étrange ou maladroit. En effet, pour l’état Creuser par exemple, une fois terminé, le lemming devrait passer en état Chute fort probablement. Mais avec notre convention, il va d’abord passer en état Marche et juste après en état Chute. Cette petite erreur va durer 1/30eme de seconde et personne ne s’en apercevra et notre astuce nous fera économiser beaucoup de lignes de code.

Sans cette astuce, la gestion des transitions deviendrait complexe comme dans le diagramme ci-dessous :

To-do List

Attention, vous devez respecter les consignes :

Séparation de la logique et de l’affichage : il serait maladroit d’effectuer un affichage dans la partie gérant la logique

Gestion des transitions et des actions

Implémentez les fonctionnalités suivantes :

Démarrage du jeu :

Créez les états Dead & Chute

Faîtes en sorte que 15 lemmings soit créés et que leur état par défaut soit l’état Chute

Implémentez le compteur de chute

Testez la valeur du pixel sous le sprite du lemming, s’il n’est pas noir, activez la transition vers l’état Marche ou l’état Dead

Implémentez l’état marche

Implémentez l’état Marche

Gérez l’affichage de l’état Marche

Par défaut, faites les marcher vers la gauche

Les sprites utilisés pour la marche sont synchronisés : chaque lemming utilise le même ce qui produit un effet visuel désagréable. Ajoutez un paramètre « Decal » à chaque lemming et initialisez-le aléatoirement. Servez-vous de ce nombre pour désynchroniser l’animation de marche des lemmings.

La chute mortelle

Les lemmings doivent se déplacer jusqu’à la gauche, tomber de la falaise et s’écraser sur le sol

Gérez l’affichage de l’état Dead (dernière ligne en bas sur la planche de sprites)

L’état Dead est terminal, il n’y a pas de transition pour en sortir !

Gérez l’animation de l’état Dead. Attention, une fois l’animation jouée, elle ne recommence pas !

Nous allons programmer les premières modifications de comportement. Le joueur clique sur l’icône d’une aptitude dans l’interface : creuser, stopper… Ensuite, lorsqu’il clique sur un lemming, l’état de ce dernier est modifié pour correspondre à la tâche demandée.

Détectez le clic sur les icônes en bas de l’écran

Allumez la petite lampe au-dessus des icônes des aptitudes pour désigner l’aptitude active

Choisissez une couleur quelconque

Une seule lampe est allumée à la fois

Implémentez l’aptitude Blocker

C’est un état terminal, impossible d’en sortir

Si l’aptitude Blocker est activée et que le joueur clique sur un lemming, passez son état à STOP

Pour passer à l’état STOP, il faut que le lemming soit précédemment en état MARCHE

Interaction

Si en marchant un lemming rencontre un lemming en état STOP, il doit changer de direction

Programmez la détection de collision à gauche et à droite des lemmings

Un lemming doit aussi changer de direction lorsqu’il rencontre un mur

Pour détecter la collision avec un lemming, on peut calculer une distance comme dans le projet Labyrinthe

Pour détecter la collision avec un mur, on peut lire dans le sprite du décor la valeur du pixel se trouvant devant le lemming

Pour créer l’animation de marche vers la droite, utilisez la symétrie sur un sprite comme dans le projet Aquarium

Vous pouvez aussi appliquer un décalage sur le sprite symétrique pour que les animations marche gauche/marche droite soient centrées

Le scénario Creuser

Si l’icône Creuser est actif et que le joueur clique sur un lemming, passez son état à Creuser

Pour passer à l’état Creuser, le lemming doit être dans l’état Marche

Gérez l’animation de l’état Creuser

Dans l’état Creuser, le lemming fait disparaître 20 pixels du décor sous lui, ceci toutes les 2 secondes

Pour effacer une partie du décor, mettez les pixels à la couleur noire. A ce moment-là, vous pouvez aussi descendre le lemming d’un pixel

Transition : si les 20 pixels sous le lemming sont tous noirs => retour à l’état Marche, qui déclenchera probablement une transition vers l’état Chute

Relativement à l’histoire, les lemmings tombant de moins haut, ils doivent arriver vivant sur la ligne du bas, paramétrer la borne de fallcount en fonction

La sortie

Positionnez le sprite de la porte de sortie en bas à droite

Dessinez le sprite de la porte avant les sprites des lemmings afin qu’elle apparaisse en arrière-plan

Détectez lorsqu’un lemming arrive au milieu de la porte et retirez-le de la liste courante

Fin de partie

Lorsque tous les lemmings sont partis ou morts, affichez « WIN » en gros au centre de l’écran s’il y a eu plus de 10 survivants