|  | Page web Vincent THOMAS # Atelier ISN - 30/03/2017 "Moteurs physiques, jeux vidéos et comportements" Plan de la page Description de l'atelier Diaporama et code des exemples Installation de pygame Un moteur simple avec pygame Systeme masse-ressort Jeu, collisions et interactions Simulateur de comportements Moteur jeu en JAVA Références # Description de l'atelier Actuellement, de nombreuses applications numériques utilisent des moteurs physiques que ce soit pour avoir des réactions réalistes dans des jeux (déplacements dans Super Mario, simulation de l'inertie du joueur dans les FPS, ...), pour proposer des simulateurs physiques (pédagogiques comme algodoo ou professionnels) ou pour aider le développement d'animations 3D (moteur dans Blender, ...). Cet atelier cherchera à faire le lien entre la physique et l'informatique. (1) Dans un premier temps, nous écrirons ensemble un moteur physique très simple constitué de quelques instructions (Pyhton ou Java) et basé sur la mécanique du point (système masse-ressort). (2) Nous verrons ensuite comment l'étendre pour en faire un moteur de jeu vidéo. (3) Puis, nous tirerons parti des lois de la physique pour aborder le domaine de l'Intelligence artificielle et simuler des comportements de foule inspirés de la biologie (boids et flocking) et utilisés dans de nombreux domaines (Dimensionnement de bâtiments, Effets spéciaux, ...). L'ensemble des fichiers est disponible dans cette archive zip # Diaporama et code des exemples Les documents utilisés lors de la présentation de l'atelier Structure générale de la présentation Transparents de l'atelier 2017 L'ensemble des exemples python Parmi les choses non présentées dans l'atelier Un moteur de jeu simple utilisable en JAVA est proposé en bas de cette page. Les références utiles pour compléter les informations sont disponibles tout en bas de cette page # Installation de pygame Cet atelier utilisera le langage python et la librairie pygame destinée à faire des animations et des jeux. Cette libraire se révèle très pratique et facile d'accès et l'atelier permettra aussi de faire un point sur son fonctionnement. Le plus simple semble de télécharger la dernière version Edupython une distribution python 3 destinée à l'enseignement et qui intègre pygame. Pour les autres distributions, il est nécessaire d'installer pygame et d'avoir des libraires compatibles. Pour cela, vous pouvez récupérer et installer les fichiers suivants sous windows (python 3.2 avec pygame adapté) Python version 3.2 (prendre win32) Pygame pour python 3.2 win32 La page web de pygame permet de télécharger d'autres versions de la librairie en fonction de votre système. Les pages suivantes proposent des liens permettant d'aborder facilement la librairie pygame OpenclassRoom - interface graphique pygame Programm arcade with pygame # Un moteur simple avec pygame ## 1 - Moteur physique La première étape consiste à écrire un moteur très simple simulant la mécanique du point. On se limitera pour commencer à simuler le comportement d'un objet mobile soumis à la gravité et lancé avec une vitesse initiale. Pour cela, il suffit de partir des équations aux dérivées partielles (acceleration = somme des forces) et de les intégrer en discrétisant le temps. Ces équations se transforment simplement en affectation (avec un dt trés petit)
    //definition de l'acceleration (gravite uniquement)
    ax=0
    ay=-9

    //integration des equations de la dynamique v (temps discret)
    vx=vx+ax.dt
    vy=vy+ay.dt
    x=x+vx.dt
    y=y+vy.dt
