class LevelDesc {
    tiles: Tile[][] = [[]];
    ballPos: [number, number] = [0, 0];
    ballDir: number = 0;
    initialLoop: boolean = false;
    placedExit: boolean = false;
}

function randInt(upper: number) {
    // choose a random integer from 0 to upper - 1
    return Math.floor(Math.random() * upper);
}

function makeLevel(w: number, h: number, requireInitialLoop: boolean): LevelDesc {
    let steps = 1000;
    while (true) {
        let result = makeLevelCore(w, h, steps);
        let ok = result.placedExit;
        if(requireInitialLoop) ok = ok && result.initialLoop;
        if (ok) {
            return result;
        }
    }
}

function makeLevelCore(w: number, h: number, steps: number): LevelDesc {
    // The pathsOut variable will keep track of the directions you
    // can exit a given tile from.
    let pathsOut: number[][][] = [];
    for (let col = 0; col < w; col++) {
        pathsOut[col] = [];
        for (let row = 0; row < h; row++) {
            pathsOut[col][row] = [];
        }
    }

    // Make the "maze" of connections. We'll do this by starting with
    // a single tile (and no connections) and adding a connection at
    // random every step, while keeping the whole thing connected and
    // not creating any vertices of degree 4.
    let seenTilesSet: Set<[number, number]> = new Set();
    let seenTilesList: [number, number][] = [];
    seenTilesSet.add([randInt(w), randInt(h)]);
    seenTilesList.push([randInt(w), randInt(h)]);
    for (let k = 0; k < steps; k++) {
        // Choose a random tile (that we have seen) and direction.
        let ok = false;
        let t: [number, number] = [-1, -1];
        let ot: [number, number] = [-1, -1];
        let d: number = -1;
        while (!ok) {
            ok = true;
            t = seenTilesList[randInt(seenTilesList.length)];
            d = randInt(4);
            ot = [t[0] + DIR_OFFSETS[d][0], t[1] + DIR_OFFSETS[d][1]];
            if (ot[0] < 0 || ot[0] >= w || ot[1] < 0 || ot[1] >= h) {
                ok = false;
            }
        }
        // Check if adding this edge will make either vertex have degree 4,
        // and whether we already have this edge. We'll also try to avoid
        // making lots of degree-3 tiles too close to each other.
        let pot = pathsOut[t[0]][t[1]];
        let poot = pathsOut[ot[0]][ot[1]];
        if (pot.indexOf(d) > -1 || pot.length >= 3 || poot.length >= 3) {
            ok = false;
        }
        else if (pot.length == 2 && poot.length == 2) {
            ok = false;
        }
        else if (pot.length >= 2 || poot.length >= 2) {
            for (let offset of DIR_OFFSETS) {
                for (let orig of [t, ot]) {
                    let curx = orig[0] + offset[0];
                    let cury = orig[1] + offset[1];
                    if (curx >= 0 && curx < w && cury >= 0 && cury < h &&
                        pathsOut[curx][cury].length >= 3) {
                        ok = false;
                    }
                }
            }
        }

        if (ok) {
            // we're ok - add this edge
            pot.push(d);
            poot.push((d + 2) % 4);
            if (!seenTilesSet.has(ot)) {
                seenTilesSet.add(ot);
                seenTilesList.push(ot);
            }
        }
    }

    // Make the grid of tiles and fill the tiles info
    let tiles: Tile[][] = [];
    for (let col = 0; col < w; col++) {
        tiles[col] = [];
        for (let row = 0; row < h; row++) {
            let t = new Tile();
            let pot = pathsOut[col][row];
            if (pot.length <= 2) {
                for (let dir of pot) {
                    t.outDirs[dir] = true;
                }
            }
            else if (pot.length === 3) {
                // There's only one direction missing so we can work
                // out what direction it is by subtracting the sum from 6.
                let missing = 6 - pot[0] - pot[1] - pot[2];
                let offset = randInt(2) + 1;
                let firstDir = (missing + offset) % 4;
                let secondDir = (firstDir + 1) % 4;
                t.outDirs[firstDir] = true;
                t.outDirs[secondDir] = true;
                t.modi = true;
            }
            else {
                throw Error("Not handled.");
            }
            tiles[col][row] = t;
        }
    }

    // place the ball
    let ballPos = seenTilesList[randInt(seenTilesList.length)];
    let bt = tiles[ballPos[0]][ballPos[1]];
    let ballDirs = [];
    for (let k = 0; k < 4; k++) if (bt.outDirs[k]) ballDirs.push(k);
    let ballDir = ballDirs[randInt(ballDirs.length)];

    // Calculate the ball's initial path, because we want to place the exit
    // away from it.
    let [predictedTiles, initialLoop] = predictBallPath(ballPos, ballDir, tiles);

    // Calculate each tile's distance from the initial path
    let dfip: number[][] = []; // distance from initial path
    for (let col = 0; col < w; col++) {
        dfip[col] = [];
        for (let row = 0; row < h; row++) {
            dfip[col][row] = Number.POSITIVE_INFINITY;
        }
    }
    let q = [];
    for (let xy of predictedTiles) {
        dfip[xy[0]][xy[1]] = 0;
        q.push(xy);
    }
    while (q.length > 0) {
        let curxy = q.splice(0, 1)[0];
        let val = dfip[curxy[0]][curxy[1]];
        for (let offset of DIR_OFFSETS) {
            let nextxy: [number, number] = [curxy[0] + offset[0], curxy[1] + offset[1]];
            if (nextxy[0] >= 0 && nextxy[0] < w && nextxy[1] >= 0 && nextxy[1] < h) {
                if (val + 1 < dfip[nextxy[0]][nextxy[1]]) {
                    dfip[nextxy[0]][nextxy[1]] = val + 1;
                    q.push(nextxy);
                }
            }
        }
    }
    let goodSpots = [];
    for (let col = 0; col < w; col++) {
        for (let row = 0; row < h; row++) {
            let val = dfip[col][row];
            let accessible = tiles[col][row].outDirs.some(x => x);
            if (accessible && val >= 4) {
                goodSpots.push([col, row]);
            }
        }
    }

    // place the exit and make it enterable from all sides
    let placedExit = goodSpots.length > 0;
    if (placedExit) {
        let exitLoc = goodSpots[randInt(goodSpots.length)];
        let t = tiles[exitLoc[0]][exitLoc[1]];
        t.exit = true;
        t.outDirs = [true, true, true, true];
        t.modi = false;
    }

    let result = new LevelDesc();
    result.tiles = tiles;
    result.ballPos = ballPos;
    result.ballDir = ballDir;
    result.initialLoop = initialLoop;
    result.placedExit = placedExit;
    return result;
}

