Life of a cell (Game of Life Like)

      I’m sharing this project that was completed in 2019 for the computer science baccalaureate with a classmate: JG W. In the end, there was no exam, but we prepared the project documentation, so here it is. Enjoy reading!

You can try it here !
The GUI looks terrible so as the code but it was a great project to get the gist of javascript programming.

Concept

      Ce programme a pour but de simuler l’évolution de populations dans un même espace limité suivant des règles établies à paramètres modifiables. On souhaite avoir une interface pour effectuer les modifications et avoir des résultats et analyses sous forme graphique.

On définit 2 populations : 

• Les “Passifs”, c’est une population qui se contente de se mouvoir, de manger la végétation présente et de se reproduire
• Les “Agressifs”, c’est une population qui peut se mouvoir, se nourrit exclusivement d’être Passifs et peut se reproduire uniquement après avoir mangé.

Il existe aussi de la végétation qui apparaît à intervalle régulier dans l’espace. 

      Ces deux populations se développent dans un environnement appelé carte ou map. Elle est fixe tout au long de la simulation et ses bords ne communiquent pas entre eux et ferment comme des palissades.
      Le but de la simulation est donc d’observer l’impact de chaque paramètres sur celle-ci. Par exemple : faciliter la reproduction d’un des types acteurs aura pour conséquences de la faire croître plus rapidement.

A la fin on veut un affichage sous forme de graphiques pour mieux visualiser.

---

Le concept s’inspire du “jeu de la vie” de John Horton Conway créé en 1970. Il est basé sur l’idée d’automates cellulaires soumis à des lois simples. Ces lois permettent l’apparition de phénomènes surprenants tels que des structures motrices, des générateurs de structures motrices (sur l’exemple), des oscillateurs, des structures stables etc..

Cahier des Charges

Selon les règles décrites précédemment, on peut détailler les besoins :

• Pouvoir entrer des paramètres influant sur la simulation 
• Permettre de lancer la simulation avec ces paramètres
• Permettre un affichage en temps réel de l’évolution de la simulation
• Rendre un affichage clair et lisible des résultats de la simulations
• Le langage de programmation utilisé est le Javascript, il permet en effet une certaine souplesse de programmation et une gestion simple de front-end (interface homme machine). Le HTML5 et le CSS3 seront aussi utilisés mais dans une moindre mesure.
• La simulation suivra les règles décrites dans la partie précédente, et l’affichage se devra d’être clair et lisible. L’utilisation de couleur simples doit être privilégié pour aider à la lisibilité. 
• Le moteur graphique utilisé est celui de base, c’est à dire l’élément Canvas.
• L’utilisateur doit pouvoir être en mesure de pouvoir modifier facilement les paramètres de la simulation.
• La simulation doit être fluide et se dérouler en temps réel
• L’espace est un carré de longueur de côté modifiable
• Notre documentation principale est w3School, un site proposant une documentation pour le développement Web.
• L’apparition des acteurs en début de simulation est aléatoire parmi les cases non occupéesLes acteurs doivent être doté d’une petite intelligence artificielle pour reconnaître leur nourriture.

Mise en œuvre

       Avant de foncer tête baissée dans le code, j’ai pris de le temps de bien définir une structure pour mon programme. Ainsi, je vise une approche objet du problème pour plusieurs raisons :

• ¨Puissance de modification de paramètres : je veux dire par là qu’il est plus facile de changer les variables à grande échelle avec l’héritage.
• Avoir une structure solide : une architecture objet est facile à structurer et aide beaucoup à  ne pas se perdre

De plus, comme c’est une simulation, je pense utiliser une boucle qui va à chaque fois calculer un nouveau “tour”. Ainsi la variables de temps entre peut être dénombré et l’unité sera le tour.

Ensuite j’ai définit les variables globales qui vont entrer en compte :

• Dimensions de l’espace
• Le nombre initial d’acteurs passifs
• Le nombre initial d’acteurs agressifs
• Les caractéristiques initiales des acteurs
• Le nombre de végétaux apparaissant tous les x tours
• Le temps (en tours) deux apparitions de végétaux
• Le temps (en tours) maximum pour la simulation
• Le temps (en ms) entre deux tours.

Puis j’ai divisé les différentes tâches en les regroupant par catégories.

Acteurs de la simulations

Pour les acteurs je mets en place le design pattern “template”.

      Ce pattern à la base de l’héritage va être utile pour notre cas car nos deux acteurs peuvent se déplacer, manger de la nourriture, être mangé, ont les mêmes paramètres initiaux et peuvent se reproduire. Ainsi on ne va pas avoir de code qui se répète. 

