/cefet-ai-a_star-path-finder

Aplicação do algoritmo A* (A-estrela) para a obtenção de um caminho ótimo.

Primary LanguagePython

Algoritmo A* (A-estrela) para a obtenção de um caminho ótimo

O que é o A* (A-estrela)?

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.

Aplicação

Nesta aplicação, o algoritmo desenvolvido tem como objetivo determinar o melhor caminho entre as posições final e inicial em um tabuleiro.

Regras

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.

Formatação do Tabuleiro

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.