셀룰러오토마타

셀룰러 오토마타는 세포를 기반으로 구성되는 체계를 말한다. 세포는 그리드(grid) 안의 하나의 셀을 말하고 세포는 각각 ‘살음’, ‘죽음’ 과 같은 상태를 지닌다. 세포는 이웃을 가지고 이웃의 상태에 따라 자신의 상태가 결정하는 식으로 동작하는 체계. 셀룰러 오토마타라고 하고 줄여서 CA라고 한다.

1. 1차원

1차원 가장 기본적인 오토마타는 이 체계가 어떤것인지 이해하기 위한 가장 간단한 형태이다.

1.1. Rule

000 => 0
001 => 1
010 => 0
011 => 1
100 => 1
101 => 0
110 => 1
111 => 0

마치 이진수처럼 양 옆을 이웃 가운데를 본인 셀이라고 하면 위 8가지 패턴이 나오게 되는데 각 패턴별로 본인이 취해야할 다음 상태를 나타내는 것이다. 위 01011010을 다시 이진수로 인식하면 십진수로 90이 되며 이를 ‘Rule90’이라고 한다.

1.2. GPT에게 물어보기

<canvas id="ca" width="400" height="400"></canvas>
<script>
const canvas = document.getElementById("ca");
const ctx = canvas.getContext("2d");

const cols = 101;        // 셀 개수
const cellSize = 4;      // 셀 크기
const rows = Math.floor(canvas.height / cellSize);

let current = Array(cols).fill(0);
current[Math.floor(cols / 2)] = 1; // 중앙에서 시작

// Rule 30: 111, 110, 101, 100, 011, 010, 001, 000 → 결과
const rule30 = [0, 0, 0, 1, 1, 1, 1, 0];

function draw() {
    for (let y = 0; y < rows; y++) {
        // 현재 세대 그리기
        for (let x = 0; x < cols; x++) {
            if (current[x] === 1) {
                ctx.fillStyle = "black";
                ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
            }
        }
        // 다음 세대 만들기
        let next = Array(cols).fill(0);
        for (let x = 1; x < cols - 1; x++) {
            let left = current[x - 1];
            let mid  = current[x];
            let right = current[x + 1];
            let idx = (left << 2) | (mid << 1) | right;
            next[x] = rule30[7 - idx]; // 7-idx는 비트 패턴 순서 맞추기
        }
        current = next;
    }
}

draw();
</script>

이쪽 셀룰러 오토마타 CA쪽은 엄청나게 연구가 되어있고 소스도 많아서 학습량이 많았는지 그냥 통짜로 코드를 던져준다~ 👍

GPT의 코드를 좀 수정해서 여러개의 Rule을 적용하도록 수정한다.

1.3. 분석

아래 이미지들은 사진파일이 아니라 자바스크립트로 canvas에 그려진 이미지이다.

Rule30을 적용하면 위와 같은 그림이 나온다. 즉 이런식이다.

1. 가운데 셀 하나만 상태를 1 (살음)으로 한다. (초기)
2. 현재 1차원 그리드를 그린다.
3. Rule을 적용하여 다음 상태들을 전부 구한다.
4. 그 다음 Row에 1차원 그리드를 그린다.
5. 계속 반복

1차원 그리드를 2차원으로 표현하였으므로 아래로 내려갈수록 세대가 늘어나는 진행도라고 볼수 있다.

중간부분

중간부분을 확인해보려면 일종의 ‘확대’ 개념을 생각해봐야한다. 실제로는 계산한 grid의 크기는 더 크지만 canvas는 더 좁은 범위에서 출력한다. 그래서 세대 진행은 세대진행대로 하되 시작점만 조정하며 View의 위치를 옮긴다.

canvas에는 N세대 이후 그리면 N만큼 아래로 이동한 것처럼 될 것이다.

(Rule30)

(Rule110)

해파리 수백마리가 헤엄쳐 다니는 것 같다는 생각이 들었다. 간단한 규칙이 전파되면서 복잡계를 만든다.

2. 2차원

2차원의 경우 Rule 정의하기가 힘들어지는데 이는 본인 포함 주변 9개 셀의 나열하는 경우의 수는 9비트로 512가지나 되어 그걸 일일히 나열하기엔 너무 비효율적이기 때문이다.

따라서 Rule은 주변 이웃의 상태의 개수를 세서 결정하게 된다.

2.1. Rule

let neighbors = countNeighbors(grid, x, y);
if (grid[y][x] === 1 && (neighbors < 2 || neighbors > 3)) {
    newGrid[y][x] = 0;
} else if (grid[y][x] === 0 && neighbors === 3) {
    newGrid[y][x] = 1;
}

• 세포가 살아있고 주변 살아있는 세포가 2개 미만이면 외로워서 죽음
• 세포가 살아있고 주변 살아있는 세포가 3개 초과라면 혼란스러워서 죽음
• 세포가 죽어있고 주변에 살아있는 세포가 3개 있다면 살아나게 함

2.2. Animation

• ‘랜덤뿌리기’ 버튼을 누르면 그리드에서 랜덤으로 생존 상태가 뿌려짐
• ‘글라이더’는 2차원 셀룰러 오토마타에서 알려진 대각선 이동패턴 중 하나
• ‘우주선’은 수평이동 패턴중 하나
• ‘Clear’는 생존상태를 없애고 깨끗한 상태로 세팅

