TD7 : Store Simulator

On se propose de simuler le parcours des clients dans un supermarché. Ce TD a pour objectif de vous faire découvrir la gestion de déplacement dans un jeu de simulation/gestion.

Introduction

Téléchargez le projet SimStore et lancez-le. Vous devriez voir l’interface suivante :

Le plan reprend l’organisation d’une grande surface réelle.

Voici la légende des codes couleurs. Cela sert uniquement à l’immersion ; les couleurs n’ont pas de rôle particulier dans notre TD.

Modélisation

GameData

Cette classe et plus particulièrement, son instance globale G permet de stocker toutes les informations relatives à la grande surface :

G.mapW, G.mapH : largeur et hauteur de la carte en cases
G.map[x,y] : retourne le caractère ASCII associé à la case
G.dist[x,y] : récupère la valeur associée à la case (x,y)
G.stands : liste des cases (x,y) contenant des items
G.spawns : liste des cases de spawn (x,y) sur la carte

Screen

Cette classe est une abstraction des fonctions de dessins Pygame. Le paramètre ZOOM donne la taille en pixels de chaque case. Le repère de screen est calé sur la grille. Ainsi, la coordonnée (0,0) correspond à l’origine en bas à gauche de l’écran, (1,0) au coin en bas à droite de la case de l’origine. La classe Screen a été construite pour permettre de ne pas avoir à gérer le repère inversé de Pygame et l’échelle d’affichage. Ainsi, à travers Screen, il suffit de se rappeler que 1 = la largeur d’une case.

S.clear(color) : efface l’écran
S.drawRect(x,y,L,H,coul,width) : dessine un rectangle au point (x,y) de L cases de large et de H cases de haut. Si width=0 => le rectangle est plein.
S.drawCircle(x,y,r,color) : dessine un cercle de centre (x,y) et de rayon r (r=1 => largeur d’une case)
S.drawText(…) : affiche une string à la position (x,y)
S.debugDist(..) : affiche les valeurs de G.map[x,y] dans chaque case vide (couloirs).
S.show() : envoie l’affichage à l’écran

Customer

Cette classe correspond à un client du supermarché :

self.targets : tous les endroits où doit passer le client dans le supermarché
self.drawTargets() : dessine un rond pour indiquer l’emplacement des targets
self.drawCustomer() : dessine un triangle indiquant la position et l’orientation du client

Logique

Deux fonctions gèrent le jeu :

drawMap() : qui dessine l’ensemble de la scène, appelée souvent i.e. 60 fois par seconde
playOneTurn() : appelée deux fois par seconde pour gérer les déplacements.

Attention, pour l’instant nous avons une gestion “discrète” des événements :

Le jeu se déroule tour par tour
A chaque tour, le client se déplace d’une case à l’autre

IA discrète

Nous allons faire en sorte que notre unique client se dirige le plus rapidement possible vers sa case cible.

Etape 1 : déplacement optimal

Nous allons utiliser une carte des distances. Prenons un objectif placé sur la carte, les valeurs contenues dans les cases des couloirs correspondent au nombre optimal de case à parcourir pour atteindre cet objectif.

Imaginons que nous effacions la valeur d’une case, comment la recalculer ?

Idée centrale : examinons les cases voisines, on s’aperçoit qu’une case se trouve à seulement 3 déplacements de l’objectif, c’est la plus proche apparemment. Nous en déduisons que notre case contient la valeur 3+1=4.

\[\mathrm{dist\_case} = \min_{v \in \text{Voisines}}(\mathrm{dist\_case}_v) + 1\]

Démarrage :

La case de l’objectif contient la valeur 0 : ok car cela correspond à la définition, il y a une distance nulle pour atteindre l’objectif !
Les murs ou les stands, il ne faudra jamais y passer. Pour éviter cela, nous mettons leurs valeurs à 999, une distance suffisamment grande.
Les cases correspondant aux allées, si on met à 0, cela ne marchera pas, on va donc mettre une valeur de 100 par exemple qui va être destinée à évoluer.

Critère de fin :

Nous allons ainsi appliquer la formule du min des voisins sur toutes les cases de la grille et ceci plusieurs fois. A un moins, nos valeurs vont se stabiliser vers la valeur optimale. Ce sera la fin du calcul. Pour cela, il faudra détecter si aucun changement n’a eu lieu après avoir appliqué la formule du min sur toutes les cases des couloirs, alors on arrête.

Algo de principe

Initialisation de G.dist en fonction de G.map
  - 0 pour la source
  - 100 pour les allées
  - 999 pour le reste

Tant qu il y a eu un changement
    Changement = Non
    Pour chaque case de G.dist
        Si la case est une allée
            Appliquer la formule du min des voisins
            Si la valeur de la case change
                Changement = Oui

Afficher G.dist

PS: Remarquez qu’il n’y a pas d’allée sur les bords. Ainsi, chaque case correspondant à une allée a donc toujours 4 voisins.

Affichage

Affichez le contenu de G.dist sur la carte et vérifiez que les valeurs sont correctes. Vous pouvez appuyer sur pause pour cela.

Etape 2 : déplacement

A chaque tour de jeu, faites déplacer le client d’une case. Trouvez la stratégie optimale en fonction de la carte des distances.