Ecrire le code correspondant et afficher à l'écran les valeurs de position, vitesse et accélération. Pour structurer un peu mieux le code construit, il est possible d'encapsuler les lois physiques dans une classe contenant les données de l'objet mobile (par exemple jeu). Les deux fichiers ci-dessous proposent un premier corrige: Moteur Simple Moteur Simple avec classe Jeu ## 2 - Présentation de la librairie pygame Afin d'avoir un rendu graphique mis à jour au fur et à mesure du temps, nous allons utiliser un moteur de jeu. En python, nous nous focaliserons sur la librairie pygame. La librairie pygame est une libraire destinée à développer rapidement et facilement des jeux vidéos. Elle propose toutes les primitives d'un moteur de jeu. Un moteur de jeu est un ensemble de classe et de fonctions permettant de faire tourner un jeu indépendamment de son contenu (règles du jeu, ...). Un moteur de jeu consiste (1) à répéter de manière régulière une boucle de jeu constituée de la mise à jour du jeu et de son affichage (2) à prendre en compte les commandes faites par le joueur en entrée (évènement clavier, ...) Une boucle de jeu peut simplement être représenté par l'algorithme suivant: (1) Initialisation du jeu (2) tant que le jeu n'est pas fini (2.1) prendre en compte les actions du joueur (2.2) mettre à jour les éléments du jeu (2.3) afficher l'état du jeu (2.4) attendre un certain temps La librairie pygame propose trois éléments permettant de mettre en place très rapidement un moteur de jeu un moyen permettant de répéter de manière régulière la boucle de jeu (par exemple 50 fois par seconde). On parle de FPS (frame per second = nombre de fois où la boucle s'exécute en 1 seconde). Cela se fait par la classe Clock() un moyen de prendre en compte les évènements utilisateurs. Pygame stocke tous les évènements entre deux boucles de jeu dans un tableau d'évènements que l'on pourra interroger à loisir. un moteur graphique permettant de dessiner et d'afficher le rendu de l'état du jeu. Ce moteur utilise le principe du doublebuffering: pendant qu'une image est affichée à l'écran, on dessine sur une image cachée et lorsque le dessin est fini, on inverse les deux images. ## 3 - Moteur de jeu sous pygame Le code suivant (inspiré de Programm arcade with pygame) présente un squelette simple permettant de développer un jeu sous pygame.
    #on cree un jeu (approche objet)
    jeu=Jeu()

    # jeu_fini est un boolean qui précise quand le jeu est fini
    jeu_fini = False

    # on creer une horloge pour réguler la vitesse de la boucle de jeu
    clock = pygame.time.Clock()

    # -------- Boucle principale -----------
    # tant que le jeu n'est pas fini
    while not jeu_fini:
        # --- on traite les evenements
        jeu.traiter_evenement()

        # --- on fait evoluer le jeu
        jeu.evoluer()

        # --- on dessine le jeu
        jeu.dessiner()
        # on inverse les affichages (double buffering)
        pygame.display.flip()

        # --- on demande d'attendre ce qu'il faut pour un FPS de 60
        clock.tick(60)
    # -------- Fin Boucle principale -----------

    pygame.quit()
Dans ce code: la méthode traiter_evenement() est en charge de traiter les évènements de l'utilisateur la méthode evoluer() est en charge de faire évoluer le jeu la méthode dessiner() est en charge dessiner l'état du jeu Ce squelette permettant d'exécuter une classe de jeu est disponible dans le fichier suivant: Squelette pygame ## 4 - Simulateur de chute A partir de ces éléments, il est trés simple d'écrire un simulateur physique avec un rendu graphique. Concernant la mise à jour des données, on se contentera d'utiliser les lois physiques discrétisées présentées ci-dessus:
    //definition de l'acceleration (gravite uniquement)
    ax=0
    ay=-9

    //integration des equations de la dynamique v (temps discret)
    vx=vx+ax.dt
    vy=vy+ay.dt
    x=x+vx.dt
    y=y+vy.dt
Pour l'affichage, on se limitera à dessiner un cercle avec la primitive de dessin pygame.draw.rect. Il faut néanmoins faire attention à changer le repère: les coordonnées (0,0) d'un écran correspondent au coin haut-gauche, il faut donc penser à inverser l'axe y pour passer du monde physique à l'écran.
    RED = (0xFF, 0x00, 0x00)
    pygame.draw.rect(screen,RED,(jeu.x,400-jeu.y,10,10))
Dans le code proposé ci-dessous, le changement de repère (monde-écran) est géré par la méthode changerCoordonnes ce qui permet d'ajouter une plus grande flexibilité. On peut ainsi facilement changer les coordonnées de références ou le facteur de zoom en ajoutant des paramètres supplémentaires (cf section ultérieure "changement coordonnées").
    # permet de changer de repere pour l'affichage
        def changerCoordonnes(self,dx,dy):
            nx = dx
            ny= 400-dy
            return( (nx,ny))
Enfin, la seule interaction avec l'utilisateur résidera dans la possibilité de fermer la fenêtre lancée par pygame (on récupère l'évènement pygame.QUIT)
    # --- on traite les evenements
    for event in pygame.event.get():
        #si l'utilisateur arrete
        if event.type == pygame.QUIT:
            done = True
