[WIP] Quadtree generation and pathfinding algorithm in JavaScript.

qappa.js

const QUAD_DIRS_DIAG = ['nw', 'ne', 'sw', 'se'];
const QUAD_DIRS_ORTHO = ['n', 'w', 's', 'e'];
const QUAD_DIRS_ORTHO_MIRROR = {
    'n': 's',
    's': 'n',
    'w': 'e',
    'e': 'w'
};
const QUAD_MIRRORED_DIRS = {
    'n': ['sw', 'se'],
    's': ['nw', 'ne'],
    'w': ['ne', 'se'],
    'e': ['nw', 'sw']
};

class QuadNode {
    constructor(value, pos) {
        this.leaf = true;
        this.pos = pos || [];
        this.parent = null;

        this.subnodes = {
            nw: null,
            ne: null,
            sw: null,
            se: null
        };

        this.value = (value !== undefined ? value : null);
    }

    setParent(node) {
        this.parent = node;
    }

    addChild(node, dir) {
        this.subnodes[dir] = node;
        node.pos = Array.from(this.pos);
        node.pos.push(dir);
        node.setParent(this);
        this.leaf = false;
        
        return node;
    }
    
    addChildLeaf(dir, value) {
        this.subnodes[dir] = new QuadNode(value, Array.from(this.pos));
        this.subnodes[dir].pos.push(dir);
        this.leaf = false;
        this.subnodes[dir].setParent(this);

        return this.subnodes[dir];
    }

    toJSON() {
        let subnodes = this.subnodes;

        Object.keys(subnodes).forEach((dir) => {
            if (subnodes[dir] != null)
                subnodes[dir] = JSON.parse(subnodes[dir].toJSON());

        });

        return JSON.stringify({
            value: this.value,
            subnodes: subnodes,
            pos: this.pos
        })
    }

    static fromJSON(data) {
        if (typeof data === 'string') data = JSON.parse(data);

        let node = new QuadNode(data.value, data.pos);
        
        Object.keys(data.subnodes).forEach((dir) => {
            if (data.subnodes[dir] != null) {
                node.subnodes[dir] = QuadNode.fromJSON(JSON.stringify(data.subnodes[dir]));
                node.subnodes[dir].setParent(node);
            }

            else
                node.subnodes[dir] = null;
        });

        return node;
    }
}

class GridViewNode extends QuadNode {
    constructor(grid) {
        super(null, []);
        this.grid = grid;
    }

    quadrantAt(pos) {
        // from 0 to 1
        let x = 0;
        let y = 0;
        let width = this.grid.width - 1;
        let height = this.grid.height - 1;

        pos.forEach((p) => {         
            width /= 2;
            height /= 2;

            if (p[1] == 'e')
                x += width;
            
            if (p[0] == 's')
                y += height;

            return true;
        })

        return this.grid.crop.apply(this.grid, [x, y, width, height].map(Math.round));
    }
}

class Grid {
    constructor(width, height, initialValue) {
        this.width = width;
        this.height = height;

        this.data = new Array(width * height).fill(initialValue || 0);
        this.tree = null;
    }

    uniform() {
        if (this.data.length == 1) return true;

        let val = this.data[0];
        return this.data.slice(1).every((x) => x == val)
    }

    set(x, y, value) {
        this.data[y * this.width + x] = value;
        this.tree = null;
    }

    get(x, y) {
        return this.data[y * this.width + x];
    }

    crop(x, y, width, height) {
        let grid = new Grid(width, height, 0);

        for ( let y_ = 0; y_ < height; y_++ )
            for ( let x_ = 0; x_ < width; x_++ )
                grid.set(x_, y_, this.get(x_ + x, y_ + y));

        return grid;
    }

    quadTree(maxDepth) {
        if (this.tree != null) return this.tree;

        let tree = new GridViewNode(this);

        function buildUp(n, quadrant, depth) {
            if (depth === 0) return;

            else if (quadrant.uniform())
                n.value = quadrant.data[0];

            else QUAD_DIRS_DIAG.forEach((dir) => {
                let pos = Array.from(n.pos);
                pos.push(dir);
                let nquad = tree.quadrantAt(pos);
                let ch = n.addChildLeaf(dir);
                
                buildUp(ch, nquad, depth - 1);
            });
        }

        buildUp(tree, this, maxDepth || -1);

        this.tree = tree;
        return tree;
    }
}