Java: Как реализовать игру жизни Конвея?

Question

Я изучаю игры Конвея жизни осуществить это самостоятельно, и наткнулся на следующую реализацию с правилами:

Учитывая доску с т по п ячеек, каждая ячейка имеет начальное состояние живого (1) или мертвым (0). Каждая клетка взаимодействует с его восемью соседями (по горизонтали, по вертикали, по диагонали), используя следующие четыре правила (взятые из выше статьи Википедии):

• Любая живая клетка с менее чем двумя живыми соседями умирает, как будто вызваны под -Население.
• Любая живая ячейка с двумя или тремя живыми соседями живет следующим поколением.
• Любая живая клетка с более чем тремя живыми соседями умирает, как если бы она переполнена.
• Любая мертвая ячейка с ровно тремя живыми соседями становится живой клеткой, как бы путем размножения.

И реализация (https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation):

public void gameOfLife(int[][] board) { 
    if (board == null || board.length == 0) return; 
    int m = board.length, n = board[0].length; 

    for (int i = 0; i < m; i++) { 
     for (int j = 0; j < n; j++) { 
      int lives = liveNeighbors(board, m, n, i, j); 

      // In the beginning, every 2nd bit is 0; 
      // So we only need to care about when will the 2nd bit become 1. 
      if (board[i][j] == 1 && lives >= 2 && lives <= 3) { 
       board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11 
      } 
      if (board[i][j] == 0 && lives == 3) { 
       board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10 
      } 
     } 
    } 

    for (int i = 0; i < m; i++) { 
     for (int j = 0; j < n; j++) { 
      board[i][j] >>= 1; // Get the 2nd state. 
     } 
    } 
} 

public int liveNeighbors(int[][] board, int m, int n, int i, int j) { 
    int lives = 0; 
    for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) { 
     for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) { 
      lives += board[x][y] & 1; 
     } 
    } 
    lives -= board[i][j] & 1; 
    return lives; 
} 

И водитель:

public static void main(String args[]) { 
    GameOfLife gl = new GameOfLife(); 

    int[][] board = { 
       {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 1, 0, 0, 0, 0, 0}, 
       {0, 1, 0, 1, 0, 0, 0, 0, 0}, 
       {0, 0, 1, 1, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0} 
      }; 

    gl.gameOfLife(board); 
} 

И мой вопрос, что делать x и y в liveNeighbors() представляют? Не понимаю, зачем нужна Math.min() и Math.max(). А также, lives представляет количество инициализированных жизней на доске?

Answer 1

Данный код использует функции min и max, чтобы ограничить поиск действительными записями в массиве. Если это не будет сделано, код вернет исключение ArrayOutOfBoundsException при попытке использовать -1, m или n как индексы массива. (Цикл не «знает», что дает квадрат на правом краю карты, он не должен искать соседних соседей справа, эти функции кодируют этот факт.) x и y - это просто переменные управления контуром которые используются для итерации над допустимыми квадратами, окружающими целевой квадрат.

Что касается переменной lives, то это местозаполнитель, чтобы подсчитать количество живущих соседей по петлям ниже. Возможно, вы догадались об этом из-за того, что это возвращаемое значение функции liveNeighbors.

Давайте сделаем пример. Мы назовем liveNeighbors(board,9,9,0,2), где board - плата, указанная в драйвере. Ваша доска имеет размеры 9x9, так что это m и n, которые мы проходим, и для нашего примера мы исследуем квадрат на 0, 2, который является первой записью в третьей строке (у которой есть 1 справа). Отлично, давайте начнем.

i=0, так x = Math.max(i - 1, 0) = Math.max(-1, 0) = 0 (это показывает причину для функции max. А если мы только что сказали, int x=i-1, мы бы в конечном итоге с x = -1 которая находится вне границ массива Далее мы оцениваем х < = Math.min (i + 1, m - 1) = Math.min (1, 8) = 1. Если бы мы исследовали ячейку в последнем столбце, это условие обеспечило бы правильный край массива.

Я оставлю подобную логику с использованием y и j.

Цикл упрощается:

for (int x = 0; x <= 1; x++) { 
    for (int y = 1; y <= 3; y++) { 
     lives += board[x][y] & 1; 
    } 
} 

Внутренний цикл будет работать в шесть раз, со следующими парами (x,y): (0,1),(0,2),(0,3),(1,1),(1,2),(1,3). Убедите себя, что это соседи по площади, которую мы исследуем, а также сама площадь.

Пять из этих шести квадратов вернутся 0, с одной на (1,2) возвращении 1, так что в конце этого цикла, lives будет равен 1. Последнее, что нужно сделать, это lives -= board[i][j] & 1;, что уменьшает lives на 1, если площадь мы исследуем, имеет 1 в нем. В нашем случае это не (board[i][j] = 0), поэтому мы вычитаем 0, оставив нам 1, которые мы вернем. liveNeighbors(board,9,9,0,2) = 1

Возможно, я получил x и y назад один или два раза, но, надеюсь, этого достаточно, чтобы вы могли понять, что происходит.