🎓 12주차: 셀룰러 오토마타(Cellular Automata)

단순 규칙으로 복잡한 생명 현상 구현

셀룰러 오토마타(CA)는 격자 형태로 배열된 셀(Cell)들이 주변 셀의 상태와 미리 정해진 단순한 규칙에 따라 자신의 상태를 변화시키며 시간을 진행하는 시스템입니다. 이 시스템의 가장 유명한 예가 바로 콘웨이의 생명 게임(Conway’s Game of Life, GOL)입니다.

GOL은 탄생(Birth)과 죽음(Death)이라는 단 네 가지의 단순한 규칙만으로 예측 불가능하고 복잡하며, 심지어 이동하거나 진동하는 듯한 복잡한 생명 현상을 구현합니다. 이는 단순 규칙이 어떻게 복잡성을 창발(Emergence)시키는지 보여주는 훌륭한 예시입니다.

1. 콘웨이의 생명 게임 (Conway’s Game of Life)

이 코드는 격자(Grid)를 구성하고, draw() 함수가 반복될 때마다 주변 셀의 생사(生殺) 여부에 따라 다음 세대를 계산하고 화면에 그립니다.

// ====== 전역 변수 설정 ======
let grid; // 현재 세대의 상태 (0: Dead, 1: Alive)
let cols;
let rows;
let resolution = 5; // 셀 하나의 크기 (픽셀)

function setup() {
  // 캔버스를 600x600으로 생성합니다.
  createCanvas(600, 600);

  // 셀의 개수 계산
  cols = floor(width / resolution);
  rows = floor(height / resolution);

  // 시뮬레이션 속도를 조절합니다. (초당 5 프레임)
  // 너무 빠르면 패턴 변화를 관찰하기 어렵습니다.
  frameRate(5);

  // 초기 격자 상태를 설정하고 무작위로 생명체를 배치합니다.
  grid = initializeRandomGrid(cols, rows);

  // 배경은 어두운 색으로 설정합니다.
  background(20);
}

function draw() {
  // 1. 현재 세대 그리기
  background(20); // 매 프레임마다 배경을 다시 칠해 잔상을 제거합니다.
  drawGrid(grid);

  // 2. 다음 세대 계산
  // CA의 핵심: 현재 상태(grid)를 기반으로 다음 상태(nextGrid)를 계산합니다.
  let nextGrid = computeNextGeneration(grid);

  // 3. 상태 업데이트
  // 계산된 다음 세대를 현재 세대로 교체합니다.
  grid = nextGrid;
}

// ====== 유틸리티 함수 ======

/**
 * 2차원 배열을 생성하고 무작위 초기값을 설정합니다.
 */
function initializeRandomGrid(cols, rows) {
  let arr = new Array(cols);
  for (let i = 0; i < cols; i++) {
    arr[i] = new Array(rows);
    for (let j = 0; j < rows; j++) {
      // 50% 확률로 0(죽음) 또는 1(생존)을 부여합니다.
      arr[i][j] = floor(random(2));
    }
  }
  return arr;
}

/**
 * 현재 격자의 상태를 캔버스에 그립니다.
 */
function drawGrid(currentGrid) {
  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      let x = i * resolution;
      let y = j * resolution;

      if (currentGrid[i][j] == 1) {
        // 생존한 셀 (Alive): 흰색
        fill(200, 170, 80);
        stroke(20); // 셀 경계선은 배경색과 비슷하게 설정
        rect(x, y, resolution, resolution);
      } else {
        // 죽은 셀 (Dead): 그리지 않음 (배경색 유지)
        // noStroke();
        // fill(20);
        // rect(x, y, resolution, resolution);
      }
    }
  }
}

/**
 * 콘웨이의 생명 게임 규칙을 적용하여 다음 세대를 계산합니다.
 */
