Uma implementação simples de dois algoritmos para gerar e solucionar de forma eficiente labirintos aleatórios. As implementações aplicam o Randomized Depth-First Search Algorithm e o Pathfinder A* que é uma versão estendida de heurística do algoritmo de Dijkstra's.
Objetivo: Criar um sistema que gere um labirinto e encontre o melhor caminho entre o canto superior esquerdo e o canto inferior direito.
Todo o projeto é feito apenas com SDL/SDL2 e C puro.
-
Os arquivos presentes nesse repositório possuem um delay (sleep) em suas funções principais para que a visualização de todo o processo seja possível.
-
Para encontrar o menor F no A* é aplicado uma implementação minha do famoso QuickSort ao invés da recomendável Binary Heap.
-
O arquivo do A* pode ser facilmente escalável para outros projetos com uma simples extensão da estrutura CELL.
-
Limitei o A* a apenas passos verticais e horizontais para facilitar a sua implementação no labirinto, sinta-se a vontade para criar uma versão com diagonais e compartilhar comigo se quiser.
-
Os parâmetros gerais das funções podem ser alterados nas definições do arquivo main.c
-
Não é necessário rodar os algoritmos em threads diferentes, fiz isso apenas para que a visualização fosse possível e não bloqueasse a thread principal onde está o main loop do SDL2.
-
Fique a vontade para mandar ideias, sugestões, dúvidas e requests.