(novembre 2015) Simulation d'un feu de forêt

a marqué ce sujet comme résolu.

Bonjour à tous.

Dans ce défi je vous propose de réaliser une simulation de feu de forêt à travers un modèle simple (pour ne pas dire simpliste). Si vous vous fichez des histoires de percolation et que vous voulez simplement programmer, vous pouvez sauter la section suivante.

La percolation

La percolation désigne l’idée de passer au travers. L’exemple typique est celui du café. Pour faire du café (la boisson), il faut faire passer de l’eau dans du café (la graine) moulu. Une solution consiste à mettre le café dans un filtre et faire passer l’eau dedans ; en passant, elle va se charger en poudre de café. Si vous serrez le filtre plus fortement, l’eau mettra plus de temps pour traverser le café moulu, et la boisson finale sera plus forte. Cependant, si vous serrez trop, l’eau ne passera plus : la percolation n’a plus lieu.

On voit ici apparaître un seuil. En deçà, l’eau passe, au delà, non. L’existence d’un seuil est très général dans les cas de percolation. Si vous voulez en savoir plus sur la percolation, notamment du point de vue mathématique, je vous redirige vers l’article de Hugo Duminil-Copin.

Dans le cas d’une simulation de feux de forêt, le seuil de percolation sera vue ainsi : si, partant d’un incendie originel, la forêt brûle presque entièrement, il y a percolation. Si seule une petite zone brûle, il n’y a pas percolation. Cette transition est très nette. Dans la cas d’une forêt pleine sur un réseau carrée, elle a lieu si la probabilité de propagation de l’incendie est de 0,5. Typiquement, sur un réseau 2D de 100x100, le nombre moyen d’arbre brûlé passe de moins de 100 (moins de 1%) à plus de 9000 (plus de 90%) quand cette probabilité passe de 0,4 à 0,6. Pour des compléments, ainsi que quelques résultats théorique, je vous renvoie vers un mémoire très propre sur le sujet.

La simulation

Pour commencer, on va considérer une grille. Chaque case de la grille pourra contenir soit des cendres, soit un arbre, soit un arbre en feu. Elles contiennent toute à la base un arbre.

On remplace le contenu de l’un des cases (choisie aléatoirement) par un arbre en feu.

La règle de propagation de l’incendie est la suivante : on considère une case en feu. Chacun de ses voisins, si c’est un arbre, à une probabilité p (déterminée à l’avance, c’est le paramètre de notre simulation) de devenir un arbre en feu. Une fois tous les voisins testés, la case considérée devient des cendres. On teste alors la case en feu suivante.

Le programme se termine quand plus aucune case n’est en feu. L’information utile est typiquement la proportion d’arbre ayant brûlé.

Résultats typique de deux simulations à p=0,45 et p=0,55.
Exemple de simulations. Ici, le vert désigne des arbres et le gris des cendres. La grille fait 250 par 250 cases. À gauche, p=0,45 ; la zone ayant brûlé fait 13 cases de côté. À droite, p=0,55 ; la plus grande zone n’ayant pas brûlé fait 33 cases de côté.

Attention à ce qui se passe aux bords ! Pour éviter les problèmes, le plus simple est de placer dans chacune des cases aux bords des cendre plutôt qu’un arbre (mais il ne faudra pas les compter dans le calcul de la proportion d’arbres brûlés).

Pour améliorer le modèle, on peut imaginer les situations suivantes :

  • La bords sont constituée d’arbre, mais le bord gauche est accolé au bord droit, et le haut en bas. Autrement dit, on travaille sur un tore. En physique, on parle de condition aux bords périodiques ;
  • La forêt est parsemée de trou : une partie des cases est constituée de terrain vague qui ne brûle pas. Prenez garde à la manière dont vous calculez la proportions d’arbre brûlé ;
  • Le réseau est hexagonal au lieu de carré.

Vous pouvez aussi faire une sortie graphique, même si la proportion d’arbre ayant brûlé est suffisant pour ce défi.

Bien sûre, on voudrait théoriquement faire des statistiques sur nos simulations, donc s’assurer qu’elles sont efficaces. Si vous trouvez ce défi trop simple, n’hésitez pas à chercher à faire quelque chose d’efficace. Un système un peu grand (1000 par 1000) avec un p proche mais supérieur de 0,5 donne déjà une simulation assez lente.

