-
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
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 ao nó objetivo percorrendo a menor distância possível.
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ó.
O algoritmo recebe:
- o grafo
- o nó inicial
- o nó final
- uma função de heurística
Começando pelo nó inicial, ele pega todos os vizinhos do nó atual e aplica a função de heurística. Essa função retorna um número que indica qual é a distância pro nó final (geralmente usado a distância euclidiana). O vizinho que tiver o menor valor é o mais perto do nó final, então esse vizinho se torna o nó atual. O mesmo procedimento é repetido até que o nó atual seja o nó final. Fonte: Stackoverflow
Várias estratégias para criação de grafo no campo podem ser implementadas. Recomenda-se o uso do arquivo asScratch.py como molde para as novas estratégias.