많은 탐색 / 길찾기 알고리즘의 기본이 되는 너비탐색과 깊이탐색입니다. 

 

특히 너비탐색의 경우에는 최단경로 길찾기의 기본적인 탐색 알고리즘입니다. 앞으로 진행할 길찾기 알고리즘 포스팅을 위해 먼저 정리할 목적으로 포스팅을 합니다.

너비탐색과 깊이탐색은 탐색 방법이고, 이를 통해 다양한 길찾기 알고리즘이 파생됩니다. (다익스트라, A* 등)

 

포스팅 순서는 아래와 같습니다.

  1. 너비탐색
    • 개요
    • 장단점
    • 구현방법
    • 사용예시
  2. 깊이탐색
    • 개요
    • 장단점
    • 구현방법
    • 사용예시

 

 

1. 너비탐색 (BFS)

  • 개요
    • 시작 정점으로부터 인접한 거리순으로 주변으로 넓게 퍼지는 탐색
      • 종이에 먹물이 퍼지는 것과 같음.
  • 장단점
    • 장점
      • 로직이 단순하다.
      • 최초 발견 루트를 최단경로라고 보장할 수 있다.
      • 언제나 같은 거리 결과값을 얻을 수 있다.
    • 단점
      • 비교적 많은 저장공간이 필요하다.
  • 구현방법
    • 를 활용하여 구현 ( 선입선출 )
      • 1. 시작 노드를 현재 노드로 설정.
      • 2. 현재 노드를 탐색된 노드로 저장.
      • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드를 탐색
      • 4. 3번의 노드를 큐에 저장. / 탐색된 노드로 저장.
      • 5. 현재 노드의 주변 노드가 모두 탐색된 노드가 될 때까지 3~4 반복
      • 6. 큐에서 다음 노드를 꺼내 현재 노드로 설정. 
      • 7. 목표에 도착할 때까지 5~6 반복. (전체탐색의 경우, 큐가 빌 때까지 진행.)
  • 예시
      • 최단경로 판별에 유용
      • 길찾기의 기본으로 유용

 

2. 깊이탐색 (DFS)

  • 개요
    • 시작 정점으로부터 각 분기 / 방향 별로 깊게(완전하게) 탐색하고 다음 분기 / 방향으로 넘어가는 탐색
      • 미로찾기와 같음.
  • 장단점
    • 장점
      • 로직이 단순하다.
      • 비교적 적은 저장공간
    • 단점
      • 최초로 구해지는 길이 최단이라는 보장을 할 수 없다.
        • 최단경로 길찾기에 적합하지 않음.
      • 적절한 제한을 두지 않는다면 한쪽 분기에 과도하게 깊이 빠질 수 있음.
        • 재귀함수의 경우 stack overflow 우려 (깊이 제한 필요)
      • 탐색하는 방향 우선순위에 따라 결과가 다르게 나올 수 있다.
  • 구현방법
    • 스택 또는 재귀함수로 구현 (후입선출) 
      • 1. 시작 노드를 현재 노드로 설정.
      • 2. 현재 노드를 탐색된 노드로 저장.
      • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드 탐색 
      • 4. 3번의 노드를 스택에 저장 / 탐색된 노드로 저장.
      • 5. 현재 노드의 주변노드가 모두 탐색될 때까지 3~4 반복
      • 6. 스택에서 다음 노드 (최근에 들어간) 를 꺼내 현재 노드로 설정.
      • 7. 목표에 도착 또는 전체 순회를 할 때까지 5~6 반복. (전체 탐색의 경우 스택이 빌 때까지 진행)
  • 예시
    • 자동 미로 생성기

 

 

 

 

 

여담

  • 너비탐색과 깊이탐색의 구현방법의 차이는 사실상 큐와 스택입니다. 그 외 돌아가는 기본 로직은 비슷합니다. 
  • 앞으로 4~5 포스팅 동안 길찾기 알고리즘을 시리즈로 할 생각입니다. 최종적으로는 D* lite 알고리즘까지 가는 것이 목표이며, 이를 위해 하나씩 과정을 밟아갈 예정입니다.
    • 하여 이후 길찾기 알고리즘의 순서는 A*, LPA*, D* lite 알고리즘 순으로 포스팅 할 예정입니다.

 

