Pathfinding

Escolha do Algoritmo


    De forma a poder encontrar o seu caminho mais facilmente, foi inserido no projeto código que implementa o algoritmo A*.

    A escolha do algoritmo deu-se, em parte, graças à visualização neste site, que tornou evidente que este algoritmo se adequava aos objetivos do projeto.

    Uma procura na Internet rendeu várias implementações do algoritmo, sendo esta a implementação em que o grupo se baseou. Esta é notável pelas técnicas de Python desconhecidas ao grupo (como os métodos privados que a classe Node possui) que facilitam imenso a implementação do A*. Do código dado pelo site, três partes foram utilizadas:

1. A classe Node, que representa os nós a serem utilizados no algoritmo cujo código em nada foi alterado.
2. A função a_star_search(map,start,end),  que implementa a procura. Muito alterada, mas com a estrutura básica (processo lógico) mantida.
   
3. A função add_to_open(open, neighbor), auxiliar da procura que avalia os vizinhos válidos de um nó, e, como Node, em nada alterada senão em nome.


Alterações


 

    A função a_star_search(map,start,end), renomeada no projeto para getPath(start,end), possuía referências a um mapa (utilizado para obter custos e os vizinhos), desnecessárias para o jogo. O argumento foi retirado da declaração e foi criada uma função getNeighbors(tile) que substitui a funcionalidade do mapa no algoritmo, determinando vizinhos válidos. Para a heurística, foi reaproveitada uma função getManhattan(tile_a,tile_b) já previamente criada pelo grupo que calcula a distância de Manhattan entre dois pontos do tabuleiro. As listas open e close foram também renomeadas para frontier e visited, para melhor compreensão.




    Já a função add_to_open(open, neighbor) foi apenas renomeada para canAddToFrontier(open, neighbor), a fim de maior clareza.


 

 Implementação

 

    Estas funções foram implementadas num novo ficheiro, pathfinding.py. Além das funções acima mencionadas, possui três variáveis globais: limit, illegal_moves e illegal_tiles. Estes valores são, por ordem, a coordenada do canto oposto a [0,0] (assumindo que esta coordenada está num canto!), os movimentos não permitidos e as casas proibidas.

 

   Estes valores podem ser atualizados com a função setRestrictions(_l,_im,_it) e são utilizados na função isIllegal(start,target), utilizada em getNeighbors(tile), que determina de o movimento entre duas determinadas casas é permitido ou não. 

 

     Esta implementação é, desta forma, muito versátil e aplicável em várias situações na condição de que os valores usados sejam coordenadas no formato [x,y] em que [0,0] seja um canto do tabuleiro. Apesar de não ter sido testado, é possível que possa ser usada num contexto em que movimento diagonal seja permitido, alterando a função getNeighbors(tile).

     

  Hierarquia

 

    Este ficheiro é importado por strategy.py, e está abaixo o diagrama da hierarquia resultante.

 

    

 Retângulos simples são ficheiros criados pelo grupo, duplos livrarias utilizadas; setas contínuas são importações totais, tracejadas importações parciais.