아이소 메트릭 맵을위한 정확한 A * 검색 휴리스틱?

Question

나는 A * 검색 알고리즘의 구현을 작성했다. 문제는 내가 현재 사용하고있는 휴리스틱은 정사각형 그리드에서만 정확하게 작동한다는 것입니다. 내지도가 등각 투영이므로, 휴리스틱은 실제로 지도의 레이아웃을 고려하지 않으므로 셀 사이의 거리가됩니다.

업데이트 : 광범위한 로깅 및 분석 후은 (시간의 지출을 많이는 진부함을 알아 내려고 노력으로 읽기), 내 현재 발견 한 작은 제외하고는 아주 잘 작동 결론에 도달 한 다음 실제 직선 및 대각선 이동의 경우 최종 결과가 반전됩니다.

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const 
{ 
    int diagonal = std::min(abs(coord.x-goal->position.x), abs(coord.y-goal->position.y)); 
    int straight = (abs(coord.x-goal->position.x) + abs(coord.y-goal->position.y)); 
    return 14 * diagonal + 10 * (straight - 2 * diagonal); 
} 

이 정말 아이소지도 대각선 움직임보다 sqrt(2) 배 비용 직선 이동이, 하나의 대각선의 저로 계산되는 것을 의미한다. 문제는 현재의 휴리스틱을 수정하여 등각 투영 레이아웃에 대한 정확한 결과를 얻을 수있는 방법은 무엇입니까? 단순히 diagonal을 straight으로 바꾸거나 그 반대의 경우는 이 아니며이 작동합니다. 정사각형 격자로 등각 투영 좌표로 변환 될 것이다 시도

Answer 1

한 가지는 모든 계산 설정 좌표.

0,0이지도의 루트를 유지한다고 가정 해보십시오. 0,1은 동일하게 유지되고, 1,2는 0,2가됩니다. 1,3은 0,3이되고; 2,3은 1,4가되고; 3,3은 2,5가된다; 0,2는 -1,1이된다; 좌표와 추론이 다시 작동하도록 정사각형 그리드로 되돌아갑니다.

Y 좌표는 Y + sourceX offset이됩니다 (3,3은 x = 2이므로 2,5가됩니다); sourceX를 수학적으로 찾는 것이 더 어렵다는 것을 증명합니다.

[의식의 흐름] ignore] Y = 0에서 등각 투영 좌표는 소스 X에 대해 정확합니다. 따라서 소스 X를 계산하려면 '왼쪽/위로 Y 번 이동'해야합니다. 그러면 Y/2가 변경됩니다. 대략 사각형의 좌표가 될 것이라고 제안 .... x 좌표에서 내림 :

sourceX = X - Y/2 
sourceY = Y + sourceX 

에서는 sourceX 및 sourceY 정상적인 사각형 격자의 좌표

; Y/2는 정수로 산술/내림 처리됩니다.

는

그래서, 이론적으로,이 된다 :

double DistanceToEnd(Point at, Point end) 
{ 
    Point squareStart = squarify(at); 
    Point squareEnd = squarify(end); 
    int dx=squareStart.X-squareEnd.X; 
    int dy=squareStart.Y-squareEnd.Y; 
    return Math.Sqrt(dx*dx+dy*dy); 
} 
Point squarify(Point p1) 
{ 
    return new Point(p1.X-p1.Y/2, p1.Y+(p1.X-p1.Y/2)); 
} 

업데이트을 질문의 새로운 비트를 기반으로 :

당신이 거리를 얻어내는 것이 가정 (3,2; 3,3) < (거리 (2,3; 3,3) = 거리 (3,1; 3,3)); 다음 작동한다 : (C 번호 번역, 오타가 아닌 본 보장되지 않음)

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const 
{ 
    int cx=coord.x - coord.y/2; 
    int cy=coord.y + cx; 
    int gx=goal->position.x - goal->position.y/2; 
    int gy=goal->position.y + gx; 
    int diagonal = std::min(abs(cx-gx), abs(cy-gy)); 
    int straight = (abs(cx-gx) + abs(cy-gy)); 
    return 14 * diagonal + 10 * (straight - 2 * diagonal); 
} 

EDIT : 고정 끔찍한 오타 .... 다시.

Answer 2

Amit 여기서 "육각형에 대한 맨하탄 거리"를 계산합니다. C++ 코드는 보증 할 수 없지만 Amit은 게임 개발을 위해 앞서 들었던 이름입니다.

육각형에 대한 맨하탄 거리는 적절한 휴리스틱에 적합해야합니다.

편집 : 하이퍼 링크 구문을 뒤집습니다.