게임 개발

그냥 PS를 위해 쓸 수 있는 함수들 올리는 카테고리입니다..

<2차원 동적할당 함수>

// 2차원 배열 동적할당
int** createMatrix(int col, int row) {
	int** arr = new int* [col];
	for (int i = 0; i < col; i++) {
		arr[i] = new int[row];
		fill_n(arr[i], row, 0);
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
		}
	}

	return arr;
}

<2차원 동적 배열 해제 함수>

// 2차원 동적 배열 해제
void deleteMatrix(int** arr, int col) {
	for (int i = 0; i < col; i++)
		delete[] arr[i];
	delete[] arr;
}

<사용 예시>

// 사용 예시
#include <iostream>

int main() {
	...
    // Matrix 만들기
    int col, row;
    cin >> col >> row;
 	int** arr = createMatrix(col, row)
    ...
    
    // 다 사용 후 해제
    deleteMatrix(arr, col);
    ...
}

이번엔 Point Graph에 대해 알아보려고 한다.

나머지 Graph에 대해선 알아보았으므로, 이 포스트가 Graph에 대한 마지막 포스트이지 않나 싶다.

다음 포스트부터 해당 에셋을 어떻게하면 맛깔나게 사용할 수 있는지 알아보려고 한다.

Grid Graph에 대해 알아보기 : https://game-develop.tistory.com/1

Navmesh/Recast Graph에 대해 알아보기 : https://game-develop.tistory.com/4

1. 개요

Point Graph는 사용자가 직접 node(= waypoint)를 지정할 필요가 있을때 사용하는 방식이며, 가장 기본적인 Graph 이다.

특정 포인트 → 특정 포인트로 넘어갈 때 유용하게 사용가능한 Graph인 것 같다.

또한 다른 Graph와 함께 사용하면 많은 것들을 만들 수 있을 것 같다.(ex. 기본적으로 Navmesh 이용 + 특정 지점은 Point 이용)

대표적으로 아래와 같이 <로스트아크>라는 게임에서 g키를 통해 언덕을 오르는 등 지형을 타는 것을 예로 들 수 있다.

2. Point Graph

1) 구성

• Root : Node들이 담긴 GameObject의 Transform
• Recursive : Root의 모든 하위 Node들을 찾을 것인지 여부
• Tag : Root를 지정하지 않을때 사용하며, 대신 Tag를 통해 Node들을 찾음(※ 'Untagged'라는 tag는 인식안됨)
• Max Distance : 경로로 만들 수 있는 Node들간 최대 거리(※ 0은 Infinity를 의미하며, 모든 노드간 경로가 생성됨, 아래 그림 참고)
• Max Distance (axis aligned) : Node간 X, Y, Z 각 축에 대한 최대 거리(※ 모두 0으로 하는게 좋아보임)
• Raycast : Node간 Raycast하여 장애물이 있는지 확인 (※ 해당 옵션 사용 시, 올바른 raycast를 위해 Node들은 지면에서 살짝 떨어트려야함)
  • Use 2D Physics : 2D 게임의 경우 체크
  • Thick Raycast : Raycast의 반지름을 굵게
  • Mask : Ray에 부딪힐 Layer 선택(※ Mask에서 특정 Layer를 제외할 시, 해당 Layer는 Raycast되지 않음)
• Optimize For Sparse Graph(※ Pro버전) : 기존 방식은 브루트 포스 방식으로 O(n^2) 비용을 소모, 체크하면 O(n)으로 최적화
• Nearest node queries find closet : Node, Connection(slower) 등 2가지 타입 존재
  • Node : 경로 선택 시 가까운 Node를 기준으로 함
  • Connection(slower) : Pro버전만 가능, 경로 선택 시 가까운 Node간 Connection과의 거리를 기준으로 함
  • 아래 그림 참고
• Initial Penalty : Scan시 모든 Node에 부여할 penalty(용도는 아직까지 모르겠음)

<Max Distance : 5>

<Max Distance : 0>

<Max Distance : 3> ==> 가까운 Node끼리만 경로가 생성된 것을 확인할 수 있다.

<Nearest node queries find closet>

2) 적용

① Node들 만들어주기

기본적으로 Point Graph를 이용하기 위해선, Point들을 만들어주고, 이들을 하나의 GameObject에 담아줘야 한다.

Point들을 묶은 Root의 이름은 Points라고 지어주고, 각 Point의 위치는 아래와 같이 구성하였다.

