Propagation d'un feu de forêt |
Il s'agit d'un automate cellulaire et l'algorithme original revient à Pierre Audibert, professeur d'informatique à l'Université de Paris 8. Ces merveilleux supports de cours sont accessibles uniquement sur papier au secrétariat d'informatique de l'UFR 6 : AUDIBERT Pierre, Ordre et chaos, fractales, pavages, Université de Paris 8, département Informatique, support de cours 2000. AUDIBERT
Pierre, Algorithmes et programmation, applications en combinatoire,
probabilités, théorie des nombres, géométrie,
Université de Paris 8, département Informatique, support
de cours 1995, 1997, 1999. |
|
|
TELECHARGER aaaTexte des explications, aaaExecutable (Windows), aaaSource (utilise la librairie Allegro)
|
|
EXPLICATIONS 1. Principe L’automate cellulaire
fait évoluer un plan en soumettant chaque position qui le constitue
à des lois de transition. Ces lois se fondent sur le voisinage
des positions entre elles, nombre de voisins, qualité des voisins
etc. Là il s’agit de représenter un phénomène
de propagation, le feu dans une forêt. 2 Mise en forme et initialisations Tout
d’abord, la forme de l’espace est une matrice de int «
P » (Plan) et sa taille est définie par deux macros. Le fonctionnement
réclame une seconde matrice « NP » (Nouveau Plan) en
miroir de la première afin de stocker les résultats de la
transition pour l’ensemble des positions. Ce sont au début
du programme les déclarations : Les
différentes valeurs possibles pour chaque position sont isolées
avec trois macros : Sur
le plan visuel les arbres sont représentés par des carreaux
de couleur sur l’écran et l’affichage est facilité
par une série de macros utilitaires. Avec la taille de l’écran,
il y a la définition d’une longueur « pasx »
et d’une hauteur « pasy » des carreaux. Elles correspondent
au rapport entre la taille de l’écran et la taille de la
matrice : Reste
encore deux macros pour la définition d’une densité
des arbres lors de l’initialisation de la forêt. Toutes ces
valeurs sont modifiables facilement pour toutes sortes de tests : Enfin,
trois variables globales. Une palette, une image intermédiaire
(Nous optons pour un double buffering) et un entier pour compter le nombre
des arbres en feu. L’initialisation des bois consiste à parcourir la matrice P et pour chaque position attribuer soit la valeur BOIS en fonction de la valeur de SEUIL, soit la valeur 0. C’est la fonction « init_bois » : (1)aaaavoid
init_bois( void ) (2)aaaa
for
( i = 0; i < TX; i++ ) (3)aaaaaaaaaahasard
= rand( )%MAXI; (1) « init_bois » ne prend pas d’argument et ne renvoie rien. (2) Boucles for imbriquées qui donne accès à chaque position de la matrice. (3) Affectation de la valeur de retour de l’appel de la fonction « rand » à la variable « hasard ». Ensuite comparaison de hasard à la valeur de SEUIL. Si hasard est inférieur alors la position ( i, j ) dans la matrice prend la valeur BOIS, sinon elle prend la valeur 0. Initialisation du feu En ce qui concerne le feu un front est allumé en bordure gauche de l’écran. C’est la fonction « init_feu » : (1)aaaaint
init_feu(void) (2)aaaaafor
( i = 1, j = 0, cmpt = 0; j < TY; j++ ) (4)aaaareturn
cmpt; (1) « init_feu » ne prend pas d’argument mais renvoie un entier. (2) La boucle for permet de parcourir une colonne. La position horizontale i reste toujours la même, à 1 du bord, et toutes les positions verticales sont passées en revue. Pour chacune, si elle vaut BOIS elle passe à FEU et une variable compte tous les passages à FEU. (3)
Deuxième boucle dont la vocation est la recopie de la matrice P
dans la matrice NP à l’aide de la fonction « memcpy
». La copie est faite ligne par ligne. Rappelons en effet que la
première taille d’une matrice donne le nombre de lignes et
la seconde le nombre de colonnes. Le nombre des lignes correspond ici
à la taille horizontale et le nombre de colonne à la taille
verticale. Mais nous aurions pu écrire également en une
seule ligne : (4) Pour finir, le compte du nombre de feux est renvoyé à la fonction appelante.
Fonction de propagation Le feu se communique des cellules sur FEU aux cellules sur BOIS voisines. Les cellules sur FEU passent ensuite sur CENDRE. La fonction de propagation est la suivante : (1)aaaavoid
propagation(void) (4)aaaaaaaaaafor
( j = 0; j < TY; j++ ) { (5)aaaaaaaaaaaaaif
( P[ i ][ j ]== BOIS ) { aaaaaaaaaaaaaaaaaaa
aaNP[
i ][ j ] = FEU; (1) « propagation » ne prend pas d’argument et ne renvoie rien. (2) Outre les variables i et j utilitaires pour passer en revue les positions de la matrice avec les boucles for imbriquées, quatre autres variables entières vont servir à désigner les positions adjacentes (est, nord, ouest, sud) à la position ( i, j ) courante. (3) Première boucle
for qui passe en revue toutes les lignes de la matrice. Les positions
adjacentes ( i + 1 ) et ( i – 1 ) sont conservées respectivement
dans les variable « ia » et « ib ». C’est
surtout pour une question de clarté du code. Notons que nous optons
pour un écran circulaire, c’est-à-dire que le débordement
d’un côté se retrouve de l’autre côté.
(4) Deuxième boucle for, imbriquée dans la première, avec cette fois les positions adjacentes verticales stockées respectivement dans ja et jb pour vers le bas et vers le haut. Le principe de contrôle est le même que pour la position horizontale, mais cette fois c’est la hauteur TY qui est utilisée. (5) Au centre de l’imbrication
des deux boucles, le test pour connaître la valeur de la position
courante ( i, j ) si sa valeur est BOIS un second test est effectué
pour connaître si une cellule voisine est sur FEU. Si oui, la cellule
de la position courante passe sur FEU à la même position
dans la matrice miroir NP qui accueille les résultats. Ensuite
le compteur de feux est incrémenté de un. (6) Une fois que toutes les positions ont été regardées et les valeurs modifiées sauvées dans la matrice miroir NP il faut recopier les résultats obtenus de la matrice NP vers la matrice P afin de recommencer le processus avec la nouvelle configuration. La recopie est faite ligne par ligne et avec la fonction memcpy. Boucle du processus La boucle du processus, à placer dans la fonction « main » après les initialisations d’usage, est la suivante : aaa aaa(…) (1)aaaacmpt_feu=0; (3)aaaaaaaif
( key[KEY_ENTER]){ aaaaaaa(…)
(2) Comme souvent c’est une boucle while qui se termine avec la pression de la touche échap du clavier de l’ordinateur. Dans cette boucle il y a deux tests. (3) Le premier test a pour objectif de permettre des initialisations et de relancer l’action lorsqu’un feu est fini. Il porte sur la pression de la touche « entrée ». Si oui la première fonction appelée est init_bois pour l’initialisation de la forêt. Ensuite c’est la fonction « init_feu » et le nombre de feux allumés renvoyés est affecté à la variable « cmpt_feu ». (4) Si la variable cmpt_feu est différente de zéro, c’est-à-dire s’il y a des feux allumés, la propagation a lieu. Le calcul est fait une fois et la matrice P modifiée est affichée dans la bitmap intermédiaire « page » . C’est le rôle de la fonction « affiche_plan » vue plus haut. Enfin la bitmap « page » est affichée à l’écran. Lorsqu’il n’y a plus de feu, l’action s’arrête sur la dernière image et peut être relancée avec une nouvelle initialisation en pressant la touche entrée. Fonction d’affichage La fonction « affiche_plan » prend une bitmap de référence. Toutes les positions de la matrice P sont passées en revue et chacune d’elles est représentée par un rectangle de longueur pasx et hauteur pasy aux positions « i * pasx » et « j * pasy » définies par les macros X et Y. La couleur est celle de la position. Notons qu’il n’y a besoin que de trois couleurs, celle du fond, celle des bois, celle du feu et celle des cendres. Elles vont correspondre aux indices 1, 2, 3 d’une palette à créer avant la boucle. aaaavoid
affiche_plan(BITMAP *bmp) aaaaaaaclear(
bmp ); |
|