유니티 C# tree(트리)

트리

트리는 그래프의 일종

노드들이 있고 노드간 선으로 연결되어있다면 그것을 그래프라고 부름

트리는 부모에서 자식으로 방향성을 가진 그래프라서 화살표 방향을 생략할수있다(어짜피 부모에서 자식으로 가는거라)

트리는 이런 순환의 구조를 가지면 안된다 순환은 그래프다

리프: 단말 노드. 자식이 없는, 맨마지막에 있다고 하여 리프(나뭇잎)이라고 부른다.

높이는 그레프의 길이

깊이는 그래프가 얼마나 갈수있는가를 나타냄

차

트리안 트리는 서브트리

그래프 : 노드들이 선으로 연결되어있는 것(A*, Nav mesh에서 활용.. 가중치를 활용했다캄)
트리 : 그래프에 제약을 걸어둔 것
   ㄴex) 방향 설정
간선 : 노드간을 잇는 선 
레벨 : 노드들이 있는 층
형제 : 부모를 공유하는 같은 레벨의 노드
높이 : 레벨간을 이어주는 간선의 개수
깊이 : 자신을 제외한 조상노드의 개수 
루트 : 최상위! 부모 
서브트리 : 큰 트리 안에서 트리의 형태를 이루는 부분 (손주포함)
리프 : 자식이 없는 자손 노드 (막내인듯)

 

자식이 하나만 있는 트리는 편향되었다고 함

제한을 걸어서 2진 트리로만들면 자식 3개이상 이거를 삭제...ㄷㄷ

정2진트리는 자식이 없거나 꽉차있는 것(2개)이다

후위는 보통 지울때 쓴다, 전위는 복사할때, 중위는 탐색할때

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace node
{
    public class Node
    {
        public int item;
        public Node left = null;
        public Node right = null;

        public Node(int item)
        {
            this.item = item;
        }
    }
    public class GameManager : MonoBehaviour
    {
        Node root = null;
        //전위순회
        void PreOrder(Node root)
        {
            if (root == null)
                return;
            Debug.Log(root.item);
            PreOrder(root.left);
            PreOrder(root.right);
        }
        //중위순회
        void inOrder(Node root)
        {
            if (root == null)
                return;
            inOrder(root.left);
            Debug.Log(root.item);
            inOrder(root.right);
        }
        //후위순회
        void PostOrder(Node root)
        {
            if (root == null)
                return;
            PostOrder(root.left);
            PostOrder(root.right);
            Debug.Log(root.item);
        }
        void Start()
        {
            root = new Node(0);
            root.left = new Node(1);
            root.right = new Node(2);
            root.left.left = new Node(3);
            root.left.right = new Node(4);
            root.right.left = new Node(5);
            root.right.right = new Node(6);

            PreOrder(root);
            inOrder(root);
            PostOrder(root);
        }
    }
}

노드 코드

바이너리 서치 트리

사용예

 

행동 트리

 

https://engineering.linecorp.com/ko/blog/behavior-tree

Behavior Tree를 알아봅시다

이렇게 설렉터가 또 있을수 있어서

리스트는  INode를 가져야한다. 그리고 하나하나 꺼내서 확인하기 위해 포이치 문 사용

using System.Collections;
using System.Collections.Generic;
using UnityEditor.UIElements;
using UnityEngine;
using System;

namespace TestCollection
{

    public interface INode
    {
        public enum State
        {
            RUN, SUCCESS, FAIL
        }
        public State Evaluate();
    }

    public class ActionNode : INode
    {
        public Func<INode.State> action = null;
        public INode.State Evaluate()
        {
            return action();
            // throw new System.NotImplementedException();
        }
    }

    public class SelectorNode : INode
    {
        List<INode> childs;
        public INode.State Evaluate()
        {
            foreach (INode child in childs)
            {
                switch (child.Evaluate())
                {
                    case INode.State.SUCCESS:
                        return INode.State.SUCCESS;
                    case INode.State.RUN:
                        return INode.State.RUN;
                }
            }
            return INode.State.FAIL;
        }
    }


    public class GameManager2 : MonoBehaviour
    {
        //행위트리
        //Behavior Tree

        ActionNode an;
        public bool isCheck = true;
        private void Start()
        {

            an = new ActionNode();
            an.action += () => {
                Debug.Log("어떠한 액션");
                if (isCheck)
                    return INode.State.SUCCESS;
                else
                    return INode.State.FAIL;
            };

            Debug.Log(an.Evaluate());
        }
    }
}

두번째 코드

using System.Collections;
using System.Collections.Generic;
using UnityEditor.UIElements;
using UnityEngine;
using System;

namespace TestCollection
{    

    public interface INode
    {
        public enum State
        {
            SUCCESS,FAIL
        }
        public State Evaluate();
    }

    public class ActionNode : INode
    {
        public Func<INode.State> action = null;
        public INode.State Evaluate()
        {
            return action();
            // throw new System.NotImplementedException();
        }
    }

    public class SelectorNode : INode
    {
        List<INode> childs;
        public INode.State Evaluate()
        {
            foreach (INode child in childs)
            {
                switch(child.Evaluate())
                {
                    case INode.State.SUCCESS:
                        return INode.State.SUCCESS;
                }
            }
            return INode.State.FAIL;
        }
    }

    public class SequenceNode : INode
    {
        List<INode> childs;
        public INode.State Evaluate()
        {
            foreach(INode child in childs)
            {
                switch(child.Evaluate())
                {
                    case INode.State.FAIL:
                        return INode.State.FAIL;
                    case INode.State.SUCCESS:
                        continue;
                }
            }
            return INode.State.SUCCESS;
        }
    }

    public class GameManager : MonoBehaviour
    {
        //행위트리
        //Behavior Tree

        ActionNode an;
        public bool isCheck = true;
        private void Start()
        {

            an = new ActionNode();
            an.action += () => { 
                Debug.Log("어떠한 액션");
                if (isCheck)
                    return INode.State.SUCCESS;
                else
                    return INode.State.FAIL;
            };

            Debug.Log(an.Evaluate());
        }
    }
}