② 세팅

일단 Point Graph로만 경로를 계산할 것이기 때문에, 기존 Recast Graph를 삭제하였다.

Point Graph는 아래와 같이 파라미터를 설정하였으며, 반드시 Raycast를 체크하여 Mask를 지정해줘야한다.

(안그러면 Cube를 통과하며 Target으로 도달하는 문제 생김)

추가로 Mask를 설정해줘도, raycast의 굵기가 얇아 벽을 통과하는 문제가 생겨, Thick Raycast를 체크하여 조정해주었다.

AI도 수정해줘야 하는데, 기존 이동 스크립트인 RichAI는 navmesh기반 graph에서 작동하는 스크립트이기때문에, 바꿔줘야 한다. 따라서 AIPath로 바꿔주었으며, Smooth 스크립트도 Funnel이 아닌 다른 것으로 바꿔주었다.

③ 실행

이제 실행하게 되면 설정한 Point로 기반해 만든 경로로 제대로 동작하는 것을 확인할 수 있다!

3. AnimationLink/NodeLink

Point Graph에 대해 계속 알아보다가 매우 좋은 기능을 발견하였다.

그것은 바로 "Animation Link"와 라는 스크립트인데, 이는 "NodeLink2"라는 객체를 상속받아 객체이며, 한 포인트에서 특정 포인트로 갈 때 Animation을 실행시켜주는 기능을 수행해준다.

① NodeLink란

NodeLink는 NodeLink1, NodeLink2, NodeLink3로 총 3가지 유형이 있다.

• NodeLink1 : 두 node를 직접 연결, 수동으로 Graph를 수정할 때 사용
• NodeLink2 : node를 직접 연결하는 것이 아니라, 2개의 point node를 추가하여 간접 연결. 아래 그림 참고
• NodeLink3 : recast/navmesh Graph에서 사용하는듯함

<NodeLink2>

src에서 dst로 이동할 때 가정. 또한 위로 올라갈 수 있다고 가정.

A와 B라는 Point Node가 경로에 추가되며, Src → A → B → Dst 순으로 이동함.

② Animation Link란

3가지 NodeLink중 NodeLink2를 상속받아 만든 객체이며, 특정 Point 도달 시, 특정 Animation을 취할 수 있도록 해주는 스크립트이다.

아래에 있는 Point에서 위 Point로 올라가는 Animation을 넣고 싶을 때 유용하게 사용할 수 있다.

사용법은 아래와 같이 Cube, Link, Top으로 구성된 상태에서

Link에 Animation Link를 달아주고, End엔 Top을 연결해주고, Animation을 달아주면 된다.

이제 이 Animation Link를 돌아다닐 수 있도록 한 가지 작업을 더 해주면 되는데,

바로 돌아다닐 GameObject에 "Animation"을 추가해주고, "Animation Link Traversal"를 달아준 후 연결해주면 된다.

참조

https://arongranberg.com/astar/docs/pointgraph.html#optimizeForSparseGraph

https://arongranberg.com/astar/documentation/stable/class_pathfinding_1_1_animation_link.php

https://arongranberg.com/astar/documentation/stable/nodelink2.html

https://arongranberg.com/astar/documentation/stable/editinggraphs.html

1부에선 Grid Graph로 경로를 만들었다면, 이젠 Navmesh Graph로 만들어볼 것이다.

참고로 무료 버전은 Graph를 만들때 사용자가 직접 Blender등 모델링 응용 프로그램을 사용해야하는 번거로움이 있다.

Unity 상에서 자동으로 Navmesh를 구성하려면 Pro 버전을 구입해야한다.

해당 포스트에선 Pro 버전을 가정한다.

1. 개요

Grid Graph는 그리드 패턴을 사용해 갈 수 있는 영역을 찾는다. 균일하고 구조화되어있기에 매우 직관적이다.

또한 계산 속도가 매우 빨라, 런타임 중 Graph를 업데이트하기 좋은 타워디펜스나 RTS 장르등에 사용할 수 있다.

하지만 맵의 크기가 커질수록, 한 그리드의 크기는 고정적으로 정해져있기 때문에,

Grid Graph를 구성할 때 메모리를 엄청 잡아먹을 것이다!

(※ 그리드 크기 1일 경우, 8x8의 경우 64개의 그리드를, 16x16의 경우 256개의 그리드가 필요)

또한 아래와 같이 여러 층이 존재할 경우, 일반적인 Grid Graph로는 이를 처리할 수 없다.

