[📜일지] #1 길찾기 (1) - A* 알고리즘 변형

[누아(rbfwmqwntm)]

#1 길찾기 (1) - A* 알고리즘 변형

안녕! 댓글 쓰고 종종 게임 리뷰 남기는 개발자야.

정기적으로는 아니더라도, 나도 지금 내가 만드는 게임의 개발 일지를 써보려고 해.

오늘은 RTS 방식의 유닛 길찾기에 대해 이야기를 해보려고.

가장 널리 알려진 알고리즘은 A*가 있지. 고라니 님의 영상을 참고하면 쉽게 만들 수 있어.

https://youtu.be/tqwsnUkUleA

간단히 설명하면, BFS를 이용하는 거야.

시작점 노드를 S, 도착점 노드를 E, 벽을 X라고 하면 다음과 같이 그림을 그릴 수 있겠지.

현재 지점 S로부터 주변 노드를 하나하나 검사해서, 각 정점(노드)까지 갈 수 있는 이전 노드를 쭉 저장해놔.

그 다음 도착점에 도달하면, 도착점부터 이전 노드까지 backtracing을 해서 해당 지역까지 최단 경로를 찾아낼 수 있지.

직관적이고 쉬운 알고리즘이야. 그림으로는 이런 식으로 동작해.

A*는 대각선 통과를 하게 옵션을 줄 수도 있고, 직각으로만 이동하게 할 수도 있어.

내부적으로 거리 값에 관한 G, H, F라는 변수를 들고 다니면서, 이것들을 비교해서 어떤 게 최단 경로인지 파악해놔.

G는 시작점으로부터 이동해온 거리,

H는 |가로|+|세로| 장애물 무시한 목표까지의 거리,

F는 G + H 라고 해.

하튼 A*를 이용하면 경로를 다음과 같이 찾을 수 있어. 아래는 내가 만드는 게임에서의 경로 탐색이야.

(Figure3.1) 대각선 불허	(Figure3.2) 대각선 허용, 대각선 통과 불허	(Figure3.3) 대각선 허용, 대각선 통과 허용

그런데 문제는, 이 게임에서는 유닛이 이렇게 직각/45도 보행을 하면 안 됐어.

컨트롤이 중요한 게임이라 유저가 위치 지정을 했을 때 해당 방향까지 direct로 가야 하거든.

예를 들면 이런 이동을 해야 하는 거지.

(Figure4.1)

약간 더 복잡하게라면 이렇게 이동해야 하겠고.

(Figure4.2)

이것을 어떻게 할지 고민하다가 떠오른 방법은, 탐색된 경로의 모든 노드에 대해 시점부터 종점까지

Ray를 쏴서 벽이 있는지 없는지를 보고, 직선 연결 가능한 지점 사이의 모든 점을 지우는 거야.

개인적으로 이렇게 모든 노드에 대해 Ray를 쏴보는 게 좋은 것 같지는 않은데,

가장 간단하게 떠올릴 수 있는 방법이고, 기획상 Grid의 크기가 그렇게 크지 않아서 진행해봤어.

예를 들어보자. 시작은 이런 상태야. 마찬가지로 S는 시작, E는 종료, X는 벽이야.

노드를 검사하기 위한 변수 i, j를 추가해보자.

i=0, j=1 위치에 있어. 0과 1은 연결 가능해.

j를 하나 올리고 다시 검사해봐. j==2와 i==0은 연결 가능해.

다시 j를 올리고 같은 작업을 반복해봐. 이 경우 끄트머리에 걸리지만, 이 예제에서는 연결 가능한 것으로 간주했어.

다시 j를 올리고 검사해봐. j==4이고 i==0일 때 두 노드는 가운데 벽이 있기 때문에 연결되지 않아.

그러면 우리는 지금 연결이 안 되는 노드의 직전 노드 (j-1)까지 연결 가능하다는 사실을 알고 있으니,

i+1 부터 j-1 까지 총 j-i-2 개의 노드를 1번 위치에서 지워주면 돼.

이렇게 되면 경로는 이렇게 되겠지.

i==0 인 경우의 최적 다음 종점을 찾았으니, i를 한 칸 올리고 j도 그에 맞춰 업데이트 해줘.

그리고 다시 같은 작업을 반복해봐.

