Preciso de ajuda para entender o algoritmo Triangle A * (TA *) descrito por Demyen em seu artigo Pathfinding baseado em triangulação eficiente , nas páginas 76-81.
Ele descreve como adaptar o algoritmo A * regular para triangulação, para procurar outros caminhos possivelmente mais ideais, mesmo após o nó final ser alcançado / expandido. A * regular para quando o nó final é expandido, mas esse nem sempre é o melhor caminho quando usado em um gráfico triangulado. Este é exatamente o problema que estou tendo.
O problema está ilustrado na página 78, Figura 5.4:
Eu entendo como calcular os valores de g e h apresentados no artigo (página 80).
E acho que a condição de parada de pesquisa é:
if (currentNode.fCost > shortestDistanceFound)
{
// stop
break;
}
onde currentNode é o nó de pesquisa exibido na lista aberta (fila de prioridade), que possui o menor f-score. shortestDistanceFound é a distância real do caminho mais curto encontrado até agora.
Mas como excluo os caminhos encontrados anteriormente de pesquisas futuras? Porque se eu fizer a pesquisa novamente, ela obviamente encontrará o mesmo caminho. Redefino a lista fechada? Preciso modificar algo, mas não sei o que é preciso mudar. O papel não possui pseudocódigo, o que seria útil.
fonte