zM pathfinder

// zursor master pathfinder
// updated may 26, 2019

zM.dependenciesLoaded |= 0b100000;

var visit = [];

zM.dos = function(dx, dy, items, gridSpace) {
    var gridX = 400/gridSpace,
        gridY = 300/gridSpace;
    var grid = [];
    visit = [];
    for (var i = 0; i < gridY; i++) {
        grid[i] = [];
        visit[i] = [];
        for (var j = 0; j < gridX; j++) grid[i][j] = 0, visit[i][j] = 0;
    }
    items.forEach(function(d) {
        if (d.type === 1) {
            for (var i = 0; i < d.h; i+=gridSpace) {
                for (var j = 0; j < d.w; j+=gridSpace) {
                    grid[(d.y+i)/gridSpace][(d.x+j)/gridSpace] = 3;
                }
            }
        }
    });
    var bfs = [[dx,dy]],
        bfs2 = [];
    while (bfs.length) {
        bfs.forEach(function(dat) {
            var x = dat[0],
                y = dat[1];
            if (grid[y][x] == 3) return;
            grid[y][x] = 3;
            for (var X = x + 1; X < gridX && !(grid[y][X] & 1); X++) {
                grid[y][X] |= 1;
                if (!visit[y][X]) {
                    visit[y][X] = [x, y], bfs2.push([X, y]);
                }
            }
            for (var X = x - 1; X >= 0 && !(grid[y][X] & 1); X--) {
                grid[y][X] |= 1;
                if (!visit[y][X]) {
                    visit[y][X] = [x, y], bfs2.push([X, y]);
                }
            }
            for (var Y = y + 1; Y < gridY && !(grid[Y][x] & 2); Y++) {
                grid[Y][x] |= 2;
                if (!visit[Y][x]) {
                    visit[Y][x] = [x, y], bfs2.push([x, Y]);
                }
            }
            for (var Y = y - 1; Y >= 0 && !(grid[Y][x] & 2); Y--) {
                grid[Y][x] |= 2;
                if (!visit[Y][x]) {
                    visit[Y][x] = [x, y], bfs2.push([x, Y]);
                }
            }
        });
        bfs = bfs2;
        bfs2 = [];
    }
}

zM.path = function(ox, oy, dx, dy, items, grid) {

    var rdx = dx, rdy = dy;
    ox /= grid;
    oy /= grid;
    dx /= grid;
    dy /= grid;

    ox |= 0;
    oy |= 0;
    dx |= 0;
    dy |= 0;

    var mov = [];
    if (!(ox == dx && oy == dy)) {
        zM.dos(ox,oy,items,grid);
        var xy2 = [dx,dy];
        while (visit[xy2[1]][xy2[0]]) {
            mov.push(xy2);
            xy2 = visit[xy2[1]][xy2[0]];
        }

        mov.reverse();
    }

    for (var i = 0; i < mov.length; ++i) {
        mov[i][0] *= grid;
        mov[i][0] += grid/2;
        mov[i][1] *= grid;
        mov[i][1] += grid/2;
    }
    mov.push([rdx, rdy]);
    return mov;
}