* 포스팅내에 잘못된 내용이나, 문의사항 있으시면 언제든 댓글로 지적해주시면 감사하겠습니다.

 

 

 

Posted by 검은거북

Unity ECS - Hybrid 에 대한 스크립팅 및 사용방법 기록 포스팅입니다.

 

ECS에 대한 설명및 기본세팅은 이전 포스팅으로 - https://zprooo915.tistory.com/66

아래 포스팅은 Unity ECS 샘플 프로젝트의 스크립트를 기준으로 작성하였습니다.

 

이번 포스팅은 아래순서로 진행됩니다.

  1. Hybrid ECS란?
  2. 기본적인 사용방법
  3. 사용 Tip & 오류 및 해결방법

 

1. Hybrid ECS란?

  • 간단하게 기존 Unity의 컴포넌트 방식과 ECS 방식을 융합된 방법입니다.
    • Unity Editor 상에서는 기존 Unity와 동일하게 하이러키와 컴포넌트를 사용하고, 스크립트는 ECS 방식입니다.
  • ECS 방법 자체는 기존 사용자가 바로 사용하기에는 무리가 있을 정도로 에디팅 방식이 많이 바뀌지만, Hybrid 방식으로 둘을 적당히 섞음으로써 ECS 방식을 좀 더 쉽게 접근할 수 있습니다.
  • 장점
    • 진입장벽이 낮다    
    • 기존의 유니티에서 제공하는 시스템을 함께 사용할 수 있다. (ECS만 사용한다면, 새로 만들어야 할 수도 있습니다.) 
  • 단점

 

2. 기본적인 사용방법

 편의상 component - Entity - System 순으로 진행하겠습니다.

 순서는 간단한 설명 후 플레이어블 캐릭터를 예시로 드는 식으로 진행합니다. 

 

Component

 - 하나의 정의에 필요한 데이터 집합

 

  • 아래는 플레이어블 캐릭터의 playerInput 데이터의 집합(컴포넌트) 입니다. 일반 클래스 생성하듯 만듭니다.
public class PlayerInput : MonoBehaviour 
{ 
    public float2 move; 

    public bool jump; 
    public bool seat; 

    public bool attack; 
}

 

  • 그리고 밑은 캐릭터/ 몬스터 누구나 가지고 있을법한 hp에 대한 데이터 집합(컴포넌트) 입니다.
public class Health : MonoBehaviour 
{ 
    public float value;

    public bool isDead;
}

 

  • 위와 같이 하나의 정의에 필요한 데이터 집합들이 component입니다.
    • input에 관련된 요소, Health에 관련된 요소 hp값과 죽었는지 여부입니다.

 

Entity

 - 컴포넌트들의 집합

  •  위의 컴포넌트들을 조합해서 만들어집니다. 기존의 게임오브젝트와 유사하게 생각하시면 됩니다.
  •  위에서 만든 컴포넌트들을 에디터창에서 원하는 오브젝트에 붙이면 됩니다.
    • 각 오브젝트에 필요한 특성과 정의를 부여한다고 생각할 수 있겠네요.
  •  반드시 지켜야 할 것이 ECS의 관리를 받는 오브젝트를 만들려면 Game Object Entity라는 클래스도 오브젝트에 추가해야합니다. (이것을 안하면 System에서 아예 인지를 하지 못합니다.)
  • 아래는 플레이어블 캐릭터의 인스펙터 창입니다.

  • 아래는 체력만 가진 몬스터의 인스펙터 창입니다. ( PlayerInput 빼고는 위와 동일합니다.)

 

 

 System

 - Entity들의 행동로직 

  • 데이터들을 가공하는 곳으로 일반 객체지향의 method와 비슷합니다.
  • 시스템은 방식이 두가지가 있습니다.
    • 두 방식이 어떨 때 좋을지는 정확히는 잘 모르겠네요.
    • 차이점이라면 두번째는 개체수를 얻을 수 있다는 점과 개인적으로 사용했을 때는 여러 엔티티를 가져와 로직을 돌려야 할 경우 두번째 방식이 더 편하고, 하나만 사용할 경우에는 첫번째가 편하더군요.
  • 기본 템플릿

