Алгоритм удаления / манипулирования 2D сеткой - Организация элементов и их позиций в массиве

Question

Я хотел бы представить проблему, с которой я боролся в течение нескольких месяцев. Таким образом, он основан на механике доски для сетевой игры (разработка Javascript). Плата состоит из сетки 8x6, которая может содержать элементы размером 1 или 4 пикселя.

Основная проблема заключается в том, как хранить фигуры каждого типа в многомерном массив, имея в виду, что позже мы хотим манипулировать ими и получать свойства объекта, удалять его и заставлять других перемещать их, перемещать их из одной позиции в другую и т. д. c ... В основном проблема возникает, когда удаляя элемент с доски (нажав на него), я не могу правильно все переставить. Например:

Пример удаления Мы начнем с доски в позиции 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

Прежде чем заняться этой проблемой, я должен предположить, что массив myBoard отформатирован таким образом, что вместо списка столбцов сохраняется список строк. И что в данных нет пустого места.

Просто для простоты я решил использовать 1 и 2 вместо 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]]
*/

Приветствия! :)

Answer 2

Я думаю, что проблема может быть проще, если массив, представляющий игровое поле, заполнен полностью, а у Рыцарей и Героев есть уникальные идентификаторы, чтобы было легче определить группу ячеек, принадлежащих одному герою.

Затем воспользуйтесь функцией, которая будет проходить по строкам, начиная со второго до последнего, ища пустые ячейки под Рыцарями и Героями, чтобы определить, могут ли они выпасть в ряд ...

Посмотрите в следующем примере кода. В первом тесте ничего не может упасть, поэтому результат остается прежним. Во втором тесте рыцарь был удален (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 );

Надеюсь, это поможет ...

РЕДАКТИРОВАТЬ: у приведенного выше кода был недостаток в том, что он будет сдвигать фигуру только на одну строку вниз, в то время как в некоторых случаях удаление фигуры требует, чтобы некоторые фигуры отбрасывали более одной ячейки. Многократный запуск вышеуказанного алгоритма на одной и той же плате - это хак, который работает, но неоптимально. Следующая версия использует другой подход ...

Основное отличие состоит в том, что эта версия отслеживает фигуры и строит доску на лету. При этом после удаления фигуры алгоритм просматривает список фигур, начиная с самой нижней строки, чтобы определить, является ли строка под рисунком пустой, и, если это так, отбрасывает фигуру в строку. Он продолжает проверять, может ли фигура продолжать отбрасывать другой ряд, прежде чем перейти к следующему рисунку ...

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

Этот второй ответ чище, чем первый, но может привести к большему пересмотру вашего приложения ...