Algorithme de recherche de chemin de triangulation A * (TA *)

J'ai besoin d'aide pour comprendre l'algorithme Triangle A * (TA *) décrit par Demyen dans son article Efficient Triangulation-Based Pathfinding , pages 76-81.

Il décrit comment adapter l'algorithme A * régulier pour la triangulation, pour rechercher d'autres chemins éventuellement plus optimaux, même après que le nœud final soit atteint / développé. Un A * régulier s'arrête lorsque le nœud final est développé, mais ce n'est pas toujours le meilleur chemin lorsqu'il est utilisé dans un graphique triangulé. C'est exactement le problème que j'ai.

Le problème est illustré à la page 78, figure 5.4:

Je comprends comment calculer les valeurs g et h présentées dans le document (page 80).

Et je pense que la condition d'arrêt de la recherche est:

if (currentNode.fCost > shortestDistanceFound)
{
    // stop
    break;
}

où currentNode est le nœud de recherche extrait de la liste ouverte (file d'attente prioritaire), qui a le score f le plus bas. shortestDistanceFound est la distance réelle du chemin le plus court trouvé jusqu'à présent.

Mais comment exclure les chemins trouvés précédemment des recherches futures? Car si je refais la recherche, il trouvera évidemment le même chemin. Dois-je réinitialiser la liste fermée? Je dois modifier quelque chose, mais je ne sais pas ce que je dois changer. Le papier manque de pseudocode, ce serait donc utile.

Je ne l'ai pas implémenté, mais en le lisant, je pense que vous feriez quelque chose comme ça:

shortestDistance = infinity
do A* with modified g cost
    if node.fCost > shortestDistance (section 5.5)
        don't open node
    if node.isGoal()
        run funnel algorithm (string pulling)
        update shortestDistance

La différence est que même si vous trouvez un chemin vers l'objectif, ce n'est pas nécessairement le chemin le plus court . Mais vous continuerez d'améliorer les limites supérieures sur le chemin le plus court, ce qui signifie que vous n'aurez pas à ouvrir tous les nœuds. Finalement, votre ensemble ouvert devrait être vide, et le meilleur chemin que vous avez trouvé jusqu'à présent devrait être le plus court.

Le coût en g modifié qu'il décrit semble être une grosse sous-estimation, donc je suis sceptique quant à son efficacité dans la pratique.