포켓몬 레드로 보는 과거 FSM과 현대 FSM

들어가며...

격동의 90년대 수많은 세계의 소년들이 8KB RAM이라는 제약속에서 태초 마을을 떠났다.

그리고 그 소년들은 이제 수십 GB메모리 위에 또다른 세계를 창조한다.

Z80계열(SM83)의 작은 CPU - 8비트 아키텍쳐의 작업용 RAM(WRAM)

1MB의 카트리지 ROM은 오늘날 고화질 이미지의 한장의 수천분의 일도 되지 않는 것이었다

그리고 그곳에서 시작한 게임은 세계를 놀라게 하였다.

생존 전략- 모든 것은 수작업으로

(디어셈블리 되어서 공유되는 포켓몬 레드)

Game Boy 시절, 개발자는 "코드가 돌아가도록 만드는 것"이 아니라,

64KB 주소 공간에 어떻게든 게임 전체를 욱여넣는 일을 하고 있었다.

자동화도 없고 컴파일러 최적화도 없던 시대, 모든 것은 수작업이었고, 한 줄 한 줄의 어셈블리 코드는 존재 이유와 비용을 계산한 결과였을 것이다.

자, 이제 그 시대의 최적화를 알아야하기 전 우선 우리는 레지스터란 무엇인가에 대해서 알아야한다.

(Z80 레지스터 하드웨어 핀 다이어그램)

레지스터란 무엇인가?

레지스터는 CPU 내부에 존재하는 초고속 데이터 저장소로,

연산, 제어 흐름, 메모리 접근 등에 사용되는 작고 빠른 기억장치이다.

그리고 우리는 이 Z80 아키텍쳐로 레지스터에 대해서 서술 할 것이다.

레지스터는 왜 중요한가?

이 표만 보아도 레지스터가 훨씬 빠르다.

그런데 왜 레지스터와 RAM을 비교했는가?

우선 그 전에 RAM과 레지스터의 차이에 대해서 알아보자

레지스터는 프로그래머의 눈 앞에 펼쳐진 작업대(WorkBench)이다.

작업대는 매우 비좁고, Z80에서는 7~8개의 도구만 올려둘 수 있었지만, 일단 작업대 위에서 프로그래머는 작업 도구를 빠르게 꺼내 쓸 수 있었다.

즉 그래서 시간(Cycle)이 짧게 걸린다.

하지만 RAM은 프로그래머의 공방을 벗어나야하는 자재창고(WareHouse)이다.

창고는 넓어서 많은 재료(데이터)를 보관 할 수 있지만, 필요한 재료가 생길때마다 프로그래머는 하던 일을 멈추고, 원하는 재료를 가져와야했기에

시간(cycle)이 오래걸린다.

그렇다면 포켓몬 레드에서 '최적화'란 무엇인가?

바로, 이 '창고에 다녀오는 횟수'를 최소화하는 처절한 싸움이다.

굼뜬 SM83 CPU로 프레임이 끊기지 않게 부드러운 화면을 구현하려면, 창고에 가지 않고, 최대한 모든 작업을 작업벤치 위에서 단 8개의 도구를 번갈아가며 흥미를 금세 잃는 어린아이에게 꿈을 주어야만했다

우리는 이제 그 장인의 도구가 어땠는지 볼 것이다.

추신: 참고로 여기서부터는 SM83 자체가 아니라 Z80의 레지스터 구조를 먼저 살펴본다. 게임보이의 SM83은 독립형 범용 프로세서로 판매된 칩이 아니며, 내부 아키텍처를 상세히 설명하는 공식 자료도 Z80만큼 널리 공개되지 않았다.
반면 Z80은 레지스터와 플래그, 명령어 구조에 관한 자료가 풍부하고, SM83 역시 그 구조와 어셈블리 관습을 상당 부분 공유하는 Z80 계열의 커스텀 프로세서로 설명되어 왔다.
따라서 이 글에서는 Z80을 비교 기준으로 삼아 기본적인 레지스터 구조를 먼저 설명한 뒤, 실제 포켓몬스터 적·녹이 실행된 SM83에서 어떤 기능이 제거되거나 단순화되었는지를 차례로 살펴본다.

