[FSM vs Behavior Tree] Part.4 - Behavior Tree 의 구현

Behavior Tree 의 구현

 

Part.2 에서 BehaviorTree의 개념에 대해 알아보았는데요, 이번에는 BehaviorTree 를 C#으로 구현해보겠습니다. 

BehaviorTree 구조의 장점들은 

1. 단순함.

2. FSM 을 개선하기위한 HFSM 이나 PushdownAutomata 처럼 이전 상태/상태머신에 대한 정보를 기억해둘 필요가 없음.

3. 노드 단위를 사용하기 때문에 FSM 처럼 Transition 을 위해 다른 상태들에 의존할 필요가 없음.

4. Base 노드 기반으로 다른 노드들을 확장해서 만들기 때문에, 새로운 기능의 노드를 만들때 확장만 해서 사용하면 되기 때문에 확장성이 높음

 

BehaviorTree 구조의 단점들은

1. 매번 루트로부터 DFS 탐색을 해야하기 때문에 한번에 실행하는 FSM 보다 느림. (높이 또는 동일 높이의 노드수가 늘어날 수록 AI의 의사결정 시간이 늘어남)

2. 노드 위치에 따라 탐색우선순위 선정 기준이 달라짐. ( Utility System 과 같이 우선순위를 결정하는 모델이 필요 )

 

이 있습니다.

 

우선 BehaviorTree 를 구현하기위해서 클래스 컨셉을 보도록 하겠습니다.

BehaviorTree UML

 

- Behavior

우선 기본 행동 단위인 Behavior 클래스가 필요합니다. Behavior 는 해당 행동에서 취할 행위를 호출하는 Invoke() 라는 함수를 추상화하고 있습니다. 

행동의 결과는 Status 로 성공,실패, 실행중에 대해 반환할 수 있도록 합니다. 이번 예시에서는 OnRunning 시에 간단하게 Leaf 를 바로 호출할 수 있도록 leaf 반환을 하나 더 받습니다.

public abstract class Behavior
{
    public Status abstract Invoke(out Behavior leaf);
}

 

- Root

Root 는 자식을 하나 가지고 있고, RunningLeaf 라는것을 또 하나 멤버로 지니고있습니다. 마지막 Tick() 에서 OnRunning 을 반환 받았을 때 어떻게 처리할 것인지 설계에 따라 달라질 수 있지만, 현재 컨셉은 마지막으로 OnRunning 을 반환했던 단말행동노드에 대해 지니고있어 OnRunning 상태에서 Tick() 호출시 DFS 를 하지않고 수행하기위해 RunningLeaf를 지니고 있습니다. 

public class Root : Behavior
{
    public Behavior Child {get; set;}
    public Behavior RunningLeaf {get; set;}
    private Status _tmpResult;
    
    public Status Invoke()
    {
    	_tmpResult = Invoke(out Behavior leaf);
        if (_tmpResult == Status.OnRunning)
        	RunningLeaf = leaf;
        else
        	RunningLeaf = null;
    	return _tmpResult;
    }
    
    public override Status Invoke(out Behavior leaf)
    {
    	return Child.Invoke(out leaf);
    }
    
    public Status InvokeRunningLeaf()
    {
    	_tmpResult = RunningLeaf.Invoke(out Behavior leaf);
    	if (_tmpResult == Status.OnRunning)
        	RunningLeaf = leaf;
        else
        	RunningLeaf = null;
    	return _tmpResult;
    }
}

 

- Composite

Composite 는 여러 자식들을 지니면서 단일노드처럼 행동하기위한 복합노드이기때문에, Behavior 리스트를 가지고 있습니다. Sequence, Selector, Pararell 등을 구현하기위한 추상화 클래스입니다.

public abstract class Composite : Behavior
{
    private List<Behavior> _children = new List<Behavior>;
    public void AddChild(Behavior child) => _children.Add(child);
    public void RemoveChild(Behavior child) => _children.Remove(child);
    public void ClearChildren() => _children.Clear();
}

 

- Sequence

Sequence 는 여러 자식들을 일련의 과정처럼 순회하기위한 노드이기 때문에 Composite 를 상속받고, Invoke 에서 모든 자식을 순회하고 도중에 Failure/ OnRunning 이 반환되면 해당 값을 리턴합니다.

public class Sequence : Composite
{
    private Status _tmpResult;
    public override Status Invoke(out Behavior leaf)
    {
    	leaf = this;
    	foreach(Behavior child in _children)
        {
            _tmpResult = child.Invoke();
            if (_tmpResult != Status.Success)
            {
            	leaf = child;
            	return _tmpResult;
            }
        }
        return Status.Success;
    }
}

 

- Selector

Selector 는 여러 자식들중 성공한 노드의 결과를 선택해서 반환하기위한 노드이기 때문에 Composite 를 상속받고, Invoke 에서 모든 자식을 순회하고 도중에 Success/ OnRunnig 이 반환되면 해당 값을 리턴합니다.

