Optimization with spread of fire (30 FPS minimum with 400*400 points)

Sawyer

Member
Hello everyone,

I try since some days now to create a project in which i simulate the spead of fire in a forest.

These are the rules :
  1. A burning point turns into an empty point
  2. A tree will burn if at least one neighbor is burning
  3. A tree ignites with probability f even if no neighbor is burning
  4. An empty space fills with a tree with probability p

The aim for me is just to optimize the project (and not to have something very realistic), initially i wanted to do this little simulation in a 1920*1080 room at 60 FPS, but i don't know how to do (i can't fin a way to optimize again my project) it and i don't even know if game maker can do it or if any language can do it (if you have informations, ideas, i will take them all).


Actually i have 30 FPS minimum, and i post this little text to take your advices, ideas...
For my project i used :
- Surface to draw everything
- An array + a struct to store informations about each points
- And a ds_list to store the "active" point(here an active point is a modified point)


How the project works (i don't use for loops (it cost to much ressources) to update but a ds_list, i put the point that have to be modified in this list) ?
- In the create event i fill the room with tree or nothing
- In the step event i randomly "plant" a tree on an empty point and randomly place a point "fire"
- Also in the step event i check the neighboring points of a point fire (if a point fire touch a forest --> fire spread; if a point fire is alone it die)
- Then in draw event i use surface to first draw the room (here is the only time i use for loop, because it costs too much ressources.
- Then i iterate in the list to draw what i have to draw

How i update the room? Everytime i modifysomething i put the id of the point in a list.
If the point is a point fire --> i check he neighboring points (in step event)
If the point is a point noone--> i draw it in the draw event then i delete it from the list
If the point is a point forest--> i draw it in the draw event then i delete it from the list

To update a point only 1 time per step i use update = !update (each point store an update variable).

I delete the point in the draw event to be sure i draw this point before delete it.

This is a picture of the project :

Untitled.png

Create event :
GML:
cellsize = 1;//Here each pixel will be a point
w = (room_width / cellsize);//Here room_width = 400
h = (room_height  / cellsize);//Here room_height = 400



probability_fire = 10; //1 on probability_fire
probability_forest = 1000;//Number of time i put a tree per step

enum type {
    noone,
    forest,
    fire,
}

for(var xx = 0; xx < w; ++xx) {
    for(var yy = 0; yy < h; ++yy) {
        cell[xx][yy] = {
            postion_on_x : xx,
            postion_on_y : yy,
            type_ : choose(0,1),
            updated : 0,
        }
    }
}

update = 0;
list = ds_list_create();

Step event :

Code:
repeat probability_forest {//Plant trees on empty points
    var xx = irandom_range(1,w-1);
    var yy = irandom_range(1,h-1);

    if cell[xx][yy].type_ = type.noone {
        cell[xx][yy].type_ = type.forest;
        ds_list_add(list,cell[xx][yy]);
    }
}

var chance2 = irandom(probability_fire) 
if chance2 = 0 {//Randomly place a point "fire"
    var xx = irandom_range(1,w-1);
    var yy = irandom_range(1,h-1);
    if chance2 = 0 {
        cell[xx][yy].type_ = type.fire
        ds_list_add(list,cell[xx][yy])
    }
}

Also in step event :
Code:
update = !update; //To update only 1 time a point each step

#region Check in Moore neighborhood if fire touch a forest then ad the point in a list

for (var i = 0; i < ds_list_size(list); i++) {
    var this_array = list[| i];//Get the position in array
    var pos_x = this_array.postion_on_x;
    var pos_y = this_array.postion_on_y;
    var typ = this_array.type_;//is that fire, forest, empty?
    var upd = this_array.updated;
  
    if (pos_x > 1 && pos_x < w-1 && pos_y > 1 && pos_y < h-1 && upd = update) {//Stay in the array size
      
        var chance = irandom(1);// the fire don't always spread at NW // NE // SW // SE
        if typ = type.fire {
            if cell[pos_x-1][pos_y].type_ = type.forest {//West
                cell[pos_x-1][pos_y].type_ = type.fire;
                cell[pos_x-1][pos_y].updated = !update;
                ds_list_add(list, cell[pos_x-1][pos_y]);
            }
      
            else if cell[pos_x+1][pos_y].type_ = type.forest {//East
                cell[pos_x+1][pos_y].type_ = type.fire;
                cell[pos_x+1][pos_y].updated = !update;
                ds_list_add(list, cell[pos_x+1][pos_y]);
            }
          
            else if cell[pos_x][pos_y-1].type_ = type.forest {//North
                cell[pos_x][pos_y-1].type_ = type.fire;
                cell[pos_x][pos_y-1].updated = !update;
                ds_list_add(list, cell[pos_x][pos_y-1]);
            }         
          
            else if cell[pos_x][pos_y+1].type_ = type.forest {//South
                cell[pos_x][pos_y+1].type_ = type.fire;
                cell[pos_x][pos_y+1].updated = !update;
                ds_list_add(list, cell[pos_x][pos_y+1]);
            } 
                      
            else if cell[pos_x+1][pos_y-1].type_ = type.forest && chance = 1 {//North West
                cell[pos_x+1][pos_y-1].type_ = type.fire;
                cell[pos_x+1][pos_y-1].updated = !update;
                ds_list_add(list, cell[pos_x+1][pos_y-1]);
            }
          
            else if cell[pos_x-1][pos_y-1].type_ = type.forest  && chance = 1{//North West
                cell[pos_x-1][pos_y-1].type_ = type.fire;
                cell[pos_x-1][pos_y-1].updated = !update;
                ds_list_add(list, cell[pos_x-1][pos_y-1]);
            }
          
            else if cell[pos_x+1][pos_y+1].type_ = type.forest  && chance = 1 {//South West
                cell[pos_x+1][pos_y+1].type_ = type.fire;
                cell[pos_x+1][pos_y+1].updated = !update;
                ds_list_add(list, cell[pos_x+1][pos_y+1]);
            }         

            else if cell[pos_x-1][pos_y+1].type_ = type.forest  && chance = 1{//South East
                cell[pos_x-1][pos_y+1].type_ = type.fire;
                cell[pos_x-1][pos_y+1].updated = !update;
                ds_list_add(list, cell[pos_x-1][pos_y+1]);
            }             
            else cell[pos_x][pos_y].type_ = type.noone; 
    }
      
}

if !(pos_x > 1 && pos_x < w-1 && pos_y > 1 && pos_y < h-1) {//If a cell fire is out of the room --> delete
    cell[pos_x][pos_y].type_ = type.noone;}
}

#endregion

Draw event :

Code:
if !(surface_exists(surface)) {//Draw everything when the room start
    surface = surface_create(room_width,room_height);
    surface_set_target(surface);
  
    #region Draw all the area
  
    for(var xx = 0; xx < w; ++xx) {
        for(var yy = 0; yy < h; ++yy) {
            var cell_value = cell[xx][yy].type_
            switch (cell_value)
                { 
                    case 0:
                    draw_sprite(spr_ashes,0,xx*cellsize,yy*cellsize)
                    break;
              
                    case 1:
                    draw_sprite(spr_plant,0,xx*cellsize,yy*cellsize)
                    break;
              
                    case 2:
                    draw_sprite(spr_fire,0,xx*cellsize,yy*cellsize)
                    break;             
            }
        }
    }
  
    #endregion
    surface_reset_target(); 
}

else if surface_exists(surface){//Draw point by point
    surface_set_target(surface);
  

    #region draw by point
  
    for (var i = 0; i < ds_list_size(list); i++) {
    var this_array = list[| i];//Find the position in the list
    var pos_x = this_array.postion_on_x;
    var pos_y = this_array.postion_on_y;
    var typ = this_array.type_;

    if typ = type.noone {
        draw_sprite(spr_ashes,0,pos_x*cellsize,pos_y*cellsize)
        ds_list_delete(list, i);
    }
    if typ = type.forest {
        draw_sprite(spr_plant,0,pos_x*cellsize,pos_y*cellsize)
        ds_list_delete(list, i);
    } 
    if typ = type.fire {
        draw_sprite(spr_fire,0,pos_x*cellsize,pos_y*cellsize)
    }
}

    #endregion
    surface_reset_target(); 
    draw_surface(surface, 0, 0);//Draws the surface at a given position.
}
 
Top