전체 글 (114)

01
28

 

아래 공식 문서를 참고했습니다.

https://docs.unity3d.com/Packages/com.unity.physics@1.3/manual/collision-queries.html

 

Collision queries | Unity Physics | 1.3.9

Collision queries Collision queries (also known as spatial queries) are one of the most important features of any physics engine and often drive a significant amount of game logic. Unity Physics has a powerful collision query system which supports queries

docs.unity3d.com

 

Unity에서 물리 시스템은 게임 개발의 핵심 요소입니다.

오늘은 Unity의 물리 시스템 중에서 충돌 쿼리와 콜라이더 시스템에 대해 자세히 알아보겠습니다.

 

 

1. Unity 물리 시스템 개요

Unity의 물리 시스템은 크게 두 가지 방식으로 충돌을 처리합니다:

  • 콜라이더 (Collider) 시스템
  • 물리 쿼리 (Physics Query) 시스템

 

1.1 콜라이더 시스템

public class ColliderExample : MonoBehaviour
{
    void OnCollisionEnter(Collision collision)
    {
        Debug.Log("물체와 충돌했습니다!");
    }

    void OnTriggerEnter(Collider other)
    {
        Debug.Log("트리거 영역에 진입했습니다!");
    }
}

콜라이더는 게임 오브젝트에 물리적 형태를 부여하는 컴포넌트입니다. 

  • 자동 충돌 감지
  • Unity 물리 엔진과 통합
  • 지속적인 충돌 체크
  • Rigidbody와 함께 사용 시 물리 시뮬레이션 가능

 

1.2 물리 쿼리 시스템

public class PhysicsQueryExample : MonoBehaviour
{
    void Update()
    {
        // 레이캐스트
        RaycastHit hit;
        if (Physics.Raycast(transform.position, transform.forward, out hit))
        {
            Debug.Log($"레이가 {hit.collider.name}와 충돌!");
        }

        // 구체 캐스트
        Collider[] nearbyObjects = Physics.OverlapSphere(transform.position, 5f);
        foreach (var obj in nearbyObjects)
        {
            Debug.Log($"근처에 있는 오브젝트: {obj.name}");
        }
    }
}

물리 쿼리는 필요할 때 수동으로 수행하는 충돌 검사입니다. 

  • 능동적인 충돌 검사
  • 다양한 형태의 쿼리 지원 (Ray, Sphere, Box 등)
  • 레이어 마스크를 통한 필터링
  • 일회성 검사

 

쿼리에는 대표적으로 3가지가 있습니다.

 

레이캐스트 (Ray cast)

시작점, 끝점, 필터를 입력으로 사용
방향이 있는 선분의 모든 교차점을 찾습니다.


콜라이더 캐스트 (Collider cast)

콜라이더, 시작점, 끝점, 콜라이더 스케일을 입력으로 사용
주어진 경로를 따라 콜라이더를 이동시켜 충돌 검사


거리 쿼리 (Distance query)

포인트 거리 쿼리와 콜라이더 거리 쿼리로 구분
지정된 최대 반경 내의 가장 가까운 지점을 찾음

 

2. 성능 비교 분석

2.1 콜라이더 시스템 성능

public class ColliderPerformance : MonoBehaviour
{
    void Start()
    {
        // 1. 콜라이더 수에 따른 검사 횟수
        // N개의 콜라이더 = N(N-1)/2 회의 검사
        // 10개: 45회
        // 100개: 4,950회
        // 1000개: 499,500회
    }

    void Example()
    {
        // 2. 콜라이더 타입별 성능 비교
        // 단순한 순서: Sphere > Box > Capsule > Mesh
        SphereCollider sphere;    // 가장 가벼움
        BoxCollider box;          // 중간
        CapsuleCollider capsule;  // 중간
        MeshCollider mesh;        // 가장 무거움
    }
}

2.2 물리 쿼리 성능

