2D grid deletion / manipulation algorithm - Organization of elements and their positions in array

Question

I would like to present a problem that I have been fighting with for a few months. In summary, it is based on the mechanics of the board for a web-based game (developing in Javascript). The board is made up of an 8x6 grid, which may contain elements of 1 or 4 pixels.

The main problem lies in how to store each type of figure in the multidimensional array, bearing in mind that later we want to manipulate them and obtain the properties of the object, delete it and make others reposition them, move them from one position to another, etc ... Mainly the problem has been generated when deleting an item from the board (by clicking on it), I cannot get everything to be rearranged correctly. For example:

Example of deletion We would start with the board in position 1, we erase the item marked in position 2 and the board should be as in figure 3.

Currently I have proposed a two-dimensional array, to the elements type 'hero' I add 2 times in one row and 2 in another, and I try to calculate if there are elements below, at the sides, but I always miss a variable or when deleting , they lose the relation in their position, I am saturating the code of if's and I see that I am going to end something that I will not understand neither myself and surely have a faster and more effective solution. My board currently would be as follows (corresponds to the first photo):

myBoard = [
[],
[knightObject, knightObject],
[null, heroObject, heroObjectNull, knightObject],
[knightObject, heroObjectNull, heroObjectNull, heroObject, heroObjectNull],
[knightObject, knightObject, null, heroObjectNull, heroObjectNull, knightObject],
[],
[knightObject, knightObject],
[knightObject]
];

Where knightObject, heroObject, and heroObjectNull are the same object with different properties, and null are blanks. This form was working well when generating a random array and moving elements, but when it comes to deleting or generating new movements I find the manipulation of the array very complicated. Can anyone think of a better approach? I am not looking for the problem to be carried out by me, with an idea it would be much more than enough.

Thank you in advance, I will be attentive in case any clarification arises, Greetings.

Answer 1

I think the problem might be easier if the array representing the board is fully populated, and the Knights and Heros have unique identifiers so that it is easier to determine the group of cells belonging to the same Hero.

Then, make use of a function that walks the rows starting with the second to the last, looking for empty cells below the Knights and Heros to determine whether they can drop down a row...

Take a look at the following sample code. In the first test, nothing can drop, so the result remains the same. In the second test, a Knight has been removed ( ID 1006 ) and the result reflects the Knights and Heros that can drop...

function shiftCells( board ) {
  let rowCount = board.length;
  let colCount = board[0].length;
  
  for ( row = rowCount - 2; 0 <= row; row-- ) {
    let test = new Map();
    for ( col = 0; col < colCount; col++ ) {
      // Check if there is an ID in the cell...
      if ( board[ row ][ col ] ) {
        // ...and if so, then accumulate whether all cells below this ID are empty.
        let currentTest = test.get( board[ row ][ col ] ) == undefined ? true : test.get( board[ row ][ col ] );
        test.set( board[ row ][ col ], currentTest && ( board[ row + 1 ][ col ] === null ) );
      }
    }

    // Now, loop through the test list to see if we need to drop any cells down.
    for ( col = 0; col < colCount; col++ ) {
      // Again, check if there is an ID in the cell...
      if ( board[ row ][ col ] ) {
        // ...and if so, then were all the cells below this ID empty?
        if ( test.get( board[ row ][ col ] ) ) {
          // If so, then move the ID down a row.
          board[ row + 1 ][ col ] = board[ row ][ col ];
          board[ row ][ col ] = null;
        }
      }
    }
  }
}

function printBoard( message, board ) {
  console.log( message )
  for ( row = 0; row < board.length; row++ ) {
    let rowText = '';
    for ( col = 0; col < board[0].length; col++ ) {
      rowText += board[ row ][ col ] + ' ';
    }
    console.log( rowText );
  }
  console.log( '\n' );
}

var myBoard;

myBoard = [
[ null, null, null, null, 1000, null, null, null ],
[ null, null, null, 2000, 2000, null, null, null ],
[ null, null, 1001, 2000, 2000, null, null, null ],
[ null, null, 2001, 2001, null, null, null, null ],
[ null, 1002, 2001, 2001, 1003, null, 1004, null ],
[ null, 1005, null, 1006, 1007, null, 1008, 1009 ]
];

printBoard( 'Test 1', myBoard );
shiftCells( myBoard );
printBoard( 'Test 1 results', myBoard );

