Midnight Warfare

Implementação Técnica

Estrutura do Mapa

O ambiente do jogo é modelado como um Grafo Não-Direcionado, utilizando listas de adjacência para representar as conexões entre as salas e os corredores.

Algoritmos

Implementação de Busca em Largura (BFS) para cálculo de rotas ótimas e Busca em Profundidade (DFS) para simulação de exploração de ambiente por IAs.

Complexidade

A lógica de decisão é executada a cada atualização de quadro, sendo responsivo tempo real com complexidade de busca linear em relação às arestas do grafo.

Autores

DESENVOLVEDOR	Artur Mendonça Arruda
MATRÍCULA	23/1033737
DESENVOLVEDOR	Lucas Mendonça Arruda
MATRÍCULA	23/1035464

Stack

Python 3 | Pygame

Projeto desenvolvido para a disciplina de Estrutura de Dados II, com foco na aplicação de conceitos de grafos.

Lógica dos Agentes

Cada oponente utiliza um algoritmo distinto para navegar pelo grafo do mapa.

BFS

Freddy

Utiliza Busca em Largura. O algoritmo garante que ele sempre encontrará o caminho com menor número de arestas até o nó alvo, otimizando sua perseguição.

DFS

Bonnie

Implementa Busca em Profundidade limitada ao subgrafo Oeste. Visita nós adjacentes em profundidade antes de retroceder, simulando um padrão de exploração.

DFS

Chica

Similar ao Bonnie, mas restrita ao subgrafo Leste. O uso de DFS faz com que ela explore extremidades do grafo antes de convergir para o objetivo.

Estado Direto

Foxy

Opera por transição de estados baseada em cooldown. Ignora a busca convencional, realizando travessia direta de arestas pré-definidas quando ativo.

Grafo Desconexo

Golden Freddy

Atua como um Vértice Desconexo. Sua lógica ignora as arestas do grafo, operando via probabilidade estocástica para realizar uma transição imediata ao nó do escritório.

Análise de Algoritmos

Representação

O mapa do jogo é representado computacionalmente como um grafo G(V, E), onde V são as salas e E são os corredores. A escolha da Lista de Adjacência favorece a performance de iteração sobre vizinhos.

Espaço

O(V + E)

Memória utilizada pela Lista de Adjacência.

BFS

O(V + E)

Complexidade temporal para encontrar o caminho ótimo.

DFS

O(V + E)

Complexidade temporal para travessia completa do componente.

Acesso

O(1)

Custo médio para acessar a lista de vizinhos de um vértice.

Execução

user@dev:~/midnight-warfare

$ git clone https://github.com/EDAII/Grafos_MidNightWarfare_FNAF
$ cd Grafos_MidNightWarfare_FNAF
$ pip install pygame
$ python main.py
pygame 2.6.1 (SDL 2.28.4, Python 3.12.10)
Hello from the pygame community. https://www.pygame.org/contribute.html
_

Requisitos

Python 3.x

Pygame

Mouse

Teclado