AStar.test.js

const { AStar } = require('.');

describe('A*', () => {
  describe('Completes grid successfully', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 0, 0, 0],
        [1, 0, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 0,
        j: 0,
      };
      const end = {
        i: 3,
        j: 5,
      };
      const completedPath = [
        [3, 5],
        [3, 4],
        [3, 3],
        [3, 2],
        [3, 1],
        [2, 0],
        [1, 0],
        [0, 0],
      ];
      expect(AStar(start, end, ROW, COL, inputGrid)).toEqual(completedPath);
    });
  });

  describe('Completes large grid successfully', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1],
        [1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1],
        [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1],
        [0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 0,
        j: 0,
      };
      const end = {
        i: 8,
        j: 11,
      };
      const completedPath = [
        [8, 11],
        [8, 10],
        [7, 9],
        [6, 8],
        [5, 9],
        [5, 10],
        [4, 11],
        [3, 11],
        [2, 11],
        [1, 11],
        [0, 10],
        [1, 9],
        [0, 8],
        [1, 7],
        [1, 6],
        [2, 5],
        [2, 4],
        [2, 3],
        [2, 2],
        [2, 1],
        [1, 0],
        [0, 0],
      ];
      expect(AStar(start, end, ROW, COL, inputGrid)).toEqual(completedPath);
    });
  });

  describe('Cannot complete grid successfully', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 0,
        j: 0,
      };
      const end = {
        i: 3,
        j: 5,
      };
      expect(() => {
        AStar(start, end, ROW, COL, inputGrid);
      }).toThrowError('Error: Endpoint cannot be reached');
    });
  });

  describe('Endpoint out of grid bounds', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 0,
        j: 0,
      };
      const end = {
        i: 5,
        j: 5,
      };
      expect(() => {
        AStar(start, end, ROW, COL, inputGrid);
      }).toThrowError('Error: Endpoint outside grid bounds');
    });
  });

  describe('Endpoint value is zero', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 0,
        j: 0,
      };
      const end = {
        i: 1,
        j: 3,
      };
      expect(() => {
        AStar(start, end, ROW, COL, inputGrid);
      }).toThrowError('Error: Endpoint is unreachable');
    });
  });
  describe('Completes grid successfully when no block', () => {
    it('A*', () => {
      const inputGrid = [
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
      ];
      const ROW = inputGrid.length;
      const COL = inputGrid[0].length;
      const start = {
        i: 2,
        j: 2,
      };
      const end1 = {
        i: 0,
        j: 0,
      };
      const completedPath1 = [
        [0, 0],
        [1, 1],
        [2, 2],
      ];
      expect(AStar(start, end1, ROW, COL, inputGrid)).toEqual(completedPath1);

      const end2 = {
        i: 0,
        j: 2,
      };
      const completedPath2 = [
        [0, 2],
        [1, 2],
        [2, 2],
      ];
      expect(AStar(start, end2, ROW, COL, inputGrid)).toEqual(completedPath2);

      const end3 = {
        i: 0,
        j: 4,
      };
      const completedPath3 = [
        [0, 4],
        [1, 3],
        [2, 2],
      ];
      expect(AStar(start, end3, ROW, COL, inputGrid)).toEqual(completedPath3);

      const end4 = {
        i: 2,
        j: 4,
      };
      const completedPath4 = [
        [2, 4],
        [2, 3],
        [2, 2],
      ];
      expect(AStar(start, end4, ROW, COL, inputGrid)).toEqual(completedPath4);

      const end5 = {
        i: 4,
        j: 4,
      };
      const completedPath5 = [
        [4, 4],
        [3, 3],
        [2, 2],
      ];
      expect(AStar(start, end5, ROW, COL, inputGrid)).toEqual(completedPath5);

      const end6 = {
        i: 4,
        j: 2,
      };
      const completedPath6 = [
        [4, 2],
        [3, 2],
        [2, 2],
      ];
      expect(AStar(start, end6, ROW, COL, inputGrid)).toEqual(completedPath6);

      const end7 = {
        i: 4,
        j: 0,
      };
      const completedPath7 = [
        [4, 0],
        [3, 1],
        [2, 2],
      ];
      expect(AStar(start, end7, ROW, COL, inputGrid)).toEqual(completedPath7);

      const end8 = {
        i: 2,
        j: 0,
      };
      const completedPath8 = [
        [2, 0],
        [2, 1],
        [2, 2],
      ];
      expect(AStar(start, end8, ROW, COL, inputGrid)).toEqual(completedPath8);
    });
  });
});