-
Notifications
You must be signed in to change notification settings - Fork 7
Algoritmo A estrela
"Algoritmo A* (Lê-se: A-estrela) é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final." Fonte: Wikipédia (https://pt.wikipedia.org/wiki/Algoritmo_A*)
O A* é usado no NeonFC com um grafo de nós representando pontos no campo no qual o robô poderá percorrer. O A* retorna a lista de nós em ordem na qual o robô deve percorrer para chegar no nó objetivo.
O NeonFC tem uma classe abstrata chamada FieldGraph para criar o grafo que será usado pelo A*. A classe tem como único atributo o nó inicial do grafo. Recomenda-se usar a posição do robô como posição do nó inicial. Cada nó do grafo terá sua coordenada no campo passada como parâmetro na criação do nó.
Nesse exemplo criaremos o seguinte grafo:
# estrategia
A = Node([3, 10])
B = Node([2, 6])
C = Node([4, 2])
D = Node([8, 4])
E = Node([11, 8])
F = Node([6, 8])
nodes = [A, B, C, D, E, F]
edges = [[A, B], [B, C], [D, B], [D, C], [C, F], [D, F], [D, E], [E, F]]
graph = FieldGraph()
graph.update_neighbours(edges)
graph.set_nodes(nodes)
graph.set_start(F)
print(AStar(F, [3, 10]).calculate())