Le code dans cet article a été écrit avec Code::Blocks et la SDL 2.
Vous pouvez trouver
ici un guide pour installer ces logiciels.
Bien qu'il soit basé sur la SDL, je n'utilise pas ses fonctions directement. J'ai écrit une petite bibliothèque
avec quelques fonctions basiques pour faciliter la compréhension et la portabilité dans un autre langage.
Vous pouvez en apprendre plus sur cette bibliothèque
ici.
En 1971 Thomas Schelling a écrit un article à propos de la distribution de la population dans une ville.
La ville est représentée par une grille où chaque case peut soit être vide ou contenir un des 2 types "d'agents"
(rouge ou vert).
A chaque tour on sélectionne un agent et une case vide au hasard.
L'agent peut décider de déménager dans la case vide ou pas.
Sa décision est basée sur son voisinage.
Dans les 8 cases voisines, on compte le nombre d'agents de chaque couleur.
Un des paramètres du jeu est le coefficient de "ressemblance" des agents.
Disons que ce coefficient est à 30%.
Notre agent sera "heureux" si dans son voisinage il y a au moins 30% d'agents de la même couleur que lui.
Si notre agent est malheureux dans la case courante et qu'il serait heureux dans la vide, alors il décidera de
déménager dans cette case.
Au bout d'un moment le système se stabilise, et même si les règles disent que les agents sont plutôt tolérants, on
devrait les voir se regrouper avec d'autres agents de la même couleur qu'eux.
La population a l'air plus cloisonnée que mélangée.
Cette simulation peut avoir l'air simple, mais c'est un bon exercice de programmation parce qu'elle cache des
difficultés qui sont typique de ce type de jeux.
Définition des paramètres
On va utiliser une grille carrée de 30*30 cases.
#define NB_CELLS 30
#define CELL_SIZE (SCREEN_HEIGHT / NB_CELLS)
On aura besoin de la fraction de cases vides dans cette grille
#define EMPTY 0.1 // % of empty cells
La proportion de cases rouges
#define RED_RATIO 0.5 // % of red in the initial state
Et le coefficient de ressemblance.
#define LIKENESS 0.3 // % of wanted neighbors of the same color
La grille sera stockée dans un tableau d'entiers qui pourra contenir 0 pour une case vide, 1 pour un agent rouge ou
2 pour un vert.
int grid[NB_CELLS][NB_CELLS];
// initialize the grid
for (int y = 0; y < NB_CELLS; y++)
for (int x = 0; x < NB_CELLS; x++)
grid[x][y] = 0;
Et on va utiliser une palette pour ces 3 valeurs.
// initialize the palette
Color palette[3];
palette[0] = Color( 70, 70, 70); // empty cell
palette[1] = Color(220, 0, 0); // red
palette[2] = Color( 0, 150, 0); // green
Mise en place de la grille
Pour afficher la grille, j'ai écrit une fonction pour dessiner un rectangle plein
void CGfx::rectFill(int x0, int y0, int x1, int y1, Color c)
{
for (int y = y0; y < y1; y++)
for (int x = x0; x < x1; x++)
gfx.setPixel(x, y, c);
}
J'ai aussi écrit une fonction pour les rectangles vides, mais on ne va pas l'utiliser.
Maintenant essayons d'afficher la grille.
// draw the grid
for (int y = 0; y < NB_CELLS; y++)
for (int x = 0; x < NB_CELLS; x++)
{
gfx.rectFill( x * CELL_SIZE, y * CELL_SIZE,
(x + 1) * CELL_SIZE - 2, (y + 1) * CELL_SIZE - 2,
palette[grid[x][y]]);
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ca donne ce résultat:
Ensuite, comment va-t-on remplir cette grille en respectant le ratio de cases vides et le ration rouge/vert ?
Disons qu'on a un ratio rouge/vert de 50/50 et que 10% de la grille est vide.
Si on commence par remplir la grille en suivant le 50/50, et qu'ensuite on "vide" 10% des cases aléatoirement, on
ne peut pas être surs que le 50/50 sera toujours respecté.
Alors on va commencer avec une grille vide et on remplira seulement le nombre de case occupées, qui est:
int nbOccupied = NB_CELLS * NB_CELLS * (1 - EMPTY); // number of occupied cells
Maintenant, comment remplit-on les cases occupées en respectant le ratio rouge/vert ?
Si on choisit au hasard la couleur de la case qu'on ajoute, on ne peut pas être sur que le ratio final sera bon.
Alors on doit calculer combien de cases rouge il nous faut:
int nbRed = nbOccupied * RED_RATIO; // number of red cells
Et quand on va remplir les nbOccupied cases, les nbRed premières seront rouges. Le reste sera vert.
On a juste besoin d'ajouter une boucle pour choisir des cases au hasard jusqu'à en trouver une vide.
for (int i = 0; i < nbOccupied; i++)
{
// find an empty cell
while (true)
{
int x = rand() % NB_CELLS;
int y = rand() % NB_CELLS;
if (grid[x][y] == 0)
{
// fill the cell
if (i < nbRed)
grid[x][y] = 1;
else
grid[x][y] = 2;
break;
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code produit le même résultat que la première image de cet article.
Maintenant, on va choisir au hasard une case vide
// find an empty cell
int xEmpty, yEmpty;
while (true)
{
xEmpty = rand() % NB_CELLS;
yEmpty = rand() % NB_CELLS;
if (grid[xEmpty][yEmpty] == 0)
break;
}
Et une pleine
// find an occupied cell
int xOccupied, yOccupied;
while (true)
{
xOccupied = rand() % NB_CELLS;
yOccupied = rand() % NB_CELLS;
if (grid[xOccupied][yOccupied] != 0)
break;
}
Ensuite, pour décider si l'agent va aller dans la case vide, on a besoin de calculer s'il est "heureux" dans
chacune des 2 cases.
Alors on va écrire une autre fonction pour compter les voisins d'une case.
La fonction pour compter les voisins prendra en paramètres les coordonnées de la case et la couleur de l'agent
qu'on a sélectionné.
On a besoin de passer la couleur parce que quand on va compter les voisins de la case vide on ne pourra pas la
retrouver facilement.
Le but de cette fonction va être de compter le nombre de voisins de la même couleur et celles de la couleur
opposée.
Et elle retournera le rapport entre les 2 qu'on comparera au coefficient de ressemblance.
float countNeighbors(int xCell, int yCell, int color)
{
// count neighbors
int nbSame = 0;
int nbOther = 0;
On va boucler de -1 à 1 sur les deux axes et ajouter ces valeurs aux coordonnées de la case pour avoir les
coordonnées des voisins.
Mais on ne prendra pas en compte la case courante (quand xi = 0 et yi = 0).
for (int yi = -1; yi <= 1; yi++)
for (int xi = -1; xi <= 1; xi++)
{
// don't count the center
if (xi == 0 && yi == 0)
continue;
int x = xCell + xi;
int y = yCell + yi;
On ne compte pas les cases qui sont en dehors de la grille non plus.
// check if we are not outside of the grid
if (x < 0 || x >= NB_CELLS ||
y < 0 || y >= NB_CELLS)
continue;
Et on ne compte pas les cases vides...
// empty cell ?
if (grid[x][y] == 0)
continue;
Enfin on peut incrémenter les compteurs
// count
if (grid[x][y] == color)
nbSame++;
else
nbOther++;
}
Maintenant on peut retourner le ratio. Mais attention, ce n'est pas le ratio de nbSame sur nbOther, mais le ratio
de nbSame sur le nombre de cases occupées, soit (nbSame + nbOther):
return (float)nbSame / (float)(nbSame + nbOther);
Mais il y a un autre piège ici. On ne peut pas diviser par zéro, alors on doit tester ça avant de retourner notre
valeur:
if (nbSame + nbOther == 0)
return 0.0;
De retour dans la boucle principale, après qu'on ait choisi la case occupée et la vide, maintenant on peut décider
si notre agent doit déménager.
D'abord on va calculer sa ressemblance courante:
// current likeness
int color = grid[xOccupied][yOccupied];
float likeOld = countNeighbors(xOccupied, yOccupied, color);
Ensuite on peut tester si il est malheureux
// is unHappy ?
if (likeOld < LIKENESS)
{
Si c'est le cas, on peut calculer la ressemblance qu'il aurait s'il était dans la case vide
// new likeness
float likeNew = countNeighbors(xEmpty, yEmpty, color);
Enfin, s'il serait heureux à cet endroit, on le fait bouger.
// want to move ?
if (likeNew >= LIKENESS)
{
grid[xEmpty][yEmpty] = color;
grid[xOccupied][yOccupied] = 0;
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code a tendance à donner le résultat qu'on a décrit au début.
Mais il devient de plus en plus lent, et on ne sait même pas à quel moment il a terminé.
On va essayer de résoudre ces problèmes tout de suite.
Le programme précédent ralentit parce qu'il choisit au hasard un agent, puis il essaye de voir s'il peut déménager.
Mais cet agent ne déménagera que s'il est malheureux. Et au cours de l'exécution du programme, il y a de moins en
moins d'agents qui sont malheureux.
Alors on va modifier le fonctionnement du programme.
Dans la boucle principale, à chaque frame, on va remplir un tableau qui nous dira si chaque agent est heureux.
En même temps, on va compter le nombre d'agents malheureux et la ressemblance moyenne.
bool happy[NB_CELLS][NB_CELLS];
[...]
// fill happy table
int nbUnhappy = 0;
float meanLikeness = 0.0;
for (int y = 0; y < NB_CELLS; y++)
for (int x = 0; x < NB_CELLS; x++)
{
happy[x][y] = true;
if (grid[x][y] != 0)
{
float like = countNeighbors(x, y, grid[x][y]);
meanLikeness += like;
if (like < LIKENESS)
{
happy[x][y] = false;
nbUnhappy++;
}
}
}
printf("likeness: %f%% unhappy: %f%%\n", meanLikeness * 100.0 / (float)nbOccupied, (float)nbUnhappy * 100.0 / (float)nbOccupied);
De cette facon on saura quand le programme a fini parce que le nombre d'agents malheureux va tendre vers 0.
Ensuite, au lieu de prendre un agent au hasard, on va en choisir un qui est malheureux.
// find an unhappy cell
int xOccupied, yOccupied;
while (true)
{
xOccupied = rand() % NB_CELLS;
yOccupied = rand() % NB_CELLS;
if (happy[xOccupied][yOccupied] == false)
break;
}
Et le processus de décision sera alors simplifié:
// new likeness
int color = grid[xOccupied][yOccupied];
float likeNew = countNeighbors(xEmpty, yEmpty, color);
// want to move ?
if (likeNew >= LIKENESS)
{
grid[xEmpty][yEmpty] = color;
grid[xOccupied][yOccupied] = 0;
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Ce code a l'air plus rapide même si j'ai agrandi la grille à 40*40 et que j'ai ajouté un sys.wait(50) dans la
boucle principale !
Pourtant on fait beaucoup plus de calculs à chaque frame, parce que l'on compte les voisins de tous les agents au
lieu du seul qu'on a sélectionné.
Mais c'est le genre de choses qui arrive quand un algorithme fait des choix au hasard. Parfois, faire plus de
calculs pour réduire l'aléatoire peut être payant.
Il y a d'autres techniques pour rendre ce programme encore plus rapide. J'en parlerai peut-être dans un autre
article.
Et maintenant on a un autre avantage: on peut savoir si le programme a vraiment terminé en regardant le nombre
d'agents malheureux.
Avec les paramètres qu'on a choisis ce nombre descend à 0 après un peu de temps. Et voici un exemple de l'état
final de la grille:
On peut clairement voir le regroupement. A la fin la ressemblance moyenne est environ 75%, alors que chaque agent
demandait seulement un minimum de 30% !
Maintenant, jouons avec les paramètres pour voir ce qui se passe.
Si on met la proportion de rouges à 0.3, le pourcentage d'agents malheureux ne descendre probablement pas en
dessous de 6%.
Parce que ça devient de plus en plus difficile pour les rouges de trouver une place adéquate pendant que les verts
ne bougent pas parce qu'ils sont heureux où ils vivent.
C'est probablement une autre leçon à tirer si vous voulez être maire: quoi que vous fassiez, il y aura probablement
des gens qui ne seront jamais contents de leur voisinage.
Voici un exemple de ce qu'on obtient quand le programme se stabilise:
Si on revient à 50% de rouges et qu'on met le coefficient de ressemblance à 0.5, on obtient une ségrégation encore
plus évidente.
Avec un coefficient de ressemblance de 0.6 un autre comportement intéressant apparait: les cases vides sont
ordonnées de telle sorte qu'elles agissent comme des "murs" entre les 2 groupes. Ici on atteint une ressemblance
moyenne de 96%.
Ajouter une 3ième couleur à cette simulation n'est pas difficile.
Disons qu'on veut ajouter des agents bleus.
D'abord on aura besoin d'une entrée dans la palette pour cette nouvelle couleur:
palette[3] = Color( 20, 20, 255); // blue
Ensuite on aura besoin du ratio qu'on va utiliser pour remplir la grille au départ:
#define RED_RATIO 0.333 // % of red in the initial state
#define BLUE_RATIO 0.333 // % of blue in the initial state
[...]
int nbOccupied = NB_CELLS * NB_CELLS * (1 - EMPTY); // number of occupied cells
int nbRed = nbOccupied * RED_RATIO; // number of red cells
int nbBlue = nbOccupied * BLUE_RATIO; // number of blue cells
for (int i = 0; i < nbOccupied; i++)
{
// find an empty cell
while (true)
{
int x = rand() % NB_CELLS;
int y = rand() % NB_CELLS;
if (grid[x][y] == 0)
{
// fill the cell
if (i < nbRed)
grid[x][y] = 1;
else if (i < nbRed + nbBlue)
grid[x][y] = 3;
else
grid[x][y] = 2;
break;
}
}
}
Télécharger le code source
Télécharger l'exécutable pour Windows
Et c'est tout.
Voilà le résultat:
Vidéo: Exposé à propos de cette simulation à l'Université du Michigan