public class Selector : Composite
{
    private Status _tmpResult;
    public override Status Invoke(out Behavior leaf)
    {
    	leaf = this;
    	foreach(Behavior child in _children)
        {
            _tmpResult = child.Invoke();
            if (_tmpResult != Status.Failure)
            {
            	leaf = child;
            	return _tmpResult;
            }
        }
        return Status.Failure;
    }
}

 

- Pararell

Pararell 은 병렬 처리를 위한 노드로서, BehaviorTree 에서 병렬처리란, Branch 에서 깊이가 같은 자식노드들은 결과에 상관없이 모두 호출되어야 한다는 의미를 가집니다. 전부 호출이 되었을 때 다양한 결과들을 종합해서 반환값을 결정해야하기 때문에, 반환값 결정을 위한 정책으로 Policy 타입을 가지고 있습니다. '하나만이라도' 와 '전부 다' 두가지 옵션이 있으며, 두 정책은 각각 성공반환의 척도와 실패반환의 척도로 사용됩니다.

public class Pararell : Composite
{
    public enum Policy
    {
    	RequireOne,
        RequireAll
    }
    private Policy _successPolicy;
    private Policy _failurePolicy;
    private Status _tmpResult;
    
    public Pararell(Policy successPolicy, Policy failurePolicy)
    {
    	_successPolicy = successPolicy;
        _failurePolicy = failurePolicy;
    }
    
    public override Status Invoke(out Behavior leaf)
    {
        leaf = this;
        int successCount = 0;
        int failureCount = 0;
        
        foreach(Behavior child in _children)
        {
            _tmpResult = child.Invoke();
            leaf = child;
            
            if (_tmpResult == Status.Success)
            {
            	if (successPolicy == Policy.RequireOne)
                	return Status.Success;
            	successCount++;
            }            
            else if (_tmpResult == Status.Failure)
            {
            	if (successPolicy == Policy.RequireOne)
                	return Status.Success;
            	successCount++;
            }
        }
        
        if (successPolicy == Policy.RequireAll && successCount >= children.Count)
            return Status.Success;
            
        if (failurePolicy == Policy.RequireAll && failureCount >= children.Count)
            return Status.Failure;
            
        return Status.None;
    }
}

 

- Filter

Filter 는 특정 조건들로 Sequence를 걸러내기위한 행동입니다. 마치 깔때기의 거름종이처럼 children 의 앞에 조건을 부착합니다. 모든 일련의 조건들을 통과했다면, 그 뒤에 붙은 모든 브랜치를 수행합니다.

public class Filter : Sequence
{
    public void AddCondition(Condition condition) => _children.Insert(0, condition);
}

 

- Monitor

Monitor 는 Filter 와 비슷합니다만, Filter 처럼 조건에 따라 우선순위가 낮은 Branch를 걸러내는것이 아니라, 모든 Branch를 수행은 하되, 조건의 변화에 대해서만 감시하기 위한 행동입니다. 구현은 단순히 Pararell 을 상속받아 Filter 처럼 만들어주면 모든 브랜치를 수행하면서 특정 조건들을 감시할 수 있습니다.

 

* Race condition 방지

순서대로 Conditions 와 Execution 들을 정렬해서 추가한다고 해도 Pararell 특성상 Race Condition 이 발생할 수 있기 때문에, Condition으로만 이루어진 Monitor 와 Execution 으로만 이루어진 Monitor 두 브랜치로 분리해서 각각 Sequence 의 자식으로 추가해 주어 해결하는 방법이 있습니다. 

public class Monitor : Pararell
{
    public void AddCondition(Condition condition) => _children.Insert(0, condition);
}

 

- Condition

Condition 은 일반적으로 if 문의 기능을 하는 행동입니다. 그래서 bool 값을 반환하는 대리자를 구현하고있습니다. 

public class Condition : Behavior
{
    public Behavior Child {get; set;}
    private event Func<bool> _condition;
    
    public Condition(Func<bool> condition)
    {
    	_condition = condition;
    }
    
    public override Status Invoke(out Behavior leaf)
    {
    	if (_condition.Invoke())
            return Child.Invoke(out leaf);
        else
            return Status.Failure;
    }
}

 

- Execution

Execution 은 단말노드로 위치하여 동작을 실행합니다. 그래서 자식없이 동작실행 함수만 구현하고있습니다.

public class Execution : Behavior
{
    private event Func<Status> _execute;

    public Execution(Func<Status> execute)
    {
        _execute = execute;
    }

    public override Invoke(out Behavior leaf)
    {
        leaf = this;
        return _execute.Invoke();
    }
}

 

- Decorator

Decorator 는 반환값을 꾸며주기만 하는 행동이기 때문에, 자식의 반환값에 추가 처리를 한 후 반환하도록 추상화 해놓습니다.

public abstract class Decorator : Behavior
{
    public Behavior Child {get; set;}
    
    public override Status Invoke(out Behavior leaf)
    {
        return _decorate.Invoke(Child.Invoke(out leaf));
    }
    
    public abstract Status Decorate(Status status, out Behavior leaf);
}

 

 

