SHARE
TWEET

Untitled

a guest Dec 13th, 2018 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public static class Pathfinding {
  2.  
  3.     public static List<PathfindingNode> Find(PathfindingNode start, PathfindingNode end, PathfindingNode[,] map, int width, int height)
  4.     {
  5.         int x, y, cost = 0, step = 0;
  6.  
  7.         map[end.x, end.y].cost = 0; // начало поиска с точки назначения
  8.  
  9.         if(start.x - 1 >= 0)
  10.         {
  11.             if(map[start.x-1, start.y].cost == -2) step++;
  12.         }
  13.         else step++;
  14.  
  15.         if(start.y-1 >= 0)
  16.         {
  17.             if(map[start.x, start.y-1].cost == -2) step++;
  18.         }
  19.         else step++;
  20.  
  21.         if(start.x+1 < width)
  22.         {
  23.             if(map[start.x+1, start.y].cost == -2) step++;
  24.         }
  25.         else step++;
  26.  
  27.         if(start.y+1 < height)
  28.         {
  29.             if(map[start.x, start.y+1].cost == -2) step++;
  30.         }
  31.         else step++;
  32.  
  33.         // проверка на доступность (например, юнит окружен)
  34.         if(step == 4) return null; else step = 0;
  35.  
  36.         while(true) // цикл поиска
  37.         {
  38.             for(y = 0; y < height; y++)
  39.             {
  40.                 for(x = 0; x < width; x++)
  41.                 {
  42.                     if(map[x, y].cost == step) // находим клетку, соответствующую текущему шагу
  43.                     {
  44.                         if(x-1 >= 0) // если не выходим за границы массива
  45.                         if(map[x-1, y].cost == -1) // если клетка еще не проверялась
  46.                         {
  47.                             cost = step + 1; // сохраняем стоимость клетки
  48.                             map[x-1, y].cost = cost; // назначаем стоимость
  49.                         }
  50.  
  51.                         if(y-1 >= 0)
  52.                         if(map[x, y-1].cost == -1)
  53.                         {
  54.                             cost = step + 1;
  55.                             map[x, y-1].cost = cost;
  56.                         }
  57.  
  58.                         if(x+1 < width)
  59.                         if(map[x+1, y].cost == -1)
  60.                         {
  61.                             cost = step + 1;
  62.                             map[x+1, y].cost = cost;
  63.                         }
  64.  
  65.                         if(y+1 < height)
  66.                         if(map[x, y+1].cost == -1)
  67.                         {
  68.                             cost = step + 1;
  69.                             map[x, y+1].cost = cost;
  70.                         }
  71.                     }
  72.                 }
  73.             }
  74.  
  75.             step++; // следующий шаг/волна
  76.  
  77.             if(map[start.x, start.y].cost != -1) break; // если путь найден, выходим из цикла
  78.             if(step != cost || step > width * height) return null; // если путь найти невозможно, возврат
  79.         }
  80.  
  81.         List<PathfindingNode> result = new List<PathfindingNode>(); // массив пути
  82.  
  83.         // начало поиска со старта
  84.         x = start.x;
  85.         y = start.y;
  86.  
  87.         step = map[x, y].cost; // определяем базовую стоимость
  88.  
  89.         while(x != end.x || y != end.y) // прокладка пути
  90.         {
  91.             if(x-1 >= 0 && y-1 >= 0) // если не выходим за границы массива
  92.             if(map[x-1, y-1].cost >= 0) // если клетка проходима
  93.             if(map[x-1, y-1].cost < step) // если эта клетка дешевле, базовой стоимости
  94.             {
  95.                 step = map[x-1, y-1].cost; // новая базовая стоимость
  96.                 result.Add(map[x-1, y-1]); // добавляем клетку в массив пути
  97.                 x--;
  98.                 y--;
  99.                 continue; // переходим на следующий цикл
  100.             }
  101.  
  102.             if(y-1 >= 0 && x+1 < width)
  103.             if(map[x+1, y-1].cost >= 0)
  104.             if(map[x+1, y-1].cost < step)
  105.             {
  106.                 step = map[x+1, y-1].cost;
  107.                 result.Add(map[x+1, y-1]);
  108.                 x++;
  109.                 y--;
  110.                 continue;
  111.             }
  112.  
  113.             if(y+1 < height && x+1 < width)
  114.             if(map[x+1, y+1].cost >= 0)
  115.             if(map[x+1, y+1].cost < step)
  116.             {
  117.                 step = map[x+1, y+1].cost;
  118.                 result.Add(map[x+1, y+1]);
  119.                 x++;
  120.                 y++;
  121.                 continue;
  122.             }
  123.  
  124.             if(y+1 < height && x-1 >= 0)
  125.             if(map[x-1, y+1].cost >= 0)
  126.             if(map[x-1, y+1].cost < step)
  127.             {
  128.                 step = map[x-1, y+1].cost;
  129.                 result.Add(map[x-1, y+1]);
  130.                 x--;
  131.                 y++;
  132.                 continue;
  133.             }
  134.  
  135.             if(x-1 >= 0)
  136.             if(map[x-1, y].cost >= 0)
  137.             if(map[x-1, y].cost < step)
  138.             {
  139.                 step = map[x-1, y].cost;
  140.                 result.Add(map[x-1, y]);
  141.                 x--;
  142.                 continue;
  143.             }
  144.  
  145.             if(y-1 >= 0)
  146.             if(map[x, y-1].cost >= 0)
  147.             if(map[x, y-1].cost < step)
  148.             {
  149.                 step = map[x, y-1].cost;
  150.                 result.Add(map[x, y-1]);
  151.                 y--;
  152.                 continue;
  153.             }
  154.  
  155.             if(x+1 < width)
  156.             if(map[x+1, y].cost >= 0)
  157.             if(map[x+1, y].cost < step)
  158.             {
  159.                 step = map[x+1, y].cost;
  160.                 result.Add(map[x+1, y]);
  161.                 x++;
  162.                 continue;
  163.             }
  164.  
  165.             if(y+1 < height)
  166.             if(map[x, y+1].cost >= 0)
  167.             if(map[x, y+1].cost < step)
  168.             {
  169.                 step = map[x, y+1].cost;
  170.                 result.Add(map[x, y+1]);
  171.                 y++;
  172.                 continue;
  173.             }
  174.  
  175.             return null; // текущая клетка не прошла проверку, ошибка пути, возврат
  176.         }
  177.  
  178.         return result; // возвращаем найденный маршрут
  179.     }
  180. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top