Contexte

La société MPOG lance un appel d'offre auprès de développeurs informatiques : elle cherche un sous traitant pour réaliser un moteur de jeux basé sur des automates.

La société MPOG a établi un cahier des charges qui laisse une marge de liberté. Avant de répondre à l'appel d'offre vous passez 5 jours à définir le projet et concevoir un prototype afin de vous assurez que vos idées sont réalisables. À l'issue de cette permière semaine vous faîtes une proposition (1ère soutenance). La société MPOG passe alors un contrat avec vous sur la réalisation finale qui sera livrée 7 jours plus tard (2nde soutenance).

Le projet : un moteur de jeux basé sur les automates

• Description du projet sur GitHub
• Le Parser d'automates sur GitHub

Les projets des années précédentes

Projet 2017 : Le collectionneur

• Principe du jeu
  • Un personnage doit collecter le plus d'opérateurs dispersés sur le plateau de jeu. Avec ces opérateurs il construit des robots qui seront chargés d'explorer le territoire et de récupérer encore plus d'opérateurs, lui permettant d'améliorer ses robots.
  • Le comportement des robots est régi par une expression construite avec les opérateurs récupérés.
  • Le joueur déplace son personnage sur le plateau et modifie le comportements de ses robots à l'aide des opérateurs à sa disposition.

• Quelques exemples d'opérateurs
  • les opérateurs de bases sont disponibles en nombre illimités la séquence (;) sépare deux actions, le choix non-déterministe (|) laisse le hasard choisir entre deux actions, le choix équitable (A1 || A2) effectue l'action A1 et la fois suivante l'action A2, les délimiteurs {...} permettent de grouper des actions.
  • Par défaut le comportement principal se répète indéfiniment. Autrement dit, le joueur crée un comporement C qui doit être vu comme {C}^*
  • choix préférentiel {A > B} indique que si les actions A et B sont exécutables, il faut choisir l'action A.
  • split (S) Lorsqu'un robot arrive à un croisement, il se duplique : un robot prend une direction, l'autre prend la direction opposée.
  • Hit (H) Lorsqu'un robot rencontre un robot ennemi, l'action H donne un coup.
  • Escape (E) indique au robot de fuir devant un ennemi. Le simulateur calcule le chemin le plus approprié avec une vision à k pas où k correspond au nombre de points de vision accumulés.
  • Kamikaze (K) Lorsqu'un robot rencontre un robot ennemi, il se sacrifie, se fait exploser pour détruire le robot ennemi, les opérateurs amassées par les robots sont laissés sur place.
  • Protect (P) Lorsqu'un robot est attaqué la protection P lui permet de résister à une attaque. Ainsi, P;P résiste à une attaque H;H.
  • Follow (F) l'action F consiste à se diriger vers le robot le plus proche ; la portée de la vision est déterminée par les points de vision.
  • Eepeat (A:n) itère n fois l'action A en un seul tour. Ainsi, H:2 donne 2 coups, mais prend 1 seul tour et F:3 permet d'effectuer trois déplacements en un coup. Le joueur choisit le n entre 1 et ... (une valeur raisonnable).
  • Rapporte (J) Le robot revient vers le joueur par le chemin le plus court ; le choix du chemin est conditionné par les points de vision.
  • eXplore (X) Le robot se dirige vers une case qu'il n'a pas encore explorée.
  • Closest (C) Le robot se dirige vers l'opérateur le plus proche.
  • Best (B) Le robot se dirige vers l'opérateur le plus recherché par le joueur en fonction d'une liste de préférence fourni par le joueur.
  • Where (W) Le robot choisit sa direction en fonction un point d'intérêt positionné par le joueur.
  • Others (O) Le robot se dirige vers un membre de l'autre équipe (joueur ou robot)
  • Star (*) Le robot répète indéfiniment le comportement entre délimiteur {...}*