function computeNextGeneration(currentGrid) {
  // 다음 세대를 담을 새로운 격자를 만듭니다. (중요: 현재 격자를 직접 수정하면 안 됩니다!)
  let newGrid = initializeEmptyGrid(cols, rows);

  for (let i = 0; i < cols; i++) {
    for (let j = 0; j < rows; j++) {
      // 1. 현재 셀의 상태
      let state = currentGrid[i][j];

      // 2. 이웃 셀 (8방향) 중 살아있는 셀의 개수를 셉니다.
      let liveNeighbors = countLiveNeighbors(currentGrid, i, j);

      // 3. 콘웨이의 4가지 규칙 적용
      if (state == 0 && liveNeighbors == 3) {
        // 🌟 규칙 4: 탄생 (Birth)
        // 죽은 셀이 이웃 3개를 가지면 살아납니다.
        newGrid[i][j] = 1;
      } else if (state == 1) {
        if (liveNeighbors < 2 || liveNeighbors > 3) {
          // 💀 규칙 1 & 3: 과소/과밀에 의한 죽음 (Death)
          // 이웃이 2개 미만이거나 3개를 초과하면 고독 또는 과밀로 죽습니다.
          newGrid[i][j] = 0;
        } else {
          // 💖 규칙 2: 생존 (Survival)
          // 이웃이 2개 또는 3개면 다음 세대에도 생존합니다.
          newGrid[i][j] = 1;
        }
      }
      // 그 외의 경우 (state=0, liveNeighbors!=3), 셀은 0(죽은 상태)을 유지합니다.
    }
  }
  return newGrid;
}

/**
 * 이웃 셀의 생존 개수를 셉니다. (토러스 경계 조건 적용)
 */
function countLiveNeighbors(grid, x, y) {
  let sum = 0;
  // 현재 셀의 주변 8개 셀을 순회 (-1, 0, 1)
  for (let i = -1; i <= 1; i++) {
    for (let j = -1; j <= 1; j++) {
      // ⚠️ 경계 조건 처리 (Toroidal Boundary - 토러스/도넛 모양)
      // 격자 끝을 넘어가면 반대편으로 이어지게 계산합니다.
      let col = (x + i + cols) % cols;
      let row = (y + j + rows) % rows;

      // 이웃 셀의 상태를 합산합니다.
      sum += grid[col][row];
    }
  }

  // 자기 자신은 이웃에 포함되지 않으므로, 합산에서 제외합니다.
  sum -= grid[x][y];

  return sum;
}

/**
 * 빈 2차원 배열(모든 값 0)을 생성합니다.
 */
function initializeEmptyGrid(cols, rows) {
  let arr = new Array(cols);
  for (let i = 0; i < cols; i++) {
    arr[i] = new Array(rows).fill(0);
  }
  return arr;
}

1. 🖼️ 두 개의 격자(Grid) 사용 (메모리 효율적인 상태 전이)

CA 시뮬레이션에서 가장 중요한 부분은 동시 업데이트입니다.

• grid: 현재 세대의 상태를 저장합니다.
• nextGrid: 현재 grid의 상태를 기반으로 다음 세대에 셀이 살아있을지 죽을지를 계산하여 임시로 저장합니다.

만약 하나의 배열만 사용하고 계산과 동시에 업데이트하면, 먼저 업데이트된 셀이 나중에 계산되는 셀에 영향을 주어 규칙이 오염됩니다. 두 개의 격자를 사용하면 모든 셀의 업데이트가 동시에 이루어지는 CA의 본질을 정확하게 구현할 수 있습니다.

2. 🔢 콘웨이의 4가지 규칙 (computeNextGeneration 함수)

이 함수는 모든 셀을 순회하며 다음 네 가지 규칙을 적용합니다.

• 과소(Underpopulation)에 의한 죽음: 살아있는 셀이 이웃이 2개 미만이면 죽습니다. (고독)
• 생존 (Survival): 살아있는 셀이 이웃이 2개 또는 3개이면 다음 세대에도 살아남습니다.
• 과밀(Overpopulation)에 의한 죽음: 살아있는 셀이 이웃이 3개 초과이면 죽습니다. (질식/과밀)
• 탄생 (Reproduction): 죽어있는 셀이 이웃이 정확히 3개이면 살아납니다.

3. 🔄 토러스 경계 조건 (countLiveNeighbors 함수)

• 경계 조건 (Boundary Condition): 격자의 가장자리에 있는 셀의 이웃을 어떻게 처리할지가 중요합니다. 이 예제에서는 토러스(Toroidal) 경계를 사용합니다.