Remarque : la classe définissant les végétaux va aussi hériter de Acteur car cette dernière classe contient des fonctions similaires au comportement des Végétaux dans notre simulation ex : être mangé et est affiché sur le canvas

Affichage

      On veut avoir un affichage du déroulement de la simulation. J’ai donc choisi de travailler avec un simple système canvas malgré les soucis d’optimisation des performances. (On aurait pu utiliser des framework graphique mais ici on reste simple).
      Il y a donc une superposition de 2 canvas, l’un avec la carte (un tableau de tuiles à deux dimensions) et l’autre au dessus contenant tous les acteurs. Cette solution permet de rafraîchir un seul canvas sur les deux et de gagner énormément de performances, en effet la carte ne subit aucun changement au cours du temps, il n’y a donc aucune raison de la mettre à jour à chaque tour.

Un canvas devient donc un “layer” :

      Le pensais dans un premier temps implémenter un algorithme de recherche de chemin (pathfinding A*) cependant je me suis aperçu après réalisation de gros problèmes de performances car canvas n’est pas adapté pour mon approche à plusieurs centaines d’individu.

Réalisation

Une fois toutes ces règles établies, je me suis lancé dans la programmation en commençant par générer une grille à taille modifiable : 

      Ainsi je génère une grille à deux dimensions d’objets Tile et je les enregistre dans une liste de l’objet Map. Ce dernier permet de faire instance de tout ce qu’il existe sur la carte et il contient beaucoup de méthodes utiles que nous verront plus tard.

L’objet Tile regroupe quand à lui des informations telles que sa position, son identifiant dans la liste, si il est occupé, sa couleur, et des méthodes get/set classiques. De plus on enregistre l’ensemble des cases voisines pour aider au déplacement.

L’objet Map

On va s’intéresser à  cet objet petit par petit car il contient beaucoup de méthodes. 

      En effet, il contient une référence à chaque objet présent dans la scène. Il contient ainsi beaucoup de méthodes get/set prenant différents paramètres, parfois des ID, parfois des coordonnées,  une liste des tuiles non occupées. C’est aussi cet objet qui calcule les voisins de chaque tuiles :

      Cette fonction est nécessaire pour permettre le déplacement et l’ IA des acteurs. On notera que ce sont deux boucles imbriquées qui vont le plus souvent de 1 à 9 en omettant lorsque _x=x et _y=y ce qui correspond à la case elle même. Initialement les voisins de chaque cases étaient pré-calculés cependant on expérimentait des latences en début de simulation. Ma solution est donc de les calculer que lorsque nécessaire et ensuite de les enregistrer dans l’objet tile correspondant pour pouvoir s’en resservir et donc gagner du temps.
      Map possède la fonction pour rafraîchir l’affichage et celle pour détruire les acteurs qui décède lors d’un tour.

L’objet Acteur

      J’utilise deux fonctions pour les faire apparaître : SpawnActors et SpawnNewBushes. L’une est exécutée au démarrage et le seconde est répétée à intervalle régulier.

      Le constructeur prend en compte les paramètres définis par l’utilisateur au début de la simulation, l’énergie de base, les timings de reproductions, le temps de vie maximum, la position initiale et l’id de cette tuile.

  Chaque acteur possède des fonctions pour se reproduire, se déplacer, chercher une nouvelle destination.
      La destination est choisie en fonction de l’acteur et donc de ses préférences, un passif va chercher à manger des végétaux de même pour les agressifs. On a donc un début d’IA certes peu développée mais présente.
       Maintenant il ne manque plus qu’à tout relier par une fonction d’exécution. Elle met en place une boucle qui va gérer les actions à chaque tour. De plus cette fonction prend des informations pour plus tard tel que le nombre, l’âge de chaque acteurs etc..

Problèmes rencontrés

    Lors de la réalisation je me suis heurté à quelques problèmes majeurs :

• la mauvaise superposition des deux canvas
• mauvais calcul de voisinage pour chaque cases, révisions fréquentes

Améliorations possibles : 

    Il y a beaucoup de choses qui peuvent être améliorer dans ma partie.

       Le projet étant un prototype, les graphismes sont les plus simples possible. Il est possible de faire appel à un graphiste pour améliorer le rendu de la simulation.
      Encore du côté graphique, il est possible de changer de moteur pour gagner en ressources utilisé sur les éléments visuel, cela permettrait d’intégrer plus d’éléments (plus d’acteurs, de comportements..).
      Ajouter toujours plus d’IA pourrait être intéressant pour observer d’autre comportements, par exemple : groupes etc..
      On peut aussi penser à changer les règles de la simulation.

Le programme est disponible ici pour que vous l’essayiez.