• Des exemples de comportements

  1. { X }* est le comportement par défaut: les robots se déplacent sur les cases non explorées.
  2. { P:3 > (J || O) }* est une tentative de robot protecteur : il privilégie la protection, alternativement il se dirige vers le joueur (pour constituer une barrière) et va au dévant des ennemis.
  3. { S( {O ; H:2 }* | {P > W:3 > F > K}) }* Le robot se divise en deux robots. Chaque copie effectue
     1. soit indéfiniment {chercher un ennemi et le frapper},
     2. soit se protéger de préférence à se déplacer 3 fois vers un point d'intérêt de préférence à suivre le robot le plus proche de préférence à jouer les kamikazes.
     Le choix entre 1 et 2 est fait au hasard.

Projet 2016 : Angry Automata (Combat de Codes)

• Rappel : Un automate à nombre d'états fini peut-être représenté par un tableau 2D d'entiers représentant les états A[état courant][symbole] = état suivant code la transition (état courant) --symbole--> (état suivant)
  • On peut facilement associer une action à une transition (état courant) --symbole : action --> (état suivant) en stockant des couples (action,état suivant) dans les cases du tableau.
  • On peut indiquer le statut d'un état (accepteur, initial, puit, autre, ...) en ajoutant une ligne au tableau A[état][STATUT] = ...
  • On peut associer une action à chaque état en ajoutant une ligne au tableau A[état][ACTION] = ...
• Le principe du jeu

  Chaque joueur définit le comportement des ses personnages sous forme d'automates. Le plateau de jeu est une grille qui contient les tableaux des automates de tous les joueurs. Le contenu des tableaux apparaît à l'écran sous la forme d'un décor : chaque état de l'automate est un entier auquel on associe un élément de décor, par exemple 0 = arbre, 1 = pierre, ...

  Chaque personnage a une position sur la grille et il est gouverné par un automate qui fait partie du décor.

  Les personnages se déplacent dans un décor qui représente leur comportement. Ils réagissent en fonction du décor (contenu de la case courante = symbole lu). Ils agissent sur le décor : déplacer une pierre, planter un arbre, ...

  Ce faisant il modifie les automates et agissent donc sur le comportement futur de personnages.

  Tous les personnages effectuent une transition en simultanée.

• Quelques suggestions de variantes de jeu
  1. Plateau de jeu : Il peut être délimité par des murs (ce qui nécessite de faire marche arrière) ou bien représenter un tore comme dans Pac Man.
  2. But du jeu (au choix): Supprimer tous les adversaires, les paralyser, avoir une superiorité numérique dans un délai imparti, atteindre une zone géographique, ...
  3. Disparition de personnage : Un personnage qui n'effectue aucune action pendant P tours est considéré comme paralysé et disparaît. Deux personnages adverses qui se trouvent à proximité se livrent combat : à l'issue du combat on met à jour leurs points de vivacité/paralysie. Un personnage peut combattre si son état courant a le statut «combat».
  4. Point de paralysie : Un personnage qui a 0 points de paralysie effecuent un action à chaque tour. S'il a N points de paralysie il effectue une action tous les N tours (si N>=P il disparaît).
  5. Qualité des personnages : Chaque personnage peut collecter des éléments du décor, les détruire ou les redéposer ailleurs. Chaque personnage a une capacité (limitée) de générer des éléments du décor (par exemple afin de pouvoir répliquer son automate ailleurs sur le décor)
  6. Les statuts des états : «repos» : on ne bouge pas pendant X tours, on est vulnérable, mais on gagne des points de vivacité. «combat» : on peut combattre «réplication» : on ne bouge pas pendant X tours, on est vulnérable, mais on génère un clone. «déplacement» : on se déplace deux fois plus vite «réparation» : rétablit l'élément initial du décor (afin de réparer un automate endommagé)
  7. Génération de personnage : Lorsqu'un personnage atteint un état portant le statut «réplication» il génère un clone qui apparaît à la position de l'état initial de l'automate par exemple. Chaque état de l'automate a un statut parmi les suivantes : combat, replication, ... L'idée étant que le statut réplication permet de créer d'autres automates mais rend le créateur vulnérable.
  8. Modification de l'automate des personnages : Le joueur à la possibilité de
     • déplacer un curseur sur l'écran pour modifier le décor (dans le but de réparer ou modifier un automate)
     • puis sélectionner une zone de l'écran pour qu'elle devienne l'automate associé à certains de ses personnages.
  9. Déplacement des personnages : Le joueur peut déplacer certains/tous personnages en les controllant au clavier durant un laps de temps (ensuite c'est le tour de l'autre joueur), ou bien indiquer une position sur l'écran que ses automates essaient de rejoindre, ou bien controller en permanence un leader que les autres suivent, ...
  10. Placement des tableau d'automates : On peut laisser le joueur choisir son placement sans le réveler à l'autre, ou bien faire apparaître explicitement les tableaux de chacun, ... Le reste du décor est généré aléatoirement.
  11. Pouvoirs spéciaux : Certains éléments du décor donnent des pouvoirs spéciaux que le joueur peut sélectionner et activer par une touche au clavier, à l'instar d'Angry Bird.