(장인의 도구 Z80 아키텍쳐의 레지스터)

Z80 레지스터에 대한 설명

레지스터는 단순한 8비트 상자가 아니다

그안은 비트 단위로 의미가 다르게 설계된 고정밀 도구였는데,

특히 Z80은 A,F 레지스터 조합(AF) 안에는 플래그(Flags)라는 연산결과를 추적하는 비트들이 있었다

이들 if문이 없는 Z80에서 조건 분기를 수행하는 핵심이었다.

Game Boy의 CPU(SM83)는 흔히 Z80을 기반으로 대폭 수정된 커스텀 프로세서로 설명된다. 완전한 Z80과 비교하면 휴대용 게임기에 불필요한 일부 기능이 제거되고 저전력·게임용 기능이 추가되었다.¹ 이러한 단순화는 칩 면적과 비용, 전력 효율에 유리했을 것으로 보인다. 플래그 레지스터 역시 Z80의 6개에서 Z·N·H·C의 4개로 축소되었다.

아래가 바뀐 지점이다.

S(Sign)와 P/V(Parity/Overflow)는 제거되었다. 포켓몬 레드의 조건 분기는 이 4개의 플래그만으로 구현된 것이다.

8개라는 제약은 변하지 않았다. 대신 SM83은 그 8개를 극한까지 쥐어짜기 위해, 두 개의 레지스터를 묶어 16비트 쌍으로 운용하는 것이 가능했다. 도구를 늘린 것이 아니라, 같은 도구를 두 가지 방식으로 쓴 것이다.

특히 HL 쌍은 메모리 주소를 직접 가리키는 포인터 레지스터로 사용되었다. LD A, [HL]과 같은 명령어로 HL이 가리키는 주소의 값을 A에 즉시 로드할 수 있었고, [HLI], [HLD] 명령어로 로드 후 자동으로 주소를 증감하는 것도 가능했다.

즉, 프로그래머는 8개의 레지스터를 개별 도구로 쓰는 동시에, 필요할 때는 두 개를 합쳐 주소 탐색용 자를 만들어 쓸 수 있었던 것이다.

타일맵 순회나 스프라이트 데이터 복사가 이 HL 쌍 없이는 불가능에 가까웠다.

작업대 위의 8개 도구를 극한까지 활용한 것이다.

자, 그럼 이 도구는 어떻게 사용되었을까?

(상록시티)

상록시티의 화면과 상록시티에서 쓰인 이벤트 스크립트들이다

그들의 세계는 상태(state)로 구성되어 있었다 

SM83이 가진 한계는 단순히 연산 능력에 그치지 않았다.

"프로그래머는 이벤트를 일일이 기억할 수 없었다."

그 대신 FSM(Finite State Machine, 유한 상태 기계) 이라는 구조가 도입되었다.

FSM이란?

FSM은 현재 상태에 따라 행동이 달라지는 시스템이다.

즉, "지금 뭐 하고 있느냐"에 따라 "다음에 뭘 할 수 있는지"가 정해져 있는 구조이다.

일상적인 가장 간단 FSM 예시: 신호등

현재 상태(State): 빨간불, 초록불, 노란불

전이 조건(Condition): 일정 시간 경과

동작(Action): 다음 상태로 전환

신호등은 FSM이다.

현재 색(상태)에 따라 다음 동작(Action)이 정해져있기때문이다.

즉 신호등의 경우 상태(State) 다음 색이 바뀌는 동작(Action)을 가지는 FSM이라고 할 수 있다.

FSM이란 ‘상태(state)’라는 개념을 중심으로 동작을 분리하는 설계 방식이며,

하나의 상태는 하나의 동작을 의미하고, 입력이나 조건에 따라 다음 상태로 넘어간다.

그리고 이것이 우리가 포켓몬을 이해하는 열쇠이다.