Etape 3 : multi-targets

Notre client va maintenant avoir une liste de courses correspond à une dizaine de targets dans le magasin. Modifiez cette ligne en conséquence :

self.targets   = random.sample(game.stands, nb_targets)

Par rapport à l’algo de principe, que doit-on changer pour que le client se dirige vers le target le plus proche ?

Modifiez son IA pour qu’une fois arrivée sur un target il le retire de la liste et recommence son parcours.

Etape 4 : machine à états

La machine à états du customer est assez simple.

Il spawne devant une des cases de spaws, sa machine à état passe en mode « faire les courses »
Chaque fois qu’il arrive sur un target, il le retire de la liste, il est toujours en mode « faire les courses »
Lorsque sa liste de course est vide, il passe en mode « aller aux caisses », attention, il doit aller vers la caisse la plus proche
Lorsqu’il arrive à la caisse, il passe en mode « passage en caisse » :
- Il ne se déplace plus
- Il attend juste 10 secondes pour traiter ses courses et payer
- Ensuite il disparaît

Passage au continu

Nous allons maintenant coder un déplacement qui correspondrait à un « vrai jeu » c’est à dire plus en mode case par case.

Etape 5 : mode déplacement continu

Augmentez le nombre d’appels à la fonction playOneTurn à 10 fois par seconde
Les coordonnées du client sont maintenant des valeurs flottantes
On peut choisir une vitesse de 1 ou 2 cases/seconde
A partir du paramètre dt de la fonction playOneTurn, faites avancer le client de : direction*vitesse

Comment calculer la direction ?

A partir des coordonnées (x,y) du client =>
  calculer les valeurs entières *ix* et *iy* des cases voisines
Trouver parmi les 4 cases voisines, celle qui correspond à la valeur minimale
Déduire le vecteur direction indiquant la position de la case voisine sélectionnée

Par exemple, si la case de droite contient la distance minimale, on retourne (1,0) :

Montée en puissance

Nous allons maintenant simuler plusieurs clients dans le magasin. Il est possible que certaines fonctions de notre programme soient de véritables goulets d’étranglement.

Commencez par désactiver l’affichage des targets pour chaque client.

Etape 6 : le décor

Nous avons une double boucle pour dessiner le décor de fond, cela charge le système en appels à Pygame. Comme ce décor est statique, dessinez le une fois pour toute dans un buffer et faites une copie brutale de ce buffer en lieu et place de la fonction clearScreen

Etape 7 : carte des distances

Il va maintenant falloir calculer la carte des distances pour chaque client, cela peut coûter cher.

Faites en sorte que chaque client dispose de sa propre carte des distances
Isolez ce calcul dans une fonction
- La fonction ne doit recevoir en arguments que des tableaux Numpy et des valeurs numériques
- Pas de listes Python, pas de dictionnaire, pas d’objets…

Consultez la doc de la librairie Numba. Cet outil permet de convertir à la volée une fonction Python en code C, de la compiler et de la réintégrer dans le programme. Cela est très puissant car on obtient des performances optimales. Ainsi la triple boucle contenue dans l’algo de la carte des distances aura moins d’impact sur nos performances.

Rush hour

Etape 8 : les spawners

Faites en sorte que chaque spawner crée 200 clients, à un rythme de 2 clients à la seconde par spawner
Faites en sorte que chaque client soit créé avec une position en x choisie aléatoirement entre [0,1]

La simulation est peu réaliste : les clients se déplacent indépendamment les uns des autres, comme s’ils traversaient des fantômes. Leurs déplacements sont caricaturaux : ils avancent en ligne droite et tournent de 90°.

Etape 9 : Sytadin

Pour chaque case des allées, comptez le nombre de clients présents
Associez un code couleur à chaque niveau, au delà de la limite, on affiche toujours la même couleur

colors = [
    (183, 228, 199), # vert
    (183, 228, 199),
    (183, 228, 199),

    (144, 214, 180),
    (104, 200, 160),
    (178, 222, 122),
    (222, 230, 109),
    (255, 214, 102),
    (255, 183, 77),
    (255, 138, 51),
    (240, 84, 44),
    (214, 40, 40),  # rouge
]

Faites le rendu de chaque case des allées en tenant compte du nombre de clients
Eventuellement, retirez les couleurs des rayons pour faciliter la lecture

Vous devez obtenir un rendu type « sytadin »

Pour augmenter le réalisme, faites varier la vitesse de chaque client en fonction de la densité de chaque case. Ainsi nous allons diviser la vitesse en utilisant cette formule :

\[v_{\text{corrigée}} = \frac{v}{\text{max(1,nb clients sur la case-2})}\]

Ainsi, avec 1 2 ou 3 clients présents sur la même case, pas de pénalité, au delà, la vitesse diminue.

Avertissement

Les densités changent à chaque tour, ainsi les cartes des distances de chaque client doivent être recalculées à chaque fois.

Etape 10: blocage

Maintenant, faites en sorte que lorsqu’une case contient plus de 8 clients, plus personne ne puisse y entrer.

PS: cela devrait provoquer des bouchons aux caisses ! Enfin une vraie simulation.