myBoard = [
[ null, null, null, null, 1000, null, null, null ],
[ null, null, null, 2000, 2000, null, null, null ],
[ null, null, 1001, 2000, 2000, null, null, null ],
[ null, null, 2001, 2001, null, null, null, null ],
[ null, 1002, 2001, 2001, 1003, null, 1004, null ],
[ null, 1005, null, null, 1007, null, 1008, 1009 ]
];

printBoard( 'Test 2', myBoard );
shiftCells( myBoard );
printBoard( 'Test 2 results', myBoard );

Hope this helps...

EDIT: The above code had a shortcoming in that it would only shift a figure down one row, whereas in some cases, removing a figure requires some figures to drop more than one cell. Running the above algorithm multiple times on the same board is a hack that works, but is suboptimal. The following version takes a different approach...

The main difference is that this version tracks the figures, and builds the board on the fly. In doing so, after deleting a figure, the algorithm walks the list of figures starting from the bottom most row, to determine if the row beneath the figure is empty, and if so, drops the figure a row. It continues checking to see if the figure can continue dropping another row, before moving on to the next figure...

function printBoard( message, board ) {
  console.log( message )
  for ( row = 0; row < board.length; row++ ) {
    let rowText = '';
    for ( col = 0; col < board[0].length; col++ ) {
      rowText += board[ row ][ col ] + ' ';
    }
    console.log( rowText );
  }
  console.log( '\n' );
}

function buildBoardFromFigures( figures ) {
  let board = [];
  
  for ( let row = 0; row < boardHeight; row++ ) {
    board[ row ] = [];
    for ( let col = 0; col < boardWidth; col++ ) {
      board[ row ][ col ] = null;
    } 
  }
      
  for ( let id of Object.keys( figures ) ) {
    for ( let row = figures[ id ].row; row < figures[ id ].row + figures[ id ].height; row++ ) {
      for ( let col = figures[ id ].col; col < figures[ id ].col + figures[ id ].width; col++ ) {
        board[ row ][ col ] = id;
      } 
    } 
  }
  
  return board;
}

function shiftDown( figures ) {

  let bottomFirst = Object.keys( figures ).sort( ( a, b ) => figures[ b ].row - figures[ a ].row );

  let board = buildBoardFromFigures( figures );
  let rowCount = board.length;
  
  for ( let id of bottomFirst ) {
    let emptyBelow = true;
    while ( emptyBelow ) {
      let rowToCheck = figures[ id ].row + figures[ id ].height;
      
      for ( let col = figures[ id ].col; col < figures[ id ].col + figures[ id ].width; col++ ) {
        emptyBelow = emptyBelow && ( rowToCheck < rowCount && board[ rowToCheck ][ col ] == null );
      }
      
      if ( emptyBelow ) {
        for ( let col = figures[ id ].col; col < figures[ id ].col + figures[ id ].width; col++ ) {
          board[ figures[ id ].row ][ col ] = null;
          board[ figures[ id ].row + figures[ id ].height ][ col ] = id;
        }
        figures[ id ].row++;
      }
    }
  }
  
  return board;
}


var boardHeight = 6;
var boardWidth = 8;

var myFigures;
myFigures = {
  "1000": { type: "knight", row: 0, col: 4, width: 1, height: 1 },
  "2000": { type: "hero",   row: 1, col: 3, width: 2, height: 2 },
  "1001": { type: "knight", row: 2, col: 2, width: 1, height: 1 },
  "2001": { type: "hero",   row: 3, col: 2, width: 2, height: 2 },
  "1002": { type: "knight", row: 4, col: 1, width: 1, height: 1 },
  "1003": { type: "knight", row: 4, col: 4, width: 1, height: 1 },
  "1004": { type: "knight", row: 4, col: 6, width: 1, height: 1 },
  "1005": { type: "knight", row: 5, col: 1, width: 1, height: 1 },
  "1006": { type: "knight", row: 5, col: 3, width: 1, height: 1 },
  "1007": { type: "knight", row: 5, col: 4, width: 1, height: 1 },
  "1008": { type: "knight", row: 5, col: 6, width: 1, height: 1 },
  "1009": { type: "knight", row: 5, col: 7, width: 1, height: 1 }
};


printBoard( 'Test 1', buildBoardFromFigures( myFigures ) );
shiftDown( myFigures );
printBoard( 'Test 1 Result', buildBoardFromFigures( myFigures ) );

delete myFigures[ "2000" ];

printBoard( 'Test 2', buildBoardFromFigures( myFigures ) );
shiftDown( myFigures );
printBoard( 'Test 2 Result', buildBoardFromFigures( myFigures ) );

This second answer is cleaner than the first, but might cause more overhauling of your app...