二维网格删除/操作算法 - 元素的组织及其在数组中的位置

Question

我想提出一个困扰我几个月的问题。总之，它基于网络游戏的棋盘机制（在 Javascript 中开发）。该板由 8x6 网格组成，其中可能包含 1 或 4 个像素的元素。

主要问题在于多维数组中如何存储每一种图形，考虑到后面我们要操作它们，获取对象的属性，删除它，让别人重新定位，移动它们从一个位置到另一个位置，等等...主要是从板上删除项目（通过单击它）时产生的问题，我无法正确重新排列所有内容。例如：

删除示例我们将从位置 1 的木板开始，我们删除位置 2 标记的项目，木板应如图 3 所示。

目前我提出了一个二维数组，元素类型'hero'我在一行中添加2次，在另一行中添加2次，我尝试计算是否有元素在下面，在两侧，但我总是错过一个变量，或者在删除时，他们失去了他们位置上的关系，我正在使 if 的代码饱和，我看到我要结束一些我自己都不会理解的东西，并且肯定会有更快更多有效的解决方案。我目前的板子如下（对应第一张照片）：

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

其中knightObject、heroObject、heroObjectNull是同一个对象，属性不同，null为空。这种形式在生成随机数组和移动元素时效果很好，但在删除或生成新动作时，我发现数组的操作非常复杂。谁能想到更好的方法？我不是要找我来解决问题，有一个想法就足够了。

提前谢谢你，如果有任何澄清，我会注意的，你好。

Answer 1

我认为如果代表棋盘的数组被完全填充，问题可能会更容易，并且骑士和英雄有唯一的标识符，这样更容易确定属于同一英雄的单元格组。

然后，使用从第二行到最后一行遍历的函数，寻找骑士和英雄下方的空单元格，以确定它们是否可以下降一行...

看看下面的示例代码。在第一次测试中，没有任何东西可以掉落，所以结果保持不变。在第二次测试中，移除了一个骑士（ID 1006），结果反映了可以掉落的骑士和英雄...

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 );

希望这对您有所帮助...

编辑：上面的代码有一个缺点，它只会将一个数字向下移动一行，而在某些情况下，删除一个数字需要一些数字删除多个单元格。运行在同一块板上多次使用上述算法是一种可行的 hack，但不是最优的。以下版本采用不同的方法...

主要区别在于此版本跟踪图形，并动态构建电路板。这样做时，在删除图形后，算法会从最底部的行开始遍历图形列表，以确定图形下方的行是否为空，如果是，则将图形删除一行。它会继续检查图形是否可以继续删除另一行，然后再转到下一个图形...

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 ) );

第二个答案比第一个更清晰，但可能会导致对您的应用程序进行更多检修...

Answer 2

在解决这个问题之前，我需要假设数组 myBoard 的格式是存储行列表而不是列列表。而且数据没有空位。

为了简单起见，我决定使用 1s 和 2s 而不是 knightObject 和 heroObject。

我在这里假设一次可以操作多少数据没有限制，这意味着该项目可以无限制地掉落。

myBoard = [
[1,1,2,0,0,0,0,0],
[1,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,2,0,0,0,0,0],
[0,2,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
];

会变成

myBoard = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[1,1,0,0,0,0,0,0],
[1,1,2,0,0,0,0,0],
[0,2,2,0,0,0,0,0]
];

。这是我写的代码。基本上，dropDestinationIndex 存储项目被放置到的行的最终索引。

myBoard = [
[1,1,2,0,0,0,0,0],
[1,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,2,0,0,0,0,0],
[0,2,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
];

function updateBoard(){
    for (let rowIndex = myBoard.length-2; rowIndex>=0; rowIndex--){ //don't check the final row
        for (let cellIndex = 0; cellIndex<myBoard[rowIndex].length; cellIndex++){ //iterate through rows
            let cell = myBoard[rowIndex][cellIndex];
            let dropDestinationIndex = rowIndex+1;
            if(cell==2 && !myBoard[rowIndex+1][cellIndex]){ //check if any item below
                while (!myBoard[dropDestinationIndex][cellIndex]){ //set how many rows will it fall
                    dropDestinationIndex++;
                    if (dropDestinationIndex>myBoard.length-1){
                        break;
                    }
                }
                myBoard[dropDestinationIndex-1][cellIndex] = cell;
                myBoard[rowIndex][cellIndex] = 0;
            }else if(cell==1){ //check if any item below
                if(!myBoard[rowIndex+1][cellIndex] && !myBoard[rowIndex+1][cellIndex+1]){
                    while (!myBoard[dropDestinationIndex][cellIndex]&&!myBoard[dropDestinationIndex][cellIndex+1]){ //set how many rows will it fall
                        dropDestinationIndex++;
                        if (dropDestinationIndex>myBoard.length-1){
                            break;
                        }
                    }
                    myBoard[dropDestinationIndex-1][cellIndex] = cell;
                    myBoard[dropDestinationIndex-1][cellIndex+1] = myBoard[rowIndex][cellIndex+1];
                    myBoard[rowIndex][cellIndex] = 0;
                    myBoard[rowIndex][cellIndex+1] = 0;
                }
                cellIndex++;
            }
        }
    }
}

updateBoard()
console.log(myBoard);
/*out:
[[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 2, 0, 0, 0, 0, 0]
[0, 2, 2, 0, 0, 0, 0, 0]]
*/

干杯！ :)

二维网格删除/操作算法 - 元素的组织及其在数组中的位置

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

javascript

algorithm

2d

game-physics