deutsch     english    français     Print

 

8.9 GROUP DYNAMICS

 

 

INTRODUCTION

 

Systems with many partners that interact with each other are widely used. Computer programs can often simulate such systems with surprisingly little effort, since the computer can store anywhere from thousands to millions of single individual states and temporally track them. However, if we deal with atomic many-body systems with a numbers of particles in the order of 1023, computers reach their limits. To simulate such systems, we need to use simplifying procedures, such as dividing the system into several larger cells. Examples for this include the simulation of Earth's atmosphere for weather forecast and the prediction of long-term climate change.

PROGRAMMING CONCEPTS: Computer simulation, population dynamics, swarming behavior

 

 

CONWAY'S GAME OF LIFE

 

Conway's Game of Life examines a two-dimensional grid-like arrangement of individuals (green squares), where each individual interacts with its 8 nearest neighbors. It was proposed by the British mathematician John Conway in 1970, and it made him famous outside of the mathematics world as well. Almost all scholars have at least an idea of what the Game of Life is. Here you will program it yourself with Python.

The population is arranged in cells and evolves in discrete time steps  (generations). Each cell can be either living or dead.
 

When transitioning to the next generation, the current state is saved and the following state of each cell is determined based on its 8 nearest neighbors by the following four transition rules:

1.
If the cell is living, it dies if it has fewer than two living neighbors (isolation)
2.
If the cell is living, it continues to live if it has two or three living neighbors (group cohesion)
3.
If the cell lives, it dies if it has more than three living neighbors (overpopulation)
4.
If a cell is dead, it will come back to life when it has exactly three living neighbors (reproduction). Otherwise, it stays dead.

The cell structure of GameGrid is ideal for implementing the game. You use a two-dimensional list a[x][y] for the population, where the value 0 is a dead cell and 1 is a living cell. The simulation cycle is regarded as a generation cycle, and the current population from the list a is copied into the new population b in the callback onAct() and will finally be regarded as the current list. You choose 1,000 random living cells in the callback onReset(), which is called by clicking on the reset button.

In order to activate the callbacks, you have to register them with registerAct() and 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()
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

The Game of Life is an example of a cellular automaton, consisting of grid cells that interact with each other. They are perfectly suited to study the behavior of complex natural systems. Some examples are:

  • biological growth, emergence of life
  • social, geological, ecological behavior
  • traffic volume and control
  • formation and evolution of the cosmos, of galaxies and stars

In 2002, Stefan Wolfram, the scientist and chief developer of Mathematica pointed out in his well known book "A New Kind of Science" that such systems can be investigated with simple programs. With computer simulations, we are at the beginning of a new era of gaining scientific knowledge.

During the initialization of the two-dimensional list, a special Python syntax called list comprehension is used (see addional material).

 

 

SWARMING BEHAVIOR

 


As you know from your daily life, large groups of living beings often have the tendency to team up together in groups. This can be observed particularly well in birds, fish, and insects. A group of demonstrating people also shows this "swarming behavior". On the one hand, outside (global) influences play a role in the formation of a swarm, but the interaction between partners in their close surroundings (local influences) also play a role.

In 1986 Craig Reynolds showed that the following three rules lead to a swarm formation between individuals (he called them Boids):

1.
Cohesion rule: Move towards the center (median point) of the individuals in your neighborhood
2.
Separation rule: Move away if you get too close to an individual
3.
Alignment rule: Move in approximately the same direction as your neighbors

To implement this, you use JGameGrid again in order to keep the effort of the animation low. It helps to use a grid with pixel sizes and to specify the position, velocity, and acceleration of the actors with float vectors from the class GGVector. In each simulation period you first determine the new acceleration vector according to the three rules using setAcceleration(). This results in the new velocity and position vectors

and

Since the absolute time scale is insignificant, you can set the time increment to dt = 1.

Applying the separation rule not only leads to a rejection between the closely flying birds, but also between them and obstacles (in this case, trees).

You have to particularly deal with the edge of the flying area (the wall). For this, there are various possibilities to choose from. You could, for example, use a toroidal topology, where the birds leaving the area on one side enter it again on the other. In this case, the birds are simply forced to turn around at the edge.

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()
Highlight program code (Ctrl+C to copy, Ctrl+V to paste)

 

 

MEMO

 

The simulation is dependent on several coupling constants that determine the "strength" of the  interaction. Their values are very sensitive and you may eventually need to adjust them to the performance of your computer.

Again, the callback onAct() is activated using registerAct() so that it is automatically called in every simulation cycle. The birds are moved with the method act() of the class bird.

 

 

EXERCISES

 

1.


Study the behavior of the following patterns in Game of Life:

a. b. c.
           
d. e.    

2.


Describe three typical swarm behaviors that occur in the animal world. For each example, think about why the animals join together in a swarm.


3*.


In the swarm simulation, introduce three raptors who follow a flock of birds that they are avoided by. Instructions: For the raptors, use the sprite image arrow2.png.


4*.


Make it so that the raptors from exercise 3 eat the flock birds at a collision.

 

   

ADDITIONAL MATERIAL


 

LIST COMPREHENSION

 

Lists can be created neatly in Python with a special notation. It is based on mathematical notation from set theory

Mathematics Python
S = {x : x in {1...10}} s = [x for x in range(1, 11)]
T = {x2 : x in {0...10}} t = [x**2 for x in range(11)]
V = {x | x in S und x gerade} v = [x for x in s if x % 2 == 0]
m = [[0 for x in range(3)] for y in range(3)]

Use the console to test the Python expressions. You can copy them from the table and paste them into the 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 iff 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]]