FSM이 필요한 이유: '게임의 모든 것'은 상태다

포켓몬 레드를 뜯어보면, 모든 것이 FSM이다.

그중에서 가장 상록시티(영문명: ViridianCity)를 예로 들어보자

(상록시티 어셈블리 화면)

우선 FSM을 보기전에 포켓몬에서는 어떻게 상태를 옮길까?

FSM의 엔진: 스크립트 포인터 테이블과 디스패처

ViridianCity_Script:
	call EnableAutoTextBoxDrawing
	ld hl, ViridianCity_ScriptPointers    ; 1. 스크립트 주소 목록의 시작점을 HL에 로드
	ld a, [wViridianCityCurScript]      ; 2. '현재 스크립트 번호'를 A에 로드
	jp CallFunctionInTable              ; 3. 테이블에서 A번째 함수를 찾아 점프



ViridianCity_ScriptPointers:
	def_script_pointers
	dw_const ViridianCityDefaultScript,               SCRIPT_VIRIDIANCITY_DEFAULT ; 0번
	dw_const ViridianCityOldManStartCatchTrainingScript, SCRIPT_VIRIDIANCITY_OLD_MAN_START_CATCH_TRAINING ; 1번
	; ... 등등

이것이 상록시티 이벤트 FSM의 심장이자 엔진이다.

상태 저장 변수(The State) wViridianCityCurScript라는 RAM의 특정소에 저장된 1바이트 값이 FSM의 현재 상태를 결정한다

그리고 디스패쳐(The Dispatcher)인 ViridianCity_Script는 매 게임 틱마다 호출되어 wViridianCityCurScript 값을 확인한다

그리고 점프 테이블 CallFunctionInTable은 wViridianCityCurScript값을 인덱스로 사용하여 ViridianCity_ScriptPointers 테이블에서 실행해야할 실제 스크립트(상태)의 주소를 찾아, 그 주소로 JP(점프)한다.

이는 switch 문을 하드웨어 레벨에서 가장 효율적으로 구현한 방식이다. 긴 if-else 비교 없이, 단 몇번의 연산만으로 정확한 로직 블록으로 실행을 옮겨버린다.

상태(State)와 행동(Action)의 구현

테이블이 가리키는 ViridianCityDefaultScript 같은 레이블들이 바로 FSM의 각 '상태(State)'에 해당하는 실제 코드이며,

그리고 그 안의 명령어들이 '행동(Action)'이다

실제 게임상의 코드에서는 이렇게 구현되어있다.

ViridianCityCheckGymOpenScript:
	CheckEvent EVENT_VIRIDIAN_GYM_OPEN ; 행동 1: 체육관 오픈 이벤트를 체크
	ret nz                             ; 조건이 만족되면(nz), 아무것도 안하고 리턴
	; ... (중략) ...
	ld a, TEXT_VIRIDIANCITY_GYM_LOCKED ; 행동 2: '문 잠김' 텍스트 ID를 로드
	ldh [hTextID], a
	call DisplayTextID                 ; 행동 3: 텍스트 출력

여기서 CheckEvent나 DisplayTextID 같은 call 명령어들이 바로 해당 상태에서 수행되는 행동(Action) 이다..

그렇다면 call은 무엇인가?

기본 설명: call의 동작 단계

call SomeLabel

Z80계열에서 call이 실행되면 다음이 일어난다:

1.현재 PC (Program Counter + 3) 값을 스택에 push

->즉, 다음 명령어 주소를 기억

2.PC를 SomeLabel 주소로 설정

->곧바로 점프한다

3.이후 ret 명령어를 만나면:

->스택에서 PC를 pop

->원래 위치로 되돌아감

이 call이 중요한 것은

이 저수준에서 

행동을 독립적으로 모듈화하는데

call display

call Delay3

등등 각각의 행동이 모듈화된 서브 루틴으로 구현된다.

즉 call은 전화와 같아서, 