1. 

using UnityEngine; 
using Unity.Entities; 

public class ClassName : ComponentSystem 
{ 
    public struct StructName
    { 
        public ComponentClass name; 
         
    } 
    protected override void OnUpdate() 
    { 
        foreach(var entity in GetEntities<StructName>()) 
        {

            // 로직 진행
            // ex ) entity.name.property = 0;
        } 
    } 
}

 

2.

using Unity.Entities; 
using UnityEngine; 

public class ClassName : ComponentSystem 
{ 
    public struct StructName
    { 
        public readonly int Length; 
        public ComponentArray<ComponentClass > name; 
    } 
    [Inject] 
    private StructName m_data; 

    protected override void OnUpdate() 
    {         
        for(int i = 0; i < m_data.Length; i++) 
        {

            // 로직 진행
            // ex ) m_data.name[i].property = 0; 
             
        } 
    } 
}

 

  • 사용예시

  • 아래는 인풋제어 컴포넌트를 가진 엔티티들을 불러와 키맵핑을 해주는 시스템입니다.
    • 다른 컴포넌트를 가지고 있든말든 인풋제어만 있으면 다 로직이 돕니다.
using UnityEngine; 
using Unity.Entities; 

//사용자의 입력을 input component에 배정하는 시스템 
// 이동 점프 앉기 공격 등 키입력 맵핑 
public class PlayerInputSystem : ComponentSystem 
{ 
    public struct PlayerData 
    { 
        public PlayerInput input; 
         
    } 
    protected override void OnUpdate() 
    { 
        foreach(var entity in GetEntities<PlayerData>()) 
        { 
            entity.input.move.x = Input.GetAxis("Horizontal"); 

            entity.input.seat = false; 
            entity.input.jump = false; 

            if (Input.GetKey(KeyCode.DownArrow)) entity.input.seat = true; 
            if (Input.GetKey(KeyCode.UpArrow)) entity.input.jump = true; 

        } 
         
    } 
}

 

 

  • 아래는 플레이어블 캐릭터의 컴포넌트들을 가진 엔티티들을 불러와 이동시켜주는 시스템입니다.
    • 마찬가지로 PlayerData에 있는 컴포넌트를 가진 모든 엔티티를 불러옵니다.
using Unity.Entities; 
using UnityEngine; 

// 입력된 input에 맞춰 캐릭터 이동  
public class PlayerMoveSystem : ComponentSystem 
{ 
    public struct PlayerData 
    { 
        public readonly int Length; 
        public ComponentArray<PlayerInput> input; 
        public ComponentArray<Health> health; 
        public ComponentArray<Rigibody2D> rigid; 
    } 
    [Inject] 
    private PlayerData m_data; 

    protected override void OnUpdate() 
    { 
        // 병렬로 전체 캐릭터들이 모두 별도로 이동하고, 나중에 한꺼번에 적용 
        float dt = Time.deltaTime; 
        for(int i = 0; i < m_data.Length; i++) 
        { 
            m_data.rigid[i].AddForce(new Vector2(m_data.input[i].move.x * 4, 0)); 
             
        } 
    } 
}

 

  • 아래는 Health를 가진 모든 오브젝트에 대해 죽음 판별하는 시스템입니다.
    • 캐릭터와 몬스터 모두 Health를 가졌으니 모두를 대상으로 돌겠죠
using UnityEngine; 
using Unity.Entities; 

public class HealthCheckSystem : ComponentSystem 
{ 
    public struct PlayerData 
    { 
        public Health health; 
         
    } 
    protected override void OnUpdate() 
    { 
        foreach(var entity in GetEntities<PlayerData>()) 
        { 
            if(entity.health.value <=0) entity.health.isDead = true;

        } 
         
    } 
} 

 

  • 그래서 필요 기능별로 컴포넌트들을 구분지어야 나중에 시스템을 돌릴때 편해지고 직관적이게 됩니다. 오브젝트를 사용할 때도 컴포넌트만으로 제어하기 편합니다.
    • 예를들어 이 캐릭터는 무적인 특성이 있다 했을 때, 예외처리를 하는게 아니라 단지 그 캐릭터에게 Health 컴포넌트만 제거하면 Health에 관련된 모든 로직을 무시할 수 있게되죠.
    • 마찬가지로, 스킬이나 특성들도 컴포넌트만으로 제어할 수 있겠죠.

 

 

