유한상태기계 (FSM)에 대하여

프로그래밍/프로그래밍 메모장 2006/07/20 11:47

유한상태기계(FSM)에 대하여 . ~  From Xevious7.  http://www.xevious7.com/106
2006.7.20.

글 요약:
  FSM의 매우 기본적인 개념 , 관련된 지식 요약정리.


에프에스엠 (FSM - Finite State Machine) 피니트스테이트머신 은 원어 그대로
해석하여 우리나라에서 보통 유한상태기계라는 용어로 쓰여지고 있습니다.
제가 FSM를 본격적으로 사용하고 공부하기 시작했던때는 94년 이었습니다.
처음 용어를 접한것은 89년쯤으로 기억합니다.

디지탈라직프로세스(Digital Logic Process)라는 과목에서 본격적으로 공부했었는데
학기내내 FSM디자인만 죽어라 했던 기억이 납니다.


FSM은 그자체로 보면 유한한 상태를 가진 기계를 의미하지만 실제적으로는
유한한 상태를 가지는 기계를 정의하는 방법을 의미합니다.
단순하게 요약하면 어떤 행동양식을 정의하는 하나의 도구입니다.

FSM은 언어론, 컴퓨터공학, 디지탈기기 디자인, AI 등등에서 광범위하게 쓰여지고
있습니다. 파스칼이나 SQL을 공부한 적이 있는 사람은 아마도 언어설명 부분에
다음과 같은 다이어그램을 본적이 있을 것입니다.



요즈음의 책은 이러한 형태의 다이어그램을 실은 언어책이 없지만
파스칼이 한참 유행했던 시절만 해도 이러한 다이어그램을 쉽게 볼 수 있었습니다.
이런 다이어그램은 실제로 문장구조가 어떻게 구성되는지를 보여줍니다.

FSM은  보통 동그라미로 표현되는 상태와 상태전이를 표현하는 화살표연결선 으로
구성되는 상태 다이어그램(상태도) 이라는 것으로 표현됩니다.



상태 다이어그램은 FSM을 표현하며 실제적인 FSM의 디자인과 구현을 위해서
사용합니다.


위의 상태 다이어그램은 일반적인 디지탈 라직에서 표현하는 다이어그램으로
상태전이를 할수 있는 값이 오로지 0과 1 즉 디지탈라직에서 표현할 수 있는
값이 0과 1이기때문에  두 값만 가지고 있습니다. 가장 일반적인 상태 다이어그램
입니다. 0과 1은  F(거짓) , T(참) 꼴로 표현할 수 있습니다.
이것은 나중에 그대로 상태전이테이블을 만들어 디지탈라직으로 구현됩니다.


위의 상태 다이어그램은 게임상의 캐릭터의 움직임의 간단한상태와
상태전이를 가지고 구성해본 상태다이어그램 입니다.
이러한 상태다이어그램은 게임 프로그램에서는 프로그래밍 언어로 구현이
되서 VFSM의 역활을 합니다. VFSM은 가상유한상태기계 라는 뜻이며
FSM을 소프트웨어적으로 구현하는 것을 말합니다.

위 상태 다이어그램을 초간단 절차적수도코드로 나타나면 다음과 같습니다.

state = s_normal  // 기본상태 설정

입력처리(조건팩터를 받는다.)

캐릭터 처리 루프 ----------------

switch(state)
         s_sleep  :  대기상태처리 함수
         s_normal :  기본동작처리 함수
         s_walk    : 걷기동작처리 함수
         s_jump    :  점프동작처리 함수
------------------------- 루프 끝

함수정의

s_sleep
{
     입력체크
     if 입력없슴  상태유지
     else 상태전이(s_normal)
}

s_normal
{
     입력체크
     if 입력없슴 {
                       if 일정시간 이상 then 상태전이(s_sleep)
                       상태유지
      }
     else 입력있슴 {
             걷기관련 입력이라면 상태전이(s_walk)
             점프관련 입력이라면 상태전이(s_jump)
       }
}

s_walk
{
    걷기수행
     if 걷기완료 then 상태전이(s_normal)
     상태유지
}

s_jump
{
    점프수행
     if 점프완료 then 상태전이(s_normal)
     상태유지
}

위의 수도코드는 단순한 예에 지나지 않습니다.
구현은 또다른 문제이며 어떤 성향의 언어를 쓰느냐에 따라 달라지겠습니다.

상태도단계와 그와 관련한 설명정도의 단계는 게임을 기획하는
사람에게 어떤  행동양식을 정의하는 목적으로도 유용하게 사용할수
있기 때문에 기획자들도 FSM을 응용하고 있습니다.

어떤 유한의 동작을 하는 것이라면 FSM을 이용하는것이 좀더 쉽게
구현할 수 있는 방법이 되겠습니다. 위의 수도 코드를 보면 결국 상태라는
하나의 변수를 통해서 행동이 관리되는것을 알 수 있습니다.
만약 FSM적인 형태로 구현하지 않는다면 좀더 많은 플래그나 변수가
필요하며 복잡하게 될 것 입니다.  이전에 FSM을 몰랐다고 하더라도
보다 나은 구현을 위해서 알고리즘을 직관적으로 구현한 경우는 그 원리는
몰랐어도 그런형태로 구현했을 수도 있습니다.

원리를 알고나면 좀더 디자인단계부터 여러가지를 고민하여 좀더 나은
형태가 될 수 있을 것입니다.

FSM의 응용은 어떤 유한한 행동을 하는 기계(여기서 기계의 의미는 회로도
모듈도 소프트웨어 함수도 될수 있는것이죠)라면 모두 적용될 수 있기 때문에
꼭 위에서 말한 몇가지 예 뿐만 아니라 그렇게 모델링 할 수 있는 것이라면
다 적용가능하다 할 수 있습니다. 다시 말하면 FSM은 어떤 행동양식을
모델링 하는 방법중에 하나인 것입니다.

개념 파악을 위한 분들에게 도움이 되길 바랍니다.

top

Trackback Address :: http://www.xevious7.com/trackback/106

  1. kpro 2008/01/13 20:10 MODIFY/DELETE REPLY

    좋은글!! 담아갈게요!

  2. a 2014/02/08 20:48 MODIFY/DELETE REPLY

    좋은 글 감사합니다.

Write a comment