콘웨이의 생명 게임

콘웨이의 생명 게임은 1970년 영국의 수학자 존 호턴 콘웨이(John Horton Conway) 가 고안한 셀룰러 오토마톤(Cellular Automaton)입니다.

"생명"의 탄생과 소멸을 아주 단순한 규칙으로 시뮬레이션하는 모델로 복잡한 행동이 단순한 규칙에서 어떻게 나타나는지를 보여주는 대표적인 예로 유명합니다.

2차원 격자 위에서 각 셀은 살아 있거나 죽어 있는 두 상태 중 하나를 가지며, 모든 셀은 자신의 이웃을 관찰해 다음 세대의 상태를 결정합니다.

규칙

모든 셀은 동시에 다음 세대로 갱신되는데요. 주변 8칸의 이웃에 따라 운명이 결정됩니다.

현재 상태	주변의 살아 있는 셀 수	다음 세대의 상태
살아 있음	< 2	죽음
살아 있음	2 or 3	생존
살아 있음	> 3	죽음
죽어 있음	= 3	탄생

살아 있는 셀은 이웃이 너무 적거나 많아도 죽고, 죽은 셀은 정확히 세 명의 이웃이 있을 때만 다시 살아납니다.

이 네 가지 규칙만으로 무작위 셀들이 모여 스스로 움직이는 세계처럼 만들어집니다.

시각화

대표적인 몇 가지 패턴을 시각화해 봤습니다.

그리드를 누르면 다음 세대로 갱신됩니다.

정물(Still life)

정물은 변하지 않는 안정된 구조를 가집니다.

Block

Boat

Tub

Beehive

Loaf

진동자(Oscillator)

진동자는 주기적으로 반복되는 구조를 가집니다.

Blinker

Toad

Beacon

우주선(Spaceships)

우주선은 세대를 거듭하며 이동하는 구조를 가집니다.

Glider

장수(Methuselah)

장수는 작은 초기 배치로 시작하지만, 오랜 세대를 거쳐서 안정화되는 구조를 가집니다.

아래 R-Pentomino는 초기에는 3x3 그리드에 그려지지만 1103세대에 안정화 된다고 합니다. 그리드도 훨씬 큰 영역이 필요한데 블로그 영역 상 최소 크기만 표현했습니다.

R-Pentomino

이 영상에서 전체 세대를 확인하실 수 있습니다.

코드

직접 테스트해 보실 분들을 위해 코드를 공유해 드립니다.

automaton.ts

export type Cell = 1 | 0;

// prettier-ignore
const NEIGHBOR_OFFSETS = [
  [-1, -1], [0, -1], [1, -1],
  [-1,  0],          [1,  0],
  [-1,  1], [0,  1], [1,  1],
] as const;

const BIRTH = new Set([3]);
const SURVIVE = new Set([2, 3]);

class Automaton {
  private cell: Cell[][];
  private width: number;
  private height: number;

  constructor(seed: Cell[][]) {
    this.cell = seed;
    this.width = seed[0].length;
    this.height = seed.length;
  }

  private get(x: number, y: number) {
    if (x < 0 || x >= this.width || y < 0 || y >= this.height) return 0;
    return this.cell[y][x];
  }

  private neighbor(x: number, y: number) {
    let n = 0;

    for (const [dx, dy] of NEIGHBOR_OFFSETS) {
      n += this.get(x + dx, y + dy);
      if (n > 3) return n;
    }

    return n;
  }

  next() {
    const nextCell = this.cell.map((row) => row.slice());

    for (let y = 0; y < this.height; y++) {
      const row = this.cell[y];
      const nextRow = nextCell[y];

      for (let x = 0; x < this.width; x++) {
        const alive = row[x] === 1;
        const n = this.neighbor(x, y);

        nextRow[x] = (alive ? SURVIVE.has(n) : BIRTH.has(n)) ? 1 : 0;
      }
    }

    this.cell = nextCell;
  }

  view() {
    return this.cell;
  }
}