• 구현: 배열 인덱스를 계산할 때 (x + i + cols) % cols 와 같이 모듈로 연산(%)을 사용하여, 오른쪽 끝을 넘어가면 자동으로 왼쪽 끝으로, 위쪽 끝을 넘어가면 아래쪽 끝으로 연결되도록 만듭니다. 마치 격자가 도넛처럼 둥글게 이어진 것처럼 동작하여 경계면 없이 자연스러운 패턴 이동을 관찰할 수 있습니다.

2. 규칙 기반 패턴 생성기

간단한 1차원 규칙의 2차원 확장
이 예제는 1차원 셀룰러 오토마타(Elementary Cellular Automata, ECA)의 아이디어를 2차원으로 확장하여 사용합니다. 각 셀은 오직 자신과 바로 위쪽 이웃들의 상태에만 의존하여 다음 상태를 결정합니다. 이는 GOL처럼 8방향 이웃을 보는 것보다 훨씬 간단한 규칙이지만, 반복되면 매우 복잡하고 흥미로운 프랙탈적 구조를 만들어냅니다.

// ====== 전역 변수 설정 ======
let grid; // 셀 상태를 저장할 2차원 배열
let cols;
let rows;
let resolution = 8; // 셀 하나의 크기 (픽셀)
let currentRow = 0; // 현재 패턴을 계산하고 있는 행
let rule = 90; // 사용할 1차원 CA 규칙 번호 (Rule 90)
let ruleset; // 규칙 번호에 해당하는 8비트 규칙 배열

function setup() {
  // 캔버스 생성 및 기본 설정
  createCanvas(800, 800);

  // 셀의 개수 계산
  cols = floor(width / resolution);
  rows = floor(height / resolution);

  // 초기 격자를 모두 '죽은 상태(0)'로 초기화
  grid = initializeEmptyGrid(cols, rows);

  // 초기 시드 (Seed) 설정: 가장 윗줄 중앙 셀만 '살아있는 상태(1)'로 시작
  grid[floor(cols / 2)][0] = 1;

  // 규칙 번호를 8비트 배열로 변환
  ruleset = decimalToBinaryArray(rule);

  // 배경은 검은색으로 설정
  background(0);
}

function draw() {
  // 현재 행을 그립니다.
  drawRow(currentRow);

  // 다음 행을 계산합니다.
  if (currentRow < rows - 1) {
    computeNextRow(currentRow);
    currentRow++;
  } else {
    // 모든 행을 다 채우면 멈춥니다.
    noLoop();
    console.log("패턴 생성이 완료되었습니다.");
  }
}

// ====== 유틸리티 함수 ======

/**
 * 빈 2차원 배열(모든 값 0)을 생성합니다.
 */
function initializeEmptyGrid(cols, rows) {
  let arr = new Array(cols);
  for (let i = 0; i < cols; i++) {
    arr[i] = new Array(rows).fill(0);
  }
  return arr;
}

/**
 * 규칙 번호 (Decimal)를 8비트 배열 (Binary)로 변환합니다.
 * 예: Rule 90 -> [0, 1, 0, 1, 1, 0, 1, 0]
 */
function decimalToBinaryArray(decimal) {
  // 10진수를 8자리 2진수 문자열로 변환하고 배열로 만듭니다.
  let binaryString = decimal.toString(2).padStart(8, "0");
  // 배열을 뒤집는 이유: 1차원 CA 규칙은 보통 우측 비트(인덱스 0)부터 중요도가 낮음
  // 컨텍스트: [111, 110, 101, 100, 011, 010, 001, 000] 에 대응
  return Array.from(binaryString).reverse().map(Number);
}

/**
 * 현재 행의 셀 상태를 기반으로 다음 행의 상태를 계산합니다.
 * 규칙: 현재 셀의 상태는 바로 위 3개 이웃 (왼쪽 위, 위, 오른쪽 위)에 의해 결정됩니다.
 */
