FSM 구현과 관련된 질문입니다.

게임의 인공지능에 관한 포럼입니다.

Moderator: 류광

Locked
비회원

FSM 구현과 관련된 질문입니다.

Post by 비회원 »

게임 객체의 상태에 따른 행동 처리(효율적인)를 구현하려고 합니다.

의례 검색해서 나오는 것이 유한 상태 기계라 그것을 적용하려고 자료를 찾아보았습니다.

유한 상태 기계에 대해서 알아보기 전에는 디자인 패턴과 같은 설계 방법같은 것으로 나름 상상하고있었는데 디자인 패턴과 같은 정형적인 해결방법이 아니라서 그런지 예제 코드들의 모양이 다 달라서 이것 저것 찾아봐도 구체적으로 어떤식으로 구현하면 되겠구나 싶은 그림이 그려지지 않습니다.

그래서 개념 이해 차원에서 짧막하게 코딩하면서 이렇게 저렇게 해보고있는 상태입니다.

class IState
{
public:
virtual Begin(Object* object) = 0;
virtual Update(Object* object) = 0;
virtual End(Object* object) = 0;
};

class Patrol : public IState {};

class Object
{
Type;
IState = new Patrol;
Update()
{
IState->Update(this);
}
};

위와 같았던 구현을 'Type에 따라 정찰 방법이 달라야 한다'라는 조건을 만들어 아래와 같이 변경했는데

class MonsterA_Patrol : public IState {};
class MonsterB_Patrol : public IState {};

class Object
{
IState = Type == MonsterA ? new MonsterA_Patrol : new MonsterB_Patrol;
Update()
{
IState->Update(this);
}
};

질문1) 위와 같이 오브젝트의 타입(이라기 보다는 행동 방식에 따라 분류한 그룹정도의 느낌인거 같은데 아직 개념이 확실하게 서지 않은 상태)과 상태에 따라 각각의 클래스들을 모두 구현해 주는 것이 올바른 방법인지 궁금합니다(상태 클래스 개수만 수십개가 넘어갈거 같고, 그런 클래스들의 상태 전이를 조합(?조립)하는 것도 만만한 일이 아닌듯하여).

질문2) 그리고 위와 같은 방법이 일반적인 방법이라면 구현방식을 아예 달리한 아래와 같은 방법과 비교해 위의 방법이 갖는 장점이 무엇인지 궁금합니다.
아래 방법이 MonsterA의 구체적인 Patrol 방법이 MonsterA 클래스 안에서 구현되어 있기 때문에 제 개인적으로는 모양세가 나아보입니다.
class MonsterA : public Object
{
Update()
{
case PATROL:
Patrol();
break;
}

Patrol() {}
};

class MonsterB : public Object {};
class MonsterC : public Object {};

질문3) FSM 구현에 참고할만한 글이나 예제 포탈 좀 열어주시면 감사하겠습니다(나름대로 찾아보곤했는데 예제가 완벽한 풀소스가 아니라 짧은 지식으로 그것만 보곤 잘 이해도 안되고해서-_-;;).
Zeprod
Posts: 480
Joined: 2006-11-04 16:24
Location: Creaty Networks
Contact:

Post by Zeprod »

FSM뿐만아니라 거의 대부분의 알고리즘이 어떻게 구현하느냐에 중점을 두고 설명하기때문에, 실제 구현을 찾으시긴 힘드실겁니다.


해당 알고리즘이 어떤이유로 그런 방법을 택했는지를 알아보고, 그런 점들을 충분히 이해하는 등의 선행과정이 필요하겠죠.



FSM은 단순히 상태전이를 통해 현재 어떤일을 하면 좋을지를 결정하기 쉬운 모델이라고 할 수 있습니다.

표현하는 방법은 사람마다 다른게 당연하니 스스로 구현해보시는 것도 좋으리라 생각합니다.