public class QueryPerformance : MonoBehaviour
{
    [SerializeField] private LayerMask targetLayer;
    private float queryInterval = 0.1f;
    private float nextQueryTime;

    void Update()
    {
        // 최적화된 쿼리 사용
        if (Time.time >= nextQueryTime)
        {
            Physics.Raycast(transform.position, transform.forward, out hit, 100f, targetLayer);
            nextQueryTime = Time.time + queryInterval;
        }
    }
}

 

 

3. 실제 게임플레이 적용 가이드

3.1 이동 및 물리 상호작용

public class PlayerController : MonoBehaviour
{
    private CharacterController controller;
    private float groundCheckDistance = 0.2f;

    void Update()
    {
        // 이동 처리
        Vector3 moveDirection = new Vector3(Input.GetAxis("Horizontal"), 0, Input.GetAxis("Vertical"));
        controller.Move(moveDirection * speed * Time.deltaTime);

        // 지면 체크
        bool isGrounded = Physics.Raycast(transform.position, Vector3.down, groundCheckDistance);

        // 점프 처리
        if (isGrounded && Input.GetButtonDown("Jump"))
        {
            // 점프 로직
        }
    }
}

3.2 전투 시스템

public class CombatSystem : MonoBehaviour
{
    [SerializeField] private float attackRadius = 2f;
    [SerializeField] private LayerMask enemyLayer;

    void ProcessMeleeAttack()
    {
        // 근접 공격 판정
        Collider[] hits = Physics.OverlapSphere(
            transform.position,
            attackRadius,
            enemyLayer
        );

        foreach (var hit in hits)
        {
            var enemy = hit.GetComponent<Enemy>();
            if (enemy != null)
            {
                enemy.TakeDamage(attackDamage);
            }
        }
    }

    void ProcessRangedAttack()
    {
        // 원거리 공격 판정
        RaycastHit hit;
        if (Physics.Raycast(firePoint.position, firePoint.forward, out hit))
        {
            var enemy = hit.collider.GetComponent<Enemy>();
            if (enemy != null)
            {
                enemy.TakeDamage(attackDamage);
            }
        }
    }
}

 

 

4. 최적화 전략

4.1 레이어 마스크 활용

public class OptimizedQueries : MonoBehaviour
{
    [SerializeField] private LayerMask interactableLayer;
    [SerializeField] private LayerMask groundLayer;

    void Update()
    {
        // 특정 레이어만 체크하여 성능 최적화
        Physics.Raycast(transform.position, transform.forward, out hit, 100f, interactableLayer);
        Physics.Raycast(transform.position, Vector3.down, out hit, groundCheckDistance, groundLayer);
    }
}

4.2 쿼리 빈도 최적화

public class QueryOptimization : MonoBehaviour
{
    private float checkInterval = 0.1f;
    private float nextCheckTime;

    void Update()
    {
        if (Time.time >= nextCheckTime)
        {
            PerformPhysicsChecks();
            nextCheckTime = Time.time + checkInterval;
        }
    }

    void PerformPhysicsChecks()
    {
        // 주기적으로 수행할 물리 검사들
        CheckEnemiesInRange();
        CheckInteractableObjects();
    }
}

 

Burst 컴파일된 Job 내에서 쿼리를 실행하면 최적의 성능을 얻을 수 있습니다.
복잡한 씬에서는 단일 레이캐스트도 스레드 호출로 전환하는 것이 좋습니다.

 

라고 공식문서에 되어있지만 이게 뭔지 몰랐습니다.

Unity.Collections - NativeArray 등을 위한 패키지
Unity.Jobs - Job System 사용을 위한 패키지
Unity.Burst - Burst 컴파일러 사용을 위한 패키지

이런 패키지들을 다운해야 적용가능한 기능이고

 

Job System: 멀티스레딩을 쉽게 구현
Burst: 코드를 더 빠른 네이티브 코드로 변환

둘을 함께 사용하면 고성능 병렬 처리 가능하다는 장점이 있습니다.
특히 많은 물리 연산이나 대규모 데이터 처리가 필요할 때 유용합니다

 

