Advertisement
Ulabael

A* with sizes

Oct 23rd, 2022
948
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function scr_find_path(cellStart, cellEnd, grid, pushStart = false, size = [1, 1]){
  2.     var frontier = ds_priority_create()
  3.     var cameFrom = ds_map_create()
  4.     var costSoFar = ds_map_create()
  5.     var maxX = ds_grid_width(grid)
  6.    
  7.     if is_array(cellStart) {
  8.         cellStart = cellStart[0] + cellStart[1] * maxX;
  9.     }
  10.     if is_array(cellEnd) {
  11.         cellEnd = cellEnd[0] + cellEnd[1] * maxX;
  12.     }
  13.    
  14.     ds_priority_add(frontier, cellStart, 0)
  15.     ds_map_add(cameFrom, cellStart, noone)
  16.     ds_map_add(costSoFar, cellStart, 0)
  17.     var current = noone;
  18.     while !ds_priority_empty(frontier)
  19.     {
  20.         current = ds_priority_delete_min(frontier)
  21.         if (current == cellEnd) break
  22.        
  23.         var vneighbors = scr_neighbors(current, grid,,size) // Получаем ID-соседей
  24.         for (var i = 0; i < array_length(vneighbors); ++i)
  25.         {
  26.             var ncellX = vneighbors[i] mod maxX;
  27.             var ncellY = vneighbors[i] div maxX;
  28.             var newCost = ds_map_find_value(costSoFar, current) + ds_grid_get(grid, ncellX, ncellY)
  29.            
  30.             if is_undefined(ds_map_find_value(costSoFar, vneighbors[i]))
  31.             or newCost < ds_map_find_value(costSoFar, vneighbors[i])
  32.             {
  33.                 var priority = newCost + scr_heuristic(cellEnd, vneighbors[i], grid)
  34.                 ds_map_add(costSoFar, vneighbors[i], newCost)
  35.                 ds_priority_add(frontier, vneighbors[i], priority)
  36.                 ds_map_add(cameFrom, vneighbors[i], current)
  37.             }
  38.         }
  39.     }
  40.  
  41.     if (current == cellEnd)
  42.     {
  43.         var path = [];
  44.         while current != cellStart
  45.         {
  46.             array_push(path, current)
  47.             current = ds_map_find_value(cameFrom, current)
  48.         }
  49.         if (pushStart) array_push(path, cellStart);
  50.         ds_map_destroy(cameFrom);
  51.         ds_map_destroy(costSoFar);
  52.         ds_priority_destroy(frontier);
  53.         path = scr_reverse_array(path);
  54.         return path
  55.     }
  56.     else
  57.     {  
  58.         ds_map_destroy(cameFrom)
  59.         ds_map_destroy(costSoFar)
  60.         ds_priority_destroy(frontier)
  61.         return [];
  62.     }  
  63. }
  64.  
  65. function scr_neighbors(start, grid, fourSides = false, size = [1, 1])
  66. {
  67.     var cellx, celly, cells;
  68.     var neighborsAr = [];
  69.     var maxX = ds_grid_width(grid);
  70.     if is_array(start) {
  71.         cellx = start[0];
  72.         celly = start[1];      
  73.     }
  74.     else {
  75.         cellx = start mod maxX;
  76.         celly = start div maxX;
  77.     }
  78.    
  79.     if (fourSides) cells = [[cellx-1, celly], [cellx, celly-1], [cellx+1, celly], [cellx, celly+1]]
  80.     else cells = [[cellx -1, celly-1], [cellx, celly-1], [cellx+1, celly-1], [cellx-1, celly], [cellx+1, celly], [cellx-1, celly+1], [cellx, celly+1], [cellx+1, celly+1]]
  81.    
  82.     for (var i = 0; i < array_length(cells); ++i)
  83.     {
  84.         var push = true;
  85.  
  86.         for (var sy = 0; sy < size[1]; ++sy) {
  87.             for (var sx = 0; sx < size[0]; ++sx) {
  88.                 if cells[i][0] + sx < 0 or cells[i][0] + sx >= room_width div CW
  89.                 or cells[i][1] + sy < 0 or cells[i][1] + sy >= room_height div CH
  90.                 or ds_grid_get(grid, cells[i][0] + sx, cells[i][1] + sy) == 0
  91.                 {
  92.                     push = false;
  93.                     break;
  94.                 }
  95.             }
  96.             if !(push) break;
  97.         }
  98.         if !(push) continue
  99.        
  100.        
  101.         if (push) {
  102.             array_push(neighborsAr, cells[i][0] + cells[i][1] * maxX)  
  103.         }
  104.     }
  105.  
  106.     return neighborsAr
  107. }
  108.  
  109. function scr_heuristic(a,b, grid)
  110. {
  111.     var maxX = ds_grid_width(grid);
  112.     var ax, ay, bx, by;
  113.     if !is_array(a) {
  114.         ax = a mod maxX;
  115.         ay = a div maxX;
  116.     }
  117.     else {
  118.         ax = a[0];
  119.         ay = a[1];
  120.     }
  121.     if !(is_array(b)) {
  122.         bx = b mod maxX;
  123.         by = b div maxX;
  124.     }
  125.     else {
  126.         bx = b[0];
  127.         by = b[1];
  128.     }
  129.     return abs(ax - bx) + abs(ay - by)
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement