unity 2d a-star, cellular-automata algorithm
Unity로 만든 동굴형 맵 생성 + A* 추적 시스템 구현기
들어가며
github project 사이트는 아래에 링크했습니다.
이번 프로젝트는 단순히 맵을 수동 배치하는 방식이 아니라, 셀룰러 오토마타(Cellular Automata) 를 이용해 동굴처럼 보이는 2D 맵을 자동 생성하고, 적 캐릭터가 A* 알고리즘을 통해 플레이어를 추적하도록 구성한 실험형 프로젝트다.
겉으로 보면 “랜덤 맵 + 적 추적” 정도로 보일 수 있지만, 내부적으로는 다음 두 가지 알고리즘 축이 핵심이다.
- 셀룰러 오토마타 기반 맵 생성
- A* 기반 실시간 경로 탐색
이 글에서는 구현 디테일보다는, 프로젝트를 구성하는 알고리즘의 의도와 동작 방식 위주로 정리해보려 한다.
프로젝트 핵심 구조
이 프로젝트의 흐름은 대략 아래와 같다.
- 50x50 격자 맵을 만든다.
- 각 셀을 벽 또는 빈 공간으로 랜덤 초기화한다.
- 셀룰러 오토마타 규칙으로 맵을 한 번 다듬어 동굴 형태를 만든다.
- 생성된 타일 맵 위에 계단, 플레이어, 적 스폰 위치를 배치한다.
- 적은 플레이어가 감지 범위 안에 들어오면 A*를 수행하여 최단 경로를 구한다.
- 계산된 경로의 다음 노드로 이동하면서 플레이어를 추적한다.
즉, 맵 생성 알고리즘과 길찾기 알고리즘이 서로 연결되는 구조다.
1. 셀룰러 오토마타 기반 동굴형 맵 생성
왜 셀룰러 오토마타를 사용했는가
동굴형 맵은 완전히 규칙적이면 인공적인 느낌이 강하고, 반대로 완전 랜덤이면 플레이가 불가능한 수준으로 난잡해질 수 있다.
셀룰러 오토마타는 이 두 문제의 중간 지점을 잘 잡아준다.
- 시작은 랜덤하게 생성할 수 있고
- 이후 이웃 셀의 상태를 기준으로 반복 보정하면
- 자연스럽게 덩어리진 벽과 통로가 형성된다
즉, “랜덤성은 유지하되, 사람이 보기엔 그럴듯한 지형” 을 만드는 데 적합하다.
맵 데이터 표현
맵은 2차원 정수 배열로 관리된다.
public int[,] Map;
각 셀의 의미는 단순하다.
1: 벽0: 빈 공간
이 단순한 표현 덕분에 이후 타일 생성, 충돌 판정, 스폰 위치 탐색, 경로 탐색까지 모두 같은 기준으로 연결할 수 있다.
1-1. 랜덤 초기화
초기 맵은 RandomFillMap() 에서 생성된다.
핵심 아이디어는 다음과 같다.
- 맵 바깥 테두리는 반드시 벽으로 고정
- 내부는 지정된 확률(
PercentAreWalls)에 따라 벽 또는 빈 공간으로 설정 - 중앙 한 줄은 빈 공간으로 강제 설정
의사코드로 표현하면 다음과 같다.
for each cell (x, y):
if border:
map[x, y] = wall
else if y == middleRow:
map[x, y] = empty
else:
map[x, y] = random(percentWall)
이 설계의 의미
1) 테두리를 벽으로 고정
맵 바깥이 비어 있으면 경계 처리와 충돌 판정이 복잡해진다. 테두리를 벽으로 고정하면 맵이 안정적으로 닫힌 구조가 된다.
2) 내부는 확률적으로 벽 생성
40% 내외 확률로 벽을 뿌리면, 이후 셀룰러 오토마타 규칙이 작동했을 때 벽 덩어리와 통로가 자연스럽게 형성된다.
3) 중앙 행을 비워둠
이 부분은 꽤 흥미로운 장치다. 완전 랜덤으로 시작하면 맵이 지나치게 막혀버릴 수 있는데, 중앙 라인을 비워두면 최소한 하나의 가로 통로 축이 형성될 가능성이 커진다. 즉, 맵의 단절을 완화하는 안전장치 역할을 한다.
1-2. 이웃 벽 개수 계산
셀룰러 오토마타의 핵심은 “내 주변에 벽이 몇 개 있는가”이다.
이 프로젝트에서는 GetAdjacentWalls(x, y, 1, 1) 를 통해 주변 8칸을 검사한다.
for ny from y-1 to y+1:
for nx from x-1 to x+1:
if (nx, ny) is not (x, y):
if wall:
count++
여기서 중요한 특징은 맵 밖은 벽으로 취급한다는 점이다.
bool IsWall(int x, int y)
{
if (IsOutOfBounds(x, y))
return true;
...
}
왜 맵 밖을 벽으로 보는가
이 처리를 하지 않으면 가장자리 셀은 주변 이웃 수가 부족해서 비정상적으로 빈 공간이 되기 쉽다. 반대로 맵 밖을 벽으로 간주하면, 외곽이 더 안정적으로 막히고 동굴 외곽 형태가 유지된다.
이런 경계 처리 방식은 셀룰러 오토마타 기반 맵 생성에서 자주 쓰이는 테크닉이다.
1-3. 셀 상태 갱신 규칙
실제 동굴 형태를 만드는 규칙은 PlaceWallLogic() 에 구현되어 있다.
규칙은 다음과 같이 해석할 수 있다.
현재 셀이 벽일 때
- 주변 벽 수가 4개 이상이면 벽 유지
- 주변 벽 수가 2개 미만이면 빈 공간으로 변경
현재 셀이 빈 공간일 때
- 주변 벽 수가 5개 이상이면 벽으로 변경
이를 정리하면 다음과 같다.
if current is wall:
if adjacentWalls >= 4: stay wall
else if adjacentWalls < 2: become empty
else:
if adjacentWalls >= 5: become wall
else: stay empty
이 규칙이 만드는 효과
벽 덩어리는 더 단단해진다
주변에 벽이 많으면 해당 셀도 벽으로 유지되므로 작은 틈이 메워진다.
외딴 벽은 제거된다
혼자 떨어진 벽은 주변 벽 수가 적기 때문에 사라진다.
빈 공간도 너무 넓게 퍼지지 않는다
주변이 벽으로 둘러싸인 빈 공간은 다시 벽으로 바뀌므로, 결과적으로 맵은 “들쭉날쭉한 랜덤 노이즈”에서 “덩어리진 동굴 구조”로 수렴한다.
1-4. 맵을 한 번만 다듬는 구조
보통 셀룰러 오토마타는 여러 세대를 반복 적용하는 경우가 많다. 그런데 이 프로젝트는 MakeCaverns() 호출을 보면 전체 맵을 순회하며 한 번 보정하는 구조에 가깝다.
for row ...
for column ...
Map[column, row] = PlaceWallLogic(column, row);
장점
- 구현이 단순하다
- 생성 속도가 빠르다
- 과도하게 맵이 뭉개지지 않는다
아쉬운 점
- 세대 반복이 적으면 맵 품질 편차가 커질 수 있다
- 좁은 통로, 고립 구역, 끊긴 공간이 남을 수 있다
즉, 현재 구조는 실험용/학습용으로는 충분히 직관적이지만, 완성도를 더 높이려면 다음과 같은 후처리를 붙일 수 있다.
- 3~5회 반복 보정
- flood fill로 가장 큰 연결 영역만 남기기
- 시작점과 목표점 사이 연결성 검사
- 고립된 작은 방 제거
1-5. 스폰 위치 탐색 방식
맵 생성 후에는 계단, 플레이어, 적을 배치해야 한다. 이 프로젝트는 MapGCR2x2() 를 통해 특정 크기 영역이 비어 있는지 검사한 뒤 스폰 위치를 정한다.
핵심 아이디어는 다음과 같다.
- 랜덤 좌표를 뽑는다.
- 해당 위치 주변
S x S영역을 검사한다. - 전부 빈 공간이면 배치한다.
- 아니면 다시 랜덤 시도한다.
즉, 이것은 일종의 빈 영역 샘플링(empty region sampling) 이다.
왜 중요한가
플레이어나 계단이 벽 위에 생성되면 게임 진행이 불가능해진다. 따라서 맵 생성만큼이나 “안전한 스폰 위치 찾기”도 중요하다.
이 프로젝트는 복잡한 공간 분할 없이, 랜덤 시도 + 주변 영역 검사 방식으로 이를 해결한다.
단순하지만 50x50 정도 크기에서는 충분히 실용적이다.
2. A* 알고리즘 기반 적 추적
셀룰러 오토마타가 맵의 형태를 만든다면, 실제 게임 플레이의 긴장감은 적의 추적 로직에서 나온다.
이 프로젝트의 적은 플레이어를 감지하면 A* 알고리즘을 실행해 경로를 계산한다.
2-1. 노드 구조
경로 탐색용 노드는 다음 정보를 가진다.
isWall: 해당 칸이 벽인지x, y: 좌표G: 시작점에서 현재 노드까지의 실제 이동 비용H: 현재 노드에서 목표까지의 휴리스틱 비용F = G + H: 총 평가값ParentNode: 경로 복원용 부모 노드
이는 A*의 전형적인 노드 구성이다.
public int F { get { return G + H; } }
의미 정리
G는 지금까지 얼마나 돌아왔는가H는 앞으로 얼마나 남았다고 추정하는가F는 둘을 합친 우선순위 값
즉, A*는 매 순간 “지금까지 비용 + 앞으로 예상 비용” 이 가장 좋은 노드를 선택해 탐색한다.
2-2. 탐색 격자 생성
적은 탐색을 시작할 때 먼저 현재 공간을 노드 배열로 변환한다.
NodeArray = new Node[sizeX, sizeY];
각 칸이 벽인지 여부는 Physics2D.OverlapCircleAll() 을 통해 검사한다.
foreach (Collider2D col in Physics2D.OverlapCircleAll(...))
if (col.gameObject.layer == LayerMask.NameToLayer("Wall"))
isWall = true;
이 방식의 특징
맵 데이터를 그대로 참조하는 대신, 실제 물리 충돌 정보로부터 탐색용 그리드를 다시 생성한다.
이 방식은 다음 장점이 있다.
- 씬에 실제로 존재하는 장애물을 기준으로 탐색 가능
- 타일맵 외의 오브젝트도 벽 판정에 포함 가능
- 경로 탐색과 렌더링/충돌 시스템이 자연스럽게 연결됨
반면 단점도 있다.
- 경로 탐색을 실행할 때마다 물리 쿼리를 반복하므로 비용이 크다
- 적 수가 많아지면 성능 저하가 빠르게 발생한다
즉, 소규모 프로젝트에는 직관적이지만, 대규모로 확장하려면 캐싱 또는 별도 내비게이션 그리드가 필요하다.
2-3. Open List / Closed List
A*의 기본 구조도 정석적으로 구현되어 있다.
- OpenList : 앞으로 탐색할 후보 노드
- ClosedList : 이미 검사한 노드
시작 시점에는 시작 노드만 OpenList에 들어간다.
OpenList = new List<Node>() { StartNode };
ClosedList = new List<Node>();
탐색 루프는 아래와 같다.
- OpenList에서 가장 좋은 노드를 고른다.
- 그 노드를 OpenList에서 제거하고 ClosedList에 넣는다.
- 목표 노드면 탐색 종료
- 아니면 이웃 노드를 검사해서 OpenList에 추가한다.
이것이 A*의 핵심 반복 구조다.
2-4. 현재 노드 선택 기준
현재 노드는 OpenList 중 가장 우선순위가 높은 노드로 선택된다.
if (OpenList[i].F <= CurNode.F && OpenList[i].H < CurNode.H)
CurNode = OpenList[i];
즉,
- 기본적으로
F가 작은 노드를 우선 F가 같으면H가 더 작은 노드를 우선
이 tie-break 방식은 목표 방향으로 좀 더 공격적으로 전진하게 만드는 효과가 있다.
2-5. 이동 비용 설계
이 프로젝트는 직선 이동과 대각선 이동의 비용을 다르게 둔다.
- 직선 이동:
10 - 대각선 이동:
14
int MoveCost = CurNode.G + (straight ? 10 : 14);
이 값은 흔히 쓰는 근사값이다.
- 직선 거리 1칸 = 1.0 → 비용 10
- 대각선 거리 1칸 = 1.414… → 비용 14
즉, 정수 연산만으로 유클리드 거리 느낌을 어느 정도 반영할 수 있다.
2-6. 휴리스틱 함수
휴리스틱 H 는 맨해튼 거리 기반으로 계산된다.
NeighborNode.H = (Mathf.Abs(NeighborNode.x - TargetNode.x) + Mathf.Abs(NeighborNode.y - TargetNode.y)) * 10;
즉,
H = (|dx| + |dy|) * 10
해석
맨해튼 거리는 격자 기반 탐색에서 가장 기본적인 휴리스틱이다. 목표 지점까지 가로/세로로 몇 칸 남았는지를 빠르게 추정할 수 있다.
주의할 점
이 프로젝트는 대각선 이동을 허용할 수 있으므로, 이 경우에는 맨해튼보다 Octile Distance 같은 휴리스틱이 더 잘 맞는다.
예를 들어:
H = 14 * min(dx, dy) + 10 * (max(dx, dy) - min(dx, dy))
현재 구현도 동작은 하지만, 대각선 허용 상황에서는 휴리스틱이 최적에 덜 가깝게 작동할 수 있다.
2-7. 대각선 이동과 코너 통과 제어
이 프로젝트에서 특히 좋은 부분은 대각선 이동 옵션을 단순 허용하는 데 그치지 않고, 코너 뚫기 문제를 제어하려 했다는 점이다.
관련 옵션은 다음 두 가지다.
allowDiagonaldontCrossCorner
이웃 노드를 추가할 때,
- 양쪽 직교 방향이 모두 벽이면 대각선 진입 금지
- 또는 옵션에 따라 한쪽이라도 막혀 있으면 대각선 진입 금지
이런 검사를 수행한다.
왜 중요한가
격자 기반 경로 탐색에서 대각선 이동을 허용하면, 실제로는 통과할 수 없는 벽 모서리를 비집고 지나가는 문제가 생긴다. 이를 corner cutting 문제라고 한다.
현재 구현은 그 문제를 의식하고 있으며, 게임 플레이상 더 자연스러운 이동을 만들 수 있다.
2-8. 경로 복원
목표 노드에 도달하면 탐색이 끝나고, 부모 노드를 역추적해서 최종 경로를 만든다.
Node TargetCurNode = TargetNode;
while (TargetCurNode != StartNode)
{
FinalNodeList.Add(TargetCurNode);
TargetCurNode = TargetCurNode.ParentNode;
}
FinalNodeList.Add(StartNode);
FinalNodeList.Reverse();
이 과정은 매우 전형적인 A* 경로 복원 방식이다.
- 탐색 중에는 각 노드가 “어디서 왔는지”만 기억한다.
- 도착 후에는 목표에서 시작까지 거꾸로 따라간다.
- 마지막에 뒤집으면 실제 이동 순서가 된다.
알고리즘적으로도 깔끔하고, 구현 난이도도 낮다.
2-9. 실제 이동 방식
경로가 만들어지면 적은 전체 경로를 한 번에 따라가는 것이 아니라, 다음 노드 한 칸씩 이동한다.
Vector2 FinalNodePos = new Vector2(FinalNodeList[1].x, FinalNodeList[1].y);
transform.position = Vector3.MoveTowards(..., FinalNodePos, 0.07f);
도착하면 첫 노드를 제거하고 다음 노드로 간다.
if ((Vector2)transform.position == FinalNodePos)
FinalNodeList.RemoveAt(0);
이 구조는 간단하지만, 현재 구현에서는 매 프레임 PathFinding() 을 다시 호출하므로 연산량이 꽤 많다.
3. 알고리즘 관점에서 본 이 프로젝트의 장점
1) 학습용으로 구조가 명확하다
- 맵 생성: 셀룰러 오토마타
- 이동 AI: A*
서로 다른 두 알고리즘이 한 프로젝트 안에서 유기적으로 이어진다. 그래서 단순한 예제보다 훨씬 교육 효과가 좋다.
2) 데이터 흐름이 직관적이다
격자 맵 → 타일 배치 → 장애물 판정 → 경로 탐색이라는 연결이 명확하다. 알고리즘이 실제 게임 시스템으로 이어지는 흐름을 이해하기 좋다.
3) 옵션화 포인트가 보인다
- 벽 비율 조정
- 대각선 허용 여부
- 코너 통과 허용 여부
- 스폰 영역 크기
이런 파라미터들이 알고리즘 결과에 어떤 영향을 주는지 실험하기 좋다.
4. 개선해볼 수 있는 알고리즘 포인트
4-1. 셀룰러 오토마타 반복 횟수 늘리기
현재는 한 번 보정하는 수준이어서 맵 품질 편차가 있다. 3~5회 정도 반복하면 더 안정적인 동굴 구조를 얻을 수 있다.
4-2. 연결성 보장
셀룰러 오토마타만으로는 플레이 가능한 맵이 항상 보장되지 않는다. flood fill 또는 BFS를 이용해 가장 큰 연결 영역만 남기면 맵 완성도가 훨씬 올라간다.
4-3. A* 성능 개선
현재는 매번 OpenList 선형 탐색으로 최적 노드를 찾는다. 이를 우선순위 큐(최소 힙)로 바꾸면 성능이 크게 좋아진다.
현재: O(n)으로 최적 노드 선택
개선: O(log n)으로 최적 노드 선택
4-4. 물리 쿼리 캐싱
Physics2D.OverlapCircleAll() 을 경로 탐색 때마다 전부 다시 수행하는 구조는 비용이 크다. 맵이 변하지 않는다면 벽 정보를 한 번만 추출해서 재사용하는 편이 낫다.
4-5. 휴리스틱 개선
대각선 이동을 허용한다면 맨해튼 거리보다 Octile Distance가 더 적합하다.
4-6. 재탐색 주기 조정
플레이어가 조금 움직였다고 매 프레임 전체 경로를 다시 계산할 필요는 없다. 예를 들면 다음처럼 줄일 수 있다.
- 0.2초마다 재탐색
- 목표가 일정 거리 이상 변했을 때만 재탐색
- 기존 경로가 막혔을 때만 재탐색
이렇게 하면 적 수가 많아져도 훨씬 안정적이다.
5. 이 프로젝트를 통해 느낀 점
이 프로젝트의 가장 좋은 점은, 흔히 따로 배우는 두 주제인 절차적 생성(Procedural Generation) 과 경로 탐색(Pathfinding) 이 하나의 플레이 흐름 안에서 연결된다는 점이다.
맵을 랜덤하게 만든다고 끝이 아니라, 그 랜덤 맵 위에서 적이 실제로 플레이어를 따라올 수 있어야 하고, 그 과정에서 장애물과 공간 구조가 길찾기 난이도에 직접 영향을 준다.
즉, 이 프로젝트는 단순한 예제를 넘어서,
- 맵 생성 알고리즘이 게임 플레이를 어떻게 바꾸는지
- 경로 탐색이 맵 구조에 얼마나 민감한지
- 랜덤성과 플레이 가능성 사이의 균형이 왜 중요한지
를 직접 확인할 수 있는 좋은 구조였다.
마무리
정리하자면 이 프로젝트의 핵심은 다음과 같다.
- 셀룰러 오토마타로 자연스러운 동굴형 타일 맵을 생성한다.
- A* 알고리즘으로 적이 플레이어까지의 경로를 탐색한다.
- 두 알고리즘이 결합되면서, 매번 다른 지형 위에서 추적 플레이가 이루어진다.
아직 개선 여지는 많다. 하지만 학습용, 포트폴리오용, 혹은 알고리즘 실험용 프로젝트로 보면 꽤 좋은 출발점이다. 특히 “맵 생성”과 “AI 이동”을 따로 보지 않고 하나의 시스템으로 연결해봤다는 점에서 의미가 있다.
다음 단계로 확장한다면 아래 주제를 이어서 실험해보고 싶다.
- 연결 영역 보정이 포함된 고품질 동굴 생성
- 힙 기반 A* 최적화
- 여러 적이 동시에 움직이는 군집 추적
- FOV(시야각)와 탐지 반경을 포함한 더 정교한 적 AI
- 타일 비용(weight)을 도입한 지형별 경로 탐색
한 줄 요약
이 프로젝트는 셀룰러 오토마타로 맵의 형태를 만들고, A*로 그 공간 위의 추적 행동을 완성한, 알고리즘 중심의 2D 게임 실험 프로젝트다.
Leave a comment