Projet 2015 : Extension de l'application LigthBot

• Principe du jeu

  LightBot est un jeu qui apprend à programmer aux enfants (en savoir plus). Le jeu consiste à résoudre des puzzles (allumer des cases sur un damier) par l'intermédiaire d'un robot (LightBot) que l'on doit programmer. LightBot possède déjà les notions de programmation suivantes: les instructions de bases, la séquence, les routines (procédures sans arguments), les conditionnelles, les goto et les break pour créer et sortir des boucles, ainsi que les pointeurs (téléportations). L'objectif du projet RICM est de réaliser des extensions à LightBot en gardant l'esprit du jeu, c'est à dire :

  « Apprendre les concepts de la programmation sans en avoir conscience, en jouant. Le but du jeu doit rester simple: LigthBot doit allumer toutes les cases bleues. Le jeu ne doit pas d'explications compliquées, du genre, il faut trier le tableau. L'introduction d'un nouveau concept de programmation doit être au minimum accompagnée d'une illustration du concept, d'une application évidente, d'un casse-tête facile et d'un casse-tête plus difficile. »

• Suggestions d'extensions
  • Deux LightBots avec des capacités différentes :
    • L'un (B) assez basique mais capable d'allumer les cases bleues (commande «on/off»). L'autre (S) est plus Smart c'est à dire possédant plus de commandes mais pas la commande «on/off». Il est chargé préparer le travail pour le LightBot basique. Remarque: Ceci nous oblige à distinguer -- contrairement au jeu original -- l'action switch on/off, de l'action qui teste la couleur du sol et de celle qui téléporte.
    • Nombre de procédures illimité pour S
    • Conditionnelle + marquage au sol: LigthBot peut prendre la couleur du sol (pick up) et effectuer les actions qui sont de cette couleur. Il peut revenir à sa couleur initiale au moyen d'une commande (wash up). Il peut peindre la case (paint) sur laquelle il se trouve d'une couleur de son choix pour pouvoir la tester plus tard.
    • Dépassement mémoire (segmentation fault): si LightBot (B) s'avance au delà des limites du damier il tombe (sauf si le joueur a activé le mode «tore»)
    • Opérations non autorisées: si LightBot (B) allume une case qui ne doit pas être activé, il s'életrocute.
    • Variables, affectations: d'autres LigthBot (chacun avec un couleur) peuvent mémoriser des valeurs. LightBot discute avec eux sous la forme de dialogue BD (blue? 17! 5 for blue! Ok,5!).
    • Opérations unaires, binaires
      • opérandes: LigthBot peut ramasser une ou deux données dans ses mains et effectuer une opération sur ces données.
      • opérations arithmétiques (+1, -1) (min, max, +, -) : les opérandes disparaissent et le résutlat est placé dans la main droite.
      • opérations booléennes (==, <=, <, >, >=) : LigthBot devient vert si le résultat vaut vrai et rouge sinon. Dans le cas des opérateurs de comparaison (par exemple <=) la valeur la plus petite passe dans la main droite et la plus grande dans la main gauche.
      • Applications: calculer la hauteur du saut par algorithme essai/erreur et l'inscrire au sol pour ne plus avoir à refaire des essais.
  • Tableaux 1D, 2D
    • indices de lignes et colonnes : ce sont des variables représentées par des LightBot placés sur le bord de la ligne (la colonne correspondante)
    • adressage direct d'une case T[i][j]: LightBot glisse vers la case correspondante plutôt que de s'y rendre pas à pas en sautant.
    • valeur d'une cellule: les cases du damier sont les cases du tableau, elle porte une valeur entière. Une case est un ascenceur qui monte à l'étage indiqué lorsque LightBot l'active (lift).
    • affectation d'une cellule: LigthBot peut prendre la valeur d'une case dans une main et la déposer sur une autre case
    • Application tableau 1D : tri d'un tableau, égalité de 2 tableaux triés, égalité de 2 tableaux non triés
    • Application tableau 2D : labyrinthe
  • Structures chaînées, pointeurs, backtraking, zoom/unzoom
    • un pointeur: c'est un fil pointant sur une case que Lightbot peut accrocher à une case, décrocher, prendre dans sa main et conserver pendant qu'il se déplace, qu'il peut suivre (téléportation)
    • Backtrack: LightBot peut déposer des bulles numérotées sur des cases afin de pouvoir s'y téléporter. La téléportation le ramène à la dernìere bulle déposée, dans la même orientation que lors du dépôt de la bulle.
    • Graphe: on se limite au cas des graphes formés de noeuds avec au plus 8 arcs sortant. Une cellule du graphe est représentée par un damier à 9 cases: LightBot est au centre et les cases périphériques portent des pointeurs vers d'autres cellules qu'on ne voit pas à l'écran.
    • Unzoom: Le mode unzoom permet de voir tout le graphe et de visualiser le parcours effectué apr LightBot.
    • Application: algorithmes d'exploration de structures chainées (liste circulaire ou non, arbre n-binaire, graphe, dag). Le Smart LigthBot doit préparer la structure afin que le LightBot basique puisse facilement la parcourir et allumer toutes les cases. Par exemple, parcourir les feuilles d'un arbre binaire: S parcourt l'arbre et relie les feuilles, B parcourt uniquement les feuilles en suivant les pointeurs installé par S. À vous de trouver comment amener le joueur à cette solution grâce aux restrictions des capacités du Basic LightBot.
  • Création/mort de processus
    • Réplication / Clone : LightBot peut créer un clone qui effectura la procédure P0. Le clone démarre quand LightBot appelle P0. Les bots effectuent une action (en simultatnée) par tour.
    • Énergie : Chaque clone est muni à sa création d'une batterie d'une durée de vie fixée dans le puzzle. La commande NRJ peut être insérer à tout endroit dans le code et force le clone à puiser dans sa batterie, Lorsque sa batterie est vide, le clone disparaît.