Un défi plus corsé

Vous trouvez la simulation précédente trop facile ? Dans ce cas, je vous propose une autre simulation de percolation plus compliquée, en particulier dans l’analyse des résultats. Une version plus détaillé de ce problème a été présentée par GéoMl17, alias Micmaths, sur Openclassrooms.

Réseau de segment percolant
Réseau de segment percolant, CC BY SA, par Erzbischof, source.

On considère un réseau de point régulièrement espacé, et on s’intéresse aux segments qui relient les points. Ils ont une probabilité p d’être plein, et 1-p d’être vides. On applique cela pour chaque segment. Si p est grand, on pourra passer de quasiment n’importe quel segment plein à n’importe quel autre. Si p est plus faible, on va avoir des domaines au sein desquels on peut se déplacer, mais qui ne sont pas liés entre eux. Le but est d’identifier les domaines en question.

Dans ce modèle, il y a percolation par exemple s’il est possible de passer de gauche à droite (ce qui est équivalent à dire que l’on ne peut pas passer de haut en bas en sautant de segments vides en segments vides)

Pour ce faire, vous pouvez vous inspirez de ce qui existent pour les recherches de chemin ou les parcours… d’arbre.

Sur ce, n’hésitez pas à montrer votre code, ou à poser des questions, que ce soit sur la percolation ou sur l’implémentation des simulations.

Les codes

Ici seront ajoutés les différents codes proposés, classés par langage.

Ada

vaati

C

fromvega, variante à 6 états (2 brulant, 2 ne brulant pas, le feu et les cendres). Images disponibles.

Nodraak

yoch, avec des détail sur le côté algorithmique.

C++

Berdes, en utilisant un automate cellulaire.

Olybri, jolie animation avec la SFML.

Raymo, parallélisation avec openMPI.

