-
Encontrar o menor caminho num labirinto de tiles hexagonais
-
Um ponto de partida e várias saídas
-
Imprimir como resultado uma direção (W, NW, NE, ...) por linha do ponto de partida ao objetivo
NW NE \ / W - ⬡ - E / \ SW SE
Representação visual de diversos algoritmos de pathfinding
Path Finding Algorithms
Hexagonal Grids
Amit’s Thoughts on Grids
Best-first search
Algoritmo A
Heurísticas
Alguns tipos de distância
Otimizações para pathfinding em grids
`Root`
│ `__main__.py` - Ponto inicial da execução
│ `Cell.py` - Objeto que representa uma célula do grid. Cada célula armazena quem são seus vizinhos
│ `conf01.py` - Arquivo com entradas para o programa
│ `Directions.py` - Enum com as direções que o gato pode seguir (foi necessário pois é preciso inverter a direção em um ponto)
│ `Executor.py` - Arquivo que irá receber o grid e os gatos para executar a busca
│ `Grid.py` - Arquivo que gerencia um conjunto de células, o grid
│
│
└───`cats` - Diretório onde ficarão os gatos (cada gato deve receber um nó de entrada e um de saída e fazer o caminho usando algum algoritmo ou heurística)
│ `CatFather.py` - Pai de todos os gatos - ao criar um novo gato, herde dele
│
├───`astarcat`
│ │ `AstarCat.py` - Gato que faz a busca com o algoritmo A* (V1 - NÃO USAR)
│ └ `HeuristicValuesCalculator.py` - Arquivo auxiliar para calcular os valores da heurística
│
│
├───`astarcat2`
│ │ `AstarCat.py` - Gato que faz a busca com o algoritmo A* (V2)
│ └ `HeuristicValuesCalculator.py` - Arquivo auxiliar para calcular os valores da heurística
│
├───`bestfirstcat`
│ └ `BestFirstCat.py` - Gato que faz a busca com o algoritmo Best First
│
│
├───`bfscat`
│ └ `BreadthFirstSearchCat.py` - Gato que faz a busca com o algoritmo Breadth First Search (Busca em Largura ou BFS)
│
└───`catshelper` - Diretório com códigos auxiliares para os gatos
│ `DistanceCalculator.py` - Possibilita o cálculo de distâncias entre pontos no grid (USE A DISTÂNCIA HEXAGONAL PARA ESTE PROBLEMA)
└ `Path.py` - Possibilita a geração do caminho até o objetivo (não esqueça de definir o valor `previous` para cada nó ao fazer o algoritmo no gato)
Para obter uma visualização do grid use:
print(grid.show())
Para visualizar o grid com os movimentos do gato use:
print(grid.show(cat))
- Caso o caminho seja construído partindo do gato e indo para o objetivo use
reversed_direction = True
ao atribuir o objetoPath
ao gato. caso o caminho seja construído do fim para o começo usereversed_direction = False
: construindo do começo para o fim cada ponto do labirinto apontará para um ponto anterior (mais perto do início) então o caminho formado será do fim para o início... marcandoreversed_direction = True
o caminho resultante será invertido:
Sem inverter:
INICIO <- ( ) <- ( ) <- ( ) <- ( ) <- FIM
gera:
W, W, W, W, W,
Invertendo para o correto:
INICIO -> ( ) -> ( ) -> ( ) -> ( ) -> FIM
E, E, E, E, E,
- Com o código para o gato fornecido pelo professor criar um algoritmo que crie bloqueios impedindo com que o gato fuja do labirinto.
- O pegador faz seu movimento, em seguida o gato.
│ `confs.bat` - arquivo que testa 100 tabuleiros
│ `game.py` - arquivo que controla um jogo
│ `gato.py` - gato
│ `logfile.txt` - arquivo de log
│ `multithread_tester.py` - testa jogos usando mais de uma thread
│ `my_catcher.py` - cathcer escrito
│ `pegador.py` - cathcer fornecido pelo professor
│ `plano.pdf` - arquivo com a explicação do trabalho
│ `runOnce.bat` - arquivo para testar o catcher (uma vez)
│ `tester.py` - testa jogos usando uma única thread
│
├───`games` - armazena o .gif com a execução
│ `game_0.gif`
│
└───`tabuleiros` - armazena tabuleiros vazios em diversos formatos
`tabuleiro.bmp`
`tabuleiro.eps`
`tabuleiro.gif`
`tabuleiro.jpg`
`tabuleiro.png`
`tabuleiro.tga`
`tabuleiro.tif`