Labirinto

Projeto para a disciplina Paradigmas de Programação, da Universidade Federal do ABC, orientado pelo professor Emilio Francesquini.

Proposta

O trabalho proposto é baseado nesse vídeo do canal Computerphile. A ideia é criar um programa que resolve labirintos a partir de imagens.

Dada uma imagem, onde pixels brancos representam caminho e pixels pretos representam parede, a borda é feita de parede, exceto por dois pixels (uma entrada e uma saída). O programa deve encontrar o caminho entre a entrada e a saída e o output do programa deve ser uma imagem com o mesmo labirinto, mas com o caminho que deve ser feito do ínicio à saida destacado.

Abaixo, um exemplo de uma entrada e de uma saída do programa.

Além disso, o programa mostra o tempo de execução de cada algoritmo

Execução

• stack run <mazeName> roda o programa para os 3 algoritmos (BFS, DFS e A*) no labirinto passado como parâmetro. Para isso, a imagem de nome mazeName deve existir na pasta labirinto/resources/mazes com o nome mazeName.png. As imagens disponíveis são MAZE00 até a MAZE06. As imagem de saída irão ser criadas na pasta labirinto/output/mazes (é importante garantir que a pasta existe antes da execução do programa). Nas imagens de saída teremos o caminho feito do início do labirinto até o final, em amarelo, e um mapa de calor dos nós que foram visitados na busca desse algoritmo, por ordem cronológica, com azul sendo os primeiros e vermelho sendo os últimos.

  • Exemplo: stack run MAZE05

• stack run generate <XS | S | M | L | XL> roda o programa gerando um labirinto aleatorio com o tamanho especificado (XS é o menor possível, XL é o maior possível). O tamanho é opcional, e M é o padrão, caso nenhum outro seja especificdo. Esse labirinto estará disponivel na pasta output com o nome "randomMaze.png". Os 3 algoritmos irão ser executados nesse labirinto (assim como acima).

  • Exemplo: stack run generate M

• stack test roda os testes do programa. Os testes são especificados em labirinto/test/Spec.hs.

• Observação: Os labirintos MAZE00 - MAZE06 são usados nos testes. Assim, é importante que eles estejam presentes na pasta labirinto/resources/mazes ao rodar o comando stack test

Assim, a estrutura do projeto deve se econtrar na forma:

labirinto
 |_ output
   |_ mazes
 |_ resources
   |_ mazes
 |_ app
 |_ src
 |_ test

Dificuldades no desenvolvimento

A maior dificuldade enfrentada foi a integração de todos os módulos. Módulos desenvolvidos independentemente tiveram alguma dificuldade para serem integrados, o que resultou falhas nos testes de integração desenvolvidos.

Outra dificuldade foi implementar os algoritmos de busca em grafo, pois não estamos acostumados a escrever algoritmos desse tipo em linguagens funcionais, portanto levamos bastante tempo para implementa-los e corrigir os bugs gerados.

Além disso, houve também um erro de planejamento que, somado à semana de provas e de entregas de outros trabalhos, resultou na necessidade de grandes esforços no fim de semana da entrega.

Os testes foram escritos com o Hspec, sendo que algum deles usam o QuickCheck. Descobrir como criar testes e propriedades com essa biblioteca foi bem trabalhoso. Em específico, implementar a classe Arbitrary para os nós, arestas e grafos (Node, Edge e Graph) foi especialmente desafiador (essa implementação se encontra no arquivo labirinto/test/Spec.hs). Contudo, no final, deu certo, e foi possível realizar testes com Grafos Arbitrários.

Créditos

Autores: Bryan Cruz, Daniel Escudero, Filipi Brabo, Jonatas Duarte.