Moteur Graphique ## 5 - Affichage de la trajectoire Il est possible d'afficher la trajectoire suivie en stockant les valeurs de (x,y) de l'objet à chaque itération. Cela est fait dans la méthode evoluer() qui stocke les positions successives dans les attributs de type tableau trajX et trajY.
    self.trajX+=[self.x]
    self.trajY+=[self.y]
L'affichage consiste alors à tracer des lignes entre les points successifs de la trajectoire (à l'aide d'une simple boucle dans la methode dessiner()).
    #on peut afficher la trajectoire stockee dans trajX et trajY
    #pour chaque point de la trajectoire
        for i in range(0,len(self.trajX)-1):
            x=self.trajX[i]
            y=self.trajY[i]
            coord=self.changerCoordonnes(x,y)
            x2=self.trajX[i+1]
            y2=self.trajY[i+1]
            coord2=self.changerCoordonnes(x2,y2)
            #PS : on peut ameliorer la boucle car le x2 et y2 sont les futurs x,y
            pygame.draw.line(screen,BLUE,coord,coord2,1)
Moteur Graphique avec affichage trajectoire ## 6 - Controleur clavier En récupérant les évènements claviers, il est possible d'interagir avec l'objet mobile. A la réception d'un évènement correspondant à la touche "haut", il suffit de modifier la vitesse vy de l'objet mobile. Le moteur physique prend ensuite en charge son déplacement et l'intégration de la gravité. La méthode controler() gére les évènements utilisateurs. Dans pygame, ceux-ci sont stockés dans un tableau (accessible via pygame.event.get()) qu'il suffit de parcourir à chaque iteration. On ajoute un paragraphe sur la gestion de l'appui d'une touche (le type de l'évènement correspond à la constante pygame.KEYDOWN)
    # la gestion des touches
    # appelee dans la boucle de jeu
    def controler(self):
        global done

        #traitement des evenements
        for event in pygame.event.get():

    		#si l'utilisateur arrete
            if event.type == pygame.QUIT:
                done = True

            #gestion de l'appui d'une touche
            if event.type == pygame.KEYDOWN:
                # si c'est la touche "haut"
                if event.key == pygame.K_UP:
                    print("up")
                    jeu.vy=50
Moteur Graphique avec contrôleur ## 7 - Angry birds Une fois que le système de gestion de la gravité est mis en place, on peut imaginer de nombreux jeux basés sur ce type de moteur. Par exemple, un jeu comme "angry birds" en est la conséquence directe: (1) gerer les evenements souris permet de determiner la vitesse initiale de l'objet tant que celui-ci ne vole pas (2) lorsqu'on lache le bouton de la souris, l'objet s'envole avec la vitesse initiale convenue et est soumis à la gravité Angry birds like # Ajouts au moteur ## 1 - Système masse-ressort Une fois qu'on dispose d'un système permettant de simuler la mécanique du point, il est possible d'ajouter la notion de ressort. Il suffit simplement de définir des ressorts entre des objets et de calculer à chaque itération les forces exercées entre les objets aux extrémités des ressorts. Le moteur physique s'occupe ensuite de prendre en compte ces accélérations dans la modification de la vitesse et de la position des objets. Dés que la classe ressort est définie, il est possible de gérer plusieurs ressorts. Sur chaque particule mobile, on ajoute la contribution de chaque ressort à la somme des forces et on fait ensuite évoluer le système. Moteur Graphique avec ressort Moteur Graphique avec ressort controle Moteur Graphique multi-ressort controle Il est aussi possible d'afficher à des positions régulières le vecteur force exercé par le ressort (car, dans ce cas, la force ne dépend que de la position de l'objet attaché au ressort). Il est ensuite possible de rendre compte des équilibres stables et instables en raisonnant sur le champ de force. L'application ralentit beaucoup car à chaque itération, toutes les forces sont calculées et réaffichées (comme le champ de force ne bouge pas, l'idéal pour accélérer l'affichage consisterait à sauver ce champ de force dans une image qu'on recopiera à chaque itération) champ de force ressort ## 2 - Systeme de ressort - Blob Une fois le système masse-ressort écrit, il est possible de créer des jeux basés sur des créatures composées de ressorts. Le plus simple consiste à créer une classe Systeme constituée d'une liste objets mobiles de la liste des ressorts liant ces objets mobiles La méthode evoluer() de cette classe prend en compte tous les ressorts pour mettre à jour l'accélération des objets concernés puis intégrer le résultat sur chaque objet.
    class Systeme():

            # un systeme est constitue d'objets et de ressorts
            def __init__(self):
                    self.ressorts=[]
                    self.objets=[]

            # executer
            def evoluer(self):
                    # initialiser a a g
                    for objet in self.objets:
                            objet.ax=0
                            objet.ay=-9

                    # pour chaque ressort
                    for ressort in self.ressorts:
                            ressort.metreAJourAcc()

                    # mettre à jour objet
                    for objet in self.objets:
                            objet.evoluer()