S-sonic`, affichage en temps réel avec la SFML.

Olive.

C#

ThuleMalta, avec affichage.

Coffeescript

Umbra

Excel

AurelB. Avec Excel… En VBA. Le code.

Fortran

Gabbro, tentative d’usage des forall sur un modèle avec des trous placés aléatoirement, et une probabilité de brûler fixée à 1 (inspiré par yoch).

Haskell

AlphaZeta

Javascript

luuka, avec une démo live.

Python

Aabu, avec un lac. :D

Folaefolc, modèle de base avec affichage.

Gabbro, modèle de base uniquement (code ayant servi a générer les premières images du défi).

klafyvel, avec affichage.

yoch, une variante avec des trous placés aléatoirement, et une probabilité de brûler fixée à 1.

Scheme

kelepoc, version épidémiologie.

Windev

elegence, avec des trous.

+20 -0

En aucun cas !

L'information utile est typiquement la proportion d'arbre ayant brûlé.

Cette information est suffisante pour savoir s'il y a ou non percolation. Ce que tu appelles interface graphique dans mon cas, c'est juste une image qui est créé avec 10 lignes de python. :D

D'ailleurs, voici un code python pas efficace du tout (c'est avec lui que j'ai généré les images du dessus), mais j'espère assez lisible, qui fait la version ultra-basique de la simulation, avec en sortie la proportion d'arbre brûlé, et un jolie nimage.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# /usr/bin/env python3
# coding: utf-8

"""Simulation de percolation dans le cadre des feux de forêt.
Cette version est a deux paramètres :
- la probabilité *p* que le feux se propage
- *l* la taille du système.
Les conditions aux bords sont fermées (_open boundary_) et aucun parallélisme ne sera tenté.
Entrée : aucune ;
Sortie : flottant entre 0 et 1, r, proportion d'arbre restant après l'incendie.
         et une image.
"""

def voisins(case):
    """Renvoie les voisins de la case via un générateur."""
    x=case[0]
    y=case[1]
    yield x+1,y
    yield x-1,y
    yield x,y+1
    yield x,y-1
    
from PIL import Image, ImageDraw
import numpy as np
from random import randint, random
p = 0.55
l = 250

monde = np.zeros((l, l), dtype=int) #Convention : 0 = arbre, 1 = feu, 2 = cendre
#Conditions aux limites: on entoure de cendre
monde[0:,0] = 2 ; monde[0:,l-1] = 2 ; monde[0,0:] = 2 ;monde[l-1,0:] = 2 

monde[randint(1,l-2), randint(1, l-2)] = 1 #1er feu

#On continue tant qu'il reste du feu (1) sur la grille.
while 1 in monde:
    #Boucle principale
    en_feu = []
    #Recherche des cases en feu, de manière pas du tout optimale.
    for i in range(1,l):
        for j in range(1,l):
            if monde[i,j] == 1:
                en_feu.append((i,j))
    #Enflammement des arbres.
    for case in en_feu:
        for voisin in voisins(case):
            #va tester chaque voisin tels que définis dans la fonction.
            if monde[voisin] == 0 and random()<p:
                monde[voisin] = 1
        monde[case] = 2

#Post-traitement
restant = 0
#Création d'une image
img = Image.new('RGBA', (l, l), (255,255,255,0))
d = ImageDraw.Draw(img)
for i in range(0,l):
    for j in range(0,l):
        if monde[i,j] == 0:
            #En passant, on regarde combien d'arbre il reste.
            restant += 1
            d.rectangle((i, j, i+1, j+1), (0, 150, 50, 255))#vert
        else:
            #Le cas "feu" n'est pas possible.
            #Si ce n'est pas un arbre, c'est donc des cendres.
            d.rectangle((i, j, i+1, j+1), (50, 50, 50, 255))#gris
print(restant/(l-2)**2)#Proportion d'arbre restant.
img.save("perco_arbre"+str(p)+".png", "PNG")

+0 -0

Voici une solution dans un langage pas très courant : Windev.

C'est effectivement impressionnant de voir comment les résultats peuvent être très différents, selon que le seuil est à 0.45 ou 0.55 par exemple.

Je galère pour poster le code en 'contenu masqué' … je vais donc ouvrir un thread dédié , pour éviter d'avoir un code en clair ici.

thread dédié

+1 -2

Par contre elegance, on ne peut pas créer un topic pour chaque code proposé, ça risque rapidement de devenir un bazar immonde dans le forum Programmation. Tu devrais t'en sortir en suivant les instructions de Folaefolc. Sinon, tu peux quand même poste ton code en clair.

Salut,

Je me suis amusé avec Python, que je découvre plus ou moins.

J'ai fait une petite forêt avec un lac au milieu.

Forêt avec un petit lac

Et ensuite j'ai regardé la proportion d'arbres restants pour différentes probabilités de propagation. Je retrouve le résultat théorique d'un des liens ci-dessus, avec une inflexion à 0.25. Sur la courbe ci-dessous, les ordonnées sont les proportions d'arbres restants, et l'abscisse est la probabilité.

Probabilité en abscisse, proportion d'arbres restants en ordonnée

Et le code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import sys
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import colors

# Pour s'épargner des "RuntimeError"
sys.setrecursionlimit(3000)

# Paramètres
taille_zone = 50,50

# Constantes
CENDRE = 0
ARBRE = 1
EAU = 2

# ALLUUUMEEEEEEER LE FEU !
def allumer_le_feu(foret, position, probabilite_embrasement):
   foret[position] = CENDRE
   decalages = [(-1,-1), ( 0,-1), ( 1,-1), ( 1, 0),
               ( 1, 1), ( 0, 1), (-1, 1), (-1, 0)]
   coord_voisins = [(position[0]+x, position[1]+y) for x, y in decalages]
   for v in coord_voisins:
       if (v[0] > 0 and v[0] < taille_zone[0] -1
      and v[1] > 0 and v[1] < taille_zone[1] -1         
      and foret[v] == ARBRE         
      and np.random.rand(1) < probabilite_embrasement):
           allumer_le_feu(foret,v,probabilite_embrasement)

# Une forêt carrée, bordée de cendres, avec un lac au milieu.
def planter_foret():
   foret = np.zeros(taille_zone,dtype='int_')
   foret.fill(CENDRE)
   foret[1:-1,1:-1].fill(ARBRE)
   foret[20:30,20:-10].fill(EAU)
   return foret


# Calcul

nb_echantillons = 60
proba_embrasement = [i/80 for i in range(80)]
proba_embrasement.extend([i/100 for i in range(20,30)])
res_proba = []
res_ratio = []
for proba in proba_embrasement:
   for i in range(nb_echantillons):
       foret = planter_foret()
       nb_arbres_total = np.count_nonzero(foret == ARBRE)
       position_foyer = np.random.randint(0,taille_zone[0]), np.random.randint(0,taille_zone[1])
       allumer_le_feu(foret, position_foyer, proba)
       nb_arbres_restant = np.count_nonzero(foret == ARBRE)
       res_proba.append(proba)
       res_ratio.append(nb_arbres_restant/nb_arbres_total)

# Graphe
plt.plot(res_proba,res_ratio,".")
plt.show()


# Affichage de la forêt initiale

cmap = colors.ListedColormap(['black', 'green','blue'])
bounds=[0,1,2,3]
norm = colors.BoundaryNorm(bounds, cmap.N)
plt.imshow(planter_foret(),interpolation="nearest",cmap=cmap, norm=norm)
plt.show()

Il y aurait plein d'améliorations à faire, comme éviter les effets de bord et régler le problème de la récursivité (parce que Python ne connaît pas vraiment la récursivité terminale).

+2 -0

D'ailleurs, pour les trous, on les place aléatoirement ou pas … ?

Aabu a fait avec un lac (un truc qui brûle pas, que tu l'appelles lac, plaine ou trou, c'est pareil) fixe. On peut aussi les placer aléatoirement. C'est très ouvert comme défi. ^^

Comme le note Aabu, le choix du maillage change le résultat. La percolation a lieu a p=0,5 pour 4 voisins, mais p=0,25 pour 8 voisins.


On m'a demandé des applications concrètes de la percolation. La corrosion est liée à la percolation. Un cas que je connais mieux, c'est en géologie, avec la traversée par l'eau des différentes couches géologiques jusqu'à la nappe phréatique. Ça sert aussi en écologie, la question est de savoir si les animaux peuvent passer d'un lieu de vie (forêt, lac…) à un autre, ou si des obstacles ville, autoroute, champs) les en empêche. C'est un cadre assez général, et il est aussi beaucoup utilisé par les mathématiciens. Wikipedia a un bon article assez court là-dessus.

+2 -0

Je ne sais pas si c'est exactement ce qui était prévu, mais j'ai traité le problème comme un automate cellulaire. J'ai une première version (faite rapidement) qui affiche plusieurs simulations à la suite dans le terminal et qui indique la proportion d'arbre brûlées à la fin.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <thread>

using namespace std::chrono_literals;

void clear() {
  std::cout << "\x1B[2J\x1B[H";
}

enum Cell { Live, Burning, Ashes };

template<int N>
using State = std::array<std::array<Cell, N>, N>;

template<int N>
void print(const State<N>& s)
{
  clear();
  for(const auto &l : s) {
    for(Cell c : l) {
      std::cout <<
        (c == Live ? "T":
         c == Burning ? "B":
         ".");
    }
    std::cout << std::endl;
  }
}

template<int N>
bool update(State<N>& s, double p) {
  State<N> newS{s};
  std::random_device rd;
  std::mt19937 g(rd());
  std::uniform_real_distribution<double> dis(0, 1);
  bool updated = false;

  for(int i=0; i<N; ++i) {
    for(int j=0; j<N; ++j) {
      if(s[i][j] == Burning) {
        if(i > 0 && newS[i-1][j] == Live && dis(g) < p) {
          newS[i-1][j] = Burning;
          updated = true;
        }
        if(i < N-1 && newS[i+1][j] == Live && dis(g) < p) {
          newS[i+1][j] = Burning;
          updated = true;
        }
        if(j > 0 && newS[i][j-1] == Live && dis(g) < p) {
          newS[i][j-1] = Burning;
          updated = true;
        }
        if(j < N-1 && newS[i][j+1] == Live && dis(g) < p) {
          newS[i][j+1] = Burning;
          updated = true;
        }
        newS[i][j] = Ashes;
      }
    }
  }

  std::swap(s, newS);
  return updated;
}

int main() {
  const int size = 60;
  const double p = 0.55;
  const int max_iter = 100;
  int total_burned = 0;

  for(int iter=0; iter<max_iter; ++iter) {
    State<size> state{};
    state[size/2][size/2] = Burning;
    do {
      print<size>(state);
      std::this_thread::sleep_for(20ms);
    } while(update<size>(state, p));
    print<size>(state);
    int burned = 0;
    for(const auto &l : state) {
      for(Cell c : l) {
        if(c == Ashes) {
          burned++;
        }
      }
    }
    total_burned += burned;
  }
  std::cout << "Probability " << p << std::endl;
  std::cout << "Average burning ratio " << (total_burned*100)/(size*size*max_iter) << "%" << std::endl;

  return 0;
}

La prochaine étape serait de modifier l'architecture pour avoir une gestion générique d'un automate cellulaire et pouvoir s’amuser avec d'autres (jeu de la vie, wireworld et autres).

Note : le code actuel ne compile qu'avec C++14.

+1 -0

Bonjour,

J'ai fait un peu différemment que dans l'énoncé: dans mon modèle, seul le placement des arbres est aléatoire (il y a donc toujours des trous), ensuite un arbre en feu brûle systématiquement ses voisins s'ils existent (voisinage à 4 points). Est-ce que ça change quelque chose aux probas (a priori non, mais j'ai l'impression que l'équilibre est un peu au dessus de 0.5, et aussi la quantité d'arbres brulés dépasse rarement 70%) ?

Voici le code (python + pygame) avec 1) grilles rectangulaires, 2) simulation optimisée pour passer à l'échelle et 3) affichage en live. La taille des cases et le temps de pause peuvent être adaptées selon la taille de la grille :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import random
from itertools import product
import pygame
from pygame.locals import *


# variables globales
C_SZ = 2                            # taille des cases
WIDTH, HEIGHT = 512, 256            # nombre de cases (hauteur / largeur)
COLORS = 'green', 'gray', 'red'     # couleurs possibles des cases (sauf fond)
STATES = 'arbre', 'cendre', 'brule' # etats des cases
PROBA = 0.60                        # probabilite qu'une case soit occupee par un arbre
DELAY = 10                          # delai entre 2 frames (ms)
SURFACES = {}                       # dictionnaire de surfaces (color => sprite)
S2C = dict(zip(STATES, COLORS))     # correspondance (state => color)


# initialise les surfaces à blitter
def init_surfaces():
    for color in COLORS:
        SURFACES[color] = pygame.Surface((C_SZ, C_SZ))
        SURFACES[color].fill(pygame.Color(color))

# affichage
def display(screen, dct):
    for (i,j), content in dct.items():
        screen.blit(SURFACES[S2C[content]], (j * C_SZ, i * C_SZ))
    pygame.display.flip()

# avance d'un tour
def step(mat, dct):
    new_dct = {}
    for (i,j), content in dct.items():
        if content == 'brule':
            new_dct[i,j] = 'cendre'
            for x, y in [(-1,0), (1,0), (0,-1), (0,1)]:
                pos = i + x, j + y
                if mat.get(pos) == 'arbre':
                    new_dct[pos] = 'brule'
    return new_dct


if __name__ == '__main__':
    # initialise aléatoirement la position des arbres sur le terrain
    mat = {pos: 'arbre'
           for pos in product(range(HEIGHT), range(WIDTH))
           if random.random() < PROBA}
    N = len(mat)

    pygame.init()
    init_surfaces()
    screen = pygame.display.set_mode((C_SZ * WIDTH, C_SZ * HEIGHT))
    screen.fill(pygame.Color('yellow'))

    display(screen, mat)

    dct = {random.choice(list(mat.keys())): 'brule'}    # premier arbre en feu
    while dct:
        pygame.time.wait(DELAY)
        display(screen, dct)
        mat.update(dct)
        dct = step(mat, dct)

    K = N - len([v for v in mat.values() if v == 'arbre'])
    print("proba = {}, {:.2%} d'arbres brules ({} / {})".format(PROBA, K / N, K, N))

    pygame.quit()

EDIT: code cleanup

+1 -0

À yoch : ce n'est effectivement pas équivalent. Tu tires les cases qui vont brûler, et les fait effectivement brûler si il y a contact avec le feu originel. Chaque case a donc une probabilité de brûler p testée une seule fois.

Dans l'algorithme proposé, un arbre a une chance de brûler p chaque fois qu’apparaît une flamme parmi ses voisins.

Le seuil de percolation est certes le même, mais rien ne dit à priori que le comportement de ces deux systèmes soit identiques tout le temps. À l'évidence, il ne l'est pas pour les valeurs de p supérieur à 0,5. Édit : mal lu, le seuil de percolation est différent.

+0 -0

@Gabbro: Oui, effectivement la proba n'est pas la même dans les deux cas.

Dans le mémoire que tu as linké ci-dessus (cf. 2.3.3), j'ai vu qu'ils font la distinction entre "percolation de site" et "percolation de lien", et indiquent que le seuil de percolation dans mon cas est situé vers 0.59, ce qui correspond à mes observations.

+0 -0

Voilà ma participation, sans doute peu originale et pas forcément très élégante, mais elle a le mérite de sortir un résultat assez vite ^^

Une image du résultat (la carte est animée pendant la simulation) :

Simulation

Le code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
import random

import pygame
from pygame.locals import *


class Tree:
   BURNED = 0
   BURNING = 1
   ALIVE = 2
   def __init__(self):
       self.state = self.ALIVE
   def __repr__(self):
       s = {self.BURNED:'BURNED', self.BURNING:'BURNING', self.ALIVE:'ALIVE'}[self.state]
       return '<Tree ' + s + '>'

class World:
   def __init__(self, s, p):
       self.map = [list([Tree() for i in range(s)]) for j in range(s)]
       self.burning = []
       self.new_burning = []
       self.burned = []

       self.there_is_fire = False

       self.nb_alive = s ** 2
       self.nb_burned = 0

       self.surface = pygame.Surface((s,s))
       self.surface.fill((0,255,0))

       self.font = pygame.font.Font(None,24)
       self.txt = None

       self.p = p

   def fire_on(self, pos):
       x,y = pos
       if x<0 or x>=len(self.map) or y<0 or y>=len(self.map):
           return
       if self.map[x][y].state is not Tree.ALIVE:
           return
       self.map[x][y].state = Tree.BURNING
       if not self.there_is_fire:
           self.burning = [(x,y)]
           self.there_is_fire = True
           self.nb_burned = 0

       self.nb_burned += 1
       self.new_burning.append((x,y))

   def on_update(self):
       if not self.there_is_fire:
           self.txt = self.font.render("{} % d'arbres brûlés".format(round(self.nb_burned/self.nb_alive * 100, 2)), \
                                       True, (0,0,0), (50,200,255))
           return
       elif self.txt:
           self.txt = None
       self.there_is_fire = False

       self.new_burning = []

       #self.surface.fill((0,255,0))
       burner = lambda : random.random() < self.p

       for x,y in self.burned:
           self.surface.set_at((x,y),(0,0,0))
       self.burned = []

       for x,y in self.burning:
           self.there_is_fire = True
           self.surface.set_at((x,y), (255,0,0))

           self.map[x][y].state = Tree.BURNED

           up = burner()
           down = burner()
           left = burner()
           right = burner()
           if up:
               self.fire_on((x,y+1))
           if down:
               self.fire_on((x,y-1))
           if left:
               self.fire_on((x-1,y))
           if right:
               self.fire_on((x+1,y))

           self.burned.append((x,y))
       self.burning = self.new_burning[:]

   def on_render(self,dst):
       dst.blit(self.surface, (0,0))
       if self.txt:
           dst.blit(self.txt, (0,0))

class App:
   def __init__(self):
       self.window = pygame.display.set_mode((512, 512))
       self.running = False

       self.world = World(512, 0.5)

       self.font = pygame.font.Font(None, 24)
       self.menu = self.font.render("Appuyez sur 'R' pour ré-initialiser la simulation.", \
                                    True, (0,0,0),(50,200,255))

       self.clock= pygame.time.Clock()

   def on_event(self, e):
       if e.type == QUIT:
           self.running = False
       elif e.type == MOUSEBUTTONDOWN:
           self.world.fire_on(e.pos)
       elif e.type == KEYDOWN:
           if e.key == K_r:
               p = self.world.p
               self.world = World(512,p)
           elif e.key == K_LEFT:
               self.world.p -= 0.1
               if self.world.p < 0:
                   self.world.p = 0
           elif e.key == K_RIGHT:
               self.world.p += 0.1
               if self.world.p > 1:
                   self.world.p = 1

   def on_render(self):
       self.world.on_render(self.window)
       if not self.world.there_is_fire:
           prob_txt = "Probabilité : < {} >".format(str(round(self.world.p,2)))
           prob = self.font.render(prob_txt, True, (0,0,0), (50,200,255))
           x = (self.window.get_width() - self.menu.get_width()) // 2
           y = (self.window.get_height() - self.menu.get_height()) // 2
           self.window.blit(self.menu,(x,y))
           x = (self.window.get_width() - prob.get_width()) // 2
           y += 1.2 * self.menu.get_height()
           self.window.blit(prob, (x,y))

   def on_update(self):
       self.world.on_update()

   def on_mainloop(self):
       self.running = True

       while self.running:
           for e in pygame.event.get():
               self.on_event(e)
           self.on_update()
           self.on_render()
           pygame.display.flip()
           pygame.display.set_caption(str(round(self.clock.get_fps(),2))+" FPS")
           self.clock.tick(70)

if __name__ == "__main__":
   pygame.init()
   a = App()
   a.on_mainloop()
   pygame.quit()

J'ai presque fini de coder mon implémentation en C# qui fonctionne à priori : quelques problèmes avec la représentation graphique (je découvre la génération de bitmap).

ThuleMalta

En fait, mon erreur était que la fonction printImage() marchait très bien mais j'avais oublié de l'appeler lors de la simulation… My bad :p

Donc j'ai terminé avec une simulation en live, la taille de la grille se modifie par le code pour le moment mais la probabilité par une UI.
Ce n'est pas très optimisé car c'est la première version et que j'ai fait ce qui me passait par la tête directement sans chercher une manière efficace de répondre au problème. J'améliorerai ça dans des updates.

Génération en live

J'ai ouvert une repo ici et l'exécutable est ici.

+3 -0

Hello,

Pour ma première participation à un défi de clem j'ai tenté une implémentation en JavaScript avec Canvas et de L'OO.(Oui oui, JS ça peut servir à autre chose que faire des sliders :p )

Un petit aperçu :

percolation

Petit conseil : Allez y doucement avec la taille de la grille, votre navigateur risque de ne pas apprécier un temps de traitement trop long !

Malheureusement le traitement est trop lourd pour avoir un affichage en temps réel. Si j'ai du temps dans le prochains jours (ce dont je doute un peu), j’essaierai d'améliorer encore mon code pour pouvoir choisir le point de départ ou gérer les zones qui ne brûlent pas.

En tous cas c'était un défi très sympa avec des observations très intéressantes et pour le coup vraiment accessible à une grande variété de langages et de niveaux.

Hello,

Voici ma participation en C à ce défi, le code se trouve ici.

La solution gère 6 types d'états:

  • Arbres/Bâtiments (qui peuvent brûler)

  • Clairières/Eau (qui ne brûlent pas)

  • Feu et Cendres

Il y a 3 formats de sortie possible: statistiques seules/texte/html

Le pattern de départ, le pourcentage de propagation et le nombre de cycles de la simulation sont définis en entrée.

Un exemple de résultat au format html (désolé pas de mode "live" ;) ). C'est le résultat correspondant au fichier d'entrée forestfire_input2.txt, présent dans le dépôt github.

EDIT: petit ajout concernant les perfs - en ne parcourant que les cellules en feu à chaque cycle, on gagne beaucoup de temps d'exécution, ci-dessous avec un carré de 4000x4000

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
FOREST FIRE SIMULATION

Propagation factor 55% - Number of cycles planned 100000

Initial map

Glades             0   0.00%
Trees       16008000 100.00%
Water              0   0.00%
Buildings          0   0.00%
Fire               1   0.00%
Ashes              0   0.00%

Map after 2369 cycles

Glades             0   0.00%
Trees          28342   0.18%
Water              0   0.00%
Buildings          0   0.00%
Fire               0   0.00%
Ashes       15979659  99.82%

real    0m4.586s
user    0m3.681s
sys     0m0.655s
+5 -0

Ça fait un moment que je voulais essayer la parallélisation en fortran, avec les forall typiquement. J'ai repris le modèle de yoch, qui me semblait plus simple pour ça. Le code marche. Point de vue parallélisation, c'est pas encore ça…

Plu le temps passe, et moins je suis convaincu par fortran.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
! Gestion de l'alétoire.
 module alea
 use iso_fortran_env, only: int64
 implicit none
 contains 
 subroutine init_random_seed()
 integer, allocatable :: seed(:)
 integer :: i, n, dt(8), pid
 integer(int64) :: t
 
 call random_seed(size = n)
 allocate(seed(n))
 call system_clock(t)
 call date_and_time(values=dt)
 t = (dt(1) - 1970) * 365_int64 * 24 * 60 * 60 * 1000 &
 + dt(2) * 31_int64 * 24 * 60 * 60 * 1000 &
 + dt(3) * 24_int64 * 60 * 60 * 1000 &
 + dt(5) * 60 * 60 * 1000 &
 + dt(6) * 60 * 1000 + dt(7) * 1000 &
 + dt(8)
 pid = getpid()
 t = ieor(t, int(pid, kind(t)))
 do i = 1, n
   seed(i) = lcg(t)
   end do
   call random_seed(put=seed)
   
   contains
   ! This simple PRNG might not be good enough for real work, but is
   ! sufficient for seeding a better PRNG.
   function lcg(s)
   integer :: lcg
   integer(int64) :: s
   s = mod(s, 4294967296_int64)
   s = mod(s * 279470273_int64, 4294967291_int64)
   lcg = int(mod(s, int(huge(0), int64)), kind(0))
   end function lcg
end subroutine init_random_seed
end module alea
   
   
program feu
! programme principale.
use alea
integer, dimension(:,:), allocatable :: monde
real, dimension(:,:), allocatable :: stocha
integer, dimension(:,:), allocatable :: en_feu, en_feu2
integer :: l, i, j, k, k2, nb_en_feu, ok
real :: pa, x, y

!Les nx/ny permettent de facilement passer d'un réseau à un autre.
!Il suffit de modifier une variable pour passer à un réseau 6.
integer, parameter, dimension(6) :: nx=(/1,-1, 0, 0, 1,-1/)
integer, parameter, dimension(6) :: ny=(/0, 0, 1,-1, 1,-1/)
integer, parameter :: res = 4

l = 1000
pa = 1!proba d'un arbre.

!Convention : 0 = arbre, 1 = lac, 2 = feu, 3 = cendre
allocate(monde(l,l)) ; allocate(stocha(l,l)) ; allocate(en_feu(l*l,2))
en_feu = -1
call init_random_seed()
call random_number(stocha)

! Création du monde, avec arbre et lac.
forall (i=1:l)
  forall (j=1:l)
    monde(i,j) = CEILING(stocha(i,j)-pa)
  end forall
end forall
deallocate(stocha)

!Flamme et CL
call random_number(x) ; call random_number(y)
monde(1,:) = 3 ; monde(l,:) = 3 ; monde(:,1) = 3 ; monde(:,l) = 3
monde(int(x*(l-2))+2,int(y*(l-2))+2) = 2
en_feu(1,:) = (/int(x*(l-2))+2, int(y*(l-2))+2/)
nb_en_feu = 1

allocate(en_feu2(l*l,2))
do while (nb_en_feu /= 0)
  
  k2 = nb_en_feu
  nb_en_feu = 0
  do k=1,k2
    do i=1,res
      do j=1,res
        if (monde(en_feu(k, 1)+nx(i), en_feu(k,2)+ny(j)) == 0 ) then
          monde(en_feu(k, 1)+nx(i), en_feu(k,2)+ny(j)) = 2
          nb_en_feu = nb_en_feu + 1
          en_feu2(nb_en_feu,:) = (/ en_feu(k, 1)+nx(i), en_feu(k,2)+ny(j)/)
        end if
      end do
    end do
    monde(en_feu(k, 1), en_feu(k,2)) = 3
  end do
  en_feu(:,:) = 0
  en_feu(:nb_en_feu,:) = en_feu2(:nb_en_feu,:)
end do
write(*,*) "Proportion d'arbre brulé : ", real(count(monde == 3)-4*(l-1))/((l-2.)*(l-2.))
deallocate(monde)
end program

+2 -0

Plop,

Je partage une ébauche fonctionelle en C1, qui sera améliorée dès que j'aurais du temps (le we prochain à priori). Pour le moment la simulation fonctionne, j'ai des arbres qui brulent et des stats qui s'affichent à chaque tour. Pour les améliorations à venir, il y aura bientôt un retour graphique et plus d'options pour déterminer la grille de départ (changer la probabilité et ajouter des lacs facilement).

Montre moi le code !


  1. Je l'aurais bien fait en Python, mais autant essayer de diversifier les langages ! 

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte