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

a marqué ce sujet comme résolu.

Voilà ma réalisation en Ada :

with entrees_sorties; use entrees_sorties; with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

with Ada.Real_Time; use Ada.Real_Time; procedure simulationfeu is
G : Generator; –Crée la taille de la grille procedure maxGrilleLong (max: out Integer) is begin put("Veuillez entrer la longueur de la forêt."); get(max); end maxGrilleLong;
function maxLong return Integer is maximum : Integer; begin maxGrilleLong (maximum); return maximum; end maxLong;
procedure maxGrilleLarg (max: out Integer) is begin put("Veuillez entrer la largeur de la forêt."); get(max); end maxGrilleLarg;
function maxLarg return Integer is maximum : Integer; begin maxGrilleLarg(maximum); return maximum; end maxLarg;
LARG : Integer := maxLarg; LONG : Integer := maxLong;

  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
subtype Longueur is Integer range 1..LONG;
subtype Largeur is Integer range 1..LARG;

type TabGrille is array (Largeur, Longueur) of Integer;

function createGrille (maxLong, maxLarg : Integer) return TabGrille is -- Fonction créant le tableau de la forêt
    tab : TabGrille;
begin
    for i in 1..maxLarg loop
        for j in 1..maxLong loop
            tab(i, j) := 0;
        end loop;
    end loop;
    return tab;