j==5, i==1일 때 두 노드는 직접 연결할 수 없음이 판정됐어.

마찬가지로 사이의 노드를 지워주자.

그러면 이렇게 되겠지.

이후 종점까지 같은 방식으로 쭉 진행해보면 돼.

이후 남은 점이 없으므로 j는 총 노드 수인 5가 되고, 반복문에서 탈출해.

그러면 남은 점에 대해서도 처리를 해주면 되구.

그러면 최종적으로 다음과 같은 선이 나와.

두 경로의 직접 비교

원래 경로	새 경로

이 방법대로라면 Figure4.1과 Figure4.2에 모두 대응할 수 있어서,

실기기에서 부하가 느껴지지 않는다면 이대로 계속 진행할 예정이야.

인게임 반영

대각선 허용, 대각통과 불허	대각선 허용, 대각통과 허용

그 밖에도 A* 외에 성능 상 효과가 뛰어난 것으로 알려진 건 JPS라는 게 있고,

특히 다음 영상에서는 JPS(B)를 사용하여 응답 속도를 100ms 이하로 안정적으로 뽑았다고 해.

https://youtu.be/rfOgaPXCADQ

실제로 서비스되고 있는 게임에서 사용된 JPS(B) 알고리즘을 공유하고 있다시니,

A*보다 빠른 성능을 얻어야 하는 게임을 개발한다면 참고하면 좋을 것 같아.

나중에 C# version으로 포팅해보고 나서 commit 해보려고.

다음에는 A* 알고리즘으로 길 찾기를 하는 경우 목적지에 갈 수 없을 때, 근사 종점이라도 구하는 방법에 대해 이야기해보자.

오늘 개발 일지는 여기까지야.

관심 있다면 아래의 인디 게임 체험 소감도 보고 의견 공유해줘!

[체험 소감 모아보기]

#1 클로크 클럭 - https://gall.dcinside.com/game_dev/87748

#2 에픽 레전더리 - https://gall.dcinside.com/game_dev/87918

#3 크레이지팜 - https://gall.dcinside.com/game_dev/88036

#4 문경새재 - https://gall.dcinside.com/game_dev/88280

#5 듀얼 - https://gall.dcinside.com/game_dev/88490

#6 로프 킹 - https://gall.dcinside.com/game_dev/88527

#7 하이퍼 점프 - https://gall.dcinside.com/game_dev/88628

#8 Brackeys Game Jam 2022 - https://gall.dcinside.com/game_dev/88831

#9 Brackeys Game Jam 2022 파트 투 - https://gall.dcinside.com/game_dev/88942

#10 좀비 서바이벌 - https://gall.dcinside.com/game_dev/88975

#11 내 맘대로 오브 더 데드 4 - https://gall.dcinside.com/game_dev/89136

#12 I'm Still ALive - https://gall.dcinside.com/game_dev/89263

#13 DEMO

#14 KIN:D - https://gall.dcinside.com/indiegame/27851

[개발 일지 모아보기]

#1 길찾기 (1) A* 알고리즘 변형

#2 길찾기 (2) 우선순위 큐를 활용하여 근사 목적지 구하기 - TBD

[익명(219.249)]

개추

[누아(rbfwmqwntm)]

[쿠키맛촉촉(zz5414)]

이런건 무조건 추천이지! 밤이라 글이 안들어오니 내일 읽어볼게!

[누아(rbfwmqwntm)]

꺆 고마워! 도움 됐으면 좋겠다~ - dc App

[레시(gksdjf051)]

개추

[누아(rbfwmqwntm)]

[익명(210.110)]

이거 추천안하면 1번남

[누아(rbfwmqwntm)]

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[누아(rbfwmqwntm)]

[익명(7hvc5bphs4sv)]

최단경로 탐색 직접짤때 대가리 깨졋엇는데 엔진에 있더만... 시펄

[누아(rbfwmqwntm)]

엇 asset store에서 하는 거 말고 UnityEngine 안에 component 정의가 있니? 3D에 한정으로 NavMesh라는 걸 쓸 수 있다고는 하던데 그거랑 다른 걸까? - dc App

[퀼트(mok9181)]

록리 개추

[누아(rbfwmqwntm)]

노력파가 멋있지~