Una precisa * búsqueda heurística para mapas isométrica?

Question

He escrito una implementación del algoritmo de búsqueda A *. El problema es que la heurística Actualmente estoy usando sólo funciona con precisión en rejillas cuadradas. Como mi mapa es isométrica, la heurística no tiene en cuenta real el diseño del mapa y, por tanto, la distancia entre las células.

Actualización: Después de un amplio registro y análisis (que se lee pasar mucho tiempo tratando de encontrar una banalidad ), que han llegado a la conclusión de que mis obras heurísticos actuales bastante bien, con una pequeña excepción:. el resultado final se invierte para real movimiento recto y en diagonal

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);
}

Esto significa que un movimiento recto, lo que realmente cuesta veces sqrt(2) más que un movimiento diagonal en un isométrica mapa, se calcula que es el que de una diagonal. La pregunta es: ¿cómo puedo modificar mi heurística actual, de modo que producirá resultados correctos para obtener una distribución isométrica? Simplemente reemplazando diagonal con straight y viceversa será no de trabajo.

Answer 1

Una cosa a intentar sería la conversión de coordenadas isométricas de una cuadrícula de coordenadas definido para todos los cálculos.

Supongamos que 0,0 se mantiene la raíz del mapa. 0,1 se mantiene igual, 1,2 se convierte en 0,2; 1,3 se convierte en 0,3; 2,3 se convierte en 1,4; 3,3 se convierte en 2,5; 0,2 se convierte en -1,1; etc. Esto lo pone de nuevo en una cuadrícula de tal manera que las coordenadas y la heurística deben trabajar de nuevo.

Y de coordenadas se convierte en Y + sourceX compensado (3,3 es en x = 2, de modo que se convierte en 2,5); encontrar sourceX mathmatically está demostrando más difícil.

[corriente de la conciencia; Ignorar] isométrica coordenadas en Y = 0 son precisas para la fuente de X. Por lo tanto, para calcular fuente X que necesita para 'mover hacia la izquierda / los tiempos de Y' que debería neto un cambio de S / 2; redondean hacia abajo, en la coordenada x .... más o menos lo que sugiere que las coordenadas cuadrados serían:

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

Donde sourceX y sourceY son las coordenadas en una rejilla cuadrada normal; e Y / 2 es la aritmética de enteros / redondeado hacia abajo.

Por lo tanto, en teoría, esto se convierte en:

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));
}

Actualizar basado en nuevos trozos de pregunta:

Si se asume que usted está tratando de obtener la distancia (3,2; 3,3) <(distancia (2,3; 3,3) = distancia (3,1; 3,3)); la siguiente debería funcionar: (traducido de C #; errores tipográficos no garantiza que sea no presente)

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:. fijo terrible typo .... otra vez

Answer 2

Amit aquí calcula la "distancias Manhattan por hexágonos". Su código C ++, y no puedo dar fe de ello, pero Amit es un nombre que he escuchado antes para el desarrollo del juego.

La distancia Manhattan para hexágonos debe ser adecuado para una heurística adecuada.

Edit: invertido la sintaxis para los hipervínculos, whoops

.