5. 결론

Unity의 물리 시스템은 상황에 따라 적절한 방식을 선택하는 것이 중요합니다.

  • 콜라이더
    • 기본적인 물리 충돌이 필요한 경우
    • 지속적인 충돌 감지가 필요한 경우
    • Rigidbody를 사용한 물리 시뮬레이션
  • 물리 쿼리
    • 공격 판정
    • 시야 체크
    • 특정 조건에서의 충돌 검사
    • 일회성 검사

두 시스템을 적절히 조합하여 사용하면 효율적이고 안정적인 게임 물리 시스템을 구축할 수 있습니다.

 

COMMENT
 
12
28

 

 

 

최근 쉐이더 분석해보던중 Ping-Pong 버퍼링을 알게되었습니다.

게임 개발에서 자주 사용되는 Ping-Pong 버퍼링(더블 버퍼링)에 대해 알아보겠습니다. 

 

Ping-Pong 버퍼링이란?

Ping-Pong 버퍼링은 두 개의 버퍼를 번갈아가며 읽기와 쓰기 작업을 수행하는 기법입니다.

마치 탁구(ping-pong)에서 공이 양쪽을 오가는 것처럼, 데이터가 두 버퍼 사이를 왔다갔다 하면서 처리됩니다.

작동 원리

 

1. 기본 구조

public class FboPingPong {
    private RenderTexture[] _buffer = new RenderTexture[2]; // 두 개의 버퍼
    private int _readTex = 0;  // 읽기 버퍼 인덱스
    private int _writeTex = 1; // 쓰기 버퍼 인덱스
}



2. 버퍼 스왑 과정

public void Swap() {
    int temp = _readTex;
    _readTex = _writeTex;
    _writeTex = temp;
}

 

 

예시

 

물감이 종이에 번지는 과정

프레임 1:
[버퍼 A] = 물감을 찍은 초기 상태
[버퍼 B] = 물감이 번진 상태를 계산

프레임 2:
[버퍼 B] = 이전에 번진 상태를 기준으로
[버퍼 A] = 더 번진 상태를 계산

 

유체 시뮬레이션


프레임 1:
[버퍼 A] = 현재 물 표면 상태
[버퍼 B] = 파동 계산 결과

 

프레임 2:
[버퍼 B] = 이전 파동 상태
[버퍼 A] = 새로운 파동 계산

코드 예시

수목화 효과

public class WatercolorEffect : MonoBehaviour {
    private FboPingPong _buffers;
    private Material _material;

    void Start() {
        // 버퍼 초기화
        _buffers = new FboPingPong(width, height);
    }

    void Update() {
        // 1. 현재 상태 읽기
        _material.SetTexture("_MainTex", _buffers.GetReadTex());
        
        // 2. 다음 상태 계산
        Graphics.Blit(_buffers.GetReadTex(), _buffers.GetWriteTex(), _material);
        
        // 3. 버퍼 스왑
        _buffers.Swap();
    }
}

 

장점


 데이터 일관성
   - 계산 중에 원본 데이터가 변경되지 않음
   - 안정적인 결과 보장

메모리 효율
   - 두 개의 버퍼만으로 복잡한 처리 가능
   - 추가 메모리 할당 최소화

성능 최적화
   - GPU 메모리 접근 최적화
   - 병렬 처리 가능

 

 

주의사항

초기화
   - 버퍼 생성 시 적절한 포맷과 크기 설정
   - 사용 후 메모리 해제 필수

동기화
   - 읽기/쓰기 작업의 순서 관리
   - 프레임 간 일관성 유지

메모리 관리
   - RenderTexture 사용 시 적절한 해제
   - 불필요한 버퍼 스왑 피하기

 

Ping-Pong 버퍼링은 게임 개발에서 복잡한 이미지 처리나 시뮬레이션을 구현할 때 필수적인 기법입니다.

