알고리즘 프로젝트 - 랜덤 장애물 회피 게임 개발

Algorithm Project Unity 3D

인공지능을 활용한
랜덤 장애물 회피 게임 개발

알고리즘 프로젝트 보고서

1. 프로젝트 개요

기획 배경 및 메인 테마

목표: 학교 급식실 도달하기

급식실 도달 레이스 — 복도에서 불규칙하게 움직이는 학생들을 피해 신속하게 급식실로 도달하는 3D 러닝 게임.
쿠키런 모티브 — 스피디한 가속 주행 및 장애물 회피 메커니즘 차용.
예측 불가능성 — 실시간 횡단 경로가 바뀌는 확률 이동 NPC 장애물 설계.

1. 프로젝트 개요

인게임 그래픽 샷

질주 가속도에 비례해 카메라 3차원 화각(FOV)이 조율된 인게임 통로 씬

로우폴리 스타일 3D 학교 복도를 조형했습니다.
장애물에 피격되었을 때 라이프(하트)가 깎이며 화면이 거칠게 떨리는 Perlin Noise 카메라 피드백을 구축해 타격감을 높였습니다.

2. 시스템 설계

시스템 아키텍처 및 구동 로직

Player Control — 마우스 턴 감도 회전각 전환, 키보드 점프·슬라이드 제어.
Camera System — 속도 기반 동적 FOV 변화, Perlin Noise 진동 피드백.
NPC AI — 격자 기반 탐색 및 확률 가중치 행동 결정.
로직 흐름 — UI 오픈 시 인풋 차단 → 매 프레임 속도 계산 및 이동 → AABB 충돌 검출 → 성공/사망 분기.

3. 적용 자료구조 및 알고리즘

핵심 자료구조 및 물리 제어

상태 관리 & 충돌 검출

타이머 제어 — 상태머신(FSM) 대신 무적/디버프 주기를 float 변수로 선언하고 deltaTime 차감 업데이트 처리 (연산 최소화).
AABB 충돌 판정 — 3D 공간 상에서 정렬된 박스 오버랩 연산(BoxCollider)으로 정밀한 피격 즉시 감출 및 이벤트 전파.

의사 결정 & 경로 평활화

확률 가중치 행동 선택 — 내부 주기마다 난수를 생성하고 직진, 대기, 조향 가중치 테이블에 따라 목적 좌표 능동 변경.
선형 보간 (Vector3.Lerp) — 선정된 목표 좌표로 적이 순간이동하지 않고 부드럽게 미끄러지며 나아가도록 곡선 보행 렌더링.

4. 핵심 알고리즘

BFS 기반 장애물 회피 경로 탐색

BFS 알고리즘 채택 — 무작위 목표지 설정 시 복도 사물함이나 방 벽면에 NPC가 끼어 멈추는 오작동을 극복하기 위해 BFS 도입.
좌표계 실시간 변환 — 유니티 월드 float 좌표를 격자 정수 인덱스(Vector2Int)로 변환해 BFS 최단 경로 산출 후, 다시 월드 waypoint로 복원.
벽 충돌 차단 — 큐 노드 방문 도중 벽 인덱스 검사(bfsObstacles.Contains)를 거쳐 장애물을 자연스럽게 우회.

5. 소스코드 분석

NPC AI 및 오토스포너

// BFS 최단경로 복원 알고리즘
private void BuildBfsPath(Vector3 destination) {
    path.Clear(); pathIndex = 0;
    float cellSize = Mathf.Max(0.1f, bfsCellSize);
    Vector2Int start = WorldToCell(transform.position, cellSize);
    Vector2Int goal = WorldToCell(destination, cellSize);
    Queue<Vector2Int> queue = new Queue<Vector2Int>();
    Dictionary<Vector2Int, Vector2Int> previous = new Dictionary<Vector2Int, Vector2Int>();
    queue.Enqueue(start); previous[start] = start;

    while (queue.Count > 0) {
        Vector2Int current = queue.Dequeue();
        if (current == goal) break;
        foreach (Vector2Int dir in directions) {
            Vector2Int next = current + dir;
            if (previous.ContainsKey(next)) continue;
            previous[next] = current; queue.Enqueue(next);
        }
    }
}

