[💬] 아래 다익스트라 알고리즘 자세한 설명.

[hong(121.186)]

내가 그의 이름을 불러 주기 전에는
그는 다만
하나의 몸짓에 지나지 않았다.

내가 그의 이름을 불러 주었을 때
그는 나에게로 와서
꽃이 되었다. - 김춘수

( 크.. 그가 나에게 정성이 있어서 개추라고 하지 않았을 때는 나는 한마리 백수에 지나지 않았따! 정성 투적! )

사진을 확대해서 볼 것을 추천합니다.

2개의 화면이 있습니다.

위에는 맵화면

아래는 이동에 필요한 경로수 ( 턴수, 이동력수 혹은 비용 )을 적은 다익스트라맵입니다.

( 저는 대각선 이동이 가능한 8path로 알고리즘을 돌렸습니다. )

( 영문자는 사실 숫자를 1글자로 표현하기 위한것이다.

10->a, 11->b........z까지 z다음엔 A부터 ... )

상황은 이렇습니다.

(5,5) 위치에는 위의 그림이나 아래그림이나 똑같이 x로 목표가 표시되어있다.

x로 표시된 놈은 플레이어입니다.

e행의 좌측끝 동그라미 쳐진 g값을 봅시다.

그래서 좌측 배열의 범위를 넘어서는 부분을 제외하면

gf

gf

gf

위 처럼 생긴 곳에 빨간 네모가 쳐져있죠?

이것은 여기에 몬스터가 있다고 가정하고 해당 몬스터가 움직일 수 있는 칸을 표시한 것입니다.

빨간 g( 혹은 그림에 그려진 동그라미 쳐진 부분 )이 몬스터고 요놈을 고블린이라고 해봅시다.

이 고블린은 플레이어의 위치 ( 5,5 ) 까지 시야가 닿아서 플레이어가 거기 있다는 걸 이미 알고 있습니다. (벽이 있지만 투시를 한다고 칩시다)

그리고 최단거리로 공격하러 가고싶습니다.

g니까 이동거리가 총 16이네여 ( f가 15 )

이동은 8방향중에 숫자가 적은 방향으로 움직입니다. f가 3개 있으니까 우상단, 우측, 우하단 어디로 움직여도 상관없습니다.

우리는 귀찮으니까 우측으로 바로 움직였습니다. ( 이동은 화살표로 표시했습니다. 확대해서 보기를 추천합니다 )

이후에는 같은 방향으로 움직입니다.

화살표 숫자를 세보면 16번 이동한다는 걸 알 수 있습니다.

항상 8방향중 작은쪽으로 움직였다는 것 두요.

9행 h열에도 고블린이 한마리 있다고 쳣습니다.

c인걸 보면 거리가 12네요.

마찬가지로 움직이게 됩니다.

이렇게 다익스트라 맵을 만들어놓으면 다수의 몬스터가 아군을 향해 다가올 경로를 지정 할 수 있게 됩니다.

1턴마다 이 작업을 하는 모양입니다. 플레이어 위치가 변경되면요. 안되면 그냥 이전턴의 다익스트라 맵을 써도 되죠.

참고한링크

http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized

여기를 보면 몬스터가 접근하는경우, 튀는경우, 아이템을 주으면서 접근하는경우,

플레이어가 안개를 헤치며 자동이동하는 경우, 유저가 화면 클릭시 이동하는 경우등을

설명하고 있네여.