Systeme de ressorts A partir de la classe Systeme, on peut produire des formes constituées de treillis de ressorts. Le comportement général de l'objet dépend de la manières dont les objets mobiles sont connectés. Il est à noter que chaque objet du treillis dispose de sa propre masse (puisqu'on ajoute la gravité à l'accélération de chaque objet). Il est possible d'avoir des objets de masses différentes en modifiant le vecteur accélération (les forces autres que la gravité doivent être modulées par le rapport de masses m/m_unitaire). blob systeme 1 blob systeme 2 blob systeme 3 La version ci-dessous ajoute un contrôleur qui permet de modifier en temps réel la raideur des ressorts (avec les flèches "haut" "bas" du clavier). En fonction de cette raideur, le blob peut s'affaisser sous son propre poids. En baissant la raideur puis en l'augmentant rapidement il est possible de faire "sauter" la forme (du fait de la reaction des ressorts) Blob systeme 3 raideur variable C'est sur cette base, que le jeu gish a été développé (mais il intègre beaucoup plus d'éléments en particulier, la manière de se déplacer en réponse aux contrôles des utilisateurs). ## 3 - Gravité et système à plusieurs corps De la même manière, simuler la gravité entre planètes consiste simplement à ajouter à notre moteur de jeu de nouveaux types de force comme la force de gravitations exercée par d'autres corps. Cette force est dirigée selon la direction reliant les deux objets ; et a une intensité proportionnelle à la masse / distance au carré.
    # definition des planetes sous la forme [x,y,rayon]
    planete = [200,200,20]

    # vecteur direction de la force
    direction=[planete[0]-self.x,planete[1]-self.y]

    # calcul distance entre balle et planete
    dcarre=direction[0]*direction[0]+direction[1]*direction[1]
    from math import sqrt
    d=sqrt(dcarre)

    # si la distance est plus petite que le rayon => crash
    if (d < planete[2]):
        self.enVol=False
        return

    # calcul de la force de gravite exercee en 1 / d^2
    # (ici au cube car la direction n'est pas normalisée)
    direction[0]=direction[0]/(d*d*d)
    direction[1]=direction[1]/(d*d*d)

    # ajoute contribution a l'acceleration
    self.ax+=masse*direction[0]
    self.ay+=masse*direction[1]
Angry birds like avec planete Il est ensuite possible d'ajouter plusieurs planètes. Angry birds like avec plusieurs planetes Il est aussi possible d'ajouter planètes de "masse négative" pour générer des forces de répulsion comme le présente la figure ci-dessous (sur ce schémas, ce sont les planètes bleues qui repoussent la particule). 05_version_classe_angrybirds_orbite_multiples_masses ## 4 - Poussée d'Archimède Il est aussi possible de représenter la poussée d'archimede sur une solide. Il suffit pour cela d'adapter l'acceleration verticale en fonction de la partie immergée de l'objet considéré.
            # poussee totale
            total=12

            # calculer acceleration
            # si en dehors de l'eau
            if (self.y>0+self.taille/2):
                self.ay = -9
                partie = 0
            else :
                #totalement immerge
                if (self.y<0-self.taille/2):
                    self.ay = -9+total
                    partie = 1
                #partiellement immerge
                else:
                    #calcul propotion immergee
                    partie = (self.taille/2-self.y)/self.taille
                    self.ay = -9+partie*total

            #amortissement fonction de la proportion immergee
            self.ay=self.ay-self.vy*0.2*partie
