[💬] 길찾기 알고리즘

[익명(218.38)]

몇일전에 A* 알고리즘 노드 사이에 벽있으면 어쩌냐고 질문했었는데

간편한 방법은 못찾고 대충 때워서 만들었음

제일 중요하게 생각한 게 맵 그리는 난이도를 낮추는 거였는데

미로 그리다 보니까 한참 부실해서 다시 갈아엎어야 할듯

[ㅇㅇ 1(14.33)]

절차적 미로생성 알고리즘 같은것도 해보셈

[디붕쿤(divide6198)]

[익명(110.10)]

요즘 대각선 이동 못하면 똥겜이니까 대각선도 넣자

[에뚜(ssss4610)]

[ㅇㅇ 2(121.158)]

근데 걍 x1,y1에서 x2,y2로 최단 경로로 갈 때 이동할 방향을 저장해 버리면 안됨? 2비트로 되니까 100*100이라 치면 2억 비트 = 200MB로 가능

[q(218.157)]

그걸 모든 칸별로 다른 모든 칸으로 경로를 다 저장해야 해서 저장해야 할 양도 기하급수적으로 늘어나고 그렇게 아무리 잘 짜놔도 지도 조금만 수정되면 다 망해서 새로 만들어야 한다.

[q(218.157)]

칸 별로 갈 수 있는 방향과 갈 수 없는 방향만 설정해 두면 애초에 못 가는쪽으론 계산 못하게 하는게 되니까 돌아갈거. 한칸 가는데 이동 1 쓴다 치면 위랑 오른쪽이 뚫린 칸에서 위나 오른쪽으로 가는데 1씩 쓰는데 왼쪽이나 밑으로는 아예 이동 요구량이 무한대라거나 같은걸로 설정하거나 아예 그쪽으로는 가는걸 고려도 안 하고 탐색을 돌리거나 하면 되니. 벽=갈 수 없는 방향이니 벽 방향으로 넘어가야 하는 옆칸으로는 탐색 고려를 못하게 막으란거임.