function predictBallPath(initialBallPos: [number, number], initialBallDir: number, tiles: Tile[][]):
    [[number, number][], boolean] {
    // Simulate the movement of the ball from the current information,
    // and make a list of tile coordinates it will visit.
    // While we're at it, determine if the initial path is a loop.
    let visitedTiles: [number, number][] = [];
    let visitedStates: boolean[][][] = [];
    let gw = tiles.length;
    let gh = tiles[0].length;
    for (let col = 0; col < gw; col++) {
        visitedStates[col] = [];
        for (let row = 0; row < gh; row++) {
            visitedStates[col][row] = [];
            for (let dir = 0; dir < 4; dir++) {
                visitedStates[col][row][dir] = false;
            }
        }
    }
    let lastPos = initialBallPos;
    let curDir = initialBallDir;
    let nextPos: [number, number] = [lastPos[0] + DIR_OFFSETS[curDir][0], lastPos[1] + DIR_OFFSETS[curDir][1]];
    let done = false;
    let isLoop = true;
    while (!done) {
        // Keep a record of the current state
        visitedTiles.push(lastPos);
        visitedStates[lastPos[0]][lastPos[1]][curDir] = true;
        // Simulate bounce, if needed
        let bounce = checkBounceNeeded(nextPos, curDir, tiles);
        if (bounce) {
            let nbp = nextPos;
            nextPos = lastPos;
            lastPos = nbp;
            curDir = (curDir + 2) % 4;
            isLoop = false;
        }
        // Simulate decision on reaching the centre of the next tile
        curDir = calculateNextBallDir(nextPos, curDir, tiles);
        lastPos = nextPos;
        nextPos = [lastPos[0] + DIR_OFFSETS[curDir][0], lastPos[1] + DIR_OFFSETS[curDir][1]];
        // Check if we've seen this state before.
        if (visitedStates[lastPos[0]][lastPos[1]][curDir]) {
            done = true;
        }
    }
    return [visitedTiles, isLoop];
}