[💬] a* 알고리즘 이거 이렇게 쓸까말까

[123(116.43)]

엑스컴같은 턴제 게임에서 보면

이동가능한 범위 표시해주는거 있짜나

내 경우에는 엑스컴같이 행동횟수가 아니라 행동력 수치로 움직여

2d 탑다운 픽셀 그리드 기반 턴제 겜이고

저 바깥쪽 파란테두리는 행동력이 10일 때 이동가능한 범위얌

직선방향은 행동력 1 소모, 대각선은 1.4 를 소모해

그래서 저런 원과 비슷하지만 아주 살짝 다른 범위가 만들어졌어

고민해봐야할 건 인겜 상에선 행동력이 시시때때로 바뀔 건데,

그때마다 행동력에 따라 자동으로 범위를 그려주도록 공식화해야 한다는 거야

그래서 생각한건

1. 캐릭터 중심으로 21 (행동력 10 * 2 + 1) x 21 크기의 정사각형 안에 있는 타일들에 전부 A* 알고리즘 돌려서
   갈 수 있는 타일을 표시하여 범위 표현하기
    
2. 노란색 테두리 범위 내에 있는 타일들은 어차피 갈 수 있는 타일이므로 무시하고
   나머지 부분 A* 하기.
   이 노란색 테두리 범위 구하는 공식은 행동력 / 14 로 나온 정수 부분을 B라 가정하고,
   (B * 2 + 1) 를 C라 했을 때, 캐릭터 중심으로 C x C 크기의 정사각형임.

둘 중 어느게 더 나을까?

행동력은 스탯이랑 뭐 합쳐서 최대 20 초과하진 않게 할거긴 한데

20만 해도 41 x 41 개의 타일을 A* 해야 하니까... 

좋은 방법 있으면 공유 부탁드려요!

[연어(smosal)]

BFS 쓰십쇼

[거붓(ggp02217)]

최솟값이 아닌 한정 범위내 모든 길을 갈 수 있는 길을 구하는 거니 A*과 상관없지 않냐

[거붓(ggp02217)]

뭐 늪지나 높이 같은 가중치 넣겠다면야 다익스트라 쓰는 것도 있지