call로 함수에게 전화를 걸면, Z80계열은 전화를 끊은 뒤 다시 돌아갈 장소(주소)를 스택에 메모해두고, ret은 전화를 끊고, 다시 돌아가는 것이다.

그리고 이렇게 상태와 행동이 구현된다면 FSM의 가장 중요한 부분인 '상태 변경'은 어떻게 일어날까?

바로 바로 wViridianCityCurScript 변수에 새로운 값을 쓰는 것으로 이루어진다.

스크립트 예시를 보자

플레이어 행동에 의한 전이 (ViridianCityOldManText) 예시:

ViridianCityOldManText:
	; ... (대화 출력) ...
	call YesNoChoice             ; "예/아니오" 선택지를 띄운다.
	ld a, [wCurrentMenuItem]     ; 플레이어의 선택(0=아니오, 1=예)을 A에 로드
    and a                        ; A가 0인지(아니오) 확인
    jr z, .refused               ; 0이면(아니오) .refused로 점프
	ld hl, .KnowHowToCatchPokemonText ; "예"를 선택했을 경우
	call PrintText

    ; === 상태 전이 발생! ===
	ld a, SCRIPT_VIRIDIANCITY_OLD_MAN_START_CATCH_TRAINING ; 새 상태(1번) 번호를 A에 로드
	ld [wViridianCityCurScript], a                         ; 현재 상태 변수에 덮어쓴다.
	jr .done
; ...

플레이어가 "예"를 선택하는 순간, wViridianCityCurScript의 값이 스크립터 포인터내의 SCRIPT_VIRIDIANCITY_DEFAULT(0)에서 SCRIPT_VIRIDIANCITY_OLD_MAN_START_CATCH_TRAINING(1)으로 변경된다.

이로써 상태 전이가 완료되고.

다음 게임 틱에서 디스패처는 이제 ViridianCityOldManStartCatchTrainingScript를 실행하게 되는 것이다.

포켓몬 레드의 루트 기반 상태 머신을 간단하게 요약하면 다음과 같다

MainGameLoop:
    LD A, (wGameMode)
    CP $00
    JP Z, InitBattle

    CP $01
    JP Z, HandleOverworld

    CP $02
    JP Z, HandleMenu

    JP MainGameLoop

포켓몬 레드의 FSM은 다음의 특징을 가진다.

모든 상태는 1바이트 값 (enum 같은 개념)

분기는 CP + JP Z, label 조합

스택 기반 함수 호출이 아닌, 직접 점프 구조

서브 루틴도 가능하면 CALL 대신 JP로 처리하여 스택 사용 최소화

왜 이렇게 짰을까?

Z80계열의 스택은 RAM 공간을 소모하고, 크기도 SP 레지스터 초기값에 따라 프로그래머가 직접 결정하며, 스택 오버플로우 위험이 항상 존재했다

CALL -> RET 구조는 느리고 오류 위험 존재하는데,

그래서 대부분의 FSM은 CP + JP로 플랫 분기 처리 되어있는 것이다.

FSM vs 현대 FSM - 그 구조는 어떻게 바뀌었는가?

(현대 게임 엔진 대표자중 하나인 Unity의 애니메이션 FSM)

Z80계열에서의 FSM은 말 그대로 기계 그 자체였다.

상태는 레지스터에 저장된 값

전이는 조건 플래그를 기반으로 점프

행동은 call과 jp로 직접 연결

스택, 함수, 추상화는 최소화

하지만 오늘날의 FSM은 구조적으로 완전히 다르다.

1. 상태는 더 이상 레지스터 값이 아니다

포켓몬의 예시

ld a, [wViridianCityCurScript]
jp CallFunctionInTable

OOP로 구현한 FSM

switch (currentState)
{
    case GameState.TitleScreen:
        ShowTitleUI();
        break;
    case GameState.Battle:
        StartBattle();
        break;
}

상태는 명시적인 Enum

전이는 의미 기반 조건문

리턴 주소를 걱정할 필요도 없다

2. 전이는 조건 플래그가 아닌, 의미적 조건으로 제어된다

