deutsch     english    français     Imprimer

 

8.9 DYNAMIQUE DE GROUPE

 

 

INTRODUCTION

 

Les systèmes comportant de nombreux partenaires en interaction sont très répandus. Il est souvent possible de simuler sans problème de tels systèmes à l’aide de programmes informatiques puisque l’ordinateur peut sans autre stocker des milliers ou même des millions d’états individuels tout en suivant leur évolution temporelle. Il va sans dire qu’une telle simulation n’est pas possible avec des systèmes à l’échelle atomique comportant un nombre de particules en interaction de l’ordre de 1023. Ceux-ci dépassent en effet de loin les capacités de stockage et de traitement des ordinateurs. Pour simuler de tels systèmes, il faut utiliser des procédures simplifiées consistant par exemple à diviser le système en plusieurs cellules plus larges. Les simulations des phénomènes liés à l’atmosphère terrestre utilisées pour effectuer les prévisions météorologiques ou les prédictions de l’évolution du climat sur le long terme sont de bons exemples de telles simplifications.

CONCEPTS DE PROGRAMMATION:
Simulation informatique, dynamique de population, comportement en essaim

 

 

LE JEU DE LA VIE DE CONWAY

 

Le jeu de la vie de Conway a pour but d’étudier le comportement d’individus en interaction disposés dans une structure de grille bidimensionnelle. Chaque individu est en interaction avec les huit cases qui lui sont adjacentes. Cette simulation fut proposée par le mathématicien britannique John Conway en 1970 et le rendit célèbre même en dehors des cercles mathématiques. Pratiquement tout scientifique a au moins une vague idée du jeu de la vie. Vous aurez une idée bien précise de son fonctionnement après l’avoir développé en Python.

La population est formée de cellules et évolue dans le temps par étapes discrètes (générations). Chaque cellule peut être en état de vie ou en état de mort.

 

La simulation passe de la génération i à la génération i+1 en considérant, pour chaque cellule, les règles de transitions suivantes basées sur l’état des huit cellules environnantes :

1.
Si la cellule est vivante en i, elle va mourir si elle comporte moins d’une cellule voisine vivante actuellement (isolation)
2.
Si la cellule est vivante en i, elle va continuer à vivre si elle possède deux ou trois cellules actuellement vivantes (cohésion de groupe)
3.
Si la cellule est vivante en i, elle va mourir si elle possède plus de trois cellules voisines vivantes (surpopulation)
4.
Si une cellule est morte en i, elle revient à la vie si elle possède exactement trois cellules voisines vivantes en i, (reproduction). Sinon, elle reste morte.

La structure en grille de GameGrid convient à merveille pour implémenter ce jeu. On utilise une liste bidimensionnelle a[x][y] pour encoder l’état de chaque cellule de la population en représentant une cellule morte par un 0 et une cellule vivante par un 1. Le cycle de simulation de GameGrid est considéré comme le temps de vie d’une génération. La population actuelle stockée dans la liste a est copiée dans la liste b au sein de la fonction de rappel onAct() et sera finalement considérée comme la liste actuelle. La population est initialisée en choisissant au hasard 1000 cellules initialement vivantes dans la fonction de rappel onReset() qui est appelée lors d’un clic sur le bouton « reset ».
Il ne faut pas oublier d’enregistrer les fonctions de rappel à l’aide des fonctions registerAct() et registerNavigation().

from gamegrid import *

def onReset(): 
    for x in range(s):
        for y in range(s):
            a[x][y] = 0  # All cells dead
    for n in range(z):
        loc = getRandomEmptyLocation()
        a[loc.x][loc.y] = 1
    showPopulation()
        
def showPopulation():
    for x in range(s):
        for y in range(s):
            loc = Location(x, y)
            if a[x][y] == 1:
                getBg().fillCell(loc, Color.green, False)
            else:
                getBg().fillCell(loc, Color.black, False)
    refresh()
    
def getNumberOfNeighbours(x, y):
    nb = 0
    for i in range(max(0, x - 1), min(s, x + 2)):
        for k in range(max(0, y - 1), min(s, y + 2)):
            if not (i == x and k == y): 
                if a[i][k] == 1:
                    nb = nb + 1
    return nb

