Ajuster AStar pour trouver l'emplacement le plus proche d'une destination inaccessible

11

J'ai implémenté AStar en Java et cela fonctionne bien pour une zone avec des obstacles où la destination choisie est accessible.

Cependant, lorsque la destination est inaccessible, le «chemin» calculé n'est en aucun cas vers l'emplacement le plus proche (vers l'emplacement inaccessible) mais est plutôt un chemin aléatoire.

Existe-t-il un moyen possible de modifier AStar pour trouver le chemin vers l'emplacement le plus proche d'une destination inaccessible?

path-finding Shivan Dragon
la source

Réponses:

20

Gardez une trace du nœud avec le plus bas EstimatedDistanceToEnd(c.-à-d. Le plus bas h(x)), et si aucun nœud d'extrémité n'est accessible à partir de la marche arrière, faites marche arrière à partir de ce nœud à la place.

BlueRaja - Danny Pflughoeft
la source
Facile. J'aime cela!
John McDonald
Je viens de me gifler la tête et suis allé "doh" quand j'ai lu votre réponse. Merci!
Shivan Dragon
1

Ce n'est pas vraiment une question A *. A * consiste à trouver un chemin du point A au point B. Même s'il peut être étendu, les résultats pourraient facilement être compliqués et imprévisibles. Vous avez plutôt besoin d'un algorithme qui sélectionne la destination accessible la plus proche.

Voici une façon de procéder: si A * renvoie un chemin valide (les nœuds de début / fin dans les nœuds d'entrée de correspondance de chemin), renvoyez le chemin. Autrement...

  • Lancer la recherche à partir du nœud initial
  • Traversez tous les nœuds liés (n'oubliez pas de marquer les nœuds visités pour éviter une récursion infinie)
  • Comparez les distances jusqu'à la destination pour trouver le nœud le plus proche
snake5
la source
Quelque chose comme Flood Fill semble approprié en.wikipedia.org/wiki/Flood_fill notez que vous devez toujours A * du nœud de départ au nœud avec la distance la plus basse. Notez également que cela implique toujours d'inspecter tous les nœuds connectés et peut donc être extrêmement lent.
Roy T.
Oui, ça pourrait être lent. Mais la lenteur proviendrait très probablement de la dispersion des nœuds dans la mémoire; qui peut être facilement réparé. En outre, il est possible de l'accélérer en sacrifiant une certaine précision - il suffit de sauter les liens trop éloignés ou de pointer dans la mauvaise direction.
snake5
1
@Roy: A *, BFS et tous les algorithmes de recherche de chemin d'accès similaires seront exactement aussi lents que le remplissage, car ils doivent tous inspecter chaque nœud connecté pour s'assurer qu'il n'y a pas de chemin vers la fin. Il existe cependant des moyens de résoudre ce problème; voir ici .
BlueRaja - Danny Pflughoeft