(※ Pro 버전은 이를 처리해주는 LayerGridGraph 지원)

따라서 복잡한 구조를 가지며, 맵이 넓은 3D 게임에선 Grid Graph를 사용하는게 힘들것이다.

이를 해결하기 위해선, 고정된 크기로 나누는 것이 아니라 유동적으로 크기를 조절하여 나누는 것이 가능해야하며,

맵을 바둑판같은 모양으로 Grid를 찍어내어 계산하는 것이 아니라, 지형지물을 자세히 스캔하여 영역을 계산해야 한다.

이 방식으로 Graph를 만드는 것이 바로 Navmesh이다.

Navmesh는 길을 폴리곤(삼각형) 단위로 표시한다. 그런데 폴리곤들의 크기가 일정하지 않다.

장애물이 없는 넓은 평지를 나타낼 경우 큰 폴리곤으로 표현하며,

좁은 통로나 장애물이 있을 경우 작은 폴리곤으로 영역을 구체적으로 쪼갠다.

아래 Grid Graph와 비교하면 확연히 차이가 보인다.

<NavMesh>

<Grid>

따라서 같은 노드를 사용하더라도, 나타낼 수 있는 맵의 크기는 NavMesh가 압도적으로 더 넓다.

그러나, Grid보단 계산 속도는 많이 느리기때문에, 지형 지물이 자꾸 변하는 게임은 어울리지 않는다.

차이점을 보기좋게 표로 비교하면 아래와 같다.

2. Navmesh 자동 생성(Pro 버전만 해당)

0) AI 수정

앞서 추가한 AIPath를 Navmesh에 기반한 이동 스크립트인 RichAI로 바꾸자.(※ 물론 AIPath를 이용해도됨)

또한 Smooth를 위한 스크립트를 Funnel로 바꿔줘야 한다.

이들또한 Pro 버전에만 존재한다.

1) Adding Recast Graph

수동의 경우, 대충 Blender를 사용해 Navmesh를 만들고, Pathfinder의 "Navmesh Graph"에 집어넣어 만든다.

그러나 이 포스팅에서는 자동 생성에 대해서만 알아보려고 한다.

자동 생성은 Navmesh Graph가 아닌, "Recast Graph"를 클릭하면 된다.

Recast Graph의 구성은 아래와 같으며, 중요 파라미터만 살펴본다.

• Width(voxels), Height(Voxels) : 직접 수정은 불가능하지만, Cell size와 Size를 바꿔주어 수정 가능
• Cell Size : voxel의 크기, 이를 통해 Width, Height 조절하여 해상도 결정. 해상도가 높을수록 그래프가 더 구체적임.
• Use Tiles : Tiles 단위로 계산할 것인지 아닌지 여부. 이때 Use Tiles를 선택하게 되면, Tile Size/2의 길이를 가진 정사각형 청크가 나타남. 사용하는 이유는 병렬 스캔때문인듯함.(아래 그림 참고)
  • Tile Size가 클수록 초기 스캔 속도는 빠르지만, 지형이 변경될 시 계산 속도가 느림.
  • Tile Size가 작을수록 path의 quality는 높아지지만, 너무 작으면 AI가 구불구불하게 움직이게 됨
  • 일반적인 Tile Size는 64 ~ 256값
• Layer Mask : 갈 수 있는 영역을 탐색할 Layer

Navmesh 그래프는 항상 최적 경로를 보장해주지 않는데, 길 찾기가 폴리곤 중심에서 이뤄지기 때문이다.

2) 파라미터 조절

① Snap bounds to scene 클릭

먼저 Snap bounds to scene을 눌러 Graph의 Center와 Size, Rotation등을 알맞게 조정해야한다.

② Layer Mask 지정

AI와 Target까지 Navmesh에 포함돼있기 때문에, Scan해보면 그 주변부가 못가는 길로 구성돼있다.

이를 없애기 위해, Target과 AI에 따로 Layer를 지정하여 Layer Mask에서 제외시켜줘야한다.

이제 Scan하면 제대로 제외된것을 확인할 수 있다.

③ 이외 파라미터 알아서 조정

이외는 테스트를 해보며 입맛에 맞게 조정해주면 된다.

3) 실행

이제 실행하면 navmesh 기반으로 경로가 계산되고 길 찾기를 진행함을 볼 수 있다!

참조

https://arongranberg.com/astar/docs/getstarted2.html