a first try on breadth-first search with costs

[IgniFerroque]

He there,
I just wanted to ask if my solution on breadth-first search and pathfinding for my procedural generation is fine. I have some performance issues on very large grids, which surely comes from my bad programming style.

I used this as a source/blueprint for my try https://www.redblobgames.com/pathfinding/a-star/introduction.html

I have some input grids, namely:
a grid which saves the pathcosts which is copied for the subtraction
a grid where the searched values are stored
a grid which saves the set roads
and a grid which saves the landmasses

Does somebody have an advice for a bit of performance improvement?
Or would a switch to YYC make a notable difference in speed?

Thank you in advance

/// @param pathcost_grid
/// @param startx
/// @param starty
/// @param steps
/// @param targetgrid
/// @param targetvalue
/// @param roads_grid
/// @param land_grid

var pathcost_grid = argument0; //grid with pathcosts
var startx = argument1;
var starty = argument2;
var steps = argument3; //failsafe variable, not used atm
var i = 0;
var feature_grid = argument4; //the grid which the algorithm is searching
var target_value = argument5; //the value that is searched for
var roads_grid = argument6;
var land_grid = argument7;

var width = ds_grid_width(pathcost_grid);
var height = ds_grid_height(pathcost_grid);

var pathcost = ds_grid_create(width,height);
ds_grid_copy(pathcost,pathcost_grid);//copy of the grid for subtracting the costs every step

//searchgrid saves the searchstatus of a given tile ( unvisited = 0  / frontier = 1 / visited = 2 )
var search_grid = ds_grid_create(width,height);
ds_grid_clear(search_grid,0);

//pathgrid saves the direction where the frontier has come from (1= right, 2= up, 3 = left, 4 = down)
var path_grid = ds_grid_create(width,height);
ds_grid_clear(path_grid,0);

// queues to save the frontier's x/y coordinates and setting the first entry to the start position
var queuex = ds_queue_create();
var queuey = ds_queue_create();
ds_queue_enqueue(queuex,startx);
ds_queue_enqueue(queuey,starty);
search_grid[# startx,starty] = 1;

var resultx;
var resulty;

#region
while (!ds_queue_empty(queuex)){
   var xx = ds_queue_dequeue(queuex);
   var yy = ds_queue_dequeue(queuey);
   search_grid[# xx,yy] = 1;
   
   if(pathcost[# xx,yy] = 0){
       if (scr_on_grid(search_grid,xx+1,yy) && search_grid[# xx+1,yy] = 0 && land_grid[# xx+1,yy] = 1) { //right
           ds_queue_enqueue(queuex,xx+1);
           ds_queue_enqueue(queuey,yy);
           search_grid[# xx+1,yy] = 1;
           path_grid[# xx+1,yy] = 3;
           tilemap_set(arrow_map_id,3,xx+1,yy);
           if (feature_grid[# xx+1,yy]=target_value){
               resultx = xx+1;
               resulty = yy;
               break;
           }       
       }

       if (scr_on_grid(search_grid,xx,yy-1) && search_grid[# xx,yy-1] = 0 && land_grid[# xx,yy-1] = 1){ //up
           ds_queue_enqueue(queuex,xx);
           ds_queue_enqueue(queuey,yy-1);
           search_grid[# xx,yy-1] = 1;
           path_grid[# xx,yy-1] = 4;
           tilemap_set(arrow_map_id,4,xx,yy-1);
           if (feature_grid[# xx,yy-1]=target_value){
               resultx = xx;
               resulty = yy-1;
               break;
           }
       }

       if (scr_on_grid(search_grid,xx-1,yy) && search_grid[# xx-1,yy] = 0 && land_grid[# xx-1,yy] = 1){ //left
           ds_queue_enqueue(queuex,xx-1);
           ds_queue_enqueue(queuey,yy);
           search_grid[# xx-1,yy] = 1;
           path_grid[# xx-1,yy] = 1;
           tilemap_set(arrow_map_id,1,xx-1,yy);
           if (feature_grid[# xx-1,yy]=target_value){
               resultx = xx-1;
               resulty = yy;
               break;
           }
       }
   
       if (scr_on_grid(search_grid,xx,yy+1) && search_grid[# xx,yy+1] = 0 && land_grid[# xx,yy+1] = 1){ //down
           ds_queue_enqueue(queuex,xx);
           ds_queue_enqueue(queuey,yy+1);
           search_grid[# xx,yy+1] = 1;
           path_grid[# xx,yy+1] = 2;
           tilemap_set(arrow_map_id,2,xx,yy+1);
           if (feature_grid[# xx,yy+1]=target_value){
               resultx = xx;
               resulty = yy+1;
               break;
           }
       }
       search_grid[# xx,yy] = 2;
   }else{
       pathcost[# xx,yy] = pathcost[# xx,yy] - 1;
       ds_queue_enqueue(queuex,xx);
       ds_queue_enqueue(queuey,yy);
   }
   //i++;
   //if (i >= steps){
   //   resultx = false;
   //   resulty = false;
   //   show_debug_message("abbruch")
   //   return(false);
   //   break;
   //}
}
#endregion


#region
var xx = resultx;
var yy = resulty;
roads_grid[# xx,yy] = 1;
roads_grid[# startx,starty] = 1;

do{
   var dir = path_grid[# xx,yy];
   switch (dir){
       case 1:
           roads_grid[# xx,yy] = 1;
           pathcost_grid[# xx,yy] = 1;
           xx = xx+1;//-
       break;
   
       case 2:
           roads_grid[# xx,yy] = 1;
           pathcost_grid[# xx,yy] = 1;
           yy = yy-1;//+
       break;

       case 3:
           roads_grid[# xx,yy] = 1;
           pathcost_grid[# xx,yy] = 1;
           xx = xx-1;//+
       break;

       case 4:
           roads_grid[# xx,yy] = 1;
           pathcost_grid[# xx,yy] = 1;
           yy = yy+1;//-
       break;
   }
}until (xx = startx and yy = starty)

#endregion
ds_queue_destroy(queuex);
ds_queue_destroy(queuey);
ds_grid_destroy(path_grid);
ds_grid_destroy(search_grid);

 

[Hyomoto]

Compiling would add some benefit but there's some benefit to be had into breaking down the search into smaller bits. Just as an example, I was working on a spaceship game at one time, and I would break the pathfinding up between rooms and levels. Essentially have a path drawn from the current location to where they needed to be from room to room, and if it were on a different level, to the nearest elevator. Per-tile pathfinding was limited to finding a path from the current position to the next room on the list, essentially. Large games with lots of units, such as RTS', will usually break up paths over long distances in terms of cells of the map, and more precise pathfinding is used over smaller distances. Or find the path once, and share it among all the units. Things like that.

There's probably some gains to be made in your search here, but it's worth remembering the biggest gains are in what you don't do at all, so if you can find a way to simplify a path by reducing how much, how many or how often, you'll be on the right path.