typedef enum {
start,
live,
death,
end,
} STATE;

이런식으로 상태를 구현해서, 실제 판단시에 start 상태에선 무슨일을, end 상태에선 무슨일을 하는지 구현하는 것으로 다양한 상태를 손쉽게 관리하고자 하는것이 FSM입니다.

상당히 고전방식이나 지금도 구현의 편의성때문에 자주 이용되는 방식입니다만...



중요한건 알고리즘이 아니라 마음이겠죠.
세상이 기다리는 나만의 SHOW!
----------------------------------------------
Zeprod 홈 : http://Zeprod.org
Project. Creaty : http://Creaty.net/
Creaty 게임제작 커뮤니티 : http://Creaty.net/game/
----------------------------------------------
futurity
Posts: 65
Joined: 2003-01-23 14:40

도움이 됐으면 합니다. ^^

Post by futurity »

정말 오랜만에 글을 쓰네요.
저도 AI업무를 하고 있어서 같은 고민을 했었습니다.
제 답변이 정답은 아닙니다. 참고만 해주세요 ^^
질문1) 위와 같이 오브젝트의 타입(이라기 보다는 행동 방식에 따라 분류한 그룹정도의 느낌인거 같은데 아직 개념이 확실하게 서지 않은 상태)과 상태에 따라 각각의 클래스들을 모두 구현해 주는 것이 올바른 방법인지 궁금합니다(상태 클래스 개수만 수십개가 넘어갈거 같고, 그런 클래스들의 상태 전이를 조합(?조립)하는 것도 만만한 일이 아닌듯하여).
우선 제 방식을 간단히 설명드리면, 상태분류에 따라서 Layer로 나누어서 처리했습니다.
저 같은 경우는 행동 Layer, 전략 Layer, Script Layer를 구분하여서 상태를 분리했습니다.
(Ai Wisdom, Game Gems 참고했습니다.)

행동 Layer는 뛰기, 걷기, 공격, 죽기등 직접적인 행동에 대한 상태
전략 Layer는 도망, 근거리공격, 원거리공격, 무작위배휘, WayPoint배회등 전략에 따른 상태로 행동Layer 상태를 선택합니다.
Script Layer는 간단히 전략 상태를 설정하시면 됩니다. 여기서는 기획자가 생태를 생성하고 전략Layer 상태를 설정합니다.

질문 내용을 답하자면 Layer별로 상태를 관리 하시는것을 추천드립니다.
어떤 Layer가 존재해야 되고 어떤 상태가 존재해야 되는지는 프로그래머가 결정해야 됩니다.
(이야기가 길어질거 같아서 여기까지만 ^^)
질문2) 그리고 위와 같은 방법이 일반적인 방법이라면 구현방식을 아예 달리한 아래와 같은 방법과 비교해 위의 방법이 갖는 장점이 무엇인지 궁금합니다.


