유한상태머신이란?
유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA; 복수형: 유한 오토마타 finite automata)는 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델이다. 간단히 '상태 기계'라고 부르기도 한다.
유한 상태 기계는 유한한 개수의 상태를 가질 수 있는 오토마타, 즉 추상 기계라고 할 수 있다. 이러한 기계는 한 번에 오로지 하나의 상태만을 가지게 되며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 이러한 기계는 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. 특정한 유한 오토마톤은 현재 상태로부터 가능한 전이 상태와, 이러한 전이를 유발하는 조건들의 집합으로서 정의된다.
-Wiki 백과
FSM을 이용하면 복잡한 상태변화를 비교적 간단하게 처리할 수 있다. 특히 게임 AI에 많이 사용되는데, 애플리케이션 UI도 점점 상태가 복잡해지면서 한번 공부 해봤다.
젤다의 전설을 만들어보자
젤다의 전설의 보코블린 무리를 떠올려보자.
- 보코블린은 모닥불에 둘러 앉아있다.
- 플레이어가 보코블린의 인식 범위에 들어오면 느낌표(!)가 뜨면서 전투 BGM이 흘러나오고 보코블린들이 일어나서 플레이어에게 다가와 공격한다.
- 플레이어가 보코블린으로부터 멀리 도망치면 보코블린은 경계상태를 풀고, 다시 모닥불에 둘러 앉는다.
- 보코블린은 체력이 0이되면 쓰러진다.
이 보코블린의 상태 전이도를 mermaid를 사용해서 그려보았다.
조건문으로 구현...도전!
이걸 전통적인 if-else나 switch-case문으로 구현하면 아주 복잡해진다. 그래도...일단 도전해볼까?
익숙한 kotlin으로 구현할 것이고 조금 단순화 하기 위해서 위에서 적은 이벤트들을 enum class로 뽑았다.
이벤트
interface Event
enum class GameEvent(val message: String): Event {
OnPlayerEnterArea("- 플레이어가 보코블린의 시야에 들어옵니다. -"),
OnPlayerLeaveArea("- 플레이어가 보코블린의 시야를 벗어납니다. -"),
CloseToAttack("- 보코블린의 타격 범위안에 플레이어가 있습니다. -"),
OnPlayerAttack("- 플레이어가 공격합니다 -"),
OnHealthZero("- 보코블린의 체력이 0이 되었습니다. -")
}상태
interface State
sealed interface MonsterState : State {
data object Rest : MonsterState
data object Alert : MonsterState
data object Attack : MonsterState
data object Death : MonsterState
}fun main(args: Array<String>) {
runBlocking {
var cnt = 0
var currentState: MonsterState = MonsterState.Rest
while (cnt < 10) {
delay(Random.nextInt(5) * 1000L)
val event = GameEvent.values().random()
when (event) {
GameEvent.OnPlayerAttack -> {
if (currentState in arrayOf(MonsterState.Alert, MonsterState.Rest)) {
currentState = MonsterState.Attack
}
}
GameEvent.OnPlayerEnterArea -> {
if (currentState == MonsterState.Rest) {
currentState = MonsterState.Alert
}
}
GameEvent.OnPlayerLeaveArea -> {
if (currentState in arrayOf(MonsterState.Alert, MonsterState.Attack)) {
currentState = MonsterState.Rest
}
}
GameEvent.OnHealthZero -> {
currentState = MonsterState.Death
}
GameEvent.CloseToAttack -> {
if (currentState == MonsterState.Alert) {
currentState = MonsterState.Attack
}
}
}
}
}
}10개의 랜덤한 이벤트를 발생시키고, 조건문으로 상태 전이를 해보았다. 이걸 작성하면서 매우 혼란스러웠다. 저 조건문을 작성할때마다 "현재 무슨상태였더라..?", "혹시 다른 상황이 벌어지진 않겠지..?"하는 생각이 들었다. 하지만 어쩐지 익숙한 맛...
게임 개발자셨던 분이 안드로이드 UI 코드를 보면서 "이렇게 상태관리하면 안돼"라고 하셨던 이유를 이제 깨달았다...
fun somAndroidUiLogic() {
when (uiState) {
Success -> {
when (uiState.data) {
MyProfile -> {}
UserProfile -> {}
}
}
Error -> {}
}
}
오케이, 이정도 조건문까진 참을 수 있다고 가정하겠다.
하지만 문제는 저기에서 끝나지 않는다.
- 보코블린이 경계상태로 돌입하면 "!"를 머리위에띄우고, 경계상태를 벗어나면 "!"를 지우고, 공격할때의 공격 모션과 BGM 재생, 그리고 또 보코블린이 죽었을때 죽는 모션과 죽고나서 시체가 사라지는 것들을 어떻게 저 코드에서 처리를 할 것인가?
- 혹은 상태가 몇가지 더 추가된다면 프로그래머는 얼마나 복잡한 상황들을 생각해야할까?
FSM 구현하기
FSM은 다음 4가지 개념적 요소들로 구성된다.
- 상태(State): 특정 시간에 처한 상황
- 상태간 전이(Transition): 상황 변화
- 이벤트(Event): 상태간 전이를 유발시키는 사건
- 행동(Action): 이벤트에 반응하여 다른 상태로 전이할때 하는 동작
즉 - 유한한 상태 집합이 있고, 한번에 하나의 상태만을 가지며 이벤트가 발생하면 정해진 다음 상태로 전이해서 행동이 발생한다.
상태
위에서 정의했던 State 인터페이스에 행동을 구현하기 위해 몇가지 메소드를 추가했다.
interface State {
fun onPreEnter() {}
fun onPreLeave() {}
fun onEnter() {}
fun onLeave() {}
}그에따라 몬스터의 상태들에도 몇가지 행동(Action)을 추가해보았다.
sealed interface MonsterState : State {
data object Rest : MonsterState {
override fun onEnter() {
println("보코블린이 앉아서 쉬고 있다.")
}
override fun onPreLeave() {
super.onPreLeave()
println("보코블린이 일어선다.")
}
}
data object Alert : MonsterState {
override fun onPreEnter() {
println("보코블린 머리위에 ! 를 띄운다.")
}
override fun onEnter() {
println("보코블린이 플레이어에게 다가온다.")
}
override fun onPreLeave() {
println("보코블린 머리위에 ! 를 지운다.")
}
}
data object Attack : MonsterState {
override fun onPreEnter() {
println("보코블린이 등에 있던 곤봉을 꺼낸다.")
}
override fun onEnter() {
println("보코블린가 플레이어를 공격한다.")
}
}
data object Death : MonsterState {
override fun onPreEnter() {
println("보코블린이 비명을 지릅니다. 크아아아아악!")
}
override fun onEnter() {
println("보코블린이 쓰러졌습니다.")
}
}
}BaseStateMachine
어떤 상태든 전이 시킬 수 있는 베이스 상태머신이다. 상태가 동일하면 전이되지 않고, 상태가 전이되면 그에 따라 onPreEnter, Enter, PreLeave, Leave 등 State의 메소드를 적절히 호출한다.
abstract class BaseStateMachine<T : State>(
private var currentState: T
) {
init {
currentState.onPreEnter()
currentState.onEnter()
}
fun get() = currentState
fun set(next: T) {
if (currentState == next) {
return
}
currentState.onPreLeave()
next.onPreEnter()
currentState.onLeave()
currentState = next
next.onEnter()
}
}FiniteStateMachine
다음은 BaseStateMachine을 상속받아 만든 FSM이다. FSM은 전이할 수 있는 경우의 수가 제한적이다. 어떤 이벤트가 일어날때 현재 상태 -> 다음상태로 넘어갈 수 있는 상황들을 transitions에 담을 수 있게 했다.
사건이 일어났을때 전이될 수 있다면 전이하는 역할을 한다.
abstract class FiniteStateMachine<T : State>(
initialState: T,
private val transitions: Map<Transition, T>
) : BaseStateMachine<T>(initialState) {
data class Transition(
val state: State,
val event: Event
)
fun onEvent(event: Event) {
val next = transitions[Transition(state = get(), event)] ?: return
set(next)
}
}MonsterStateMachine
만들었던 FSM을 이용해 보코블린의 초기 상태와, 전이할 수 있는 상태의 집합을 정의해주면 끝이다.
class MonsterStateMachine(initialState: MonsterState) : FiniteStateMachine<MonsterState>(
initialState = initialState,
transitions = mapOf(
Transition(
state = MonsterState.Rest,
event = GameEvent.OnPlayerEnterArea
) to MonsterState.Alert,
Transition(
state = MonsterState.Rest,
event = GameEvent.OnPlayerAttack
) to MonsterState.Attack,
Transition(
state = MonsterState.Alert,
event = GameEvent.CloseToAttack
) to MonsterState.Attack,
Transition(
state = MonsterState.Alert,
event = GameEvent.OnPlayerAttack
) to MonsterState.Attack,
Transition(
state = MonsterState.Alert,
event = GameEvent.OnPlayerLeaveArea
) to MonsterState.Rest,
Transition(
state = MonsterState.Attack,
event = GameEvent.OnPlayerLeaveArea
) to MonsterState.Rest,
Transition(
state = MonsterState.Attack,
event = GameEvent.OnHealthZero
) to MonsterState.Death,
Transition(
state = MonsterState.Rest,
event = GameEvent.OnHealthZero
) to MonsterState.Death,
Transition(
state = MonsterState.Alert,
event = GameEvent.OnHealthZero
) to MonsterState.Death,
)
)이 부분이 사실상 위에 "조건문으로 구현하기"에서 if-else문에 해당하는 부분인데 그때 겪었던 고통없이 구현을 할 수 있었던것이, 상태전이도를 그릴때 썼던 mermaid 코드 그대로를 나열하기만 하면 됬다.
graph LR
rest((휴식))
alert((경계))
attack((공격))
death((죽음))
rest -- 플레이어가 시야에 들어온다 --> alert
rest -- 플레이어가 공격했다 --> attack
alert -- 플레이어가 공격 범위안에 있다 --> attack
alert -- 플레이어가 공격했다 --> attack
alert -- 플레이어가 시야를 벗어났다. --> rest
attack -- 플레이어가 시야를 벗어났다. --> rest
attack -- 체력이 0이 되었다 --> death
rest -- 체력이 0이 되었다 --> death
alert -- 체력이 0이 되었다 --> death
실행해보기 - 텍스트 젤다의 전설
메인 함수는 이렇게 된다. 실제 게임은 아니기때문에 이벤트가 랜덤으로 발생해서 이벤트 사이의 연관성이 좀 없지만...ㅋㅋㅋ 상태전이가 올바로 되는지 보기에는 아주 좋다.
fun main(args: Array<String>) {
runBlocking {
var cnt = 0
val monster = MonsterStateMachine(MonsterState.Rest)
while (cnt < 10) {
delay(Random.nextInt(5) * 1000L)
val event = GameEvent.values().random()
println(event.message)
monster.onEvent(event)
cnt++
}
}
}보코블린이 앉아서 쉬고 있다.
- 플레이어가 보코블린의 시야에 들어옵니다. -
보코블린이 일어선다.
보코블린 머리위에 ! 를 띄운다.
보코블린이 플레이어에게 다가온다.
- 플레이어가 보코블린의 시야에 들어옵니다. -
- 플레이어가 보코블린의 시야를 벗어납니다. -
보코블린 머리위에 ! 를 지운다.
보코블린이 앉아서 쉬고 있다.
- 플레이어가 공격합니다 -
보코블린이 일어선다.
보코블린이 등에 있던 곤봉을 꺼낸다.
보코블린가 플레이어를 공격한다.
- 보코블린의 타격 범위안에 플레이어가 있습니다. -
- 보코블린의 체력이 0이 되었습니다. -
보코블린이 비명을 지릅니다. 크아아아아악!
보코블린이 쓰러졌습니다.-안에는 랜덤하게 발생한 이벤트가 출력됨- <Event> -- 나머지는 액션이 출력됨
실제로 프로그램을 돌려보면 원하던대로 상태전이가 되고, 보코블린이 말도 안되는 이벤트는 무시하고 자연스럽게 행동함을 볼 수 있다. 콘솔에는 찍히지 않았지만 보코블린이 죽고나면 아무런 이벤트에도 반응하지 않는다. 이렇게 직접 만들어보니 복잡한 문제를 이렇게나 간단하게 풀 수 있구나 확 와닿는다.
참고자료
http://www.ktword.co.kr/test/view/view.php?no=3203
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84
'프로그래밍 > General' 카테고리의 다른 글
| Android Studio Custom Shortcuts (0) | 2024.01.07 |
|---|---|
| [VideoJS] 영상 타임라인에 프리뷰를 표시하는 방법 (1) | 2023.12.03 |
| 홈서버 설치과정 요약 (0) | 2023.10.28 |
| 멀티 플레이 게임서버 구현 4편: 지연 보정 (0) | 2023.09.29 |
| 멀티플레이 게임서버 구현 3편: 엔티티 인터폴레이션 (2) | 2023.09.22 |