A * 길 찾기 - 알 수없는 목적지와 가장 가까운 곳

Question

나는 이미 작동하는 A * 구현이 있습니다. 문제는 탐색 할 수없는 대상을 선택하면 경로가 반환되지 않는다는 것입니다. 나는 내가 얻을 수있는 '가장 가까운'것을 얻을 수 있기를 원한다.

바람직한 옵션은 목적지 주위의 8 개의 타일을 확인하는 것뿐만 아니라 완전히 동적 인 것입니다. 그렇게하면, 거대한 사각형의 거친 사각형으로 둘러싸인 비할 데없는 타일을 클릭하더라도 가능한 한 가까이에있게됩니다.

Answer 1

가장 낮은 h 값을 가진 타일을 보유하는 포인터를 유지할 수 있습니다. 경로가 반환되지 않으면 보유하고있는 타일에 대한 경로를 생성하십시오.

Answer 2

여기에 제공된 간단한 대답만으로도 충분할 수도 있지만 게임 유형과 달성하려는 목표에 따라 다릅니다. 예를 들어

, (미안 해요 내가 당신에게 전쟁의 안개를 표시하는 데 사용되는 동일한 소프트웨어 : 재사용하고있어)이 플레이 필드를 가지고 :

당신이 볼 수 있듯이를, 화가 치킨 왼쪽과 오른쪽 사이의 경로를 차단하고 있습니다. Angry Chicken은 아무 것도 될 수 있습니다 ... 정적 인 장애물 인 경우 가장 낮은 숫자 인 h node으로 충분할 수도 있지만 동적 인 객체 (예 : 잠긴 문, 무승부 등) 인 경우 다음 예제가 도움이 될 수 있습니다 어떻게하면 문제를 해결할 수 있는지 알 수 있습니다.

우리가 분명히 우리가 도달 할 수 있기 때문에

우리는, 우리가 경로가되고 싶어 무엇을 생각해야 다른 측면에서 우리의 영웅의 대상을 설정합니다. manhattan 거리 나 euclidian 거리와 같은 표준 휴리스틱을 사용하여,이 결과를 얻을 것이다 : 어떤 방법이 있는지 충분히 좋은 수 있습니다

,하지만 닭과 상호 작용할 수있는 우리의 작은 영웅 통과를, 그것은 아무튼 '는 t는 당신이 원하는 것은

이 어떻게 할 수있는이있다, 전혀 이해가? 글쎄, 쉬운 방법은 hierarchical graphs을 찾아내는 것입니다. 이것은 복잡하게 들리지만 그렇지 않습니다. 먼저, (일을 변하지 않을 것, 또는 다른 표현) 여러 그리드 노드가 포함됩니다 높은 수준의 노드와 엣지의 새로운 세트를 구축 할 수 있도록하려는

당신이 볼 수 있듯이 , 우리는 이제 오른쪽 blue node과 왼쪽 red node을가집니다. 화살표는 두 노드 사이의 가장자리를 나타냅니다. 당신이 묻는이 그래프를 만드는 방법? 간단합니다. 열려있는 노드에서 시작하여 이웃 노드를 모두 확장 한 다음 상위 노드에 추가합니다. 끝나면 그래프의 다른 부분으로 이어질 수있는 동적 노드를 열고 같은 작업을 수행합니다.

이제 우리의 영웅에서 빨간색 X 경로를 묻는다면, 먼저 높은 레벨에서 길 찾기를 수행하십시오 ... blue node에서 red node까지의 길은 있습니까? 예! 닭고기를 통해.

닭고기를 교차시킬 수있는 edge으로 이동하면 파란색면에서 쉽게 탐색하는 방법을 쉽게 알 수 있습니다. 그냥 일반 벽이라면

, 당신은 아마도 당신이 원하는 방식으로 반대편에 도달 한 후 처리 할 수있는 방법이 없다는 것을, 단일 노드를 방문하여, 매우 신속하게 결정할 수있다 여전히 A *를 수행하고 최저 h 노드를 반환합니다.