diamond.square.js

function powerOfTwo(x) {
    return Math.log2(x) % 1 === 0;
}

module.exports = class DiamondSquare {

    createHeightMap(matrixSize) {

        if (matrixSize <= 2) {
            throw `Matrix Cannot be smaller than 3. Received ${matrixSize}`;
        }

        if (!powerOfTwo(matrixSize - 1)) {
            throw `Matrix size must be 2^n+1. Received ${matrixSize}`;
        }

        const matrix = this.createStartingMatrix(matrixSize);
        const randomFactor = Math.round(Math.random() * 5);
        let size = matrixSize - 1;

        while (size > 1) {
            const middle = size/2;
            for (let i = middle; i < matrixSize - 1; i += size) {
                for (let j = middle; j < matrixSize - 1; j += size) {
                    matrix[i][j] = this.diamondStep(matrix, i, j, middle) + this.generateRandom(randomFactor);
                    //left
                    matrix[i][j - middle] = this.squareStep(matrix, i, j - middle, middle) + this.generateRandom(randomFactor);
                    // top
                    matrix[i - middle][j] = this.squareStep(matrix, i - middle, j, middle) + this.generateRandom(randomFactor);
                    // bottom
                    matrix[i + middle][j] = this.squareStep(matrix, i + middle, j, middle) + this.generateRandom(randomFactor);
                    // right
                    matrix[i][j + middle] = this.squareStep(matrix, i, j + middle, middle) + this.generateRandom(randomFactor);
                }
            }
            size /= 2;
        }

        return matrix;
    }

    createStartingMatrix(matrixSize) {
        const newArray = new Array(matrixSize)
            .fill(0)
            .map((val, ui) => new Array(matrixSize))
        newArray[0][0] = Math.floor(Math.random() * 10);
        newArray[0][matrixSize - 1] = Math.floor(Math.random() * 10);
        newArray[matrixSize - 1][0] = Math.floor(Math.random() * 10);
        newArray[matrixSize - 1][matrixSize - 1] = Math.floor(Math.random() * 10);
        return newArray;
    }

    generateRandom(random) {
        const h = Math.random() * -.1;
        return random * Math.pow(2, h);
    }

    diamondStep(matrix, x, y, middle) {
        function safeMatrixMember(x1, y1) {
            if (matrix[x1] === undefined || matrix[x1][y1] === undefined) {
                meanMembers -= 1;
                return 0;
            }

            return matrix[x1][y1];
        }

        let meanMembers = 4;

        meanMembers = 4;
        return (safeMatrixMember(x + middle, y - middle) +
            safeMatrixMember(x + middle, y + middle) +
            safeMatrixMember(x - middle, y - middle) +
            safeMatrixMember(x - middle, y + middle)) / meanMembers;
    }

    squareStep(matrix, x, y, middle) {
        function safeMatrixMember(x, y) {
            if (matrix[x] === undefined || matrix[x][y] === undefined) {
                meanMembers -= 1;
                return 0;
            }

            return matrix[x][y];
        }

        let meanMembers = 4;
        return (safeMatrixMember(x - middle, y) +
            safeMatrixMember(x + middle, y) +
            safeMatrixMember(x, y - middle) +
            safeMatrixMember(x, y + middle)) / meanMembers;
    }
}

diamond.square.spec.js

const DiamondSquare = require('./diamond.square');

