게임 AI 탐색 프로젝트 · 2025 가을 · CS380

Pathfinding & Terrain Analysis

A*로 격자 경로를 찾고 장애물을 피해 경로를 다듬는 C++ 과제입니다. 시야와 점유 정보 계산을 구현하고, AI와 함께 경로 처리 코드를 검토·수정했습니다.

C++A*Priority QueueCatmull-RomTerrain Analysis

OVERVIEW

프로젝트 소개

A*로 시작점부터 목표까지 길을 찾고 캐릭터가 이동할 경로로 다듬었습니다. 휴리스틱을 바꾸거나 한 단계씩 탐색해 과정과 결과를 확인할 수 있도록 했습니다.

별도 지형 분석 과제에서는 가시성·점유 전파·시야각·LOS를 구현했습니다. A* 코드와 과제 요구사항을 AI와 함께 검토하며 노드 재탐색, 장애물 모서리 통과, 경로 보간 문제를 수정했습니다.

MY CONTRIBUTION

우선순위 큐와 노드별 g·h·f 값, parent, open/closed 상태를 관리하도록 구현했습니다. Octile·Euclidean·Manhattan·Chebyshev·Inconsistent 휴리스틱을 선택하고 한 단계씩 진행하거나 다시 탐색할 수 있습니다.

대각선 이동이 장애물 모서리를 가로지르는지 검사합니다. 직선으로 갈 수 있는 구간의 중간 지점을 줄이는 rubberbanding과 Catmull-Rom smoothing으로 격자 경로를 다듬었습니다.

시야·LOS와 점유 값 전파 등 지형 분석 함수를 작성했습니다. A*에서는 AI와 inconsistent heuristic의 노드 재탐색, corner cutting, smoothing 오류 가능성을 검토했습니다.

ENGINEERING STORY

결과

A* 탐색에 rubberbanding·smoothing 옵션을 추가하고 직선 이동과 장애물 모서리 판정을 점검했습니다. 실행 화면과 AI를 활용한 코드 검토 기록을 남겼습니다.

문제

격자 경로를 직선이나 곡선으로 바꾸면 장애물 모서리를 가로지를 수 있었습니다.

해결 과정

인접 칸으로 이동할 수 있는지와 두 지점 사이를 직선으로 지나갈 수 있는지를 따로 검사했습니다. A* 결과에 rubberbanding과 smoothing을 적용하면서 장애물과 모서리 조건을 확인했습니다.

DELIVERED WORK

수업에서 제공한 Rabin Engine에 작성한 코드입니다. Floyd–Warshall과 goal bounding 추가 기능은 구현하지 않았습니다.