Obtenir l'heuristique de 2 coordonnées pour l'algorithme A *

Question

Pour mon projet d'école, créer une carte de tuiles en 2D avec l'algorithme A * pour trouver le chemin le plus court à travers les obstacles. Je l'ai utilisé une formule pour obtenir un score heuristique pour les prochaines tuiles de http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html

Ceci est la fonction pour obtenir heuristique

public static int geth(int cx, int cy, int ex, int ey) 
    { 
     //cx = current position x 
     //cy = current position y 
     //ex = end (goal) position x 
     //ey = end (goal) position y 

     int c = 14; 
     int d_min = Math.Min(cx - ex, cy - ey); 
     int d_max = Math.Max(cx - ex, cy - ey); 
     int h = c * d_min + (d_max - d_min); 
     if (h < 0) //make h positive in case it's negative 
     { 
      h = h * -1; 
     } 

     return h; 
    } 

Cela fonctionne lorsque le point de départ est plus élevé sur l'axe y que le point final, mais doesn Ne pas trouver le chemin le plus efficace lorsque le début est plus bas sur l'axe des ordonnées.

J'ai ajouté une version console de mon problème. Le plus efficace devrait être en diagonale, mais cela prend un mauvais chemin.

(bleu 'C' sont les noeuds vérifiés, le chemin 'P' vert fait, 'N' rouge encore à vérifier, d'autres ne sont pas encore atteint)

Answer 1

Dans l'article lié, Je vois cet algorithme:

les symboles de tuyauterie | autour des différences sont les absolute value function, ce qui est représenté en C# comme Math.Abs.

La distance n'a pas de signe attaché. cx - ex sera négatif lorsque ex est plus grand que cx (et de même avec cy - ey) ce qui peut amener votre Math.Min et Math.Max à choisir la mauvaise dimension pour d_min et d_max. Vous devez utiliser Math.Abs pour supprimer le signe des quantités comparées.

par exemple.

int d_min = Math.Min(Math.Abs(cx - ex), Math.Abs(cy - ey)); 

(Et aussi pour d_max.)