function computeNextRow(y) {
  let nextY = y + 1;
  // 각 열을 순회하며 새로운 행의 상태를 결정
  for (let x = 1; x < cols - 1; x++) {
    // 1. 위쪽 3개의 이웃 상태를 가져옵니다.
    // 경계 조건 처리를 위해 (x=0, x=cols-1) 열은 무시합니다.
    let left = grid[x - 1][y]; // 왼쪽 위
    let center = grid[x][y]; // 바로 위
    let right = grid[x + 1][y]; // 오른쪽 위

    // 2. 3비트 패턴을 10진수 인덱스로 변환합니다.
    // 예: [1, 0, 1] -> 1*2^2 + 0*2^1 + 1*2^0 = 5
    let index = left * 4 + center * 2 + right * 1;

    // 3. 규칙 배열(ruleset)에서 해당 인덱스의 값을 가져와 다음 상태로 설정합니다.
    // ruleset[index]는 0 또는 1 (다음 세대의 상태)
    grid[x][nextY] = ruleset[index];
  }
}

/**
 * 현재 행의 셀 상태를 캔버스에 그립니다.
 */
function drawRow(y) {
  for (let x = 0; x < cols; x++) {
    let cellState = grid[x][y];
    let drawX = x * resolution;
    let drawY = y * resolution;

    if (cellState == 1) {
      // 생존한 셀 (Alive): 흰색
      fill(70, 200, 180);
      noStroke();
      rect(drawX, drawY, resolution, resolution);
    }
    // 죽은 셀 (0): 그리지 않음 (배경색 유지)
  }
}

💡 코드 상세 설명: 1차원 CA 규칙의 2D 적용

1. 🔢 규칙 세트(ruleset)와 번호(rule)

• 규칙 번호: rule = 90은 이 시뮬레이션의 작동 방식을 결정하는 핵심입니다. 1차원 CA에서는 주변 3개 셀(왼쪽, 중앙, 오른쪽)의 8가지 가능한 조합($2^3=8$) 각각에 대해 다음 상태(0 또는 1)를 지정합니다.
• decimalToBinaryArray(rule): 90과 같은 10진수 규칙 번호를 8비트의 2진수 배열로 변환합니다. 이 배열(ruleset)이 바로 8가지 상황에 대한 8가지 결과를 저장합니다.
  • 예: Rule 90은 2진수로 01011010이며, 이를 배열로 변환하여 패턴 결정에 사용합니다.

2. ↕️ 시간성 (Temporal Systems)의 구현

• draw() 루프: GOL처럼 전체 격자를 동시에 계산하는 대신, 이 예제는 draw() 함수가 반복될 때마다 하나의 행(row)씩 패턴을 아래로 생성해 나갑니다.

• currentRow: 시간이 지남에 따라 currentRow가 0부터 rows-1까지 증가하며, 이는 패턴이 시간의 흐름에 따라 위에서 아래로 쌓이는 것을 시각화합니다.

3. 🧠 다음 상태 결정 (computeNextRow 함수)

이 함수는 GOL의 computeNextGeneration보다 훨씬 단순한 규칙을 사용합니다.

• 이웃 정의: 오직 바로 윗 행의 3개 셀(왼쪽, 중앙, 오른쪽)만을 이웃으로 간주합니다.

• 인덱스 변환: left 4 + center 2 + right * 1 공식은 3개의 1(Alive) 또는 0(Dead) 상태를 0부터 7까지의 고유한 10진수 인덱스로 변환합니다.

  • 이 인덱스는 현재 3개 이웃의 패턴이 ruleset 배열의 몇 번째 규칙과 일치하는지를 알려줍니다.

• 상태 결정: newGrid[x][nextY] = ruleset[index]를 통해, 해당 패턴에 미리 정의된 규칙(0 또는 1)에 따라 다음 셀의 상태를 결정합니다.

🎨 이 예시의 흥미로운 점

• 프랙탈 패턴: Rule 90은 실행하면 시에르핀스키 개스킷과 유사한 대칭적이고 프랙탈적인 구조를 생성합니다.

• 패턴 다양성: let rule = 90 값을 다른 규칙 번호(예: Rule 30, Rule 110, Rule 184)로 바꾸면 완전히 다른 시각적 패턴을 관찰할 수 있습니다. 특히 Rule 110은 튜링 완전성(Turing Completeness)을 가진 것으로 알려져 있어 복잡성이 매우 높습니다.

• 메모리 효율: GOL과 달리 이웃 계산이 8개가 아닌 3개로 단순