Une précision * heuristique de recherche pour les cartes isométrique?

Question

J'ai écrit une implémentation de l'algorithme A * de recherche. Le problème est que l'heuristique J'utilise actuellement ne fonctionne que sur des grilles de précision carrés. Comme ma carte est isométrique, l'heuristique ne prend pas en compte réelle la mise en page de la carte et ainsi, la distance entre les cellules.

Mise à jour: Après l'enregistrement et une analyse approfondies (lire comme passer beaucoup de temps à essayer de trouver une banalité ), je suis venu à la conclusion que mes œuvres heuristiques actuelles très bien, avec une petite exception:. le résultat final est inversé pour real mouvement rectiligne et diagonale

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

Cela signifie qu'un mouvement rectiligne, qui coûte vraiment sqrt(2) fois plus qu'un mouvement en diagonale sur une isométrique carte, est calculée pour être la celle d'une diagonale. La question est: comment puis-je modifier mon heuristique actuelle il produira des résultats corrects pour une mise en page isométrique? Il suffit de remplacer diagonal avec straight et vice versa sera pas travail.

Answer 1

Une chose à essayer serait la conversion de coordonnées isométriques à une grille carrée pour tous ensemble de coordonnées de calculs.

Dire que la racine reste 0,0 de la carte. 0,1 reste le même, 1,2 devient 0,2; 1,3 devient 0,3; 2,3 devient 1,4; 3,3 devient 2,5; 0,2 devient -1,1; etc. Cela vous met dans une grille carrée de telle sorte que les coordonnées et heuristiques devraient fonctionner à nouveau.

coordonnée Y devient Y + sourceX décalée (3,3 est à x = 2, de sorte devient 2,5); trouver sourceX mathmatically est se révèle plus difficile.

[Courant de conscience; ignorer] isométriques coordonnées Y = 0 sont exactes pour la source X. Donc, pour calculer la source X, vous devez « aller à gauche / les temps Y » qui devrait un changement net de Y / 2; arrondies vers le bas, dans la coordonnée X .... plus ou moins ce qui suggère que les coordonnées carrés seraient:

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

Où sourceX et sourceY sont les coordonnées dans une grille carrée normale; et Y / 2 est arithmétique entière / arrondi.

Donc, en théorie, cela devient:

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

Mise à jour basée sur de nouveaux morceaux de question:

En supposant que vous essayez d'obtenir la distance (3,2; 3,3) <(distance (2,3; 3,3) = distance (3,1; 3,3)); les éléments suivants devraient fonctionner: (traduit de C #, typos non garantis non présent)

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:. Correction d'une faute terrible .... à nouveau

Answer 2

Amit ici calcule les distances "manhattan pour hexagones". Son code C ++, et je ne peux garantir, mais Amit est un nom que je l'ai entendu avant pour le développement du jeu.

La distance manhattan pour hexagones devrait convenir à une heuristique appropriée.

Edit: inverser la syntaxe pour hyperlinking, oups

.