describe(`diamond square`, function () {
    let diamondSquare, dummyMatrix3, dummyMatrix5, dummyMatrix;
    beforeEach(function () {
        diamondSquare = new DiamondSquare();
        dummyMatrix3 = [
            [1, undefined, 2],
            [undefined, undefined, undefined],
            [4, undefined, 3],
        ];

        dummyMatrix5 = [
            [1, undefined, undefined, undefined, 2],
            [undefined, undefined, undefined, undefined, undefined],
            [undefined, undefined, undefined, undefined, undefined],
            [undefined, undefined, undefined, undefined, undefined],
            [4, undefined, undefined, undefined, 5],
        ];

        jest.spyOn(diamondSquare, 'createStartingMatrix').mockImplementation(() => dummyMatrix);
        jest.spyOn(diamondSquare, 'generateRandom').mockReturnValue(1);
    });

    it(`should throw if matrix of size less than 3`, function () {
        expect(() => diamondSquare.createHeightMap(0)).toThrow(`Matrix Cannot be smaller than 3. Received 0`);
        expect(() => diamondSquare.createHeightMap(1)).toThrow(`Matrix Cannot be smaller than 3. Received 1`);
        expect(() => diamondSquare.createHeightMap(2)).toThrow(`Matrix Cannot be smaller than 3. Received 2`);
    });

    it(`should accept only matrix of size 2^n+1`, function () {

        expect(() => diamondSquare.createHeightMap(3)).not.toThrow(`Matrix size must be 2^n+1. Received 3`);
        expect(() => diamondSquare.createHeightMap(5)).not.toThrow(`Matrix size must be 2^n+1. Received 5`);
        expect(() => diamondSquare.createHeightMap(17)).not.toThrow(`Matrix size must be 2^n+1. Received 17`);

        expect(() => diamondSquare.createHeightMap(4)).toThrow(`Matrix size must be 2^n+1. Received 4`);
        expect(() => diamondSquare.createHeightMap(8)).toThrow(`Matrix size must be 2^n+1. Received 8`);
        expect(() => diamondSquare.createHeightMap(19)).toThrow(`Matrix size must be 2^n+1. Received 19`);
    });

    it(`should return a matrix of given size`, function () {
        diamondSquare.createStartingMatrix.mockRestore();
        const heightMap3 = diamondSquare.createHeightMap(3);
        const heightMap5 = diamondSquare.createHeightMap(5);
        const heightMap17 = diamondSquare.createHeightMap(17);
        const heightMap3HasThreeColumns = heightMap3.every((row) => row.length === 3);
        const heightMap5HasFiveColumns = heightMap5.every((row) => row.length === 5);
        const heightMap17HasSeventeenColumns = heightMap17.every((row) => row.length === 17);


        expect(heightMap3.length).toEqual(3);
        expect(heightMap3HasThreeColumns).toEqual(true);
        expect(heightMap5.length).toEqual(5);
        expect(heightMap5HasFiveColumns).toEqual(true);
        expect(heightMap17.length).toEqual(17);
        expect(heightMap17HasSeventeenColumns).toEqual(true);
    });

    it(`should generate a random number that is multiplied by 2 in the power 0 to -0.1`, function () {
        diamondSquare.generateRandom.mockRestore();

        jest.spyOn(Math, 'random').mockReturnValue(1);
        const randomFactorWithOne = diamondSquare.generateRandom(1);

        jest.spyOn(Math, 'random').mockReturnValue(.1);
        const randomFactorWithTenth = diamondSquare.generateRandom(1);

        expect(randomFactorWithOne).toEqual(Math.pow(2, -.1));
        expect(randomFactorWithTenth).toEqual(Math.pow(2, .1*-0.1));
    });
    
    it(`should calculate the center of a matrix correctly`, function () {
        dummyMatrix = dummyMatrix3;
        const heightMap3 = diamondSquare.createHeightMap(3);
        dummyMatrix = dummyMatrix5;
        const heightMap5 = diamondSquare.createHeightMap(5);
        expect(heightMap3[1][1]).toEqual(2.5 + 1);
        expect(heightMap5[2][2]).toEqual(3 + 1);
    });

    it(`should calculate the square correctly`, function () {
        jest.spyOn(diamondSquare, 'createStartingMatrix').mockImplementation(() => dummyMatrix);
        jest.spyOn(diamondSquare, 'generateRandom').mockReturnValue(1);

        dummyMatrix = dummyMatrix3;
        const heightMap3 = diamondSquare.createHeightMap(3);

        dummyMatrix = dummyMatrix5;
        const heightMap5 = diamondSquare.createHeightMap(5);

        expect(heightMap3[0][1]).toEqual(6.5 / 3 + 1);
        expect(heightMap3[1][0]).toEqual(8.5 / 3 + 1);
        expect(heightMap3[2][1]).toEqual(10.5 / 3 + 1);
        expect(heightMap3[1][2]).toEqual(8.5 / 3 + 1);

        expect(heightMap5[0][2]).toEqual(7/3 + 1);
        expect(heightMap5[2][0]).toEqual(4);
        expect(heightMap5[4][2]).toEqual(13/3 + 1);
        expect(heightMap5[2][4]).toEqual(11/3 + 1);
    });

    it(`should run diamond-square sequences`, function () {
        dummyMatrix = dummyMatrix5;
        const sequence = `diamondStep ${[1,2,3,4].reduce((v) => v += 'squareStep ', '')}`
        const expectedSequence = `${[1,2,3,4,5].reduce(v => v += sequence, '')}`;

        let output = '';

        jest.spyOn(diamondSquare, 'diamondStep').mockImplementation(() => {
            output += 'diamondStep ';
        });
        jest.spyOn(diamondSquare, 'squareStep').mockImplementation(() => {
            output += 'squareStep ';
        });

        diamondSquare.createHeightMap(5);

        expect(output).toEqual(expectedSequence);
    });

    it(`should do a diamond-square sequence`, function () {
        dummyMatrix = dummyMatrix5;
        const heightMap5 = diamondSquare.createHeightMap(5);

        expect(heightMap5).toMatchSnapshot();
    });
});