특히 Unity의 셰이더 시스템에서 이 기법을 활용하면 효율적이고 안정적인 처리가 가능합니다.

이 기법을 잘 이해하고 활용하면, 물리 기반 시뮬레이션이나 고급 이미지 효과 등 다양한 기능을 구현할 수 있습니다.

 

관련 자료

https://www.reddit.com/r/FPGA/comments/xvmfrx/can_someone_explain_what_is_a_ping_pong_buffer/

 

From the FPGA community on Reddit

Explore this post and more from the FPGA community

www.reddit.com

https://discussions.unity.com/t/help-with-simple-ping-pong-buffer/945063

 

 

COMMENT
 
12
09

 

 

BFS = O(V + E)

파도타기

DFS = Θ(V + E)

미로탐험

 

위상정렬 Topoplogical Sort = Θ( |𝑉| + |𝐸| )

DFS로 만드는거, DAG 기준으로 정렬

 

크루스칼 알고리즘 =  O ( E log E) 

프림 알고리즘 = O(E log V) 

 

Dijkstra Algorithm =

Binary Heap을 사용하는 경우, O(E log V)
Fibonacci Heap을 사용하는 경우, O(V log V + E)

 

Bellman-Ford Algorithm = O(VE)

 

 
 

 

 

COMMENT
 
12
04

 

문제 정의

두 점 사이의 최단 경로를 찾는 방법

 

입력

방향 그래프 G = (V, E)
가중치 함수 w : E → R

 

경로의 가중치 : 경로 p = <v0, v1, …, vk>의 가중치는 경로에 있는 모든 간선의 가중치의 합으로 정의됩니다.

즉 w(p) = w(v0, v1) + w(v1 + v2) + ... + w(vk-1, vk)이런식으로 더하면 됩니다.
기존 경로의 가중치를 구할 땐 경로의 Weight w(p)는 경로 사이에 존재하는 모든 간선의 Weight의 합입니다.

 

최단 경로 가중치 : 두 정점 u와 v 사이의 최단 경로 가중치는 다음과 같이 정의됩니다.

여기서 w(p)는 경로 p의 가중치입니다.

min으로 u에서 v로 가는 모든 경로 p 중에서 가중치가 가장 작은 경로를 찾습니다.

 

만약 u에서 v로 가는 경로가 없다면, 최단 경로 가중치는 무한대(∞)로 설정됩니다. 이는 도달할 수 없는 경로를 나타냅니다.

 

u에서 v까지의 최단 경로는 w(p)=δ(u,v)를 만족하는 모든 경로 p입니다.

 

 

예시

 

해당 예시에서는 BFS로 적용된 weight가 그래프에 보여집니다.

예시에서 최단 경로가 유일하지 않을 수 있음을 보여줍니다. 즉, 여러 경로가 동일한 최단 가중치를 가질 수 있습니다.

 

한 정점에서 다른 모든 정점으로 가는 최단 경로를 고려할 때, 이 경로들이 트리 구조로 조직된다는 점을 강조합니다. 

이는 최단 경로 트리(Shortest Path Tree)라고 불립니다.

예를 들면 s에서 y로 가는 최단 경로가 s → y라면, y에서 다른 정점으로 가는 최단 경로도 s를 기준으로 연결됩니다.
이와 같은 방식으로 모든 정점이 s로부터의 최단 경로를 통해 연결되면, 최단 경로 트리가 형성됩니다.

 

최단 경로 문제들 

Single-source : 주어진 출발 정점 s에서 모든 정점 v로 가는 최단 경로를 찾는 문제입니다.
Single-destination : 주어진 목적지 정점으로 가는 최단 경로를 찾는 문제입니다.
Single-pair : 두 정점 u와 v 사이의 최단 경로를 찾는 문제입니다.
이 경우, 최악의 경우에 대해 Single-source 문제를 해결하는 것보다 더 나은 방법이 알려져 있지 않습니다.