end createGrille;
--grille(largeur, longueur);
grille : TabGrille := createGrille (LONG, LARG);
grilleTampon : TabGrille  := grille;
procedure separation is
begin
    put(Character'val(10));
end separation;

procedure createProba (p : out Float) is -- Procédure demandant à l'utilisateur la probabilité de la propagation du feu
begin
    put("Veuillez entrer la probabilité de propagation du feu.");
    p := -1.0;
    while p<0.0 or p>1.0 loop
        get(p);
    end loop;
end createProba;

function probabilite return Float is -- Fonction permettant de récupérer la probabilité
    p : Float;
begin
    createProba(p);
    return p;
end probabilite;

p : Float := probabilite; -- Variable contenant la probabilité

procedure afficherGrille(grille : in TabGrille; long, larg : in Integer) is -- Procédure affichant la grille
    tab : TabGrille;
begin
    tab := grille;
    for i in 1..larg loop
        new_line;
        for j in 1..long loop
            if tab(i, j)=0 then
                put('A');
            end if;
            if tab(i, j)=1 then
                put("M");
            end if;
            if tab(i, j)=2 then
                put("X");
            end if;
        end loop;
    end loop;
end afficherGrille;

procedure premArbre (grille : in out TabGrille; long, larg : in Integer) is -- Fonction créant le foyer du feu
    newGrille : TabGrille;
    x, y : Integer;
begin
    y := -1;
    while y<=0 or y>long loop
        y := Integer(Random(G)*float(long));
    end loop;
    x := -1;
    while x<=0 or x>larg loop
        x := Integer(Random(G)*float(larg));
    end loop;
    newGrille := grille;
    newGrille(x, y) := 1;
    grille := newGrille;
end premArbre;

procedure editerGrille(tab, tabT : in out TabGrille; long, larg : in Integer; p : Float) is -- Procédure affichant la grille
begin
    -- On enregistre la position des arbres qui vont s'enflammer dans le tableau
    -- Puis on va changer la grille en remplacant les arbres en feu par des cendres et en enflammant les arbres qu'il faut
    for i in 1..larg loop                                           -- Réinitialise le tableau tampon
        for j in 1..long loop
            tabT(i,j) := 0;
        end loop;
    end loop;

    
    for i in 1..larg loop                           -- Enregistre les positions des arbres qui vont s'enflammer au prochain tour dans le tableau tampon
        for j in 1..long loop
            if tab(i,j)=1 then                                      --Teste si l'arbre actuellement traité est en feu
                if i/=1 then
                    if tab(i-1,j)=0 and Random(G)<p then      --Teste si l'arbre du haut est entier
                        tabT(i-1, j) := 1;
                    end if;
                end if;
                if i/=larg then
                    if tab(i+1, j)=0 and Random(G)<p then   --Teste si l'arbre du bas est entier
                        tabT(i+1, j):= 1;
                    end if;
                end if;
                if j/=1 then
                    if tab(i, j-1)=0 and j/=1 and Random(G)<p then      -- Teste si l'arbre de gauche est entier
                        tabT(i,j-1) := 1;
                    end if;
                end if;
                if j/=long then
                    if tab(i, j+1)=0 and j/=long and Random(G)<p then   --Teste si l'arbre de droite est entier
                        tabT(i,j+1) := 1;
                    end if;
                end if;
            end if;
        end loop;
    end loop;

    for i in 1..larg loop                                           -- Enflamme et met en cendres les arbres qu'il faut
        for j in 1..long loop
            if tab(i,j)=1 then
                tab(i,j) := 2;
            end if;
            if tabT(i,j)=1 then
                tab(i,j) := 1;
            end if;
        end loop;
    end loop;

end editerGrille;
grilleP : TabGrille;

begin Reset(G); afficherGrille(grille, LONG, LARG); grilleTampon := grille; grilleP := grille; premArbre(grille, LONG, LARG); while grilleP/=grille loop grilleP := grille; editerGrille(grille, grilleTampon, LONG, LARG, p); separation; separation; afficherGrille(grille, LONG, LARG); delay 1.00; end loop; end simulationfeu;

Je sais, c'est pas très beau d'utiliser des caractères pour représenter la forêt, mais j'ai fait au plus simple ^^. Les 'A' représentent les arbres, les 'M' représentent les arbres en feu et les 'X' les cendres. L'affichage se fait en temps réel avec une seconde entre chaque tour. Je pense ajouter plus tard la possibilité pour l'utilisateur d'ajouter du vent, et faire une implémentation graphique avec QT si possible.

Au fait, quelqu'un sait comment je pourrais faire pour que mon spoiler soit pas aussi moche ?..

+2 -0

Voici un code en C++ impératif avec la bibliotèque MPI de calcul parallèle. J'ai rajouté un second paramètre q dans le problème en supposant que l'arbre ne s'arrête pas de brûler directement après une itération mais a une probabilité fixée q de s'éteindre à chaque itération.

Image utilisateur

Voilà un graphe 3D pas terrible qui va avec et qui donne la proportion d'arbres brûlés en fonction des paramètres.

  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
#include "MPI.h"
#include "stdlib.h"

void percolation(size_t length, unsigned nbIter)
{
  int rank, nbprocs;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &nbprocs);
  size_t lengthLoc{length/nbprocs+1+(rank != 0 && rank != nbprocs-1);

  for (double p=0.1;p<1;p+=0.1)
  {
    for (double q=0;q<0.95;q+=0.1)
    {
      size_t numTot{0};
      for (unsigned it=0;it<numIter;++it)
      {

        // INITIALISATION DE L'IMAGE
        std::vector<unsigned char> image(length*lengthLoc,0);
        for (int i=0;i<lengthLoc;++i)
        {
          image[i*length] = 3;
          image[i*length+length-1] = 3;
        }
        if (rank == 0)
        {
          for (size_t i=0;i<length;++i)
          {
            image[i] = 3;
          }
        }
        if (rank == nbprocs-1)
        {
          for (size_t i=0;i<length;++i)
          {
            image[length*lengthLoc-i-1] = 3;
          }
        }
        if (rank == nbprocs/2)
        {
          image[length*lengthLoc/2+length/2] = 2;
        }

        unsigned char isChange{1};

        // BOUCLE PRINCIPALE
        while(isChange)
        {

          // ECHANGE AUX BORDS DES PROCESSUS
          if (rank != 0)
          {
            MPI_Send(&image[length], length, MPI_UNSIGNED_CHAR, rank-1, rank, MPI_COMM_WORLD);
          }
          if (rank != nbprocs-1)
          {
            MPI_Recv(&image[length*(lengthLoc-1)], length, MPI_UNSIGNED_CHAR, rank+1, rank+1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            MPI_Send(&image[length*(lengthLoc-2)], length, MPI_UNSIGNED_CHAR, rank+1, rank+nbprocs, MPI_COMM_WORLD);
          }
          if (rank != 0)
          {
            MPI_Recv(&image[0], length, MPI_UNSIGNED_CHAR, rank-1, rank-1+nbprocs, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
          }

          // PROPAGATION DU FEU
          for (size_t i=(rank != 0); i<lengthLoc-(rank != nbprocs-1); ++i)
          {
            for (size_t j=0; j<length; ++j)
            {
              if (image[i*length+j] == 0)
              {
                unsigned char neighb{0};
                neighb += (image[(i-1)*length+j] == 2) + (image[(i+1)*length+j] == 2) + (image[i*length+j+1] == 2) + (image[i*length+j-1] == 2);
                double pLoc{1-pow(1-p,neighb)};
                double alea{static_cast<double>(std::rand())/RAND_MAX};
                if (alea <= pLoc) image[i*length+j] = 1;
              }
            }
          }

          // ACTUALISATION DES ARBRES BRULES
          for (size_t i=(rank != 0); i<lengthLoc-(rank != nbprocs-1); ++i)
          {
            for (size_t j=0; j<length; ++j)
            {
              if (image[i*length+j] == 0)
              {
                isChange = 1;
                ++image[i*length+j];
              }
              else if (image[i*length+j] == 2)
              {
                isChange = 1;
                double stay{static_cast<double>(std::rand())/RAND_MAX};
                if (stay > q) ++image[i*length+j];
              }
            }
          }

          unsigned char isChangeTemp{0};
          MPI_Allreduce(&isChange, &isChangeTemp, 1, MPI_UNSIGNED_CHAR, MPI_MAX, MPI_COMM_WORLD);
          isChange = isChangeTemp;

        }

        // COMPTAGE DU NOMBRE D'ARBRES BRULES
        unsigned num{static_cast<unsigned>(std::count(image.begin()+length, image.end()-length, 3)-2*(lengthLoc-2))};
        unsigned numTemp{0};
        MPI_Allreduce(&num, &numTemp, 1, MPI_UNSIGNED, MPI_SUM, MPI_COMM_WORLD);

        numTot += numTemp;

      }

      unsigned size{static_cast<unsigned int>(length*length-4*length+4)};

      if (rank == 0)
      {
        std::cout << "Probabilite = " << p << " ; " << q << " ; Taux d'arbres brules => " << 100*(numTot/numIter)/size << std::endl;
      }
    }
  }
}
+2 -0

Bonjour ! Même si Novembre est maintenant terminé voici ma contribution. Je l'ai fait en C++ en m'appuyant sur la lib SFML pour l'affichage. L'affichage se fait en temps réel, c'est assez amusant à voir =).

J'ai divisé le tout en 6 fichiers que voici :

Constant.h

1
2
3
4
5
6
7
#ifndef __CONSTANT_H__
#define __CONSTANT_H__

#define board_edge_size     950
#define prob                0.55f

#endif

main.cpp

 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
#include <iostream>
#include <Windows.h>
#include <SFML/Graphics.hpp>

#include "Constant.h"
#include "Grid.h"
#include "FireSimulator.h"

void start_fire(Grid &grid, FireSimulator &sim)
{
   int x = rand() % board_edge_size;
   int y = rand() % board_edge_size;

   sim.start_fire(x, y);
}

int main(int argc, const char* argv[])
{
   srand(time(NULL));
   sf::RenderWindow window(sf::VideoMode(board_edge_size, board_edge_size), "Fire Sim");

   Grid grid;
   FireSimulator sim(&grid);

   start_fire(grid, sim);

   bool done = false;
   while(window.isOpen())
   {
       sf::Event event;
       while (window.pollEvent(event))
       {
           if (event.type == sf::Event::Closed)
           {
               window.close();
               return false;
           }
           else if(event.type == sf::Event::KeyPressed)
           {
               if(event.key.code == sf::Keyboard::Escape || done)
               {
                   window.close();
               }
           }
       }

       if(sim.is_done() && !done)
       {
           done = true;
           std::cout << "DONE !" << std::endl;
           std::cout << "Iterations : " << sim.iterations_done() << std::endl;
           std::cout << "Nb of trees : " << board_edge_size * board_edge_size << std::endl;
           std::cout << "Trees Burned : " << sim.trees_burned() << std::endl;
           std::cout << "% Trees Burned : " << (double)sim.trees_burned() / (double)(board_edge_size * board_edge_size) * 100 << " %" << std::endl;
       }
       else sim.update(prob);
       window.clear();
       grid.draw(window);
       window.display();
   }

   return 0;
}

Grid.h

 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
#ifndef __GRID_H__
#define __GRID_H__

#include <array>
#include <stdint.h>

#include <SFML/Graphics.hpp>

#include "Constant.h"

class Grid
{
public:

   enum eTileValue
   {
       Tree = 0,
       OnFire,
       Ash
   };

   Grid();

   ~Grid() {}

   uint8_t& operator() (int x, int y)
   {
       return this->_array[x + board_edge_size * y];
   }

   void draw(sf::RenderWindow &window);

private:

   std::array<uint8_t, board_edge_size * board_edge_size> _array;
   sf::VertexArray _vertexArray;
};

#endif

Grid.cpp

 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
#include "Grid.h"
#include <iostream>

Grid::Grid()
{
   memset(&this->_array, 0, sizeof(this->_array));
   this->_vertexArray.resize(board_edge_size * board_edge_size);
   this->_vertexArray.setPrimitiveType(sf::Points);
}

void Grid::draw(sf::RenderWindow &window)
{
   for(uint32_t y = 0; y < board_edge_size; ++y)
   {
       for(uint32_t x = 0; x < board_edge_size; ++x)
       {
           sf::Vertex *point = &this->_vertexArray[x + y * board_edge_size];

           point->position = sf::Vector2f((float)x, (float)y);

           sf::Color color;
           if((*this)(x, y) == Grid::eTileValue::Tree) color = sf::Color(34, 177, 76);
           else if((*this)(x, y) == Grid::eTileValue::OnFire) color = sf::Color::Red;
           else color = sf::Color(200, 200, 200);

           point->color = color;
       }
   }

   window.draw(this->_vertexArray);
}

FireSimulator.h

 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
#ifndef __FIRESIMULATOR_H__
#define __FIRESIMULATOR_H__

#include <queue>
#include <vector>

#include "Grid.h"

class FireSimulator
{
public:
    FireSimulator(Grid *grid);

    ~FireSimulator();

    void update(float p);

    void start_fire(int x, int y);

    bool is_done();

    unsigned long long iterations_done() { return this->_iterations; }

    unsigned long long trees_burned() { return this->_treesBurned; }

private:

    Grid *_grid;
    std::queue<std::pair<int, int>> _tilesOnFire;
    std::vector<std::pair<int, int>> _directions;
    unsigned long long _iterations;
    unsigned long long _treesBurned;
};

#endif

FireSimulator.cpp

 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
#include "FireSimulator.h"

#include "Constant.h"

FireSimulator::FireSimulator(Grid *grid)
{
    this->_grid = grid;

    this->_directions.push_back(std::make_pair(0, -1));
    this->_directions.push_back(std::make_pair(-1, 0));
    this->_directions.push_back(std::make_pair(0, +1));
    this->_directions.push_back(std::make_pair(+1, 0));

    /*this->_directions.push_back(std::make_pair(-1, -1));
    this->_directions.push_back(std::make_pair(-1, +1));
    this->_directions.push_back(std::make_pair(+1, +1));
    this->_directions.push_back(std::make_pair(+1, -1));*/

    this->_iterations = 0;
    this->_treesBurned = 0;
}

FireSimulator::~FireSimulator()
{}

void FireSimulator::update(float p)
{
    size_t update_to_apply = this->_tilesOnFire.size();
    ++this->_iterations;
    for(size_t i = 0; i < update_to_apply; ++i)
    {
        const std::pair<int, int> &front = this->_tilesOnFire.front();

        for(size_t d = 0; d < this->_directions.size(); ++d)
        {
            int x = front.first + this->_directions[d].first;
            int y = front.second + this->_directions[d].second;

            if(x >= 0 && x < board_edge_size && y >= 0 && y < board_edge_size
                && (*this->_grid)(x, y) == Grid::eTileValue::Tree)
            {
                if (rand() < p * RAND_MAX)
                {
                    (*this->_grid)(x, y) = Grid::eTileValue::OnFire;
                    this->_tilesOnFire.push(std::make_pair(x, y));
                }
            }
        }

        (*this->_grid)(front.first, front.second) = Grid::eTileValue::Ash;
        this->_tilesOnFire.pop();
        ++this->_treesBurned;
    }
}

void FireSimulator::start_fire(int x, int y)
{
    (*this->_grid)(x, y) = Grid::eTileValue::OnFire;
    this->_tilesOnFire.push(std::make_pair(x, y));
}

bool FireSimulator::is_done()
{
    return this->_tilesOnFire.empty();
}

Voila ! Je n'ai pas d'image désolé mais j'espere que ma contribution vous plaira =)

+2 -0

Bonjour à tous,

@S-sonic`: J'ai testé ton code, et je me permet ainsi de le critiquer un peu. :)

  • La fonction std::rand est actuellement dépréciée et à éviter.
  • Il y a encore quelques warnings à faire disparaître, des trucs du genre old-style-cast, zero-as-null-pointer ou encore unusued-variable.
  • Il ne faudrait pas inclure <SFML/Graphics.hpp> entièrement, mais seulement les classes nécessaires, pour accélérer le temps de compilation notamment.

Au niveau de la conception, je ne suis pas sûr qu'utiliser un sf::VertexArray avec des sf::Points soit une bonne idée, car en soit, comme ta classe Grid doit représenter une grille de pixel, le fait que chaque sf::Point possède une position indépendante devient absurde.

J'ai moi-même développé récemment cet exercice en C++ avec SFML, et j'ai choisi d'utiliser une sf::Image pour le rendu de la forêt. Il me semble, après avoir rapidement comparé, que c'est plus performant qu'avec un sf::VertexArray.

J'ai par ailleurs pris la peine d'ajouter un petit graphique qui représentent le nombre d'arbres brûlés, et un second pour le nombre d'arbre en train de brûler (dont la courbe est, en quelque sorte, la fonction dérivée de la première). En regardant le plus haut point de ce second graphique, j'arrive ainsi estimer le point d'inflexion du premier (la ligne verticale sur les graphiques).

J'ai finalement fait en sorte que l'utilisateur puisse choisir lui-même le nombre d'arbres par côté ainsi que la probabilité de propagation, via un invité de commande.

En voilà une image et une animation :

Forest

Simulation en cours

Vous pouvez télécharger le code source ici : olybri-forest-src.zip (4,53 Ko)
Vous pouvez télécharger le programme compilé pour Windows ici : olybri-forest.zip (679 Ko)

Je poste également le code source ici pour ceux qui voudraient juste jeter un coup d’œil :

main.cpp :

  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
// 2015, Loris Witschard

#include <SFML/Graphics/RenderWindow.hpp>
#include <SFML/Window/Event.hpp>
#include <SFML/System/Clock.hpp>

#include <iostream>
#include <regex>

#include <windows.h>

#include "Forest.h"
#include "Graph.h"

template<typename T>
T getValue(const std::string &message, T min, T max, const std::string &regexStr)
{
    const std::regex pattern(regexStr);
    std::string input;

    while(true)
    {
        std::cout << message << ": " << std::flush;
        std::getline(std::cin, input);

        if(!std::regex_match(input, pattern))
        {
            std::cout << "Veuillez entrer une valeur correcte!" << std::endl;
            continue;
        }

        T value;
        std::istringstream{input} >> value;

        if(value < min || value > max)
            std::cout << "Veuillez entrer une valeur entre " << min << " et " << max << "!" << std::endl;

        else
            return value;
    }
}

int main()
{
    SetConsoleTitle("Simulation d'un feu de forêt");

    std::cout << "Chargement...\r" << std::flush;

    sf::RenderWindow window;
    window.setFramerateLimit(60);

    sf::Font font;
    font.loadFromFile("consola.ttf");

    const unsigned minTreeSide = 100;

    const auto treeSide = getValue<unsigned>("\rEntrez le nombre d'arbre par côté", minTreeSide, 1000, "-?[\\d]+");
    const auto prob = getValue<float>("\rEntrez la probabilité qu'un arbre prenne feu", 0, 1, "-?[\\d]+(\\.[\\d]+)?");
    std::cout << std::endl << "Chargement..." << std::flush;

    unsigned scale = 900 / treeSide;
    if(scale == 0)
        scale = 1;

    const unsigned sideSize = treeSide * scale;
    const unsigned graphSize = sideSize / 3;

    window.create(sf::VideoMode(sideSize + graphSize + 70, sideSize), "Render", sf::Style::None);

    Forest forest(treeSide, scale);
    forest.setPosition(-static_cast<int>(scale), -static_cast<int>(scale));

    Graph graphDead("Dead trees", graphSize, font, 1, sf::Color::Blue);
    graphDead.setPosition(sideSize, graphSize);

    Graph graphFire("Burning trees", graphSize, font, 70, sf::Color::Red);
    graphFire.setPosition(sideSize, graphSize * 2);


    sf::Text infoText("", font, 15);
    infoText.setPosition(sideSize + 12, 10);

    unsigned cycle = 0;
    unsigned maxBurningCount = 0;

    const auto graphUpdateFrame = std::min(treeSide / minTreeSide, 5u);

    sf::Clock clock;

    while(window.isOpen())
    {
        sf::Event event;
        while(window.pollEvent(event))
            if(event.type == sf::Event::KeyPressed && event.key.code == sf::Keyboard::Escape)
                window.close();

        if(forest.isBurning())
        {
            const auto elaspedTime = clock.getElapsedTime();

            bool updated = forest.update(prob);

            if(cycle % graphUpdateFrame == 0 || !updated)
            {
                auto totalCount = treeSide * treeSide;
                auto deadCount = forest.getCount(Tree::Dead) - treeSide * 4 - 4;
                auto burningCount = forest.getCount(Tree::Fire);

                if(burningCount > maxBurningCount)
                {
                    graphDead.setMaxLine(cycle / graphUpdateFrame);
                    graphFire.setMaxLine(cycle / graphUpdateFrame);
                    maxBurningCount = burningCount;
                }

                graphDead.updatePercent(deadCount, totalCount);
                graphFire.updatePercent(burningCount, totalCount);

                std::cout << "\rNombre de cycles: " << cycle <<  "\tArbres brûtlés: " << deadCount * 100 / totalCount  << " %" << std::flush;
            }

            infoText.setString(
                static_cast<std::ostringstream&>(std::ostringstream{}
                << "trees: " << treeSide << "^2 = " << treeSide * treeSide
                << "\npropagation: " << prob
                << "\ncycles: " << cycle
                << "\ntime: " << static_cast<int>(elaspedTime.asSeconds()) / 60 << "'"
                    << std::setw(2) << static_cast<int>(elaspedTime.asSeconds()) % 60 << "\""
                    << std::setw(2) << static_cast<int>(elaspedTime.asMilliseconds() / 10 % 100)
                << "\n\npress Esc. to exit").str());

            if(!updated)
                std::cout << std::endl << "Simulation terminée! (" << elaspedTime.asSeconds() << " sec.)" << std::endl;

            else
                ++cycle;
        }

        window.clear(sf::Color(0, 20 ,0));

        window.draw(forest);
        window.draw(graphDead);
        window.draw(graphFire);
        window.draw(infoText);

        window.display();
    }
}

forest.h :

 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
#ifndef FOREST_H
#define FOREST_H

#include <SFML/Graphics/Image.hpp>
#include <SFML/Graphics/Texture.hpp>
#include <SFML/Graphics/Sprite.hpp>
#include <SFML/Graphics/RenderTarget.hpp>

#include <random>
#include <ctime>

class RandomReal
{
    public:
        static float generate();

    private:
        static std::mt19937 m_generator;
        static std::uniform_real_distribution<float> m_distribution;
};


enum class Tree { Alive, Fire, Dead };

class Forest : public sf::Drawable, public sf::Transformable
{
    public:
        Forest(unsigned length, int scale);
        bool update(float prob);
        static void setOnFire(Tree &tree, float prob);

        bool isBurning() const;

        unsigned getCount(Tree tree) const;

    private:
        virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const override;

        std::vector<Tree> m_trees;
        unsigned m_length;

        bool m_burning = true;

        sf::Image m_image;
        sf::Texture m_texture;
        sf::Sprite m_sprite;
};

#endif // FOREST_H

forest.cpp :

  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
#include "Forest.h"

std::mt19937 RandomReal::m_generator(std::time(nullptr));
std::uniform_real_distribution<float> RandomReal::m_distribution(0, 1);

float RandomReal::generate()
{
    return m_distribution(m_generator);
}


Forest::Forest(unsigned length, int scale) : m_length {length + 2}
{
    m_trees.assign(m_length * m_length, Tree::Alive);
    std::fill_n(m_trees.begin(), m_length, Tree::Dead);
    std::fill_n(m_trees.begin() + m_length * m_length - m_length, m_length, Tree::Dead);
    for(unsigned i = m_length; i < m_length * m_length; i += m_length)
    {
        m_trees[i] = Tree::Dead;
        m_trees[i - 1] = Tree::Dead;
    }

    std::mt19937 generator(std::time(nullptr));
    std::uniform_int_distribution<int> distribution(m_length + 1, m_length * m_length - m_length - 1);

    m_trees[distribution(generator)] = Tree::Fire;

    m_image.create(m_length, m_length, sf::Color(40, 96, 40));
    m_texture.loadFromImage(m_image);
    m_sprite.setTexture(m_texture);
    m_sprite.setScale(scale, scale);
}

bool Forest::update(float prob)
{
    auto prevTrees = m_trees;

    for(unsigned i = m_length; i < m_trees.size() - m_length; ++i)
        if(prevTrees[i] == Tree::Fire)
        {
            setOnFire(m_trees[i - m_length], prob);
            setOnFire(m_trees[i - 1]       , prob);
            setOnFire(m_trees[i + 1]       , prob);
            setOnFire(m_trees[i + m_length], prob);

            m_trees[i] = Tree::Dead;
        }

    if(prevTrees == m_trees)
    {
        m_burning = false;
        return false;
    }

    for(unsigned i = 0; i < m_trees.size(); ++i)
        switch(m_trees[i])
        {
            case Tree::Fire:
                m_image.setPixel(i % m_length, i / m_length, sf::Color::White);
                break;

            case Tree::Dead:
                m_image.setPixel(i % m_length, i / m_length, sf::Color::Black);
                break;

            case Tree::Alive:
            default:
                break;
        }

    m_texture.update(m_image);

    return true;
}

void Forest::setOnFire(Tree &tree, float prob)
{
    if(tree == Tree::Alive)
        tree = (RandomReal::generate() < prob ? Tree::Fire : Tree::Alive);
}

bool Forest::isBurning() const
{
    return m_burning;
}

unsigned Forest::getCount(Tree tree) const
{
    return std::count_if(m_trees.begin(), m_trees.end(),
        [tree](auto t)
        {
            return t == tree;
        });
}

void Forest::draw(sf::RenderTarget& target, sf::RenderStates states) const
{
    states.transform *= getTransform();
    target.draw(m_sprite, states);
}

graph.h :

 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
#ifndef GRAPH_H
#define GRAPH_H

#include <SFML/Graphics/Image.hpp>
#include <SFML/Graphics/Texture.hpp>
#include <SFML/Graphics/Sprite.hpp>
#include <SFML/Graphics/RenderTarget.hpp>
#include <SFML/Graphics/Text.hpp>

#include <sstream>
#include <iomanip>

class Graph : public sf::Drawable, public sf::Transformable
{
    public:
        Graph(const std::string &title, unsigned size, const sf::Font &font, float scale, sf::Color color);
        void updatePercent(float value, float max);
        void setMaxLine(float x);

    private:
        virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const override;

        sf::Image m_image;
        sf::Texture m_texture;
        sf::Sprite m_sprite;
        sf::Text m_percentText;
        sf::Text m_titleText;
        sf::VertexArray m_maxLine;

        unsigned m_size;
        std::string m_title;
        float m_scale;
        sf::Color m_color;

        unsigned m_cycle {0};
        float maxLinePos {0};
};

#endif // GRAPH_H

graph.cpp :

 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
#include "Graph.h"

Graph::Graph(const std::string &title, unsigned size, const sf::Font &font, float scale, sf::Color color)
    : m_size {size}, m_title {title}, m_scale {scale}, m_color {color}
{
    m_image.create(5000, m_size + 1, sf::Color(32, 32, 32) * m_color);
    m_texture.loadFromImage(m_image);
    m_texture.setSmooth(true);
    m_sprite.setTexture(m_texture);

    m_percentText.setFont(font);
    m_percentText.setCharacterSize(12);

    m_titleText.setFont(font);
    m_titleText.setCharacterSize(15);

    m_titleText.setPosition(12, 10);

    m_maxLine.setPrimitiveType(sf::Lines);
    m_maxLine.append(sf::Vertex(sf::Vector2f(0, 0), sf::Color::Transparent));
    m_maxLine.append(sf::Vertex(sf::Vector2f(0, m_size), sf::Color::Transparent));
}

void Graph::updatePercent(float value, float max)
{
    const float factor = value / max;
    float height = m_size - factor * m_scale * m_size;

    if(height >= m_size)
        height = m_size - 1;

    else if(height <= 0)
        height = 1;

    m_image.setPixel(m_cycle, height, sf::Color::White);
    m_image.setPixel(m_cycle, height + 1, sf::Color::White * m_color);
    m_image.setPixel(m_cycle, height - 1, sf::Color::White * m_color);

    m_texture.update(m_image);
    m_sprite.setScale(static_cast<float>(m_size) / (m_cycle + 1), 1);


    m_maxLine[0].position = sf::Vector2f(maxLinePos * static_cast<float>(m_size) / (m_cycle + 1), 0);
    m_maxLine[1].position = sf::Vector2f(maxLinePos * static_cast<float>(m_size) / (m_cycle + 1), m_size);


    std::ostringstream oss;
    oss << " " << std::setprecision(2) << std::fixed << factor * 100.0 << " %";
    m_percentText.setString(oss.str());
    m_percentText.setPosition(m_size, height - m_percentText.getGlobalBounds().height);

    oss.str("");
    oss << m_title << ": " << static_cast<int>(value);
    m_titleText.setString(oss.str());

    ++m_cycle;
}

void Graph::setMaxLine(float x)
{
    if(x < 10)
        return;

    maxLinePos = x;

    m_maxLine[0].color = sf::Color::White * m_color;
    m_maxLine[1].color = sf::Color::White;
}

void Graph::draw(sf::RenderTarget& target, sf::RenderStates states) const
{
    states.transform *= getTransform();

    target.draw(m_sprite, states);
    target.draw(m_maxLine, states);
    target.draw(m_percentText, states);
    target.draw(m_titleText, states);
}

+10 -0

Aurel_B_, envoie ton code, c'est marrant ce que certains arrivent à faire avec Excel ! Je suis pas assez masochiste pour essayer :D

Et Olybri, c'est superbe ta simulation avec la courbe en prime.

Grimur

J'aime me faire du mal, c'est pas ultra optimisé et pas dingue mon truc (par contre j'ai un collègue qui créé des usines à gaz sous Excel : simulation de paie, …).

J'ai pas fini de commenter mais voici une première mouture :

1
2
3
4
5
6
7
8
'Bouton RaZ
Sub RaZ()
   'Replanter les arbres
   For Each o In [B2:AY51]
       If o.Interior.Color = 0 Then o.Interior.Color = 5296274
   Next

End Sub


  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
'Bouton Go

Sub In_Fire()
   Dim abscisse As Integer
   Dim ordonnee As Integer
   Dim probabilite As Single
   Dim cellule As String
   Dim cell_lettre As String
   Dim cell_nombre As Integer
   Dim propagation As Integer
   'manque quelques déclarations
   
   'Case Random
   abscisse = Int(Rnd * 50)
   ordonnee = Int(Rnd * 50)
   
   'Affectation du Random => Cellule
   Select Case abscisse
       Case 0
           cell_lettre = "B"
       Case 1
           cell_lettre = "C"
       Case 2
           cell_lettre = "D"
       Case 3
           cell_lettre = "E"
       Case 4
           cell_lettre = "F"
       Case 5
           cell_lettre = "G"
       Case 6
           cell_lettre = "H"
       Case 7
           cell_lettre = "I"
       Case 8
           cell_lettre = "J"
       Case 9
           cell_lettre = "K"
       Case 10
           cell_lettre = "L"
       Case 11
           cell_lettre = "M"
       Case 12
           cell_lettre = "N"
       Case 13
           cell_lettre = "O"
       Case 14
           cell_lettre = "P"
       Case 15
           cell_lettre = "Q"
       Case 16
           cell_lettre = "R"
       Case 17
           cell_lettre = "S"
       Case 18
           cell_lettre = "T"
       Case 19
           cell_lettre = "U"
       Case 20
           cell_lettre = "V"
       Case 21
           cell_lettre = "W"
       Case 22
           cell_lettre = "X"
       Case 23
           cell_lettre = "Y"
       Case 24
           cell_lettre = "Z"
       Case 25
           cell_lettre = "AA"
       Case 26
           cell_lettre = "AB"
       Case 27
           cell_lettre = "AC"
       Case 28
           cell_lettre = "AD"
       Case 29
           cell_lettre = "AE"
       Case 30
           cell_lettre = "AF"
       Case 31
           cell_lettre = "AG"
       Case 32
           cell_lettre = "AH"
       Case 33
           cell_lettre = "AI"
       Case 34
           cell_lettre = "AJ"
       Case 35
           cell_lettre = "AK"
       Case 36
           cell_lettre = "AL"
       Case 37
           cell_lettre = "AM"
       Case 38
           cell_lettre = "AN"
       Case 39
           cell_lettre = "AO"
       Case 40
           cell_lettre = "AP"
       Case 41
           cell_lettre = "AQ"
       Case 42
           cell_lettre = "AR"
       Case 43
           cell_lettre = "AS"
       Case 44
           cell_lettre = "AT"
       Case 45
           cell_lettre = "AU"
       Case 46
           cell_lettre = "AV"
       Case 47
           cell_lettre = "AW"
       Case 48
           cell_lettre = "AX"
       Case 49
           cell_lettre = "AY"
   End Select
   
   Select Case ordonnee
       Case 0
           cell_nombre = 2
       Case 1
           cell_nombre = 3
       Case 2
           cell_nombre = 4
       Case 3
           cell_nombre = 5
       Case 4
           cell_nombre = 6
       Case 5
           cell_nombre = 7
       Case 6
           cell_nombre = 8
       Case 7
           cell_nombre = 9
       Case 8
           cell_nombre = 10
       Case 9
           cell_nombre = 11
       Case 10
           cell_nombre = 12
       Case 11
           cell_nombre = 13
       Case 12
           cell_nombre = 14
       Case 13
           cell_nombre = 15
       Case 14
           cell_nombre = 16
       Case 15
           cell_nombre = 17
       Case 16
           cell_nombre = 18
       Case 17
           cell_nombre = 19
       Case 18
           cell_nombre = 20
       Case 19
           cell_nombre = 21
       Case 20
           cell_nombre = 22
       Case 21
           cell_nombre = 23
       Case 22
           cell_nombre = 24
       Case 23
           cell_nombre = 25
       Case 24
           cell_nombre = 26
       Case 25
           cell_nombre = 27
       Case 26
           cell_nombre = 28
       Case 27
           cell_nombre = 29
       Case 28
           cell_nombre = 30
       Case 29
           cell_nombre = 31
       Case 30
           cell_nombre = 32
       Case 31
           cell_nombre = 33
       Case 32
           cell_nombre = 34
       Case 33
           cell_nombre = 35
       Case 34
           cell_nombre = 36
       Case 35
           cell_nombre = 37
       Case 36
           cell_nombre = 38
       Case 37
           cell_nombre = 39
       Case 38
           cell_nombre = 40
       Case 39
           cell_nombre = 41
       Case 40
           cell_nombre = 42
       Case 41
           cell_nombre = 43
       Case 42
           cell_nombre = 44
       Case 43
           cell_nombre = 45
       Case 44
           cell_nombre = 46
       Case 45
           cell_nombre = 47
       Case 46
           cell_nombre = 48
       Case 47
           cell_nombre = 49
       Case 48
           cell_nombre = 50
       Case 49
           cell_nombre = 51
   End Select
   
   cellule = cell_lettre & cell_nombre
   
   
   If Range(cellule).Interior.Color <> 0 Then
       Range(cellule).Interior.Color = 255
   End If
   
   cellule_a_tester = "B2"
   
   nb_cell_inFire = 1

   While nb_cell_inFire <> 0
       nb_cell_inFire = 0
       
       For Each o In [B2:AY51]
           If o.Interior.Color = 255 Then nb_cell_inFire = nb_cell_inFire + 1
       Next

       
       cellule_a_tester = "B2"
       
       While cellule_a_tester <> "$AZ$51"
       
           If Range(cellule_a_tester).Interior.Color = 255 Then
   
               If Range(cellule_a_tester).Offset(0, 1).Interior.Color = 5296274 Then
                   propagation = Int(Rnd * 2)
                   If propagation = 1 Then
                       Range(cellule_a_tester).Offset(0, 1).Interior.Color = 255
                   End If
               End If
               
               If Range(cellule_a_tester).Offset(0, -1).Interior.Color = 5296274 Then
                   propagation = Int(Rnd * 2)
                   If propagation = 1 Then
                       Range(cellule_a_tester).Offset(0, -1).Interior.Color = 255
                   End If
               End If
               
               If Range(cellule_a_tester).Offset(1, 0).Interior.Color = 5296274 Then
                   propagation = Int(Rnd * 2)
                   If propagation = 1 Then
                       Range(cellule_a_tester).Offset(1, 0).Interior.Color = 255
                   End If
               End If
               
               If Range(cellule_a_tester).Offset(-1, 0).Interior.Color = 5296274 Then
                   propagation = Int(Rnd * 2)
                   If propagation = 1 Then
                       Range(cellule_a_tester).Offset(-1, 0).Interior.Color = 255
                   End If
               End If
              
              Range(cellule_a_tester).Interior.Color = 0
              
           ElseIf Range(cellule_a_tester).Interior.Color = 16777215 Then
               Range(cellule_a_tester).Select
               cellule_a_tester = ActiveCell.Offset(1, -50).Address
           Else
               Range(cellule_a_tester).Select
               cellule_a_tester = ActiveCell.Offset(0, 1).Address
           End If
   
       Wend
      
   Wend
   
   'déclarer ttes les variables
   'gestion proba
   'récup les valeurs des couleurs dans les cases
   
End Sub

Et voici un lien pour le récupérer : [Edit : lien mort]

+1 -0

Haha, il semblerait que je soit le seul que le sujet intéresse encore :lol: .

Cette fois ci, j'ai changé complètement d'approche. Au lieu d'une grille de carrés, le terrain est un graphe de point placés aléatoirement.

1000 arbres

Ici, une forêt de 1000 arbres et un paramètre $p = 0.5$. Le plus long c'est de générer la forêt, 10 minutes pour 1000 arbres.

Par contre ce qui est intéressant, c'est que le seuil semble être aussi autour de $0.5$.

p versus ratio

Le graphe de différentes valeur de $p$ contre le ratio d'arbres non brulés. Chaque point est la moyenne de 10 ratios sur des forêts différentes. Chaque forêt est composé de 100 arbres. Ce graphe a nécessité 1 heure de calcul :( .

Bon maintenant, je vais essayer d'implémenter un vent.

+3 -0

Tu pourrais expliquer comment tu définis ton "graphe" ? Comment sont définis les voisins ? Quelle est la densité du graphe ?

Si j'en crois mon interprétation de ton image, les arbres se recouvrent, et la propagation suit une logique de contact direct. D'où une nouvelle question: comment définis-tu le rayon d'un arbre ? Et puis, comment règles-tu la densité, soit au bout de combien d'arbres tu arrêtes d'en ajouter ?

Niveau algorithmique, je ne sais pas comment tu t'y prend (pourquoi la génération de la foret est si lente si c'est aléatoire ?), mais tu devrais peut-être établir une liste des voisins pour chaque arbre au début de la simulation.

+0 -0

Le graphe est généré par l'algorithme :

  • Choisir un point $pt$ qui à moins de 5 voisins dans le graphe.
  • Choisir un point $p$ aléatoirement dans le voisinage éloigné de $pt$ (ici un disque de rayon $R = 15$).
  • Si $p$ est dans le voisinage proche (un disque de rayon $r = 10$) d'un point du graphe, on choisis un nouveau $p$.
  • Sinon, on ajoute $p$ au graphe.

Pour la propagation, quand un arbre prend feu, il enflamme (avec une probabilité $p$ donné1) les arbres dans son voisinage éloigné.

Par contre, je ne sais pas calculer la densité du graphe.

En fait les arbres sont des points, ils ne se recouvrent pas. C'est juste qu'ils sont éloignés de $10$ au minimum et je les affiche avec un rayon de $7$.2

  1. Il y a deux $p$ différents dans l'énoncé, désolé. ↩

  2. px, mais osef. ↩

+1 -0

Ton graphe est très très bizarre. Je comprends pas vraiment ce que tu fais (et encore moins pourquoi). Pourquoi n'est-tu pas parti sur de simples sphères qui se touchent, ou un truc du genre ?

Pour le fait de retrouver 0,5, il est tout à fait possible que ce soit fortuit et que ça ne le fasse pas avec d'autre valeur de voisinage. Je rappelle (cf mémoire donnée dans le 1er message) que la topologie du réseau influence le seuil de percolation.

Édit : je veux bien le code.

+0 -0

Ton graphe est très très bizarre. Je comprends pas vraiment ce que tu fais (et encore moins pourquoi). Pourquoi n'est-tu pas parti sur de simples sphères qui se touchent, ou un truc du genre ?

Gabbro

Je sais pas. C'est ce qui me semblait le plus naturel, du coup l'algorithme de génération de graphe est assez naïf.

Depuis hier soir, j'ai changé d'algo, créer un graphe de $n$ points était en $O(n^3)$ maintenant c'est en $O(n)$, ce qui est beaucoup mieux :lol: . Par contre c'est encore un peu buggé.

trees: 2000; p: 0.45

Ici, les arbres sont espacés de 10px et sont des cercles de 5px de rayons. Ils ne devraient pas se chevaucher.

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
class Network


  # points :: [Point]
  # min :: Vector
  # max :: Vector


  # constructor :: ->
  constructor: ->
      @points = []
      @isolated = []
      @min = Vector.zero()
      @max = Vector.zero()

      origin = Point.empty Vector.zero()
      @points.push origin
      @isolated.push origin


  # at :: (Vector) -> Point
  at: (pos) ->
      min @points, (pt) ->
          pt.position.soustr(pos).r




# Ajout d'un point dans le graph:
#
#    1. trouver un point pt isole dans @isolated
#    2. choisir un point p dans le voisinage de pt
#    3. retour a 2 si p est dans la zone interdite d'un voisin etendu de pt
#    4. trouver les voisins de p dans le voisinage etendu de pt
#    5. si p a des voisins dans la liste des voisins étendus des voisins étendus de pt, les ajouter
#    6. ajouter p dans les voisins et voisins étendus de a
#    7. retirer p et pt de la liste des isolated si ils ont plus de 5 voisins
#    8. calculer les nouveaux min et max avec p.
#    9. ajouter p dans les points
#   10. ajouter p dans isolated si necessaire



  # addRandom :: -> [Point]
  addRandom: ->
      # (1)
      @addAround choice @isolated



  # addAround :: Point -> [Point]
  addAround: (pt) ->
      i = 0
      found = false
      while (not found) and i++ < 100
          # (2)
          pos = Vector.randomCircle().mult(Point.R).add(pt.position)
          found = true
          [pt].concat(pt.neighboorsExtended).forEach (n) ->
              if n.position.soustr(pos).r < Point.r
                  # (3)
                  found = false

      if found
          p = Point.empty pos
          # (4)
          pt.neighboorsExtended.forEach (n) ->
              if p.position.soustr(n.position).r < Point.R
                  p.neighboors.push n
                  n.neighboors.push p

          # (5)
          ns = []
          pt.neighboorsExtended.forEach (n) ->
              ns.push n
              n.neighboorsExtended.forEach (n2) ->
                  ns.push n2
          uniq(ns).forEach (n) ->
              console.log {p, n} if n.position.soustr(p.position).r < Point.r
              if n.position.soustr(p.position).r < Point.R*2
                  p.neighboorsExtended.push n
                  n.neighboorsExtended.push p

          # (6)
          pt.neighboors.push p
          p.neighboors.push pt
          pt.neighboorsExtended.push p # already in (5)
          p.neighboorsExtended.push pt # already in (5)

          # (7)
          if p.neighboors.length >= 5
              remove @isolated, p

          if pt.neighboors.length >= 5
              remove @isolated, pt

          # (8)
          @min = Vector.carthesian
              x: Math.min @min.x, p.position.x
              y: Math.min @min.y, p.position.y
          @max = Vector.carthesian
              x: Math.max @max.x, p.position.x
              y: Math.max @max.y, p.position.y

          # (9)
          @points.push p

          # (10)
          if p.neighboors.length < 5
              @isolated.push p

          return p




module.exports = class Point

  @equals: (a, b) ->
      Vector.equals a.position, b.position


  # @R :: Real
  @R: 15

  # @r :: Real
  @r: 10


  # empty :: (Vector) -> Point
  @empty: (position) ->
      new Point {position}



  # position :: Vector
  # neighboors :: [Point]


  #constructor :: ({@position}) ->
  constructor: ({@position}) ->
      @neighboors = []
      @neighboorsExtended = []

+1 -0

Salut,

Alors, pour ma part j'avais deux heures à perdre du coup voici le début d'une ébauche:

  • Génération d'un polygone aléatoire qui consiste à générer des points autour d'un centre. Le point suivant est généré par un angle par rapport au précédent et une longueur. Les deux grandeurs sont tirées suivant une loi normale, et les paramètres de variance et de moyenne permettent de gérer la régularité et la rotondité du polygone.
  • Comme le polygone n'est pas forcément très joli, on le lisser via l'algorithme itératif de Chaïkin, qui s'apparente à une régularisation via des Splines. Une ou deux passes sont suffisantes, surtout que chaque passe multiplie par deux le nombre de faces du polygone.

Ces deux premières étapes permettent d'obtenir une zone pour une forêt qui semble réaliste.

Ensuite, on générer des arbres aléatoirement dans cette zone et selon une distribution de probabilité particulière. Pour cela, on utilise la méthode de rejet pour générer des points à l'intérieur de notre polygone uniquement, et la méthode d'inverse généralisée pour simuler une distribution particulière (sur l'image suivante, selon l'axe x on a une loi normale et selon l'axe y une distribution exponentielle).

Pour le feu, ce qui nous intéresse c'est la "zone d'influence" de l'arbre, c'est à dire la zone dans laquelle tout autre arbre est susceptible de brûler. Sans vent, on peut admettre que globalement cette zone correspond au feuillage, qu'on peut approximer par un disque. Comme le rayon du feuillage est plus ou moins proportionnel à l'age de l'arbre, on modélisera le rayon d'influence par une loi exponentiel. Du coup, pour chaque arbre, on tire aléatoirement un rayon selon cette loi.

Pour chaque arbre on calcul le graphe de recouvrement, c'est à dire que si deux arbres ont une zone d'influence qui s'entrecoupe, on les relie.

Bon, comme tout à été tiré aléatoirement jusqu'à présent, on considère arbitrairement que le premier arbre de notre liste à décidé de faire une auto-combustion. De cet arbre, grâce à un algorithme de parcours tout simple, on marque comme brûlé les arbres de voisins en voisin.

Un résultat Un autre

Comme on peut s'y attendre, les arbres non brûlés sont situés à droite puisqu'il y a une densité plus faible à droite qu'à gauche à cause de la densité exponentielle.

Forêt générée selon deux lois exponentielles. Forêt générée selon deux loi uniformes.

Amélioration à venir :

  • Intégrer les statistiques sur les arbres brûlés et non brûlés.
  • intégration du vent : le vent déforme les cercles d'influence en ellipses d'influence selon le sens du vent et le rayon initial.
  • la zone d'influence est un gradient orienté vers l'extérieur.
  • la zone d'influence est probabiliste : en fonction de la distance centre à centre, et des ratios de surfaces on a pas la même probabilité de brûler, à voir.
  • une version 'temporelle', où l'on peut voir le résultat au fur et à mesure.
  • une version 'physique' où l'on a une diffusion de la chaleur dynamique (c'est facile à faire sur une zone d'influence, par contre aux interfaces et en cas de superposition, ça pue…)
+9 -0
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