Algorytm wyszukiwania ścieżki triangulacji A * (TA *)

Potrzebuję pomocy w zrozumieniu algorytmu trójkąta A * (TA *) opisanego przez Demyen w jego dokumencie „ Efficient-Triangulation-Based Pathfinding” na stronach 76-81.

Opisuje, jak dostosować zwykły algorytm A * do triangulacji, aby szukać innych możliwie bardziej optymalnych ścieżek, nawet po osiągnięciu / rozwinięciu końcowego węzła. Zwykły A * zatrzymuje się po rozwinięciu ostatniego węzła, ale nie zawsze jest to najlepsza ścieżka, gdy jest używana na wykresie triangulowanym. To właśnie mam problem.

Problem zilustrowano na stronie 78, rysunek 5.4:

Rozumiem, jak obliczyć wartości g i h przedstawione w artykule (strona 80).

Myślę, że warunkiem zatrzymania wyszukiwania jest:

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

gdzie currentNode to węzeł wyszukiwania wyskakujący z otwartej listy (kolejka priorytetowa), która ma najniższy wynik f. shortestDistanceFound to rzeczywista odległość najkrótszej znalezionej do tej pory ścieżki.

Ale jak wykluczyć wcześniej znalezione ścieżki z przyszłych wyszukiwań? Bo jeśli powtórzę wyszukiwanie, to oczywiście znajdzie tę samą ścieżkę. Czy resetuję zamkniętą listę? Muszę coś zmodyfikować, ale nie wiem, co muszę zmienić. Papier nie ma pseudokodu, więc byłoby to pomocne.

Nie wdrożyłem tego, ale kiedy to czytam, myślę, że zrobiłbyś coś takiego:

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

Różnica polega na tym, że nawet jeśli okaże się drogę do bramki, to nie koniecznie najkrótsza ścieżka. Ale będziesz nadal poprawiać górne granice na najkrótszej ścieżce, co oznacza, że ​​nie będziesz musiał otwierać wszystkich węzłów. W końcu twój otwarty zestaw powinien być pusty, a najlepsza znaleziona do tej pory ścieżka powinna być najkrótsza.

Zmodyfikowany koszt g, który opisuje, wydaje się dużym niedoszacowaniem, więc jestem sceptyczny co do tego, jak dobrze działa w praktyce.