Labirinto_grafos_game
Labirinto grafos game proposto na U3_aula1
Disciplina: Estrutura de Dados — Atividade de Grafos Figura de referência: Figura 13 | Exemplo do labirinto (adaptada de Takenaka, 2021)
Somos parte de uma equipe de desenvolvimento de jogos e precisamos construir a base de um jogo de labirinto. O jogador pode caminhar livremente pelas passagens, inclusive voltando pelo caminho de onde veio, sem limite de visitas a uma mesma sala.
A aplicação, nesta etapa, deve:
| Elemento do labirinto | Elemento do grafo |
|---|---|
| Sala (área cinza da figura) | Vértice |
| Passagem (área laranja da figura) | Aresta |
| Passagem que permite ir e voltar | Aresta não direcionada |
| Salas vizinhas da sala atual | Lista de adjacências do vértice |
O ponto central da modelagem: como o enunciado garante que o jogador pode retornar por onde
veio, o grafo do labirinto é não direcionado. O código base fornecido criava apenas a
aresta origem -> destino, ou seja, um grafo direcionado — esse é o primeiro ajuste a fazer.
Grafo evoluída (não direcionada, com validações e algoritmos de busca)JogoLabirinto (motor do jogo, sem entrada/saída)input())GrafoEvoluções em relação ao código base:
| Código base | Código evoluído | Motivo |
|---|---|---|
adicionar_aresta cria só origem -> destino | cria os dois sentidos quando o grafo é não direcionado | as passagens do labirinto são de mão dupla |
| aresta ignorada em silêncio se o vértice não existe | levanta ValueError com mensagem clara | erro de digitação no mapa não passa despercebido |
| permite arestas duplicadas | verifica antes de inserir | evita a mesma sala aparecer duas vezes na lista de vizinhos |
| só imprime na tela | métodos retornam dados (adjacentes, arestas) e outros imprimem | separa a estrutura de dados da interface |
| nenhum algoritmo de busca | percurso_largura e caminho_mais_curto (BFS) | dá suporte aos objetivos futuros do jogo |
A lista de adjacências continua sendo um dicionário
{vértice: [vizinhos]}, exatamente como no código base. Consulta aos vizinhos é O(1) para chegar na lista e O(grau) para percorrê-la — ideal para um labirinto, que é um grafo esparso.
from collections import deque
class Grafo:
"""Grafo representado por lista de adjacencias (dicionario de listas)."""
def __init__(self, direcionado=False):
# Dicionario para armazenar os vertices e suas adjacencias
self.vertices = {}
self.direcionado = direcionado
# ------------------------------------------------------------------
# Construcao do grafo
# ------------------------------------------------------------------
def adicionar_vertice(self, vertice):
"""Cria o vertice com lista de adjacencias vazia, se ainda nao existir."""
if vertice not in self.vertices:
self.vertices[vertice] = []
return self # permite encadear chamadas
def adicionar_aresta(self, origem, destino):
"""Liga dois vertices. Em grafo nao direcionado, liga nos dois sentidos."""
if origem not in self.vertices:
raise ValueError(f"Vertice de origem inexistente: {origem}")
if destino not in self.vertices:
raise ValueError(f"Vertice de destino inexistente: {destino}")
if origem == destino:
raise ValueError(f"Laco nao permitido neste labirinto: {origem} -> {destino}")
if destino not in self.vertices[origem]:
self.vertices[origem].append(destino)
if not self.direcionado and origem not in self.vertices[destino]:
self.vertices[destino].append(origem)
return self
def remover_aresta(self, origem, destino):
"""Remove a passagem entre dois vertices (util para portas que se fecham)."""
if destino in self.vertices.get(origem, []):
self.vertices[origem].remove(destino)
if not self.direcionado and origem in self.vertices.get(destino, []):
self.vertices[destino].remove(origem)
return self
# ------------------------------------------------------------------
# Consultas
# ------------------------------------------------------------------
def existe_vertice(self, vertice):
return vertice in self.vertices
def existe_aresta(self, origem, destino):
return destino in self.vertices.get(origem, [])
def adjacentes(self, vertice):
"""Retorna a lista ordenada de vizinhos do vertice."""
if vertice not in self.vertices:
raise ValueError(f"Vertice inexistente: {vertice}")
return sorted(self.vertices[vertice])
def grau(self, vertice):
"""Quantidade de passagens que saem do vertice."""
return len(self.adjacentes(vertice))
def arestas(self):
"""Retorna a lista de arestas sem repetir a mesma passagem duas vezes."""
vistas = set()
resultado = []
for origem in self.vertices:
for destino in self.vertices[origem]:
chave = (origem, destino) if self.direcionado else tuple(sorted((origem, destino)))
if chave not in vistas:
vistas.add(chave)
resultado.append((origem, destino))
return resultado
# ------------------------------------------------------------------
# Algoritmos de busca
# ------------------------------------------------------------------
def percurso_largura(self, origem):
"""Busca em largura (BFS): ordem em que as salas sao alcancadas a partir da origem."""
if origem not in self.vertices:
raise ValueError(f"Vertice inexistente: {origem}")
visitados = [origem]
fila = deque([origem])
while fila:
atual = fila.popleft()
for vizinho in self.adjacentes(atual):
if vizinho not in visitados:
visitados.append(vizinho)
fila.append(vizinho)
return visitados
def caminho_mais_curto(self, origem, destino):
"""BFS com registro de predecessores: menor caminho em numero de passagens."""
if origem not in self.vertices:
raise ValueError(f"Vertice inexistente: {origem}")
if destino not in self.vertices:
raise ValueError(f"Vertice inexistente: {destino}")
if origem == destino:
return [origem]
anterior = {origem: None}
fila = deque([origem])
while fila:
atual = fila.popleft()
for vizinho in self.adjacentes(atual):
if vizinho in anterior:
continue
anterior[vizinho] = atual
if vizinho == destino:
caminho = [destino]
while anterior[caminho[-1]] is not None:
caminho.append(anterior[caminho[-1]])
return caminho[::-1]
fila.append(vizinho)
return None # destino inalcancavel
# ------------------------------------------------------------------
# Exibicao
# ------------------------------------------------------------------
def mostrar_vertices(self):
print(f"\nVertices ({len(self.vertices)}):")
for vertice in sorted(self.vertices):
print(f" {vertice} (grau {self.grau(vertice)})")
def mostrar_arestas(self):
ligacao = "->" if self.direcionado else "<->"
lista = self.arestas()
print(f"\nArestas ({len(lista)}):")
for origem, destino in lista:
print(f" {origem} {ligacao} {destino}")
def mostrar_lista_adjacencias(self):
print("\nLista de adjacencias:")
for vertice in sorted(self.vertices):
print(f" {vertice}: {', '.join(self.adjacentes(vertice)) or '(isolado)'}")
def __len__(self):
return len(self.vertices)
def __repr__(self):
tipo = "direcionado" if self.direcionado else "nao direcionado"
return f"<Grafo {tipo}: {len(self.vertices)} vertices, {len(self.arestas())} arestas>"Leitura da figura, traduzida para o grafo:
v1 — v2 — v3 — v4 — v5 — v1 (ciclo de 5 salas)v1A: ligada a v4, com trânsito nos dois sentidosv1E: ligada a v2, com trânsito nos dois sentidosSobre as salas anexas: o texto do enunciado descreve as duas passagens externas de forma pouco clara (
v4 ↔ v1Aev1E ↔ v2A). Adotei a leitura simétrica — cada sala anexa se liga a uma sala do pentágono — que é a única que mantém o labirinto conexo (sem trecho isolado e inalcançável a partir dev1). Como todo o mapa está declarado em um único dicionárioMAPA_LABIRINTO, basta editar essa estrutura para casar exatamente com a sua figura: nenhuma outra célula precisa ser alterada.
O mapa fica separado do código de propósito: é o padrão usado em jogos reais, onde a fase é dado e não programa. Trocar de labirinto vira trocar um dicionário.
# Mapa do labirinto: cada chave e uma sala, cada valor e a lista de salas vizinhas.
# Como o grafo e nao direcionado, basta declarar cada passagem uma unica vez.
MAPA_LABIRINTO = {
"v1": ["v2", "v5"], # pentagono central
"v2": ["v3", "v1E"], # v1E = sala anexa acessivel a partir de v2
"v3": ["v4"],
"v4": ["v5", "v1A"], # v1A = sala anexa acessivel a partir de v4
"v5": [],
"v1A": [],
"v1E": [],
}
def construir_labirinto(mapa=MAPA_LABIRINTO):
"""Monta o grafo nao direcionado do labirinto a partir do dicionario do mapa."""
grafo = Grafo(direcionado=False)
# 1) cria todas as salas antes das passagens (evita aresta para sala inexistente)
for sala in mapa:
grafo.adicionar_vertice(sala)
# 2) cria as passagens
for sala, vizinhas in mapa.items():
for vizinha in vizinhas:
grafo.adicionar_aresta(sala, vizinha)
return grafo
labirinto = construir_labirinto()
print(labirinto)
labirinto.mostrar_vertices()
labirinto.mostrar_arestas()
labirinto.mostrar_lista_adjacencias()Antes de programar o jogo, vale validar duas propriedades do labirinto:
v1, senão haveria trecho morto.A é vizinha de B, B tem que ser vizinha de A — é o que garante que o
jogador consegue voltar por onde veio.# Conferencia 1: a BFS a partir de v1 alcanca todas as salas?
alcancadas = labirinto.percurso_largura("v1")
print("Ordem de alcance a partir de v1:", " -> ".join(alcancadas))
print("Salas alcancadas:", len(alcancadas), "de", len(labirinto))
print("Labirinto conexo?", len(alcancadas) == len(labirinto))
# Conferencia 2: toda passagem e de mao dupla?
simetrico = all(
labirinto.existe_aresta(destino, origem)
for origem, destino in labirinto.arestas()
)
print("Todas as passagens sao de mao dupla?", simetrico)Desenho do labirinto usando apenas matplotlib, com as coordenadas do pentágono calculadas por
trigonometria. Serve para conferir visualmente se o grafo montado bate com a Figura 13.
(Célula opcional — se matplotlib não estiver disponível, ela apenas avisa e segue.)
import math
# Posicoes das salas: pentagono regular no centro + salas anexas para fora
POSICOES = {}
for indice, sala in enumerate(["v1", "v2", "v3", "v4", "v5"]):
angulo = math.radians(90 + indice * 72) # v1 no topo, sentido anti-horario
POSICOES[sala] = (math.cos(angulo), math.sin(angulo))
# Cada sala anexa fica na mesma direcao da sala do pentagono a que se liga, porem mais afastada
for anexa, ancora in [("v1A", "v4"), ("v1E", "v2")]:
x, y = POSICOES[ancora]
POSICOES[anexa] = (x * 1.95, y * 1.95)
def desenhar_labirinto(grafo, posicoes=POSICOES, destaque=None, titulo="Labirinto"):
"""Desenha as salas (vertices) e as passagens (arestas) do labirinto."""
try:
import matplotlib.pyplot as plt
except ImportError:
print("matplotlib nao instalado - visualizacao ignorada.")
return
figura, eixo = plt.subplots(figsize=(6, 6))
# passagens (arestas)
for origem, destino in grafo.arestas():
x1, y1 = posicoes[origem]
x2, y2 = posicoes[destino]
eixo.plot([x1, x2], [y1, y2], color="#E8873B", linewidth=6, zorder=1, solid_capstyle="round")
# salas (vertices)
for sala, (x, y) in posicoes.items():
atual = (sala == destaque)
eixo.scatter(x, y, s=1500, zorder=2,
color="#4C9F70" if atual else "#B0B0B0",
edgecolors="#3A3A3A", linewidths=1.5)
eixo.text(x, y, sala, ha="center", va="center", zorder=3,
fontsize=11, fontweight="bold",
color="white" if atual else "#2A2A2A")
eixo.set_title(titulo)
eixo.set_aspect("equal")
eixo.axis("off")
plt.show()
desenhar_labirinto(labirinto, destaque="v1",
titulo="Figura 13 - labirinto modelado como grafo (jogador em v1)")JogoLabirintoA classe cuida só das regras: onde o jogador está, para onde ele pode ir, o que acontece quando ele se move. Ela não lê teclado nem imprime menu — quem faz isso são as células 5 e 6.
Essa separação é o que permite usar o mesmo motor em modo roteiro (para testar), em modo interativo (para jogar) e, mais tarde, em uma interface gráfica, sem reescrever regra nenhuma.
Estado controlado pela classe:
| Atributo | Para que serve |
|---|---|
sala_atual | posição do jogador |
historico | sequência completa de salas visitadas (permite repetição, como pede o enunciado) |
movimentos | quantos passos já foram dados |
visitadas | conjunto de salas distintas já vistas |
pontuacao | soma dos pontos das salas premiadas |
import random
class JogoLabirinto:
"""Motor do jogo: controla a posicao do jogador e as regras de movimento."""
def __init__(self, grafo, sala_inicial="v1", pontos_por_sala=None, seed=None):
self.grafo = grafo
self.pontos_por_sala = pontos_por_sala or {}
if sala_inicial is None: # ponto de partida aleatorio
if seed is not None:
random.seed(seed)
sala_inicial = random.choice(sorted(grafo.vertices))
if not grafo.existe_vertice(sala_inicial):
raise ValueError(f"Sala inicial inexistente: {sala_inicial}")
self.sala_atual = sala_inicial
self.historico = [sala_inicial]
self.movimentos = 0
self.visitadas = {sala_inicial}
self.pontuacao = self.pontos_por_sala.get(sala_inicial, 0)
# ------------------------------------------------------------------
def salas_adjacentes(self):
"""Salas vizinhas da posicao atual - o coracao do enunciado."""
return self.grafo.adjacentes(self.sala_atual)
def pode_mover(self, destino):
return self.grafo.existe_aresta(self.sala_atual, destino)
def mover(self, escolha):
"""Move o jogador. Aceita o nome da sala ('v2') ou o indice mostrado no menu ('1')."""
vizinhas = self.salas_adjacentes()
# aceita indice numerico do menu
if isinstance(escolha, int) or (isinstance(escolha, str) and escolha.strip().isdigit()):
indice = int(escolha) - 1
if not 0 <= indice < len(vizinhas):
raise ValueError(f"Opcao fora do intervalo 1..{len(vizinhas)}")
destino = vizinhas[indice]
else:
destino = str(escolha).strip()
if not self.pode_mover(destino):
raise ValueError(
f"Nao ha passagem de {self.sala_atual} para '{destino}'. "
f"Opcoes: {', '.join(vizinhas)}"
)
self.sala_atual = destino
self.movimentos += 1
self.historico.append(destino)
# pontuacao contabilizada apenas na primeira visita a sala
if destino not in self.visitadas:
self.visitadas.add(destino)
self.pontuacao += self.pontos_por_sala.get(destino, 0)
return destino
# ------------------------------------------------------------------
def rota_ate(self, destino):
"""Dica: menor caminho da sala atual ate o destino (em numero de passagens)."""
return self.grafo.caminho_mais_curto(self.sala_atual, destino)
def visitou_todas(self):
return len(self.visitadas) == len(self.grafo)
def status(self):
return (
f"Sala atual: {self.sala_atual} | movimentos: {self.movimentos} | "
f"salas distintas: {len(self.visitadas)}/{len(self.grafo)} | "
f"pontuacao: {self.pontuacao}"
)
def descrever_posicao(self):
"""Texto que a aplicacao mostra a cada rodada."""
vizinhas = self.salas_adjacentes()
linhas = [f"\nVoce esta na sala {self.sala_atual}.",
f"Salas adjacentes ({len(vizinhas)}):"]
for indice, sala in enumerate(vizinhas, start=1):
marca = "" if sala in self.visitadas else " [nova]"
linhas.append(f" {indice}) {sala}{marca}")
return "\n".join(linhas)Antes de ligar o input(), roda-se o jogo com uma sequência de jogadas pré-definida. Isso
permite executar o notebook inteiro de ponta a ponta (inclusive por quem for corrigir) e conferir
o comportamento — inclusive o retorno pelo caminho de onde veio, que o enunciado exige:
repare que o roteiro entra em v1A e volta para v4.
def jogar_roteiro(jogo, jogadas):
"""Executa uma sequencia pre-definida de jogadas, mostrando cada rodada."""
print("=" * 60)
print("MODO ROTEIRO - sequencia de jogadas pre-definida")
print("=" * 60)
print(jogo.descrever_posicao())
for jogada in jogadas:
print(f"\n>>> Jogador escolheu: {jogada}")
try:
jogo.mover(jogada)
except ValueError as erro:
print(f" [movimento invalido] {erro}")
continue
print(jogo.descrever_posicao())
print("\n" + "-" * 60)
print("FIM DO ROTEIRO")
print(jogo.status())
print("Percurso:", " -> ".join(jogo.historico))
# Jogador comeca em v1, conforme o enunciado
jogo_demo = JogoLabirinto(labirinto, sala_inicial="v1")
# Roteiro: avanca pelo pentagono, entra na sala anexa v1A, VOLTA para v4 e segue
jogar_roteiro(jogo_demo, ["v2", "v3", "v4", "v1A", "v4", "v5", "v9"])Este é o laço principal pedido pelo enunciado: mostrar as salas adjacentes, ler a escolha do jogador, mover e repetir.
Comandos aceitos durante a partida:
| Comando | Efeito |
|---|---|
1, 2, 3... | move para a sala correspondente do menu |
v3, v1A... | move informando o nome da sala |
status | mostra movimentos, salas visitadas e pontuação |
mapa | redesenha o labirinto com a posição atual destacada |
dica v5 | mostra o menor caminho até a sala informada |
sair | encerra a partida |
Atenção: esta célula usa
input()e portanto trava se o notebook for executado de forma automática (Run Allsem interação, nbconvert etc.). Ela já trata esse caso encerrando sozinha.
def jogar_interativo(jogo, desenhar=None):
"""Laco principal do jogo: mostra vizinhos, le a escolha do jogador e move."""
print("=" * 60)
print("LABIRINTO - modo interativo")
print("Digite o numero ou o nome da sala. Comandos: status | mapa | dica <sala> | sair")
print("=" * 60)
while True:
print(jogo.descrever_posicao())
try:
entrada = input("\nPara onde deseja ir? ").strip()
except (EOFError, KeyboardInterrupt):
print("\n\n[execucao nao interativa - partida encerrada]")
break
if not entrada:
continue
comando = entrada.lower()
if comando in ("sair", "q", "exit"):
print("\nPartida encerrada.")
break
if comando == "status":
print("\n" + jogo.status())
continue
if comando == "mapa":
if desenhar is not None:
desenhar(jogo.grafo, destaque=jogo.sala_atual,
titulo=f"Labirinto - jogador em {jogo.sala_atual}")
else:
jogo.grafo.mostrar_lista_adjacencias()
continue
if comando.startswith("dica"):
partes = entrada.split()
if len(partes) < 2:
print("Use: dica <sala>")
continue
try:
caminho = jogo.rota_ate(partes[1])
except ValueError as erro:
print(f"[erro] {erro}")
continue
print("Menor caminho:", " -> ".join(caminho) if caminho else "inalcancavel")
continue
try:
jogo.mover(entrada)
except ValueError as erro:
print(f"[movimento invalido] {erro}")
continue
if jogo.visitou_todas():
print(f"\n*** Voce ja visitou todas as {len(jogo.grafo)} salas do labirinto! ***")
print("\n" + jogo.status())
print("Percurso:", " -> ".join(jogo.historico))
# Descomente para jogar:
# jogo = JogoLabirinto(labirinto, sala_inicial="v1")
# jogar_interativo(jogo, desenhar=desenhar_labirinto)O enunciado lista melhorias possíveis. Todas já são suportadas pelo motor construído — esta célula demonstra cada uma delas:
MAPA_LABIRINTOJogoLabirinto(..., sala_inicial=None)pontos_por_salacaminho_mais_curto (BFS)O item 5 tem um resultado interessante neste labirinto: o desafio é impossível.
v1Aev1Esão becos sem saída (grau 1), então só podem ocupar as duas pontas do percurso — e nem assim o pentágono central é coberto inteiro. A célula abaixo testa todas as salas de partida e demonstra isso.
# --- 1) Nomes tematicos para as salas ------------------------------------
NOMES_TEMATICOS = {
"v1": "Salao de Entrada",
"v2": "Biblioteca",
"v3": "Masmorra",
"v4": "Sala do Trono",
"v5": "Jardim Interno",
"v1A": "Torre Norte",
"v1E": "Cripta",
}
mapa_tematico = {
NOMES_TEMATICOS[sala]: [NOMES_TEMATICOS[v] for v in vizinhas]
for sala, vizinhas in MAPA_LABIRINTO.items()
}
labirinto_tematico = construir_labirinto(mapa_tematico)
print("Labirinto tematico:", labirinto_tematico)
print("Vizinhos do Salao de Entrada:", labirinto_tematico.adjacentes("Salao de Entrada"))
# --- 2) Ponto de partida aleatorio ---------------------------------------
jogo_aleatorio = JogoLabirinto(labirinto, sala_inicial=None, seed=42)
print("\nPartida sorteada comecando em:", jogo_aleatorio.sala_atual)
# --- 3) Pontuacao por sala -----------------------------------------------
PONTOS = {"v1A": 50, "v1E": 30, "v3": 10}
jogo_pontuado = JogoLabirinto(labirinto, sala_inicial="v1", pontos_por_sala=PONTOS)
for sala in ["v2", "v1E", "v2", "v3"]:
jogo_pontuado.mover(sala)
print("\nApos o percurso", " -> ".join(jogo_pontuado.historico))
print(jogo_pontuado.status())
# --- 4) Objetivo: chegar a uma sala com o minimo de movimentos -----------
origem, destino = "v1", "v1A"
caminho = labirinto.caminho_mais_curto(origem, destino)
print(f"\nMenor caminho de {origem} ate {destino}: {' -> '.join(caminho)}")
print(f"Movimentos necessarios: {len(caminho) - 1}")
# --- 5) Objetivo: visitar todas as salas sem repetir ---------------------
def caminho_hamiltoniano(grafo, inicio):
"""Busca em profundidade com retrocesso: passa por todas as salas uma unica vez."""
total = len(grafo)
def explorar(atual, visitadas, caminho):
if len(caminho) == total:
return list(caminho)
for vizinho in grafo.adjacentes(atual):
if vizinho in visitadas:
continue
visitadas.add(vizinho)
caminho.append(vizinho)
resultado = explorar(vizinho, visitadas, caminho)
if resultado:
return resultado
caminho.pop() # retrocesso (backtracking)
visitadas.remove(vizinho)
return None
return explorar(inicio, {inicio}, [inicio])
print("\nDesafio 'visitar todas as salas sem repetir' - teste de todas as saidas:")
for sala_inicio in sorted(labirinto.vertices):
rota = caminho_hamiltoniano(labirinto, sala_inicio)
print(f" saindo de {sala_inicio:<4}: {' -> '.join(rota) if rota else 'impossivel'}")
# Analise: v1A e v1E tem grau 1 (sao becos sem saida), entao so podem ser INICIO ou FIM
# de um percurso sem repeticao. Como um caminho tem apenas duas pontas, ambos teriam de
# ser as extremidades - e nem assim o pentagono central e coberto por completo.
print("\nSalas com grau 1 (becos sem saida):",
[s for s in sorted(labirinto.vertices) if labirinto.grau(s) == 1])
print("Conclusao: este labirinto nao admite percurso que visite todas as salas sem repetir.")
print("Para viabilizar o desafio, bastaria abrir uma passagem extra, por exemplo v1A <-> v5.")O labirinto foi modelado como um grafo não direcionado, com salas nos vértices e passagens
nas arestas. A escolha da lista de adjacências (dicionário de listas) é o que torna imediata
a operação central do jogo — "quais são as salas vizinhas da sala atual?" —, que no código é
apenas self.vertices[sala].
As três mudanças mais importantes em relação ao código base:
Grafo), regras (JogoLabirinto) e interface
(jogar_roteiro / jogar_interativo), que permite evoluir cada parte isoladamente;TAKENAKA, M. Estrutura de Dados. Material da disciplina — Figura 13 adaptada.
Execução em Python roda no seu navegador via Pyodide (WebAssembly). Pacotes como numpy, pandas e matplotlib são suportados; outros exigem wheels puro-Python via micropip.