// 최소 거리 유지 스포닝 알고리즘
public void SpawnBatch() {
    GameObject[] targets = GameObject.FindGameObjectsWithTag(targetTag);
    int spawned = 0;
    while (spawned < spawnCount) {
        GameObject target = targets[Random.Range(0, targets.Length)];
        Vector3 pos = GetTopPosition(target) + Vector3.up * spawnHeightOffset;
        if (IsFarEnough(pos)) {
            Instantiate(obstaclePrefabs[Random.Range(0, obstaclePrefabs.Length)], pos, Quaternion.identity);
            usedPositions.Add(pos); spawned++;
        }
    }
}

최적화 설계 핵심 요약:
- sqrMagnitude 기반 가시거리 최적화로 플레이어 근접 NPC만 BFS를 활성화하여 메모리/연산 병목 방지.
- IsFarEnough() 오토스포닝 거리 검사로 NPC 밀집 중첩 렌더링 버그 차단.

6. 소스코드 분석

플레이어 피격 및 카메라 셰이크

// 피격 데미지 및 감속 디버프 트리거
public void HitObstacle(string obstacleName) {
    if (cleared || hitCooldownTimer > 0f) return;
    hitCooldownTimer = hitCooldown; // 무적 돌입
    slowTimer = slowDuration;       // 감속 돌입
    currentSpeed = Mathf.Max(startSpeed, currentSpeed - hitSpeedLoss);
    hearts = Mathf.Max(0, hearts - 1);
    heartUI?.SetHearts(hearts, maxHearts);
    followCamera?.Shake(0.45f, hearts <= 0 ? 1.2f : 0.75f);
    if (hearts <= 0) Die(); 
}

// Perlin Noise 카메라 셰이킹 알고리즘
private Vector3 GetShakeOffset() {
    if (shakeTimer <= 0f) return Vector3.zero;
    shakeTimer -= Time.deltaTime;
    float power = shakeStrength * (shakeTimer / shakeDuration);
    float x = (Mathf.PerlinNoise(Time.time * shakeFrequency, 0.17f) - 0.5f) * 2f;
    float y = (Mathf.PerlinNoise(0.41f, Time.time * shakeFrequency) - 0.5f) * 2f;
    return transform.right * x * power + transform.up * y * power;
}

비선형 카메라 피드백:
- 임의 난수가 유발하는 눈의 피로도를 낮추기 위해, 파동이 연속되는 Mathf.PerlinNoise를 사용해 생동감 넘치고 자연스러운 진동 구현.
- 피격 시 hitCooldownTimer 가동으로 중복 연쇄 타격 버그 제거.

7. 시연 영상

인게임 실제 구동 시연

8. 실행 결과 및 분석

알고리즘 동작 결과 및 분석

자연스러운 끼어들기와 리플레이 가치

동적 코스 완성 — 확률 결정 및 LERP 보간이 맞물려, NPC가 플레이어 경로에 자연스럽게 횡단 개입하는 유기적인 긴장 구도 연출.
다회차 플레이 가치 — 리셋할 때마다 NPC들의 진행 패턴과 목표 Waypoint 탐색로가 동적 재연산되어, 루트 암기식 플레이를 원천 차단하고 긴장 유지.

메인 게임 루프 실행 플로우차트

9. 소감 및 역할 분담

수행 소감 및 역할 정리

팀원 수행 소감

유은재: 3D 배치 조형과 Unity 컴포넌트 생태계를 새롭게 깊게 경험해 볼 수 있었습니다.

황동화: 코드 상의 3D 물리 제어와 Animator 컴포넌트의 유기적 맞물림 연출 과정을 깊게 체득했습니다.

역할 분담

황동화 — 학교 3D 맵 빌드 리소스 세팅, 플레이어 물리 이동 연산 및 카메라 쉐이크 C# 구현.
유은재 — 3D 맵 빌드 디자인, NPC 가중치 행동 결정 및 BFS 알고리즘 구현, UI & 보고서 작성.

부록

AI 활용 및 저장소

인간 주도 AI 보조 도구

인풋 감지, 충돌 핸들링 초안 작성 과정과 유니티 Animator가 임의로 각도를 오버라이드 덮어쓰는 캐릭터 트랜스폼 회전 충돌 문제를 분석 디버깅하는 프로세스에서 AI의 분석력을 큰 서포터로 활용했습니다.

Unity 전체 소스 코드 저장소

GitHub Code Link

인공지능을 활용한랜덤 장애물 회피 게임 개발