RblSb

Dijkstra

Jul 6th, 2019
569
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×