Comment créer des chemins naturels avec A * sur une grille?

J'ai lu ceci: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Mais il y a certaines choses que je ne comprends pas, par exemple, l'article dit d'utiliser quelque chose comme ça pour trouver un chemin avec un mouvement diagonal:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

Je ne sais pas comment définir D pour obtenir un chemin d'apparence naturelle comme dans l'article, j'ai défini D au coût le plus bas entre les carrés adjacents comme il est dit, et je ne sais pas ce qu'ils voulaient dire par les choses sur l'heuristique. être 4 * D, cela ne semble rien changer.

Voici ma fonction heuristique et ma fonction de déplacement:

def heuristic(self, node, goal):
    D = 5
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

def move_cost(self, current, node):
   cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
   return 7 if cross else 5

Résultat:

Le chemin de navigation en douceur que nous voulons réaliser:

Le reste de mon code: http://pastebin.com/TL2cEkeX

Mise à jour

C'est la meilleure solution que j'ai trouvée jusqu'à présent:

def heuristic(node, start, goal):
    dx1 = node.x - goal.x
    dy1 = node.y - goal.y
    dx2 = start.x - goal.x
    dy2 = start.y - goal.y
    cross = abs(dx1*dy2 - dx2*dy1)

    dx3 = abs(dx1)
    dy3 = abs(dy1)

    return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3)

def move_cost(current, node):
    cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
    return 7 if cross else 5

Il produit le chemin souhaité à partir de la deuxième photo, mais ne gère pas très bien les obstacles (a tendance à ramper sur les murs) et ne parvient pas à produire des chemins optimaux parfois sur de plus longues distances.

Quels sont les ajustements et optimisations que je peux appliquer pour l'améliorer?

Un * vous donne le chemin le plus court dans le graphique. Lorsque vous utilisez une grille comme graphique, il existe souvent plusieurs chemins les plus courts. Dans votre premier diagramme, qui est l' un des chemins les plus courts. Il place tous les mouvements axiaux en premier et tous les mouvements diagonaux ensuite. Mais c'est le même chemin de longueur que si vous mettiez toutes les diagonales en premier, ou si vous mélangiez des mouvements axiaux et diagonaux. Ils sont tous équivalents, et celui que A * choisit dépend de la façon dont le code est écrit et de la façon dont le graphique est représenté.

Je pense que ce que vous voulez soit:

1. Vous devez vous déplacer sur la grille, mais vous voulez mélanger les étapes axiales et diagonales pour qu'elle soit plus belle. Une approche consiste à choisir l'un des autres chemins également courts; Continuez à lire cette page Heuristique pour trouver le «bris d'égalité». Une autre approche consiste lorsque vous évaluez des voisins, choisissez au hasard lequel évaluer en premier afin qu'il ne choisisse pas toujours l'un avant l'autre. Je ne recommande pas d' utiliser la distance euclidienne / cartésienne si vous voulez vous déplacer sur la grille; c'est un décalage qui ralentit A *.
2. Vous n'avez pas besoin de vous déplacer sur la grille et vous souhaitez vous déplacer en ligne droite. Une approche consiste à redresser les chemins en utilisant le «tirage de cordes». Vous recherchez des endroits où le chemin tourne et dessinez des lignes droites entre ces points. Une autre approche consiste à appliquer cela au graphique sous-jacent lui-même. Au lieu de rechercher un chemin sur la grille, recherchez un chemin sur les points clés de la carte, puis déplacez-vous le long de lignes droites entre ces points clés. Vous pouvez voir un exemple ici . Une autre approche encore est l' algorithme Theta * .

L'algorithme A * vous permet d'attribuer différents coûts aux bords du chemin. Vous pouvez également affecter des coûts selon les circonstances. C'est votre principal outil pour façonner les chemins A * en leur donnant l'apparence que vous souhaitez.

Lorsque vous voulez décourager les longues diagonales, vous pouvez les pénaliser. Ajoutez un tout petit peu de coût à chaque fois que le chemin va dans la même direction. Lorsque vous faites cela, l'algorithme essaie automatiquement de répartir les pas diagonaux aussi uniformément que possible sur l'ensemble du chemin. Assurez-vous simplement que ce coût supplémentaire n'est jamais plus le coût de prendre un avantage supplémentaire, ou l'algorithme commencera à faire des détours complètement inutiles juste pour éviter les lignes droites.

Une bonne formule pourrait être:

cost = normal_cost * (1.1 - 0.1 / num_of_steps_in_the_same_direction)

Notez que cela nécessite que le chemin-coût soit suivi comme des valeurs à virgule flottante, pas comme des entiers.

Adapter A *

Comme l'a dit Philipp, vous devez ajouter des coûts lorsque la direction ne change pas pendant longtemps. Mais, la fonction de Philipp peut rapidement conduire à additionner des coûts supplémentaires, qui sont supérieurs au coût de traversée d'une tuile supplémentaire. Mais son idée clé est correcte!

Il semble facile d'adapter A * pour calculer "tous" les chemins optimaux (avec la plus courte longueur) puis de sélectionner l'un d'eux par une autre heuristique. Mais il y a un problème. Si vous avez un long chemin, il peut y avoir beaucoup de solutions avec une longueur optimale. Cela fait que l'algorithme A * prend beaucoup plus de temps pour calculer toutes ces autres solutions également. C'est parce que la grille. Vous ne pouvez pas marcher 80 degrés au lieu de 90 degrés, ce qui conduit à plusieurs solutions sous-optimales au lieu d'une solution optimale. Pour l'imagination, imaginez une carte sans obstacles. La distance x est 2 la distance y est 3. Cela signifie que tous les chemins les plus courts ont 2 mouvements diagonaux et 1 mouvement droit. Il existe 3 combinaisons valides: SDD, DSD, DDS (où D = diagonale, S = droite) pour ce chemin simple. Le vrai "fun" commence déjà lorsque vous avez des chemins avec par exemple 3 mouvements droits et 2 diagonaux: SSSDD, SSDSD, SSDDS, SDSSD, SDSDS, SDDSS, DSSSD, DSSDS, DSDSS, DDSSS (10 variations du chemin le plus court, si je n'en ai raté aucun). Je pense que tu aurais dû avoir l'idée ...

Nous devons donc résoudre ce problème en adaptant la fonction de coût de manière à ce que moins de solutions (ou même une seule solution) soient «optimales».

Adapter la fonction de coût

Faire l'adaptation comme Philipp le suggère dans sa formule d'exemple vous donnera de bien meilleurs résultats, mais a toujours quelques problèmes. Il ne répartira pas uniformément les «parties» plus courtes / plus longues le long du chemin, ce qui signifie: les changements de direction seront plus souvent au début du chemin ou vice-versa.

De plus, un chemin avec sans fin l'acteur à «tourner» semble être sous-optimal lorsqu'il est observé par un humain. Comme cela prend du temps (pour montrer l'animation du virage) et donc ça doit être plus lent.

Cependant, au lieu d'utiliser des flottants pour les coûts, vous pouvez implémenter un "coût secondaire" ou des critères de tri secondaires. Si les coûts primaires sont les mêmes, le coût secondaire est utilisé pour estimer la solution à privilégier. Cela n'entraînera pas accidentellement une augmentation des coûts primaires (longueur de l'itinéraire dans la mesure du réseau).