A-estrela é um algoritmo de busca de caminho, ou seja, tem o objetivo de determinar um caminho entre um vértice inicial e um vértice final. Para a determinação do caminho, é utilizada uma combinação de aproximações heurísticas e do Algoritmo de Dijkstra.
Nesta aplicação, o algoritmo desenvolvido tem como objetivo determinar o melhor caminho entre as posições final e inicial em um tabuleiro.
Para sair da posição inicial para a final, o jogador deve respeitar as seguintes regras:
- O jogador só pode se mover dentro dos limites do tabuleiro;
- Paredes são intransponíveis e posições inválidas;
- Só é possível se movimentar para: cima, baixo, direita e esquerda.
O tabuleiro deve ser formatado em um arquivo texto chamado board.txt
baseado no exemplo abaixo:
s 1 0 0 0 0
0 0 0 0 0 0
0 1 0 1 0 0
0 1 0 0 1 0
0 0 0 0 1 e
Em que:
s
: posição inicial;e
: posição final;1
: posições inválidas (paredes);0
: posições válidas.