AI나 컴파일러 개발자가 아니라면 익숙한 개념이 아닐 수 있다.
간단한 횡스크롤 플랫포머를 만들다고 할 때 버튼을 눌러서 점프하는 것을 만들 때, 점프를 했을 때, 또 한 번 더 누를 수가 있다. 이럴 때가 있을 수 있기 때문에 점프 상태가 아닐 때만 실행할 수 있도록 해야 한다.
또한, 땅에 있을 때 아래 버튼을 누르면 엎드리고, 버튼을 떼면 다시 일어서는 기능을 추가할 때, 점프 중 일 때에도 땅에 서 있는 모습으로 보일 수도 있다. 그렇기 때문에 점프 중인지 아닌지와 버튼을 누르고 있는지를 체크해야 한다.
이런 것을 보면 코드가 얼마 없는데도 조금만 건드리면 망가진다. 심지어 걷기 구현조차 시작하지도 않았다.
유한 상태 기계(FSM)
컴퓨터 과학 분야 중의 하나인 오토마타 이론에서 나왔다.
- 가질 수 있는 '상태'가 한정된다.
- 한 번에 '한 가지' 상태만 될 수 있다.
- '입력'이나 '이벤트'가 기계에 전달된다.
- 각 상태에는 입력에 따라 다음 상태로 바뀌는 '전이'가 있다.
예를 들어, 서 있는 동안 아래 버튼을 누르면 엎드리기 상태로 전이, 점프하는 동안 아래 버튼을 누르면 내려찍기 상태로 전이, 현재 상태에서 들어온 입력에 대한 전이가 없을 경우 입력을 무시
순수하게 형식만 놓고 보면 상태, 입력, 전이가 FSM의 전부, 컴파일러가 플로차트를 이해하지 못하니 구현해야 한다.
열거형과 다중 선택문
여러 플래그 변수 중에서 하나만 참일 때가 많다면 열거형(enum)이 필요하다는 신호
플래그 변수 여러 개 대신 상태 필드 하나만 만들면 된다.
분기 순서도 바뀐다. 이전에는 입력에 따라 먼저 분기한 뒤에 상태에 따라 분기
하나의 버튼 입력에 대한 코드는 모아둘 수 있었으나 하나의 버튼 입력에 대한 코드는 모아둘 수 있었으나
하나의 상태에 대한 코드는 흩어져 있었다. 상태 관련 코드를 한 곳에 모아두기 위해 상태에 따라 분기한다.
열거식으로 코드를 나눈다면 코드가 나눠졌다. 분기문을 다 없애지는 못했지만 업데이트해야 할 상태 변수를 하나로 줄였고, 하나의 상태를 관리하는 코드는 깔끔하게 한 곳에 모을 수 있다. 열거형은 상태 기계를 구현하는 가장 간단한 방벙, 이 정도만으로 충분할 때도 있다.
상태 패턴
상태 인터페이스
상태에 의존하는 모든 코드, 즉 다중 선택문에 있던 동작을 인터페이스의 가상 메서드로 만든다.
상태별 클래스
상태별로 인터페이스를 구현하는 클래스도 정의
메서드에는 정해진 상태가 되었을 때 캐릭터가 어떤 행동을 할지를 정의
다른 선택문에 있던 case별로 클래스를 만들어 코드를 옮기면 된다.
동작을 상태에 위임
객체의 현재 상태 객체 포인터를 추가해, 거대한 다중 선택문을 제거하고 상태 객체에 위임
상태 객체는 어디에 두어야 하나
상태를 바꾸려면 상태에 새로운 상태 객체를 할당해야 한다.
열거형은 숫자처럼 기본 자료형이기 때문에 신경 쓸 게 없지만
상태 패턴은 클래스를 쓰기 때문에 포인터에 저장할 실제 인스턴스가 필요
정적 객체
상태 객체에 필드가 따로 없다면 가상 메서드 호출에 필요한 가상 테이블 포인터만 있게 된다.
모든 인스턴스가 같기 때문에 인스턴스는 하나만 있으면 된다.
여러 FSM이 동시에 돌더라도 상태 기계는 다 같으므로 인스턴스 하나를 같이 사용하면 된다.
상태 객체 만들기
정적 객체만으로 부족할 떄도 있다. 엎드리기 상태에서는 시간 필드가 있는데 이 값이 객체마다 다르다 보니 정적 객체로 만들 수 없다. 객체가 하나라면 어떻게든 되겠지만, 여러 캐릭터의 객체들을 한 화면에 보여야 한다면 문제가 된다.
이럴 때는 전이할 때마다 상태 객체를 만들어야 한다. FSM이 상태별로 인스턴스를 갖게 된다. 새로 상태를 할당했기 때문에 이전 상태를 해제해야 한다. 상태를 바꾸는 코드가 현재 상태 메서드에 있기 때문에 삭제할 때 this를 스스로 지우지 않도록 주의해야 한다.
상태가 바뀔 때에만 새로운 상태를 반환하고, 밖에서는 반환 값에 따라 예전 상태를 삭제하고 새로운 상태를 저장
새로운 상태를 반환하지 않는다면 현재 상태를 삭제하지 않는다. 서 있기 상태에서 엎드리기 상태로 전이하려면 새로운 인스턴스를 생성해 반환한다.
입장과 퇴장
상태 패턴의 목표는 같은 상태에 대한 모든 동작과 데이터를 클래스 하나에 캡슐화하는 것이다.
객체는 상태를 변경하면서 객체의 스프라이트도 같이 바꾼다. 지금까지는 이전 상태에서 스프라이트를 변경했다.
이렇게 하는 것보다는 상태에서 그래픽까지 제어하는 게 바람직, 입장 기능을 추가
새로운 상태에 들어 있는 입장 기능을 호출하도록 상태 변경 코드를 수정
서기 상태로 변경하기만 하면 서기 상태가 알아서 그래픽까지 챙긴다. 그래야 상태가 제대로 캡슐화되었다고 할 수 있다.
그 전 상태와는 상관없이 항상 같은 입장 코드가 실행된다는 것도 장점, 실제 게임 상태 그래프라면 점프 후 착지 혹은 내려찍기 후 착지하는 식으로 같은 상태에 여러 전이가 들어올 수 있다. 그냥 두면 전이가 일어나는 모든 곳에 중복 코드를 넣었겠지만 이제는 입장 기능 한 곳에 코드를 모아둘 수 있다.
상태가 새로운 상태로 교체되기 직전에 호출되는 퇴장 코드도 이런 식으로 활용할 수 있다.
단점은?
상태 기계는 엄격하게 제한된 구조를 강제함으로써 복잡하게 얽힌 코드를 정리할 수 있게 해 준다.
FSM에는 미리 정해놓은 여러 상태와 현재 상태 하나, 하드 코딩되어 있는 전이만이 존재
상태 기계를 인공지능같이 더 복잡한 곳에 적용하다 보면 한계에 부딪히게 된다.
병행 상태 기계
총을 장착한 후에도 이전에 있었던 달리기, 점프, 엎드리기 같은 동작을 모두 할 수 있어야 한다.
그러면서 동시에 총도 쏠 수 있어야 한다.
FSM 방식을 고수하겠다면 모든 상태를 서기, 무장한 채로 서기, 점프, 무장한 채로 점프 같은 식으로 무장,
비무장에 맞춰 두 개씩 만들어야 한다.
무기를 추가할수록 상태 조합이 폭발적으로 늘어난다.
상태가 많아지는 것도 문제지만,
무장 상태와 비무장 상태는 총 쏘기 코드 약간 외에는 거의 같아서 중복이 많아진다는 점이 더 문제
두 종류의 상태, 무엇을 하는가와 무엇을 들고 있는가를 한 상태 기계에 욱여넣다 보니 생긴 문제
모든 가능한 조합에 대해 모델링하려다 보니 모든 쌍에 대해 상태를 만들어야 한다.
해결법은 상태 기계를 둘로 나누면 된다.
무엇을 하는가에 대한 상태 기계는 그대로 두고, 무엇을 들고 있는가에 대한 상태 기계를 따로 정의
각각의 상태 기계는 입력에 따라 동작을 실행하고 독립적으로 상태를 변경할 수 있다.
두 상태 기계가 서로 전혀 연관이 없다면 이 방법이 잘 들어맞는다.
현실적으로는 점프 도중에는 총을 못 쏜다든가, 무장한 상태에서는 내려찍기를 못한다든가 하는 식으로 복수의 상태 기계가 상호작용해야 할 수도 있다. 이를 위해 어떤 상태 코드에서 다른 상태 기계의 상태가 무엇인지를 검사하는 코드를 만들 일이 생길 수도 있다. 좋지는 않지만, 문제를 해결할 수는 있다.
계층형 상태 기계
단순한 상태 기계 구현에서는 이런 코드를 모든 상태마다 중복해 넣어야 한다.
그보다는 한 번만 구현하고 다른 상태에서 재사용하는 게 낫다.
상태 기계가 아니라 객체지향 코드라고 생각해보면, 상속으로 여러 상태가 코드를 공유할 수 있다.
점프와 엎드리기는 '땅 위에 있는' 상태 클래스를 정의해 처리,
서기, 걷기, 달리기, 미끄러지기는 '땅 위에 있는' 상태 클래스를 상속받아 고유 동작을 추가하면 된다.
이런 구조를 계층형 상태 기계라고 한다. 어떤 상태는 상위 상태를 가질 수 있고,
그 경우 그 상태 자신은 하위 상태가 된다.
이벤트가 들어올 떄 하위 상태에서 처리하지 않으면 상위 상태로 넘어간다.
상속받은 메서드를 오버라이드 하는 것과 같다.
계층형을 꼭 이렇게 구현해야 하는 건 아니다.
주 클래스에 상태를 하나만 두지 않고 상태 스택을 만들어 명시적으로 현재 상태의 상위 상태 연쇄를 모델링할 수도 있다.
현재 상태가 스택 최상위에 있고 밑에는 바로 위 상위 상태가 있으며, 그 상위 상태 밑에는 그 상위 상태의 상위 상태가 있는 식, 상태 관련 동작이 들어오면 어느 상태든 동작을 처리할 때까지 스택 위에서부터 밑으로 전달 ( 아무도 처리하지 않는다면 무시하면 된다 )
푸시다운 오토마타
상태 스택을 활용하여 FSM을 확장하는 다른 방법도 있다.
계층형 FSM에서 봤던 스택과는 상태를 담는 방식도 다르고 해결하려는 문제도 다르다.
FSM에는 이력 개념이 없다는 문제가 있다. 현재 상태는 알 수 있지만 직전 상태가 무엇인지를 따로 저장하지 않기 때문에 이전 상태로 쉽게 돌아갈 수 없다.
일반적인 FSM에서는 이전 상태를 알 수 없다. 이전 상태를 알려면 서 있는 상태에서 총 쏘기, 달려가면서 총 쏘기, 점프하면서 총 쏘기 같은 식으로 상태마다 새로운 상태를 하나씩 더 만들어 총 쏘기가 끝났을 때 되돌아갈 상태를 하드 코딩해야 한다.
이것보다는 총 쏘기 전 상태를 저장해놨다가 나중에 불러와 써먹는 게 훨씬 낫다.
이럴 때 써먹을 만한 것으로 푸시다운 오토마타가 있다.
FSM이 한 개의 상태를 포인터로 관리했다면 푸시다운 오토마타에서는 상태를 스택으로 관리
FSM은 이전 상태를 덮어쓰고 새로운 상태로 전이하는 방식
푸시다운 오토마타에서는 이외에도 부가적인 명령이 두 가지 더 있다.
- 새로운 상태를 스택에 넣는다. 스택의 최상위 상태가 '현재' 상태이기 때문에, 새로 추가된 상태가 현재 상태가 된다.
다만, 이전 상태는 버리지 않고 방금 들어온 최신 상태 밑에 있게 된다.
- 최상위 상태를 스택에서 뺀다. 빠진 상태는 제거되고, 바로 밑에 있던 상태가 새롭게 '현재' 상태가 된다.
총 쏘기 상태를 구현할 때 딱 좋다. 총 쏘기 상태를 만들고, 발사 버튼을 누르면 총 쏘기 상태를 스택에 넣고 총 쏘기 애니메이션이 끝날 때 총쏘기 상태를 스택에서 빼면, 푸시다운 오토마타가 알아서 이전 상태로 보내준다.
얼마나 유용한가
FSM에는 몇 가지 확장판이 나와 있지만 FSM만으로는 한계가 있다.
요즘 게임 AI는 행동 트리나 계획 시스템을 더 많이 쓰는 추세다.
FSM이나 푸시다운 오토마타, 그 외 간단한 시스템들이 쓸모없다는 얘기는 아니다.
이것만으로도 특정 문제 해결을 위한 모델링으로선 충분
FSM은 다음 경우에 사용하면 좋다.
- 내부 상태에 따라 객체 동작이 바뀔 때
- 이런 상태가 그다지 많지 않은 선택지로 분명하게 구분될 수 있을 때
- 객체가 입력이나 이벤트에 따라 반응할 때
게임에서는 FSM이 AI에서 사용되는 걸로 가장 잘 알려져 있지만, 입력 처리나 메뉴 화면 전환, 문자 해석, 네트워크 프로토콜, 비동기 동작을 구현하는 데에도 많이 사용되고 있다.