eh baseado no problema do labirinto, onde tenho uma origem e um destino bem definidos.
Nesse tipo de problema, o objetivo não eh necessariamente a saída, mas sim algum ponto dentro do labirinto.
Em tese, deveria ser pelo melhor caminho. No nosso pacman, eh um pouco diferente. Ele deve chegar ao objetivo,
optando sempre por caminhos aonde haja comidas necessariamente.
Os seguintes caracteres são os mais importantes:
'@': representa o nosso pacman
'#': representam paredes e obstáculos físicos
'&': fantasmas
' '(espaço): não eh necessariamente uma barreira, mas ele evita espaços em branco.
'.': comidas
Dado um mapa, com tais caracteres, ele lê o mapa. Qdo encontra '@', ele entende como origem e quando encontra o '$' eh o destino.
Por mais que ele guarde as coordenadas da origem e destino, ele guarda na memória o mapa e o mesmo eh sempre passado por parâmetro.
Só com isso ele já sabe o que tem que fazer. O lance é uma regra embutida em todos os algoritmos. Poderia ter deixado mais elegante, e colocado na estrutura de dados, mas blz. A regra é simples, mas é fundamental para resumir o modelo todo.
Uma vez que ele encontre os caracteres ('#','&',' ') ele vai evitá-los, como? Tentando uma rota alternativa.
'#' eh uma parede, não tem como passar. '&' eh um fantasma, ele tem medo. ' ', eh algo tipo "hmmm, vou tentar por uma rota que tenha mais comidinha".
Se não houver caminho algum, então "Não há caminho".
O mapa eh um arquivo de fora chamado 'maze.in'. Por que um arquivo separado? Porque o mapa pode ser facilmente modificado para tentar novas ações.
Podemos integrar ele com o nosso gerador de mapas.
Depois que o algoritmo roda, ele retorna os nós expandidos, o custo e o mapa onde o caracter '+' mostra o caminho do pacman.
Busquei a versão mais simples da regra, foi quando percebi que dava para aglutinar várias possibilidades em uma regra só, já que são semelhantes.
chm10
commented
4 years ago