랜덤으로 뿌려보면 마구 퍼지거나 없어지거나하는데 마치 전염병이 번지는 느낌이다. 유달리 오래 진행되는 케이스가 있는데 랜덤으로 뿌릴때 세대가 굉장히 오래 진행되는 어떤 패턴이 발현되어 그런것 같다.

3. Hexagonal

육각형 벌집모양의 그리드를 정의하고 여기서 적용되는 CA도 만들수 있다. 리서치하다가 찾았는데 육각형에 관련된 거의 모든 코딩 내용은 이 링크 가 압권이다.

hexagonal부터 조금씩 복잡해지니 GPT가 조금씩 틀린다. 그래서 코드를 조금씩 손 봐주어야 하는데 활용을 위해 클래스로 만들었다. 즉 GPT소스 4가지 버젼에서 몇가지를 조합하고 수정해서 정리했다. 앞으로의 개발은 이런식으로 흘러가게 되는 것일까? 🤔

3.1. Animation

위 시뮬레이션은 Hexagonal CA 중 Gliders 1 패턴으로 2456/23456/4 룰에 의해 발현된다.

• 아이스크림 모양의 글라이더가 6방향중 한 방향으로 이동한다.
• 점차 세력을 키우면서 마치 태양이 이글거리는 듯한 느낌을 준다.
• 최종적으로는 모든 화면을 채운다.

Rule 표기법 2456/23456/4 라면 survive 생존조건이 2,4,5,6 즉 주변 이웃이 저 숫자중 하나면 생존하는 것이다. 두번째는 Birth 탄생조건으로 주변 생존이 2,3,4,5,6 개면 새로 태어난다. 마지막은 state 즉 죽어가는 단계인데 생존을 만족하지 않으면 죽어가는 단계로 빠지고 4단계에 걸쳐 죽어간다.

이때 GPT가 상당히 이해를 못했는데 코드를 보면 이웃을 셀때 죽어가는 놈까지 같이 세는 식으로 사소한 곳에서 무언가 조금씩 어긋남이 있다.

3.2. Rule

step(){
    for(let y=0; y < this.rows; y++){
        for(let x=0; x < this.cols; x++){
            const v = this.grid[y][x];
            const n = this.countNeighbors(x, y);
            
            if(v == 1){
                this.nextGrid[y][x] = this.rule.survive.has(n)? 1 : 2;
            }else if(v > 1){
                this.nextGrid[y][x] = (v + 1 >= this.rule.state) ? 0 : v + 1;
            }else{
                this.nextGrid[y][x] = this.rule.birth.has(n)? 1: 0;
            }
        }
    }// end for
    [this.grid, this.nextGrid] = [this.nextGrid, this.grid];
}

• 생존이면 survive조건에 속하는지 판단 충족시 그대로 상태 1(생존), 미충족시 상태 2로 빠짐(죽어가는 단계)
• 죽어가는 단계이면 상태를 하나씩 늘리고 Rule에 지정한 state를 넘어서면 상태 0(죽음)
• 죽어있는 셀이면 Birth 탄생조건에 속하는지 판단

내가 학창시절 겪었던 javascript와 굉장히 많이 달라졌는데 swap 을 저런식으로 직관적으로 할수 있게 되었다. GPT에게 물어보니 구조 분해 할당(destructuring assignment) 이라고 한다.

3.3. 좌표계

위에 소개한 링크에서 Coordinate System 찾아보면

육각형 좌표계에 대한 내용이 나온다. 위 시뮬레이션은 Pointy-Top방식으로 Offset Coordinate로 짝홀 행에 따라서 시작위치가 반칸을 밀려나느냐 아니냐가 결정되는 식이다.

만일 GPT에게 “그냥 만들어줘” 하면 좌표계를 이렇게도 저렇게도 바꿔가면서 만들것이다. 그래서 사실 이론을 알아야 한다. Offset vs Axial 둘중 하나다. 마구 만들어낸 코드를 보면서 이게 어떤 좌표계를 기준으로 만든건지 이해가 필요하다.

4. 후기

이 내용은 우연히 집에 책을 정리하다가 Nature Of Code 오래된 버젼을 찾았다. 쭉 훑어보다가 CA챕터에서 흥미를 가지게 되었다.

코딩으로 창발적 현상을 만들어보는 것은 어렵지만 상당한 재미를 준다. 간단한 규칙으로 복잡함을 이끌어낸다면 더욱 그렇다. 이 셀룰러 오토마타가 얼마나 자연계에 있는지는 잘 모르겠지만 몇가지 사례를 소개하고 있다. 신기한 느낌이 든다.

리서치를 하면서 확인해보니 CA는 이쪽만 파고드는 사람들이 엄청 많았다. 별개 위키페이지도 있으며 굉장히 많은 패턴이 연구 되었다고 한다. Golly라고 검색하면 십여년 전부터도 이미 전용 프로그램이 있었다.

5. 생각 해볼만한 것

평면을 타일링 해서 빈틈없이 덮는 것을 테셀레이션(tessellation)이라고 하는데 이때 몇가지 도형의 Set으로 이루어진 테셀레이션을 만들수 있다. 예를 들면 3.4.6.4 테셀레이션. 이를 가지고 CA를 만들어 볼수도 있을 것이다.