def onAct():
    global a
    # Don't use the current, but a new population
    b  = [[0 for x in range(s)] for y in range(s)]
    for x in range(s):
        for y in range(s):
            nb = getNumberOfNeighbours(x, y)
            if a[x][y] == 1:  # living cell
                if nb < 2:
                    b[x][y] = 0
                elif nb > 3:
                    b[x][y] = 0
                else:
                    b[x][y] = 1
            else:             # dead cell
                if nb == 3:
                    b[x][y] = 1
                else:
                    b[x][y] = 0
    a = b # Use new population as current
    showPopulation()
    
# =================== global section ==================
s = 50   # Number of cells in each direction
z = 1000 # Size of population at start
a  = [[0 for x in range(s)] for y in range(s)]
makeGameGrid(s, s, 800 // s, Color.red)
registerAct(onAct)
registerNavigation(resetted = onReset)
setTitle("Conway's Game Of Life")
onReset()
show()
S&ecute;lectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Le jeu de la vie est un exemple typique d’automate cellulaire constitué de cellules d’une grille en interaction les unes avec les autres. Les automates cellulaires se prêtent très bien à l’étude du comportement de systèmes naturels complexes parmi lesquels on trouve

  • La croissance biologique, l’émergence de la vie
  • Le comportement social, géologique, écologique
  • La régulation du trafic
  • La formation et l’évolution du cosmos, des galaxies et des étoiles

En 2002, Stefan Wolfram, le scientifique et développeur en chef de Mathematica fit remarquer, dans son fameux livre "A New Kind of Science", que de tels systèmes peuvent être étudiés à l’aide de programmes simples. Les simulations informatiques nous placent à la veille d’une nouvelle ère dans la manière d’acquérir des connaissances scientifiques.

Pour initialiser une liste à deux dimensions (liste de listes), on utilise une syntaxe python spéciale appelée compréhension de liste (list comprehensionen anglais) (voir Matériel supplémentaire).

 

 

COMPORTEMENT EN ESSAIM

 


Comme vous avez déjà pu l’observer souvent dans la vie, de nombreux êtres vivants ont tendance à former de grands groupes d’individus. Ce phénomène est particulièrement évident chez les oiseaux, les poissons et les insectes. Un groupe de personnes réunies pour une manifestation présentent également une forme de « comportement grégaire ». La formation d’un essaim d’individus est influencée d’une part par des facteurs extérieurs globaux et d’autre part par les interactions des partenaires dans leur environnement immédiat (influences locales).

En 1986, Craig Reynolds a démontré que la formation d’un essaim d’individus qu’il appela Boids est régie par les trois règles suivantes:

1.
Règle de cohésion : se déplacer vers le centre de gravité des individus se trouvant dans son voisinage
2.
Règle de séparation: s’éloigner si l’on se rapproche trop près d’un autre individu
3.
Règles d’alignement : se déplacer approximativement dans la même direction que ses voisins

Afin d’implémenter ce comportement, on utilise à nouveau JGameGrid afin de minimiser les ressources nécessaires pour effectuer le rendu de l’animation. Il est alors possible d’utiliser une grille de jeu dont les cellules se réduisent à un pixel et de spécifier la position, la vitesse et l’accélération des acteurs à l’aide de vecteurs en virgule flottante de la classe GGVector. À chaque période de simulation, on commence par déterminer le nouveau vecteur accélération à partir des trois règles de formation d’essaim grâce à la fonction setAcceleration(). On obtient ainsi les nouveaux vecteurs vitesse et position

et

Puisque l’échelle de temps absolu n’est pas essentielle, on peut sans autre fixer l’incrément temporel à dt = 1.

L’application de la règle de séparation conduit non seulement à une répulsion entre les oiseaux trop rapprochés, mais également un évitement des obstacles, en l’occurrence les arbres.

Il faut faire particulièrement attention à bien gérer les limites de la zone de vol (les côtés du canevas). On peut imaginer plusieurs possibilités. On pourrait, par exemple, utiliser une topologie toroïdale dans laquelle les oiseaux quittant la zone de vol d’un côté réapparaissent automatiquement de l’autre. Dans le programme suivant, on a simplement fait le choix d’imposer aux oiseaux de faire demi-tour lorsqu’ils parviennent aux bords.

from gamegrid import *
import math
from random import randint

# =================== class Tree =======================
class Tree(Actor):
    def __init__(self):
        Actor.__init__(self, "sprites/tree1.png")

# =================== class Bird =======================
class Bird(Actor):
    def __init__(self):
        Actor.__init__(self, True, "sprites/arrow1.png")
        self.r = GGVector(0, 0)  # Position
        self.v = GGVector(0, 0)  # Velocity
        self.a = GGVector(0, 0)  # Acceleration
 
    # Called when actor is added to gamegrid
    def reset(self):
        self.r.x = self.getX()
        self.r.y = self.getY()
        self.v.x = startVelocity * math.cos(math.radians(self.getDirection()))
        self.v.y = startVelocity * math.sin(math.radians(self.getDirection()))
  
    # ----------- cohesion ---------------
    def cohesion(self, distance):
        return self.getCenterOfMass(distance).sub(self.r)

    # ----------- alignment --------------
    def alignment(self, distance):
        align = self.getAverageVelocity(distance)
        align = align.sub(self.v)
        return align

    # ----------- separation -------------
    def separation(self, distance):
        repulse = GGVector()
        # ------ from birds ------
        for p in birdPositions:
            dist = p.sub(self.r)
            d = dist.magnitude()
            if d < distance and d != 0:
                repulse = repulse.add(dist.mult((d - distance) / d))

        # ------ from trees ------
        trees = self.gameGrid.getActors(Tree)
        for actor in trees:
            p = GGVector(actor.getX(), actor.getY())
            dist = p.sub(self.r)
            d = dist.magnitude()
            if d < distance and d != 0:
               repulse = repulse.add(dist.mult((d - distance) / d))
        return repulse
  
    # ----------- wall interaction -------
    def wallInteraction(self):
        width = self.gameGrid.getWidth()
        height = self.gameGrid.getHeight()
        acc = GGVector()
        if self.r.x < wallDist:
            distFactor = (wallDist - self.r.x) / wallDist
            acc = GGVector(wallWeight * distFactor, 0)
        if width - self.r.x < wallDist:
            distFactor = ((width - self.r.x) - wallDist) / wallDist
            acc = GGVector(wallWeight * distFactor, 0)
        if self.r.y < wallDist:
            distFactor = (wallDist - self.r.y) / wallDist
            acc = GGVector(0, wallWeight * distFactor)
        if height - self.r.y < wallDist:
            distFactor = ((height - self.r.y) - wallDist) / wallDist
            acc = GGVector(0, wallWeight * distFactor)
        return acc
  
    def getPosition(self):
        return self.r
      
    def getVelocity(self):
        return self.v

    def getCenterOfMass(self, distance):
        center = GGVector()
        count = 0
        for p in birdPositions:
            dist = p.sub(self.r)
            d = dist.magnitude()
            if d < distance:
                center = center.add(p)
                count += 1
        if count != 0:        
            return center.mult(1.0/count)
        else:
            return center

    def getAverageVelocity(self, distance):
        avg = GGVector()
        count = 0
        for i in range(len(birdPositions)):
            p = birdPositions[i]
            if (self.r.x - p.x) * (self.r.x - p.x) + \
               (self.r.y - p.y) * (self.r.y - p.y) < distance * distance:
                avg = avg.add(birdVelocities[i]);
                count += 1
        return avg.mult(1.0/count)

    def limitSpeed(self):
        m = self.v.magnitude()
        if m < minSpeed:
            self.v = self.v.mult(minSpeed / m)
        if m > maxSpeed:
            self.v = self.v.mult(minSpeed / m)

    def setAcceleration(self):
        self.a = self.cohesion(cohesionDist).mult(cohesionWeight)
        self.a = self.a.add(self.separation(separationDist).mult(separationWeight))
        self.a = self.a.add(self.alignment(alignmentDist).mult(alignmentWeight))
        self.a = self.a.add(self.wallInteraction())

    def act(self):
        self.setAcceleration()
        self.v = self.v.add(self.a) # new velocity
        self.limitSpeed()
        self.r = self.r.add(self.v) # new position
        self.setDirection(int(math.degrees(self.v.getDirection())))
        self.setLocation(Location(int(self.r.x), int(self.r.y)))


# =================== global section ==================
def populateTrees(number):
    blockSize = 70
    treesPerBlock = 10
    for block in range(number // treesPerBlock):
        x = getRandomNumber(800 // blockSize) * blockSize
        y = getRandomNumber(600 // blockSize) * blockSize
        for t in range(treesPerBlock):
            dx = getRandomNumber(blockSize)
            dy = getRandomNumber(blockSize)
            addActor(Tree(), Location(x + dx, y + dy))
                
def generateBirds(number):
    for i in range(number):
        addActorNoRefresh(Bird(), getRandomLocation(), 
                                  getRandomDirection())
    onAct()  # Initialize birdPositions, birdVelocities
     
def onAct():
    global birdPositions, birdVelocities
    # Update bird positions and velocities
    birdPositions = []
    birdVelocities = []
    for b in getActors(Bird):
        birdPositions.append(b.getPosition())
        birdVelocities.append(b.getVelocity())
 
def getRandomNumber(limit):
    return randint(0, limit-1)

# coupling constants 
cohesionDist = 100
cohesionWeight = 0.01
alignmentDist = 30
alignmentWeight = 1
separationDist = 30
separationWeight = 0.2
wallDist = 20
wallWeight = 2
maxSpeed = 20
minSpeed = 10
startVelocity = 10
numberTrees = 100
numberBirds = 50

birdPositions  = []
birdVelocities  = []

makeGameGrid(800, 600, 1, False)
registerAct(onAct)
setSimulationPeriod(10)
setBgColor(makeColor(25, 121, 212))
setTitle("Swarm Simulation")
show()
populateTrees(numberTrees)
generateBirds(numberBirds)
doRun()
S&ecute;lectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La simulation dépend d’un certain nombre de constantes de couplage qui déterminent l’intensité de l’interaction entre les individus. Ces valeurs sont très sensibles et il pourrait être nécessaire de les ajuster en fonction de la puissance de traitement de votre ordinateur.

Encore une fois, la fonction de rappel onAct() est activée en utilisant registerAct() de sorte qu’elle est appelée automatiquement à chaque cycle de simulation. Le mouvement des oiseaux est géré par la méthode act() de la classe Bird.

 

 

EXERCICES

 

1.


Étudier le comportement des motifs initiaux suivants dans le jeu de la vie

. b. c.
           
d. e.    

2.


Décrire trois comportements en essaim typiques survenant dans le monde animal. Pour chaque exemple, réfléchissez aux raisons qui amènent ces animaux à former des essaims.


3*.


Dans la simulation avec les oiseaux, introduire trois oiseaux prédateurs qui pourchassent les volées d’oiseaux et qui sont évités par les proies. Consigne : utiliser l’image de sprite arrow2.png pour représenter les prédateurs.


4*.


Modifier la simulation de telle sorte que les prédateurs de l’exercice précédent mangent les oiseaux proies lors d’une collision.

 

   

MATÉRIEL SUPPLÉMENTAIRE


 

COMPRÉHENSION DE LISTE

 

En Python, il est possible de créer des listes de manière très élégante en utilisation une syntaxe spéciale inspirée de la notation de la théorie des ensembles que vous connaissez bien des mathématiques :

Mathématiques Python
S = {x: x élément de {1...10}} s = [x for x in range(1, 11)]
T = {x2: x élément de {0...10}} t = [x**2 for x in range(11)]
V = {x | x élément de S et x pair} v = [x for x in s if x % 2 == 0]
m = [[0 for x in range(3)] for y in range(3)]

N’hésitez pas à utiliser la console pour tester les expressions Python. Pour ce faire, vous pouvez les copier depuis le tableau ci-dessous et les coller dans la console:

s = [x for x in range(1, 11)]
s
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
t = [x**2 for x in range(11)]
[0, 1, 4, 9, 16, 25, 35, ..., 100]
v = [x for x in s if x% 2 == 0]
[2, 4, 6, 8, 10]
m = [[0 for x in range(3)] for y in range(3)]
m
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]