SHARE
TWEET

Dijkstra

RblSb Jul 6th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Dijkstra {
  2.  
  3.     static final costs:Array<Array<Int>> = [[]];
  4.     static final visited:Array<Array<Bool>> = [[]];
  5.     static final added:Array<Array<Bool>> = [[]];
  6.     static final offX = [1, -1, 0, 0];
  7.     static final offY = [0, 0, 1, -1];
  8.  
  9.     static function initGrids(w:Int, h:Int, maxInt:Int):Void {
  10.         if (costs.length != h) {
  11.             for (iy in costs.length...h) {
  12.                 costs[iy] = [];
  13.                 visited[iy] = [];
  14.                 added[iy] = [];
  15.             }
  16.         }
  17.         for (iy in 0...h) {
  18.             for (ix in 0...w) {
  19.                 costs[iy][ix] = maxInt;
  20.                 visited[iy][ix] = false;
  21.                 added[iy][ix] = false;
  22.             }
  23.         }
  24.     }
  25.  
  26.     public static function createPath(
  27.         turns:IPointArray, start:IPoint, end:IPoint,
  28.         depthMap:Array<Array<Int>>, maxInt:Int
  29.     ):Void {
  30.         final w = depthMap[0].length;
  31.         final h = depthMap.length;
  32.  
  33.         final cells = new IPointArray();
  34.         cells.push(start);
  35.         initGrids(w, h, maxInt);
  36.         costs[start.y][start.x] = 0;
  37.         added[start.y][start.x] = true;
  38.  
  39.         inline function isInside(x:Int, y:Int):Bool {
  40.             return x > -1 && y > -1 && x < w && y < h;
  41.         }
  42.  
  43.         inline function checkCells(p:IPoint, end:IPoint):Bool {
  44.             if (p.x == end.x && p.y == end.y) return true;
  45.             visited[p.y][p.x] = true;
  46.             for (i in 0...4) {
  47.                 final x = p.x + offX[i];
  48.                 final y = p.y + offY[i];
  49.                 if (!isInside(x, y)) continue;
  50.                 if (costs[y][x] > costs[p.y][p.x] + depthMap[y][x])
  51.                     costs[y][x] = costs[p.y][p.x] + depthMap[y][x];
  52.                 if (added[y][x]) continue;
  53.  
  54.                 cells.push({x: x, y: y});
  55.                 added[y][x] = true;
  56.             }
  57.             return false;
  58.         }
  59.  
  60.         inline function minCostId():Int {
  61.             var id = -1;
  62.             var min = maxInt;
  63.             for (i in 0...cells.length) {
  64.                 final x = cells[i].x;
  65.                 final y = cells[i].y;
  66.                 if (visited[y][x]) continue;
  67.                 if (costs[y][x] >= min) continue;
  68.                 min = costs[y][x];
  69.                 id = i;
  70.             }
  71.             return id;
  72.         }
  73.  
  74.         while (true) {
  75.             final id = minCostId();
  76.             if (id == -1) break;
  77.             if (checkCells(cells[id], end)) break;
  78.         }
  79.         final result = costs[end.y][end.x] < maxInt;
  80.         if (!result) return;
  81.  
  82.         final startCost = costs[start.y][start.x];
  83.         var currentCost = costs[end.y][end.x];
  84.         var currentX = end.x;
  85.         var currentY = end.y;
  86.         turns.push({x: currentX, y: currentY});
  87.         while (currentCost != startCost) {
  88.             final origX = currentX;
  89.             final origY = currentY;
  90.             for (i in 0...4) {
  91.                 final x = origX + offX[i];
  92.                 final y = origY + offY[i];
  93.                 if (!isInside(x, y)) continue;
  94.                 if (costs[y][x] < currentCost) {
  95.                     currentCost = costs[y][x];
  96.                     currentX = x;
  97.                     currentY = y;
  98.                 }
  99.             }
  100.             turns.push({x: currentX, y: currentY});
  101.         }
  102.     }
  103.  
  104. }
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