Dijkstra

class Dijkstra {

    static final costs:Array<Array<Int>> = [[]];
    static final visited:Array<Array<Bool>> = [[]];
    static final added:Array<Array<Bool>> = [[]];
    static final offX = [1, -1, 0, 0];
    static final offY = [0, 0, 1, -1];

    static function initGrids(w:Int, h:Int, maxInt:Int):Void {
        if (costs.length != h) {
            for (iy in costs.length...h) {
                costs[iy] = [];
                visited[iy] = [];
                added[iy] = [];
            }
        }
        for (iy in 0...h) {
            for (ix in 0...w) {
                costs[iy][ix] = maxInt;
                visited[iy][ix] = false;
                added[iy][ix] = false;
            }
        }
    }

    public static function createPath(
        turns:IPointArray, start:IPoint, end:IPoint,
        depthMap:Array<Array<Int>>, maxInt:Int
    ):Void {
        final w = depthMap[0].length;
        final h = depthMap.length;

        final cells = new IPointArray();
        cells.push(start);
        initGrids(w, h, maxInt);
        costs[start.y][start.x] = 0;
        added[start.y][start.x] = true;

        inline function isInside(x:Int, y:Int):Bool {
            return x > -1 && y > -1 && x < w && y < h;
        }

        inline function checkCells(p:IPoint, end:IPoint):Bool {
            if (p.x == end.x && p.y == end.y) return true;
            visited[p.y][p.x] = true;
            for (i in 0...4) {
                final x = p.x + offX[i];
                final y = p.y + offY[i];
                if (!isInside(x, y)) continue;
                if (costs[y][x] > costs[p.y][p.x] + depthMap[y][x])
                    costs[y][x] = costs[p.y][p.x] + depthMap[y][x];
                if (added[y][x]) continue;

                cells.push({x: x, y: y});
                added[y][x] = true;
            }
            return false;
        }

        inline function minCostId():Int {
            var id = -1;
            var min = maxInt;
            for (i in 0...cells.length) {
                final x = cells[i].x;
                final y = cells[i].y;
                if (visited[y][x]) continue;
                if (costs[y][x] >= min) continue;
                min = costs[y][x];
                id = i;
            }
            return id;
        }

        while (true) {
            final id = minCostId();
            if (id == -1) break;
            if (checkCells(cells[id], end)) break;
        }
        final result = costs[end.y][end.x] < maxInt;
        if (!result) return;

        final startCost = costs[start.y][start.x];
        var currentCost = costs[end.y][end.x];
        var currentX = end.x;
        var currentY = end.y;
        turns.push({x: currentX, y: currentY});
        while (currentCost != startCost) {
            final origX = currentX;
            final origY = currentY;
            for (i in 0...4) {
                final x = origX + offX[i];
                final y = origY + offY[i];
                if (!isInside(x, y)) continue;
                if (costs[y][x] < currentCost) {
                    currentCost = costs[y][x];
                    currentX = x;
                    currentY = y;
                }
            }
            turns.push({x: currentX, y: currentY});
        }
    }

}