Poussée archimede # Jeu, collision et interaction ## 1 - Gestionnaire collision Afin de faire un jeu, il faut rajouter un gestionnaire de collisions. Un gestionnaire de collision consiste avant tout à déterminer quand un objet rectangulaire intersecte un autre objet rectangulaire. Pour gérer des objets de forme quelconque, on utilise ensuite des Bounding box à savoir des rectangles englobant l'objet à tester
    if 	(b.x >= a.x + a.w)
    	or (b.x + b.w <= a.x)
    	or (b.y >= a.y + a.h)
    	or(b.y + b.h <= a.y)):
            return false
    else:
    	return true
    }
Le code ci-dessus vérifie s'il y a collision entre deux rectangles a et b caractérisé par une position initiale (x,y) et une largeur et hauteur (w,h) On sépare l'espace en quatre portions en fonction du rectangle A. Si le rectangle B se trouve dans une de ses portions, c'est qu'il n'y a pas collision. Affichage des collision avec Obstacle en U ## 2 - Rebond collision Une fois la détection, faite, il est possible de gérer l'événement, par exemple en ajoutant un rebond (si la collision est en haut, ou en gauche/droite) et un appui si la collision est en bas avec le personnage. Jeu gestion collisions # Simulateur de comportements Afin de simuler les comportements de déplacement, une approche désormais classique consiste à utiliser des steering behaviour (cf page de Craig Reynolds). Il s'agit de modéliser la dynamique de déplacement à l'aide de la mécanique du point. La motivation de l'agent se traduit sous la forme de forces qui vont influencer sa vitesse et son déplacement. ## 1 - Accélération directe La comportement le plus simple consiste à déterminer la direction de l'agent en fonction l'objectif à atteindre. La commande en accélération consiste alors simplement à suivre la direction du vecteur (position agent -> objectif). Cependant, ce type de comportement introduit des oscillations importantes puisque l'accélération change de direction uniquement quand la position de l'agent dépasse la position de l'objectif. Steering accélération directe ## 2 - Commande adaptée Une première solution à contrôler par la vitesse. La commande en accélération a alors pour objectif de modifier la vitesse courante vers la vitesse souhaitée. Steering acceleration controle vitesse ## 3 - Comportement de groupe Il est alors possible de gérer des comportements de groupe en ajoutant des répulsion entre agents. Cela permet aux agents de ne pas se percuter tout en cherchant à attaindre l'objectif souhaité. Steering acceleration multi-agent Le code suivant propose de faire plusieurs groupes. On controle l'objectif de chaque groupe avec un click gauche/droite. Tous les agents se repoussent les uns les autres ce qui permet de modéliser deux groupes qui se croisent. Steering acceleration multi-objectif ## 4 - Ajout d'une caméra En représentant explicitement la manière dont l'affichage calcule les coordonnées des points dans l'image, il est simple d'ajouter une caméra mobile permettant de changer de repère. Les lois du monde restent les même et le code permettant de faire évoluer les grandeurs physiques ne change pas, seule la fonction permettant d'afficher le résultat à l'écran doit être modifiée. Pour cela, le code suivant propose une classe Repere. Cette classe représente le lien entre le monde physique et l'écran. Elle contient 3 attributs importants: le centre de la caméra (x0,y0) et le facteur de zoom. La classe Repere possède deux méthodes de transformation de coordonnées: une permettant de passer du monde physique au monde de l'image (pour afficher le système), une permettant de passer du monde de l'image au monde physique (pour pouvoir correctement repositionner un click de souris). La composition des deux fonctions doit retourner l'identité.
        #passe du monde à l'ecran
        def transformCoord(self,xm,ym):
            tx=self.tailleFenetreX/2
            ty=self.tailleFenetreY/2
            return(tx+(xm-self.x0)*self.zoom,ty+(ym-self.y0)*self.zoom)

        #passe de l'ecran au monde(ex gerer click souris)
        def coord_inverse(self,xe,ye):
            tx=self.tailleFenetreX/2
            ty=self.tailleFenetreY/2
            return((xe-tx)/self.zoom+self.x0,(ye-ty)/self.zoom+self.y0)
