Implementação de um Jogo de Dungeon com Estruturas de Dados
Aluno: Presto
24 de julho de 2025
1 Introdução
Este projeto implementa um jogo de exploração de dungeon utilizando estruturas de dados fundamentais:
• Listas Encadeadas para gerenciamento de inventário
• Pilhas para sistema de retrocesso de movimentos
• Árvores Binárias para IA de combate
O objetivo do jogador é navegar por um labirinto gerado proceduralmente, coletar itens, evitar armadilhas
e derrotar inimigos para encontrar a saı́da.
2 Verificação de Requisitos
Tabela 1: Requisitos Implementados
Requisito Implementado
Sistema de inventário com lista encadeada ✓
Sistema de retrocesso com pilha ✓
Sistema de combate com árvore binária ✓
Mapa com elementos aleatórios ✓
Interface em terminal com menus ✓
Sistema de game over e vitória ✓
TADs implementados manualmente ✓
3 Arquitetura do Sistema
pilha.c
Histórico de arvore.c
lista.c movimentos IA de inimi-
Inventário gos
main.c
(Loop principal)
mapa.c combate.c
Geração do la- Sistema de tur-
birinto jogador.c
Controle do nos
personagem
1
4 Componentes Principais
4.1 Mapa e Geração do Labirinto
• Labirinto gerado com algoritmo de busca em profundidade
• Representado por matriz de caracteres:
– #: Parede
– P: Item (poção)
– A: Armadilha
– S: Saı́da
1 void g e r a r L a b i r i n t o R e c u r s i v o ( Mapa * mapa , int x , int y ) {
2 int dirs [4][2] = {{0 , -2} ,{0 ,2} ,{ -2 ,0} ,{2 ,0}};
3 // Embaralha d i r e es
4 for ( int i =0; i <4; i ++) {
5 int r = rand () % 4;
6 int temp [2] = { dirs [ i ][0] , dirs [ i ][1]};
7 dirs [ i ][0] = dirs [ r ][0];
8 dirs [ i ][1] = dirs [ r ][1];
9 dirs [ r ][0] = temp [0];
10 dirs [ r ][1] = temp [1];
11 }
12
13 // Abre caminho
14 for ( int i =0; i <4; i ++) {
15 int nx = x + dirs [ i ][0];
16 int ny = y + dirs [ i ][1];
17 if ( nx >0 && nx < mapa - > largura -1 &&
18 ny >0 && ny < mapa - > altura -1 &&
19 mapa - > tiles [ ny ][ nx ]== ’# ’) {
20 mapa - > tiles [ ny ][ nx ]= ’ ’;
21 mapa - > tiles [ y + dirs [ i ][1]/2][ x + dirs [ i ][0]/2]= ’ ’;
22 g e r a r L a b i r i n t o R e c u r s i v o ( mapa , nx , ny ) ;
23 }
24 }
25 }
Listing 1: Geração do Labirinto
4.2 Sistema de Inventário (Lista Encadeada)
• Itens armazenados como nós em lista encadeada
• Operações implementadas:
– Inserção no final
– Remoção por ı́ndice
– Listagem completa
• Tipos de itens:
– Poção de Cura: Restaura vida total
– Poção de Veneno: Causa morte instantânea
– Poção Surpresa: Efeito aleatório
1 typedef struct NoLista {
2 Item * item ;
3 struct NoLista * proximo ;
4 } NoLista ;
5
6 typedef struct {
7 NoLista * inicio ;
8 int tamanho ;
9 } Lista ;
Listing 2: Estrutura da Lista
2
4.3 Sistema de Retrocesso (Pilha)
• Armazena histórico de posições do jogador
• Implementado com pilha estática
• Comando U desfaz último movimento
1 void push ( Pilha * p , Posicao pos ) {
2 if (p - > topo < MAX_PILHA -1) {
3 p - > topo ++;
4 p - > elementos [p - > topo ] = pos ;
5 }
6 }
7
8 Posicao pop ( Pilha * p ) {
9 if (p - > topo >= 0) {
10 return p - > elementos [p - > topo - -];
11 }
12 return ( Posicao ) { -1 , -1}; // P o s i o inv lida
13 }
Listing 3: Operações da Pilha
4.4 Sistema de Combate (Árvore Binária)
• Árvore de decisão para IA dos inimigos
• Avalia condições baseadas no estado do combate
• Ações possı́veis: Atacar, Defender, Fugir
1 NoArvore * c o n s t r u i r A r v o r e D e D e c i s a o () {
2 NoArvore * noFugir = criarNoArvore ( NULL , ACAO_FUGIR ) ;
3 NoArvore * noAtacar = criarNoArvore ( NULL , ACAO_ATACAR ) ;
4
5 NoArvore * n o D e c i s a o J o g a d or = criarNoArvore (
6 cond_vidaJogadorBaixa , ( AcaoInimigo ) -1) ;
7 noDecisaoJogador - > sim = noAtacar ;
8 noDecisaoJogador - > nao = noAtacar ;
9
10 NoArvore * raiz = criarNoArvore (
11 cond_vidaInimigoBaixa , ( AcaoInimigo ) -1) ;
12 raiz - > sim = noFugir ;
13 raiz - > nao = n o D e c i s a o J o g a d o r ;
14
15 return raiz ;
16 }
Listing 4: Árvore de Decisão
5 Fluxo do Jogo
1. Jogador inicia na posição (1,1) do mapa
2. Explora o labirinto coletando itens (poções)
3. Encontra inimigos que iniciam combate por turnos
4. Pode desfazer movimentos com U
5. Derrota chefes para avançar de nı́vel
6. Encontra a saı́da para vencer o jogo
3
6 Conclusão
Esta implementação demonstra a aplicação prática de estruturas de dados fundamentais no desenvolvimento de
jogos. O sistema:
• Utiliza listas encadeadas para gerenciamento dinâmico de inventário
• Aplica pilhas para implementar histórico de movimentos
• Empregar árvores binárias para tomada de decisão da IA
• Integra os conceitos em um sistema coeso e funcional
O projeto atende todos os requisitos solicitados, demonstrando o valor das estruturas de dados na resolução
de problemas complexos de desenvolvimento de software.