[💬] 다익스트라 배우는 중

[yshtita..(yshtitanic)]

아까 적 AI랑 아군 움직이는 거 지정할 때 움직일 수 있는 타일 표시하려고 다익스트라 알고리즘을 좀 공부하게 됨.

다익스트라 알고리즘 가지고 거리 계산하고 하는게 A*보다는 좀 처리량이 많지만 그래도 확실하고 좋더라

다익스트라가 음수 가중치는 계산 못하는 게 안타깝기는 한데 그거 그냥 음수 값 나올때마다

1.이게 지금까지 나왔던 음수의 최솟값보다 작은가?

1-1.만약 맞으면 음수의 최솟값을 업데이트

2.이후 계산하는 모든 다익스트라에 음수 최솟값에 -1을 곱한만큼 더해서 양수로 전환

3.종료할 때까지 반복.

이렇게 하면 편법이지만 되겠다는 생각 하면서 일단 기본적인 구현 구상해보는 중

다만 내가 수험생이고(왜 고3은 수능을 보는가), 수시 자소서 작성이라는 핑계를 못 대서 3개월 정도는 컴퓨터를 평소처럼 자주 잡지 못할 것 같아서 걱정이네... 아이디어 까먹으면 큰일인데...

암튼, 오늘은 사진은 없고. 나중에 더 만들면 올릴게.

[광섬(swjwpower)]

음 다익스트라를 쓰는게 맞나 맵이 어떻게 생긴지를 몰라서 조언을 못해주겠네

[yshtitanic(yshtitanic)]

걍 육각형 타일 맵. 내 예전 게시글 보다보면 있을 거임

[yshtitanic(yshtitanic)]

다만 이제 타일마다 가중치가 달라서 A*은 어렵겠다는 생각이 들더라고

[광섬(swjwpower)]

아 그러면 써도 되겠네 음수야 뭐 편법 쓰면 계산 될거고 아니면 특정 노드(적, 나)를 포함한 크루스칼 방법 써도 되고

[광섬(swjwpower)]

아 아니네 착각했다 크루스칼 쓰면 안댄다 ㅈㅅ

[익명(175.199)]

구현 할 수만 있으면 JPS(B) 알고리즘
https://github.com/gamephysics/JPS_B

[yshtitanic(yshtitanic)]

얘는 그냥 길찾기 알고리즘 아닌가? 나는 가중치가 다 달라서 이걸로는 좀 무리일 듯 - dc App

[익명(175.199)]

근데 프로젝트가 유로파나 호이처럼 실시간 패스파인딩이 필요한거임? 맵 크기도 잘 모르겠고 맵 넓을수록 다익스트라 알고리즘은 별로 안좋을듯 아니면 Flow Field 알고리즘도 검색해봐 다익스트라 기반으로 모든 지점에서 목표지점까지 경로를 구하는건데 오브젝트 1200개 까지는 무리없이 돌아가더라 근데 얘도 마찬가지로 맵 넓을수록 비효율적임

[yshtitanic(yshtitanic)]

실시간까지는 아니고 턴제 게임 느낌. 그런게 나중에 다른 게임에서 실시간도 해야 할 텐데 그건 생각 못해봤네. 아직 맵 크기가 1만개를 안 넘고 오브젝트도 하나니 지금 무리는 없지만 추후를 위해 혹시 알고있는 거 있으면 알려주면 감사하게 배울게. - dc App

[거붓(ggp02217)]

막 걸음바 배운 놈에게 자동차 운전 배우라고 하지말자 저거 어렵다