이 부분은 답변을 못드리겠네요. 개인적인 의견으로는 클래스 설계에 차이인듯 합니다.
객체 지향 프로그래밍에서는 재사용성을 중요시 하니깐요. ^^
질문3) FSM 구현에 참고할만한 글이나 예제 포탈 좀 열어주시면 감사하겠습니다(나름대로 찾아보곤했는데 예제가 완벽한 풀소스가 아니라 짧은 지식으로 그것만 보곤 잘 이해도 안되고해서-_-;.
Ai Wisdom 씨리즈, GameGems 씨리즈등을 참고했습니다.
아마도 질문자님이 원하시는 풀소스는 찾기 어려울듯 하네요.
프로그래밍은 즐겁다...
futurity골뱅이korea.com
iremember
Posts: 9
Joined: 2006-08-10 16:42

그밖에...

Post by iremember »

안녕하세요, 저도 효율적이고, 최대한 재사용 가능한 AI구조를 고심했었습니다.

### 질문 1, 2에 대한 답변입니다.

우선, 여러가지 사례들이 있겠습니다만, 의사결정 트리(Decisioin Tree(혹은 Graph))는 어떨까요?

물론, 정답은 없습니다. 같은 고민을 했었기에...

* 하나의 상태(State)를 기호(Symbol)화하고, 각각의 선택 상황을 의사결정(Decision)객체로 놓았습니다.
여기서 말하는 상태는 true혹은 false를 말합니다. 스위치가 켜졌냐, 꺼졌냐와 같은 의미죠.

* Decision객체가 필요한 정보로는 기호화된 상태를 이용한 비교를 위한 상태 비교(StateComparision)객체,
결정된 결과에 따른 목표(Goal)객체를 가지고 있도록 했습니다. 목표를 달성하기 위해서 행동을 해야겠지요.

* 여기서 Goal객체는 바로 행동(Action)객체를 정보로 갖도록 했습니다.
행동을 하기 위해서는 다시 한번 상태를 체크해야합니다. 지금 행동을 할 수 있는지 아닌지말이죠.

* Action객체가 갖는 정보는 상태 비교를 위한, StateComparision객체를 갖도록 했습니다.
상태를 비교한 후에, 적합하다면, 행동을 하도록 하는 것입니다.

설명이 조금 복잡했습니다만, 기호화된 상태를 이용하여, 구상한 AI를 데이터화한 후에,
1) Sensor에 의하여, 현재 상태들을 수집합니다. 상태 기호들의 값을 상황에 맞게 변경해줍니다.
2) Decision Tree에 의하여, 현재 수행할 Action들을 수집합니다.
3) 수집된 Action들을 수행합니다.

위와같은 구조의 장점은,
상태 전이의 조합을 비교적 수월하게 할 수 있다는 것입니다.
Object가 느끼는 상태들의 true/ false를 적절하게 바꿔주기만 하면 됩니다.
또한 데이터화하여, 추후에 재사용하기 용이합니다.

단점은,
잘 못 사용하면 Sensor의 구현과, Action의 구현이 겹쳐버릴 수 있습니다. (비효율적으로 사용)
데이터가 많아져, 디버깅이 복잡해질 수 있습니다. (툴을 제작하거나, Graphviz등을 활용할 수 있겠습니다.)
혹은, Decision Tree의 노드가 많아져, 속도에 영향을 미칠수도 있겠군요.

* 조금 더 생각하면, 더 효율적인 구조가 있을것이라고 생각합니다. 도움이 되길 바랍니다. :)

### 질문 3번에 대한 답변입니다.

AI관련 서적도 도움이 되겠지만, GDC의 AI세션이나 Game AI 커뮤니티, Game AI Conference,

혹은 유명한 게임들에 사용된 AI문서들, 혹은 몇몇 논문들이 도움이 될 것입니다. 구글을 활용해보세요..

http://www.google.co.kr/search?complete ... ision&cd=4

http://www.google.co.kr/search?complete ... =&aq=f&oq=

음, 위에 제가 설명했던 방식과 비슷한 사례로, 에디 랭이라는 분의 사이트에 구현해놓은 실행가능한 결과물이 있군요. 소스코드도 공개인것같습니다.

http://www.edmundlong.com/Downloads/downloads.php

등등... 찾아보시면 의외로 자료가 있습니다. 대부분 영문이긴 합니다. @_@
질문하신 내용은, FSM이군요. 하지만, 답변이 먼산으로 가버렸군요..... 죄송...
/*

Let's GO─!!

*/
비회원

^^

Post by 비회원 »

글쓴이입니다.

'정답은 없다'는 정답을 얻게되네요^3^

생각보다 너무 수준높은 답변들을 주셔서(역시 쉬운게 아니었나봐요ㅠ_ㅜ) 답변 내용들 토대로 좀더 고민해봐야겠습니다.

귀중한 시간내어 해주신 답변 정말 감사합니다!:D
Locked