A* 탐색 상태 관리
우선순위 큐와 노드별 g·h·f, parent, open/closed 상태를 관리합니다. Octile·Euclidean·Manhattan·Chebyshev·Inconsistent 휴리스틱을 선택하고, 단계별 진행과 재탐색을 지원하도록 구성했습니다.
프로젝트 목록
게임 AI 탐색 프로젝트 · 2025 가을 · CS380
Pathfinding & Terrain Analysis
격자에서 A* 경로를 찾고 장애물을 고려해 경로를 다듬으며, 시야와 점유 정보를 계산한 게임 AI 과제입니다.
C++A*Priority QueueCatmull-RomTerrain Analysis
OVERVIEW
프로젝트 소개
시작점에서 목표까지의 격자 경로를 찾고 캐릭터 이동에 맞게 다듬는 과제입니다. 여러 휴리스틱과 단일 단계 탐색을 선택하면서 탐색 과정과 경로를 확인할 수 있습니다.
별도 지형 분석에서는 가시성·점유 전파·시야각·LOS를 구현했습니다. A* 코드를 요구사항과 함께 AI에 제시하고 노드 재오픈·모서리 통과·경로 보간의 오류 후보를 검토했습니다.
MY CONTRIBUTION
담당한 구현
장애물을 고려한 경로 후처리
대각 이동 때 모서리를 통과하지 않도록 이동 유효성을 확인합니다. 직선 연결 가능 여부를 검사하는 rubberbanding과 Catmull-Rom smoothing을 추가해 격자 경로를 다듬었습니다.
환경을 판단하는 지형 정보
시야와 LOS, 점유 값의 전파 등 지형 분석 함수를 구현했습니다. A* 프로젝트에서는 AI와 inconsistent heuristic의 노드 재오픈, corner cutting, smoothing의 오류 후보를 검토했습니다.
ENGINEERING STORY
짧은 경로와 실제로 이동 가능한 경로
결과
A* 탐색과 rubberbanding·smoothing 후처리 옵션을 구현하고 직선 이동·장애물 모서리 조건을 함께 점검했습니다. 과제 실행 화면과 AI를 활용한 코드 검토 기록도 남겼습니다.
문제
격자에서 찾은 경로를 단순히 직선이나 곡선으로 바꾸면 장애물 모서리를 가로지르는 문제가 생길 수 있습니다.
접근
인접 칸의 이동 조건과 직선 통과 검사를 분리했습니다. A* 결과에 rubberbanding과 smoothing을 적용하면서 장애물과 모서리 조건을 함께 점검했습니다.
DELIVERED WORK
구현 결과
- 다섯 휴리스틱과 단일 단계 탐색
- Corner-safe 이동 · Rubberbanding · Catmull-Rom smoothing
- Visibility · Occupancy · Field of View · Line of Sight
Rabin Engine은 수업 프레임워크입니다. Floyd–Warshall과 goal bounding 추가 기능은 구현 범위에 포함하지 않습니다.