Decorate 함수만 구현해주면 원하는 Decorator 를 만들 수 있습니다. 

실패하지 않을 경우 특정 횟수만큼 반복하는 반복 노드를 만들기위해서는 다음예시처럼 할 수 있습니다.

public class Repeat : Decorate
{
    private int _count;
    
    public Repeat(int count)
    {
        _count = count;
    }
    
    public override Decorate(Status status, out Behavior leaf)
    {
    	if (status == Status.Failure) 
        	return Status.Failure;
    
    	int count = _count - 1;
        while(true)
        {
            if (Child.Invoke(out leaf) == failure)
            	return Status.Failure;
            
            count--;
            
            if (count <= 0)
            	return Status.Success;
        }
    }
}

 

- BehaviorTree

위의 Behavior 들로 구성할 Tree 에 대한 클래스입니다. BehaviorTree 는 DFS 를 시작할 Root , 탐색 실행 단위인 Tick()과 자식노드들을 빌드하기위한 StartBuild() 외 관련 Behavior 노드 체이닝 함수들로 구성할 수 있습니다. 

체이닝을 위해서 현재 빌드중인 위치의 Behavior 정보, Composite 노드 스택을 구현했고, 자식으로 추가하기위한 AttachAsChild(),  빌드중인 Composite 를 빠져나오기위한 ExitCurrentComposite() 이 있으며, Execute() 는 추가시 바로 상단의 Composite 로 current 를 옮깁니다. Composite 가 존재하지 않은 상태에서 Execute() 를 추가하면 빌드가 끝나게됩니다. 간단한 예시일 뿐이기 때문에 모든 Behavior 들에 대해 구현 해 놓지는 않았습니다.

public class BehaviorTree
{
    private Root _root;
    public void Tick()
    {
        _root.Invoke();
    }
    
    // building
    private Stack<Composite> _compositeStack;
    private Behavior _current;
        
    public BehaviorTree StartBuild()
    {
        _current = _root;
        return this;
    }  
    
    public BehaviorTree Sequence()
    {
        Sequence sequence = new Sequence();
        AttachAsChild(_current, sequence);
        _compositeStack.Push(sequence);
        _current = sequence;
        return this;
    }
    
    public BehaviorTree Selector()
    {
        Selector selector = new Selector();
        AttachAsChild(_current, selector);
        _compositeStack.Push(selector);
        _current = selector;
        return this;
    }
    
    public BehaviorTree Condition(Func<bool> pred)
    {
        Condition condition  = new Condition(pred)
        AttackAsChild(_current, condition);
        _current = condition;
        return this;
    }
    
    public BehaviorTree Execution(Func<Status> execute)
    {
        Execution execution = new Execution(execute);
        AttackAsChild(_current, execution);
        
        if (_compositeStack.Count > 0)
        	_current = _compositeStack.Peek();
        else
        	_current = _root;
            
        return this;
    }
    
    private void AttachAsChild(Behavior parent, Behavior child)
    {
        if (parent is Composite)
            (parent as Composite).AddChild(child);
        else
            (parent as IChild).Child = child;
    }
    
    private BehaviorTree ExitCurrentComposite()
    {
        if (_compositeStack.Count > 1)
        {
            _compositeStack.Pop();
            _current = _compositeStack.Peek();
        }
        else
        {
            _current = _root;
        }
        return this;
    }
}

 

- BehaviorTree 빌드 예시 

위 BehaviorTree 클래스 예시처럼 함수들을 체이닝으로 구현했다면 트리를 아래와 같이 구성할 수 있습니다.

(조건 및 실행 의 익명함수 등에는 예시용으로 간단하게만 표현해두었습니다)

public class Program
{
    private static void main()
    {
        BehaviorTree bt = new BehaviorTree();
        bt.StartBuild()
        	.Selector()
                .Condition(() => false)
            	.Sequence()
	            	.Sequence()
	                	.Condition(() => true)
	                    	.Execution((status) => Status.Success)
	                	.Execution((status) => Status.Failure)
	                .ExitCurrentComposite()
	             	.Execution((status) => Console.WriteLine(Hi))
	                .Execution((status) => Console.WriteLine(Hello))
    	        .ExitCurrentComposite()
                .Condition(() => false || true)
            .ExitCurrentComposite();
    }
}

 

간단하게 BehaviorTree 를 구현해보았는데요,  매번 DFS 탐색을 해야하기 때문에 분명히 잘 짜여진 FSM 보다 성능면에서는 떨어질 수 밖에 없습니다만, 확장성이 높고 의존성도 낮기때문에 typo 가능성을 줄일 수 있어 성능면에서 크게 문제가되지 않는다면 FSM 보다 훨씬 좋은 대안이 될 수 있습니다. 또한 BehaviorTree 는 노드끼리 연결하는 특성상 VisualScripting 할 수 있는 형태로 만들어 놓았을 때, 가독성도 높이고 기획자와 프로그래머 사이에 소통하는데에 큰 이점을 가질 수 있습니다.