Projet 2014 : Une variante multi-joueur du célèbre PacMan sous la forme d'un simulateur d'automates.

Il s'agit de concevoir un jeu avec l'intention de le porter un jour sur tablette tactile. Deux équipes s'affrontent : les Fantômes et les PacMen. Chaque type de personnages est un automate. Sous certaines conditions (à définir) des personnages peuvent devienir controlables (au clavier, à la souris ou en pointant du doigt un objectif) De nouveaux personnages peuvent être importés (image + automate). Vous pouvez créer des variantes du jeu en changeant les règles : mur déplaçable, destructible, constrution de mur, ... À vous de proposer une variante intéressante en gardant l'esprit du jeu d'origine.

Projet 2013 : Le jeu Lemmings sous la forme d'un simulateur d'automates.

Chaque type de lemmings est un automate. Vous pouvez créer de nouveaux lemmings en définissant de nouveaux automates. Vous pouvez créer des variants du jeu en changeant la physique du monde des lemmings, ou en créant de nouvelle action de base (dédoublement, courte échelle, ...).

Compétition entres équipe de robots

une arène, plusieurs équipes, un jeu collectif, des joueurs avec des stratégies programmables (par des automates), des primitives, de la coopération entre joueurs,...

• Simulation de protocoles réseaux
• Simulation de robots coopératifs
• Simulation de réactons chimiques