포켓몬의 예시

cp 1

jp z, SomeState

OOP로 구현한 FSM

if (player.HasPokedex && !gym.IsOpen)
    currentState = GameState.TriggerEvent;

class BattleState : IState 
{
    public void Enter() 
    {
        UI.Show("A wild Pokémon appeared!");
    }
    public void Update() 
    {
        if (Input.GetKeyDown(KeyCode.A)) 
        {
            stateMachine.ChangeState(new FightState());
        }
    }
}

인간 친화적으로 변했고, 유지 보수 용이하게 변했으며

동작(Action)또한 모듈화하고, 캡슐화된 함수로 클래스 혹은 스크립트 단위로 행동을 나누게 된것이다.

(일반적으로 FSM 코드는 switch 문으로 구현되지만, C#에서는 Dictionary<State, Action>과 같은 매핑 구조를 사용하여 행동을 등록할 수도 있다. switch 문은 case 값이 조밀(dense) 하고, enum처럼 연속된 상수 값일 경우 컴파일러가 jump table로 최적화하므로, 매우 빠른 분기 성능을 보인다. 반면 Dictionary 방식은 상태 값이 희소(sparse) 하거나, 런타임에 동적으로 상태를 주입/확장해야 하는 경우에 유리하다. 특히 상태 수가 많고, 값들이 일정하지 않을 때는 Dictionary가 더 간결하고 유지보수가 쉬우며, 실행 성능에서도 경쟁력을 가진다.)

가장 중요한 차이점: 제어권의 흐름

물론 저마다의 장점이 있었지만 OOP의 방식이 일반적으로 더 확장성이 뛰어났고, 저수준에서의 조작은 갈수록 방대해지는 게임의 크기에서 힘들어졌기때문에

점차 OOP적 FSM을 사용했다

분명히 OOP FSM은 다음과 같은 장점이 있었다

명시적인 상태 클래스

모듈화된 Enter, Update, Exit 함수

가독성이 좋고 유지보수 용이하다는 장점 등등

하지만 그럼에도 불구하고 성능적 병목이 존재하였다.

상태를 전이한다는 것은 무엇인가? 오브젝트가 재생성이 된다는 것이다. 물론 오브젝트 풀링등의 패턴을 사용하지만 이 역시도 어느정도 한계가 있었고 

다음과 같은 성능적 병목들이 존재했다.

OOP적 FSM의 성능 병목

즉 OOP FSM은 구조는 아름답지만, 대규모 환경에서 성능적 한계가 명확했다.

그리고 이때 DOP가 등장한다.

DOP란? : Data-Oriented Programming을 말한다.

DOP FSM의 핵심

상태는 더 이상 "객체"가 아니다.

상태는 "컴포넌트 데이터"이고,

동작은 "시스템(System)"이 책임지게 변한 것이다.

DoP는 OOP가 가진 시스템이 커질수록 생기는 성능상의 병목을 극복하기 위해, 다시 데이터 중심으로 회귀한 프로그래밍 지향으로써 

유니티에서는 ECS라는 이름으로구현된다.

유니티 ECS FSM 형태를 바탕으로 DOP FSM을 C로 구조화하면 다음과 같다.

1. 상태는 구조체로 배열된다

typedef enum 
{
    STATE_IDLE,
    STATE_MOVE,
    STATE_ATTACK
} UnitState;

typedef struct 
{
    float x, y;
    UnitState state;
    int targetId;
} Unit;

이제 상태는 유닛의 필드가 아니라, 전체 유닛 배열의 하나의 열(Column)이 된다.

2. 상태(state) 별로 데이터를 선형 필터링하면서 분기한다

void processFSM(Unit* units, int count) 
{
    for (int i = 0; i < count; ++i) 
    {
        switch (units[i].state) 
        {
            case STATE_IDLE:
                // do nothing
                break;
            case STATE_MOVE:
                moveUnit(&units[i]);
                break;
            case STATE_ATTACK:
                attackTarget(&units[i]);
                break;
        }
    }
}

(앞선 코드를 DOP 방식으로 쓴 것. 다만 과거의 형태와 직접적 비교를 위한 것이며, 실제 정확한 DOP 방식은 아래와 같다.)

2-1 제대로 된 DOP 방식

// 진정한 DOP 방식: 상태 분기(if/switch)가 아예 없음
void processMoveSystem(MoveComponent* movers, int count) {
    // 오직 움직이는 놈들만 모여있는 배열을 CPU가 순차적으로 처리 (상태 분기 실패율 0%)
    for (int i = 0; i < count; ++i) {
        movers[i].x += 1;
    }
}

사실 앞서 보여준 processFSM의 switch 방식에는 아직 한 가지 문제가 남아있는데,

배열을 순차적으로 순회하므로 캐시 지역성은 해결했지만, 루프를 돌 때마다 switch 문을 만난다. 배열의 상태가 [IDLE, ATTACK, MOVE, IDLE, ATTACK...]처럼 무작위로 섞여 있다면, 현대 CPU의 분기 예측기(Branch Predictor)는 다음에 어떤 case가 실행될지 예측하지 못하고 파이프라인을 계속 초기화(Flush)해야 한다. 여기서 엄청난 사이클 낭비가 발생한다.

진정한 DOP는 이 switch 문 자체를 핫 패스(Hot Path)에서 제거한다. 같은 상태의 엔티티끼리 물리적으로 분리된 배열에 모아두고, 시스템은 오직 자신이 담당하는 배열만 순회한다.

3. 상태 전이를 '쓰기 연산'으로 구현한다.

void moveUnit(Unit* u) {
    u->x += 1;
    if (distanceToTarget(u) < 2.0f) 
    {
        u->state = STATE_ATTACK;  // 상태 전이
    }
}

즉 OOP에서 변했던, 객체간의 철학보다는

이제 오히려 과거의 직접적인 기계에 매핑하던 FSM과 유사해지기 시작한 것이다.

FSM의 진화 3단계

가장 저렴하고, 빠르며, 믿을 수 있는 부품은 존재하지 않는 부품이다. -Gordon Bell PDP 컴퓨터 설계자

8KB의 RAM, 부동소수점 연산 불가

포켓몬 개발자들에게 '존재하지 않는 부품'은 부동소수점 연산 유닛이었고, 넉넉한 RAM이었으며, 똑똑한 컴파일러였다..

그들은 '없는 것'을 당연하게 여기고, 오직 있는 것(레지스터와 약간의 메모리)만으로 세계를 빚었다.

유명한 컴퓨터 공학자는 이렇게 말했다

가장 저렴하고, 빠르며, 믿을 수 있는 부품은 존재하지 않는 부품이다.

Bell은 없는 부품이야말로 최선의 부품이라하였지만, 포켓몬의 개발자는 '없는 부품을 코드로 만든다'라고 답했다.

오늘날 우리에게 '존재하지 않는 부품'은 어쩌면 무한한 CPU 캐시와 완벽한 분기 예측일지 모른다.

우리는 풍요로움 속에서 '하드웨어가 당연히 빠를 것'이라 가정하지만,

최고의 성능은 여전히 기계의 동작 원리를 이해하고 그들의 방식으로 데이터를 구성해 줄 때 나타난다.

FSM의 진화는 '인간을 위한 추상화'와 '기계를 위한 최적화' 사이를 오가는 거대한 진자 운동과 같다.

그리고 오늘날 DOP의 모습에서, 우리는 그 둘을 모두 쟁취하려는 현대 개발자들의 새로운 도전을 목격하고 있다.

도구는 변했지만, 주어진 제약 속에서 최고의 경험을 만들어내려는 '장인의 혼'은 그때나 지금이나 변하지 않았던 것이다.

그리고 그때나 지금이나 가장 저렴하고, 빠르며, 믿을 수 있는 부품

프로그래머는 여전히 살아 숨쉬고 있다.

포켓몬 어셈블리어 코드 출처: https://github.com/pret/pokered