즉, 두 정점 간의 최단 경로를 찾기 위해 Single-source 문제를 해결하는 것이 최악의 경우에도 가장 좋은 방법이라는 것입니다.

All-pairs : 모든 정점 u와 v 쌍에 대해 최단 경로를 찾는 문제입니다.

 

음수 가중치 간선

출발점에서 도달할 수 없는 음수 가중치 사이클이 있는 경우에는 문제가 없습니다. 

즉, 이 사이클에 도달할 수 없다면 최단 경로 계산에 영향을 미치지 않습니다.

 

하지만 만약 음수 가중치 사이클이 존재하고, 이 사이클을 계속 돌 수 있다면, 최단 경로의 가중치는 무한히 작아질 수 있습니다. 
즉, w(s, v) = −∞가 되어, 사이클에 포함된 모든 정점 v에 대해 최단 경로 가중치가 무한히 작아질 수 있습니다.

경로의 가중치는 경로에 있는 모든 간선의 가중치의 합이기 때문입니다.

 

일부 최단 경로 알고리즘은 그래프에 음수 가중치 간선이 없을 때만 작동합니다. 

음수 가중치 간선이 존재하면 알고리즘의 결과가 신뢰할 수 없게 될 수 있습니다.

 


 

정리 Lemma

최단 경로의 모든 부분 경로는 최단 경로라는 것입니다. 

즉, 최단 경로의 일부를 잘라내어도 여전히 최단 경로가 유지된다는 의미입니다.

 

 

증명 Proof

잘라내기 및 붙이기 기법 (Cut-and-paste technique)을 사용하여 증명합니다.

우선 경로의 가중치 총합은 다음과 같습니다.

Shortest Path(u, v) = w(p) = w( p𝑢𝑥 ) + w( p𝑥𝑦 ) + w( p𝑦𝑣 )

정점 u에서 v까지의 최단 경로를 p𝑢𝑥 (u에서 x까지), p𝑥𝑦 (x에서 y까지), p𝑦𝑣 (y에서 v까지)로 나누어 설명합니다.
만약 x에서 y까지의 경로가 p𝑥𝑦 보다 짧다고 가정하면, 전체 경로 p𝑢𝑥와 p𝑦𝑣 를 포함한 경로가 더 짧아질 수 있습니다.