3. 사용 Tip & 오류 및 해결방법

  • 시스템 로직 도는 순서 변경하는 방법

    •  기능별로 시스템이 돌기 때문에 간혹 순서상에 문제가 발생할 수도 있습니다.
      •  물론 이런경우를 발생 안시키는게 베스트이긴 하지만, 부득이할 경우 로직 도는 순서를 변경 시킬 수 있습니다.
      • (디폴트로는 생성 순으로 진행되는 것으로 압니다.)
    • 참고 사이트 - https://docs.unity3d.com/Packages/com.unity.entities@0.0/manual/system_update_order.html
    • 방법 
// 타겟 시스템이 SystemClass 이후에 실행되도록 설정
// 같은 시스템 그룹 내에서 동작
[UpdateAfter(typeof(SystemClass))]

// 타겟 시스템이 SystemClass 이전에 실행되도록 설정
// 같은 시스템 그룹 내에서 동작.
[UpdateBefore(typeof(SystemClass))]

// 타겟 시스템을 SystemGroup에 귀속시킴.
// 디폴트로 개발자가 만든 System은 모두 SimulationSystemGroup에 속함.
[UpdateInGroup(typeof(SystemGroup))]


// 사용 예시
// PlayerInputSystem 실행 이전에 TestSystem (타켓시스템)을 실행하도록 설정.
[UpdateBefore(typeof(PlayerInputSystem))]
public class TestSystem : ComponentSystem
{
    public struct PlayerData
    {
        public PlayerInput input;
    }
    protected override void OnUpdate()
    {
        foreach (var entity in GetEntities<PlayerData>())
        {
        }
    }
}

 

  • 여러 엔티티를 하나의 시스템에서 써야할 때

    • 그냥 두개 inject 해오면 된다.
    public struct PlayerData 
    { 
        public readonly int Length; 
        public ComponentArray<PlayerInput> input; 
        public ComponentArray<Transform> transform; 

    } 
    [Inject] 
    private PlayerData p_data; 

    public struct MinimapData 
    { 
        public readonly int Length; 
        public ComponentArray<Minimap> minimap; 

    } 
    [Inject] 
    private MinimapData m_data;

 

  • Tag처럼 쓰기

    • Tag도 하나의 컴포넌트로써 사용하면 된다.
      • ex) Component로 Human클래스를 만들고 아무 내용없이 오브젝트에 붙여만 놓으면, 시스템에서 Human으로 걸러낼 수 있죠.

 

 

 

 

 

 

 

 

Posted by 검은거북

* 먼저 해당 포스트는 튜토리얼이 아닌 Firebase 사용하는 과정에서 발생한 오류 및 해결과정, TIP 중심의 글임을 알려드립니다.  

* Firebase 설명 자체가 굉장히 잘 되어있으므로 튜토리얼은 Firebase를 참고하세요. 여기서 발생한 오류/정보도 Firebase 가이드에 있으나 놓쳤을 확률이 높습니다

 

 

- Functions는 그냥 서버에 본인이 쓸 API 함수를 작성하여 업로드하는 것으로 생각하면 편안.

 - 접근할 서버의 URL = https://us-central1-프로젝트ID.cloudfunctions.net/    

 - 본인이 올린 API 함수는 위 URL을 통해 API 호출하듯 호출하면 된다. POST든 GET이든

    - ex ) https://us-central1-myproject.cloudfunctions.net/myfunc 

 

1. Functions에서의 외부 API 호출시 무시되는 현상.

 - Paypal 에 요청 API를 보냈을 때 아예 무시가 되는 경우가 발생.

 - 무료버전(spark)은 구글 외의 다른 url로 API 접근이 안된다.

    - Blaze 버전으로 업데이트 필요.

 

 

 

 

Posted by 검은거북

블로그 이미지
프로그래밍 공부 요약 및 공부하며 발생한 궁금증과 해결과정을 포스팅합니다.
검은거북

공지사항

Yesterday
Today
Total

달력

 « |  » 2025.1
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

최근에 올라온 글

최근에 달린 댓글

글 보관함