Le code correspond intègre ce changement de repère: Corrige steering multi-agent avec gestion de camera ## 5 - Flocking Le comportement de flocking est un comportement de déplacement en groupe en essaim (banc de poissons, essaim d'insectes ou nuée d'oiseaux). Ce type de comportement est caractérisé par l'absence de leader et le fait que chaque individu modifie sa trajectoire en fonction de ses voisins. Ce comportement peut d'implémenter en utilisant le type de simulateur qui a été développé et s'articule autour de trois comportements élémentaires appliqués à chaque individu et basés sur leurs observations (cf référence Flocking behaviour): le comportement d'alignement : chaque individu a tendance à suivre la même direction que celle de ses voisins. le comportement de cohésion : chaque individu a tendance à se diriger vers le barycentre de ses voisins. le comportement de séparation : chaque individu a tendance à s'éloigner de chaque voisin. L'application ci-dessous implémente un comportement de flocking. Il est possible de modifier l'importance de chaque comportement élémentaire en cliquant dans les zones de couleur. Flocking Flocking avec influence variable # Moteur de jeu en JAVA Si vous souhaitez aborder le contenu de l'atelier avec JAVA, cette partie quelques éléments pour JAVA. Tout d'abord, parmi les librairies utilisables, on peut noter slick2D qui permet de développer des jeux en JAVA page officielle http://slick.ninjacave.com/ tutoriels http://www.shionn.org/tutoriels-slick-2d Cette section vous propose un moteur simple développé personnellement et proposé aux étudiants dans différentes formations ce fichier zip contient l'ensemble des classes du moteur une documentation de prise en main sur comment utiliser le moteur présenté ci-dessus. Les premiers exemples donnés dans le fichier zip implémentent les premiers éléments de l'atelier. Il suffit ensuite de ré-implémenter progressivement les choses qui sont présentées en python en suivant le déroulement de l'atelier. # Références utiles Sur les moteurs physiques Le livre "Game Physics Engine Development" de Millington et la page associée le tutoriel trés complet d'animateurs de pixar à la conférence Siggraph 2001 modelisation d'un blob du site cowboy programming Sur le moteurs de jeu OpenclassRoom - interface graphique pygame Programm arcade with pygame Comment construire un moteur de jeu (java) Sur les steering behaviour La page web de Craig reynolds qui présente différents comportements l'article scientifique "Steering Behaviors For Autonomous Characters" (1999) trés complet et facile d'accés une page du site GameDevTuts dédiée au flocking la partie du site GameDevTuts dédiée aux steering behavior le livre "Artificial Intelligence for Games" de Millington sur l'IA dans les jeux vidéos qui débute par des comportements à base de force puis ajoute des décisions d'ordre supérieur la bibliotheque "opensteer" developpée à l'origine par Craig Reynolds Sur la modélisation de comportement la page anglaise de wikipedia sur le flocking un article de la recherche "Comment les piétons marchent dans la foule" sur la modélisation des comportements de foule l'article de D.Helbin "Simulating dynamical features of escape panic" publié dans nature (2000) un article du site AIGamDev sur les dynamiques de foule dans les jeux videos le logiciel "Massive" logiciel de reference dans l'industrie pour la simulation de comportement (films, jeux, simulation de foule, etc...) Sur les problèmes de controle de dynamique la page de karl sims sur son article "Evolved Virtual Creatures" la video " Flexible Muscle Based Locomotion for Bipedal Creatures " d'un travail de Thomas Geijtenbeek (version de l'article à ACM Transactions on Graphics 2013) description du physical TSP problem proposé à la conférence GECCO 2005 l'article de GECCO 2005 décrivant le problème du physical TSP en détail |  |
last mod. 30/03/2017 | Copyright © Vincent Thomas - vthomas@loria.fr