즉, w( p'𝑥𝑦 ) < w( p𝑥𝑦 )

그렇게 되면 최단거리였던 w(p), 즉 기존 w( p𝑥𝑦 )를 가진 경로보다 w( p'𝑥𝑦 )를 가진 w(p')가 더 작기 때문에

w(p') < w(p)이 되므로, 이는 모순이 발생하게 됩니다.

 

 

사이클 Cycle

최단 경로는 사이클을 포함할 수 없습니다. 왜냐면 위에서 얘기했던 음수 가중치 사이클을 가질 수 없기 때문입니다.

 

양수 가중치 사이클이 존재할 경우, 해당 사이클을 생략함으로써 더 짧은 경로를 얻을 수 있습니다. 

즉, 사이클을 포함하는 경로는 최단 경로가 아닙니다.

 

제로 가중치 사이클이 있을 경우, 이를 사용할 이유가 없습니다. 

따라서 최단 경로를 찾는 과정에서 이러한 사이클은 고려하지 않는다고 가정합니다.

 

 

Single-Source 최단 경로의 Output

 

Vertex V의 모든 원소 v에 대해서 얘기합니다. 즉 v ∈ V

d[v]=δ(s, v) : 정점 s에서 정점 v까지의 최단 경로 가중치입니다.

 

초기값으로 d[v] = ∞로 설정됩니다.

알고리즘이 진행됨에 따라 이 값은 줄어들 수 있지만, 항상 d[v] ≥ δ(s, v)를 유지해야 합니다.

즉, 항상 최단 경로보다 같거나 큰 값이어야한다는겁니다.

d[v]는 "최단 경로 추정치(shortest-path estimate)"라고 불립니다.

 

 

π[v] : 정점 v에 대한 최단 경로에서의 전임자(predecessor)입니다.

만약 전임자가 없다면, π[v]=NIL로 설정됩니다.

π 배열은 최단 경로 트리를 형성합니다. 즉, 최단 경로를 나타내는 트리 구조입니다.

 

 

초기화

모든 최단 경로 알고리즘은 이 초기화 단계로 시작합니다. 이 단계에서는 그래프의 모든 정점에 대해 초기 값을 설정합니다.

 

의사 코드를 보시겠습니다.

 

각 정점 v에 대해 :

d[v]를 무한대(∞)로 설정합니다. 

이는 초기 상태에서 모든 정점까지의 최단 경로 가중치가 알려지지 않음을 의미합니다.
π[v]를 NIL로 설정합니다. 이는 해당 정점에 대한 전임자가 없음을 나타냅니다.

 

출발 정점 s에 대해서는 d[s]를 0으로 설정합니다. 이는 출발점에서 자기 자신까지의 거리는 0임을 의미합니다.

 

아래 코드에 주석을 달아봤습니다.

INIT-SINGLE-SOURCE(V, s)
    // V: 그래프의 모든 정점 집합
    // s: 출발 정점

    for each v ∈ V // 그래프의 모든 정점 v에 대해 반복
        do d[v] ← ∞ // 정점 v까지의 최단 경로 가중치를 무한대로 초기화
            π[v] ← NIL // 정점 v의 전임자를 NIL로 초기화 (전임자가 없음)

    d[s] ← 0 // 출발 정점 s에서 자기 자신까지의 거리는 0으로 설정

 

 

간선 완화 Relax

간선 (u,v)를 완화하는 과정입니다. 

이는 정점 u에서 정점 v로 가는 경로를 통해 v까지의 최단 경로 가중치를 계속 업데이트하는 과정입니다.

 

의사 코드를 보시겠습니다.

 

의사 코드에 주석 달아봤습니다.

RELAX(u, v, w)
    // u: 시작 정점
    // v: 도착 정점
    // w: 간선 (u, v)의 가중치

    if d[v] > d[u] + w(u, v) then
        // 만약 v까지의 현재 최단 경로 가중치가
        // u에서 v로 가는 경로를 통해 얻은 가중치보다 크면
        d[v] ← d[u] + w(u, v) // v까지의 최단 경로 가중치를 업데이트

        π[v] ← u // v의 전임자를 u로 설정하여 최단 경로를 추적할 수 있도록 함

 

조건: d[v]가 d[u] + w(u, v)보다 크면 d[v]를 d[u] + w(u, v)로 업데이트합니다.

이는 u를 거쳐 v로 가는 경로가 더 짧다는 것을 의미합니다.

π[v]를 u로 설정하여 v의 전임자를 u로 업데이트합니다.

 

예시로 

그래프에서 간선 (u, v)의 가중치가 10일 때, u에서 v로 가는 경로를 완화하는 과정을 보여줍니다.

d[v] = 10, source 정점에서 u정점까지 weight가 4, u에서 v로 가는 간선의 weight가 3인 상황입니다.

d[u]+w(u, v)가 더 작으면 d[v]를 업데이트합니다.

그래서 u에서 v로 갈 때 4 + 3이니 더 작아서 10 -> 7로 업데이트합니다.

이제 d[v] = 7이 되었네요.

 

하나 더 보시면 u에서 v로 갈 때 4 + 3으로 7 weight를 가지지만

기존 경로 d[v] = 6이므로 더 작습니다.

그럼 업데이트할 필요가 없으니 그대로

d[v] = 6인거죠

 

 

부록

정리해보면 Single-source 최단 경로 찾기 문제는 INIT-SINGLE-SOURCE로 초기화한 뒤에 relax edges 과정을 거칩니다.

알고리즘에 따라 순서와 각 간선을 완화하는 횟수가 다릅니다.

 

COMMENT