[💬] A* 막힌 길 어떻게 처리할까

[익명(218.147)]

그냥 막힌 길 검색하면
A*가 모든 셀을 전부 검사하는데

답도 없네
그냥 막힌 길을 없애버릴까

[익명(118.130)]

막힌 길은 못가는 길로 그냥 멈추면 되지

[익명(218.147)]

그러니까 A*에서 막힌 길을 찾으려면 해당 셀이 막혔는지 검색해야 하잖아

[익명(218.147)]

예를 들면 늪지대는 가중치 추가 잔디는 가중치 감소 깊은 물은 이동 불가능만약 대륙간 a*를 돌리게 되면 중간에 깊은 물이 길을 막고 있어서 그리드 전체를 체크해야해당 셀이 막힌 셀이라고 검색됨 난 전체를 체크 안 하고 멈추고 싶은 거임

[거붓(ggp02217)]

해당 셀의 구역이 막혀있는지 검사할려면 flood fill 알고리즘으로 검사하던가 아니면 미리 막혔다고 따로 표시한거 아니면 모를껄?

[익명(218.147)]

답이 없네 ㅋㅋㅋ

[익명(218.147)]

그럼 flood fill 알고리즘으로 먼저 한 번 돌려서 연결 상태를 확인하고 그 다음에 a*를 검색해야하나?

[익명(175.223)]

경로 못찾을때 모든 셀을 다 검색하는건 어쩔 수 없고 너무당연한거임 애초에 경로가 없다고 판단하려면 모든곳에 다 가봐야하니까.. 마지막에 탐색한곳에 개구멍 있으면 어쩔건데

[익명(175.223)]

플러드필이 별게 아니라 dfs나 bfs로 갈수있는곳 다 가보는거고 에이스타는 휴리스틱이랑 그리디가 적용된 bfs랑 본질적으로 같으니까, 플러드필은 답이 아님

[익명(175.223)]

아예 다른대륙 같은 경우는 시작 전에 정적으로 여기 다른영역이라고 셀마다 지역id 같은거 달아두던가.. 그럴때 플러드필 쓸수는 있겠네

[익명(218.147)]

확실히 셀마다 인구분포 설정했던 것처럼 노이즈 값에 따라 섬 Id를 달아두면 A* 하나로도 충분할 듯 하네

[익명(218.147)]

대륙 id를 잘 쓰면 절차적 맵 생성할 때 각 대도시마다 항구 설정까지 할 수 있을 듯

[익명(usnned)]

워스트는 어쩔 수 없음 탐색 횟수 제한 거는게 최선임