The Boys

Este projeto foi inicialmente concebido pelos profs. Fabiano Silva, Luis Bona e Marcos Castilho para as disciplinas CI1001 e CI067, levemente inspirada na série de TV The Boys. Esta página descreve uma versão modificada do projeto original.

Este projeto consiste em simular um mundo com heróis, bases e missões. Cada herói possui um conjunto de habilidades (vôo, invisibilidade, visão de raios X, superaudição, etc.), um nível de experiência e outros atributos.

As bases estão espalhadas pelo mundo e os heróis se deslocam periodicamente entre elas. Cada base possui uma lotação máxima e uma fila de espera; ao chegar na base, o herói pode decidir entre esperar na fila ou desistir, viajando para outra base. Cada base possui um porteiro que gerencia a entrada/saída dos heróis e a fila de espera.

Esporadicamente surgem missões em locais aleatórios desse mundo; cada missão exige um conjunto de habilidades específicas. A missão pode ser atendida por uma equipe de heróis que se encontre em uma base, desde que os heróis da equipe tenham, em conjunto, as habilidades requeridas. Ao ser escolhido para participar de uma missão, cada herói recebe pontos de experiência.

Este projeto consiste em simular a dinâmica desse mundo durante um ano (525.600 minutos). Ao final, a simulação deve apresentar o número de missões cumpridas (pontos ganhos) por cada herói e outras estatísticas.

Simular é construir e executar um modelo computacional que imita de forma aproximada a realidade e sua evolução ao longo do tempo. A simulação é uma ferramenta muito usada no estudo de fenômenos naturais, como técnica de ensino (oferecendo para os alunos um ambiente onde é possı́vel experimentar e errar sem as consequências do ambiente real) e também em muitos jogos eletrônicos. A simulação de eventos discretos (SED) é uma forma de simulação que modela a dinâmica de um sistema como uma sequência de eventos ocorrendo ao longo do tempo.

O modelo de simulação possui uma estrutura estática e uma estrutura dinâmica:

• Estrutura estática: descreve as entidades do sistema com seus atributos; o valor desses atributos em um dado momento define o estado do sistema.

• Estrutura dinâmica: descreve como o estado do sistema evolui; geralmente é definida através de uma sequência de eventos agendados ao longo do tempo, que alteram os atributos das entidade do sistema e podem criar novos eventos.

Um simulador é um programa que executa os eventos e evolui o modelo de simulação no tempo. Para isso, ele mantém um relógio global, representando o tempo atual no modelo, e uma Lista de Eventos Futuros (LEF), que é basicamente uma lista de eventos ordenada por datas de ocorrência crescentes, como em uma agenda:

10:00 ir ao dentista
 : (aqui está no dentista)
11:45 voltar do dentista
12:00 almoçar
 : (aqui está almoçando)
13:00 ir à UFPR
13:30 ir à aula de Cálculo
 : (aqui está na aula)
15:20 sair da aula de Cálculo
15:30 ir à aula de Programação
 : (aqui está na aula)
17:30 sair da aula de Programação
18:00 voltar para casa
 : (aqui está voltando para casa)
...

O relógio do simulador geralmente é um número inteiro que representa o tempo no sistema simulado e não tem relação direta com o tempo físico. Dependendo do modelo, cada unidade de tempo simulado pode representar microssegundos (em uma simulação de circuitos lógicos), minutos (simulação de tráfego) ou mesmo milhares de anos (simulação geológica).

Executar a simulação consiste basicamente em processar os eventos em sequência, atualizando o estado do sistema a cada evento. Entre dois eventos consecutivos o estado do sistema não se altera, por isso o relógio do simulador pode saltar diretamente de um evento ao próximo. Dessa forma, o ciclo básico de funcionamento do simulador é bem simples:

1. retirar o primeiro evento da lista de eventos
2. atualizar o relógio
3. tratar o evento:
   1. atualizar o estado do sistema
   2. agendar novos eventos porventura criados
4. repetir até concluir a simulação

Dessa forma, uma simulação pode ser traduzida no seguinte pseudocódigo:

iniciar as entidades e atributos do mundo
criar os eventos iniciais
  
relógio = 0
repetir
    ev = 1º evento da lista de eventos futuros
    relógio = tempo (ev)
    caso tipo (ev) seja:
        EV1: executa evento 1
        EV2: executa evento 2
        EV3: executa evento 3
        ...
    fim
até o fim da simulação
  
apresentar resultados

Nosso mundo simulado é composto de diversos tipos de entidades, cada uma com seus próprios atributos:

Herói (H): representa cada herói:

• ID: número inteiro ≥ 0 que identifica unicamente o herói;
• Habilidades: conjunto de habilidades que o herói possui. Cada habilidade é representada por um número inteiro ≥ 0;
• Paciência: número inteiro ≥ 0 que indica quão paciente uma pessoa é. Em nosso modelo, isso afeta as decisões de permanência em bases e filas;
• Velocidade: número inteiro ≥ 0 indicando a velocidade de deslocamento de um herói, que irá afetar o tempo de deslocamento entre as bases;
• Experiência: número inteiro ≥ 0 que indica o número de missões em que o herói já participou;
• Base: ID da base onde o herói se encontra no momento.

Base (B): Representa cada local frequentado pelos heróis para formar equipes; cada base tem uma localização em um plano cartesiano, tem uma lotação, pode estar cheia e possui uma fila de espera:

• ID: número inteiro ≥ 0 que identifica cada base;
• Lotação: número máximo de heróis naquela base;
• Presentes: conjunto dos IDs dos heróis que estão atualmente na base, constituem as equipes disponíveis para realizar missões;
• Espera: fila onde os heróis esperam para poder entrar na base;
• Local: localização da base (par de coordenadas inteiras X, Y ≥ 0).

Missão (M): representa cada missão:

• ID: número inteiro ≥ 0 que identifica a missão;
• Habilidades: conjunto de habilidades necessárias para cumprir a missão;
• Local: localização da missão (par de coordenadas inteiras X, Y ≥ 0).

Mundo (W): O mundo é definido pelas entidades acima e algumas informações gerais:

• NHerois: número total de heróis no mundo;
• Herois: vetor representando todos os heróis;
• NBases: número total de bases no mundo;
• Bases: vetor representando todas as bases;
• NMissoes: número total de missões a cumprir;
• Missoes: vetor representando todas as missões;
• NHabilidades: número de habilidades distintas possíveis;
• TamanhoMundo: coordenadas máximas do plano cartesiano (as coordenadas mínimas são 0, 0); vamos considerar que o mapa de nossa supercidade é representado por um plano cartesiano de tamanho tal que cada unidade representa 1 metro;
• Relogio: número inteiro ≥ 0 indicando o tempo atual no mundo. Cada unidade de tempo no mundo simulado representa 1 minuto de tempo real.

Os eventos implementam as mudanças de estado que fazem evoluir a simulação. Cada evento tem um instante de ocorrência, pode consultar e alterar variáveis (atributos das entidades) e pode criar outros eventos no presente ou no futuro.

Representa um herói H chegando em uma base B no instante T. Ao chegar, o herói analisa o tamanho da fila e decide se espera para entrar ou desiste:

CHEGA (T, H, B):

atualiza base de H

se há vagas em B e a fila de espera em B está vazia:
    espera = true
senão:
    espera = (paciência de H) > (10 * tamanho da fila em B)

se espera:
    cria e insere na LEF o evento ESPERA (agora, H, B)
senão:
    cria e insere na LEF o evento DESISTE (agora, H, B)

O herói H entra na fila de espera da base B. Assim que H entrar na fila, o porteiro da base B deve ser avisado para verificar a fila:

ESPERA (T, H, B):

adiciona H ao fim da fila de espera de B
cria e insere na LEF o evento AVISA (agora, B)

O herói H desiste de entrar na base B, escolhe uma base aleatória D e viaja para lá:

DESISTE (T, H, B):

escolhe uma base destino D aleatória
cria e insere na LEF o evento VIAJA (agora, H, D)

O porteiro da base B trata a fila de espera:

AVISA (T, B):

enquanto houver vaga em B e houver heróis esperando na fila:
    retira primeiro herói (H') da fila de B
    adiciona H' ao conjunto de heróis presentes em B
    cria e insere na LEF o evento ENTRA (agora, H', B)

O herói H entra na base B. Ao entrar, o herói decide quanto tempo vai ficar e agenda sua saída da base:

ENTRA (T, H, B):

calcula TPB = tempo de permanência na base:
    TPB = 15 + paciência de H * aleatório [1...20]
cria e insere na LEF o evento SAI (agora + TPB, H, B)

O herói H sai da base B. Ao sair, escolhe uma base de destino para viajar; o porteiro de B é avisado, pois uma vaga foi liberada:

SAI (T, H, B):

retira H do conjunto de heróis presentes em B
escolhe uma base destino D aleatória
cria e insere na LEF o evento VIAJA (agora, H, D)
cria e insere na LEF o evento AVISA (agora, B)

O herói H se desloca para uma base D (que pode ser a mesma onde já está):

VIAJA (T, H, D):

calcula duração da viagem:
    distância = distância cartesiana entre a base atual de H e a base D 
    duração = distância / velocidade de H
cria e insere na LEF o evento CHEGA (agora + duração, H, D)

Uma missão M é disparada no instante T. São características de uma missão:

• Cada missão ocorre em um local aleatório e requer um conjunto aleatório de habilidades; ambos são definidos durante a inicialização.
• Cada equipe é formada pelo conjunto de heróis presentes em uma base.
• Uma equipe está apta para a missão se a união das habilidades de seus heróis contém as habilidades requeridas pela missão.
• Deve ser escolhida para a missão a equipe da base mais próxima ao local da missão e que esteja apta para ela.
• Ao completar uma missão, os heróis da equipe escolhida ganham pontos de experiência.
• Se uma missão não puder ser completada, ela é marcada como “impossível” e adiada de 24 horas.

MISSAO (T, M):

calcula a distância de cada base ao local da missão M
encontra BMP = base mais próxima da missão cujos heróis possam cumpri-la 
se houver uma BMP:
    incrementa a experiência dos heróis presentes na base BMP
senão:
    cria e insere na LEF o evento MISSAO (T + 24*60, M) para o dia seguinte

Encerra a simulação no instante T:

FIM (T):
  apresenta as experiências dos heróis
  apresenta as estatísticas das missões
  encerra a simulação

Inicialização do mundo virtual:

Tempo inicial:         T_INICIO        = 0
Tempo final (minutos): T_FIM_DO_MUNDO  = 525600
Tamanho do mundo:      N_TAMANHO_MUNDO = 20000
Número de habilidades: N_HABILIDADES   = 10
Número de heróis:      N_HEROIS        = N_HABILIDADES * 5
Número de bases:       N_BASES         = N_HEROIS / 6
Número de missões:     N_MISSOES       = T_FIM_DO_MUNDO / 100

Inicialização de cada herói:

id          = número sequencial [0...N_HEROIS-1]
experiência = 0
paciência   = número aleatório [0...100]
velocidade  = número aleatório [50...5000]  // em metros/minuto = 3 Km/h a 300 Km/h
habilidades = conjunto com tamanho aleatório [1...3] de habilidades aleatórias

Observe que cada herói possui entre 1 e 3 habilidades distintas, escolhidas aleatoriamente entre as habilidades possíveis.

Inicialização de cada base:

id        = número sequencial [0...N_BASES-1]
local     = par de números aleatórios [0...N_TAMANHO_MUNDO-1]
lotação   = número aleatório [3...10]
presentes = conjunto vazio (com capacidade para armazenar IDs de heróis até a lotação da base)
espera    = fila vazia

Inicialização de cada missão:

id          = número sequencial [0...N_MISSOES-1]
local       = par de números aleatórios [0...N_TAMANHO_MUNDO-1]
habilidades = conjunto com tamanho aleatório [6...10] de habilidades aleatórias

Antes de iniciar a simulação, é necessário criar e inserir na LEF alguns eventos iniciais. Esses eventos serão em seguida processados e poderão gerar novos eventos, o que fará avançar a simulação.

Cada herói chegará em uma base aleatória em algum momento dos três primeiros dias de simulação:

para cada herói H:
    base  = número aleatório [0...N_BASES-1]
    tempo = número aleatório [0...4320]  // 4320 = 60*24*3 = 3 dias
    criar e inserir na LEF o evento CHEGA (tempo, H, base)

Cada missão deve ser agendada para ocorrer em algum momento da simulação:

para cada missão M:
    tempo = número aleatório [0...T_FIM_DO_MUNDO]
    criar e inserir na LEF o evento MISSÃO (tempo, M) 

O evento FIM deve ser agendado para o instante final da simulação:

tempo = T_FIM_DO_MUNDO
criar e inserir na LEF o evento FIM (tempo)

Nenhuma divindade virtual se sente realizada sem conhecimento do que as pessoas de seu mundo estão fazendo. Por isso, nossa simulação deve imprimir algumas informações durante o processamento dos eventos. Essas mensagens também podem ser úteis no processo de depuração do código.

As seguintes mensagens devem ser geradas durante a execução dos eventos, com os formatos de impressão especificados:

 45844: CHEGA  HEROI  0 BASE 2 ( 7/ 9) ESPERA
ou
 45844: CHEGA  HEROI  0 BASE 2 ( 7/ 9) DESISTE

%6d: CHEGA  HEROI %2d BASE %d (%2d/%2d) ESPERA
%6d: CHEGA  HEROI %2d BASE %d (%2d/%2d) DESISTE

Significado: no instante 45844 o herói 0 chega à base 2, que já tem 7 heróis presentes (sem contar ele) e lotação de 9 heróis. A mensagem informa também se o herói decidiu esperar para entrar ou desistiu.

 45844: ESPERA HEROI  0 BASE 2 ( 4)

%6d: ESPERA HEROI %2d BASE %d (%2d)

Significado: no instante 45844 o herói 0 entra na fila de espera da base 2, que já tem 4 heróis aguardando na fila (sem contar ele).

 45844: DESIST HEROI  0 BASE 2

%6d: DESIST HEROI %2d BASE %d

Significado: no instante 45844 o herói 0 desiste de entrar na base 2.

 45844: AVISA  PORTEIRO BASE 2 ( 7/ 9) FILA [ 30 17 04 23  0 ]
 45844: AVISA  PORTEIRO BASE 2 ADMITE 30
 45844: AVISA  PORTEIRO BASE 2 ADMITE 17

%6d: AVISA  PORTEIRO BASE %d (%2d/%2d) FILA [ %2d %2d ... ]
%6d: AVISA  PORTEIRO BASE %d ADMITE %2d

Significado:

• no instante 45844 o porteiro da base 2 é avisado; na base há 7 heróis, ela tem capacidade para 9 heróis e a fila de espera tem os heróis 30, 17, 04, 23 e 0, nessa ordem.
• no instante 45844 o porteiro da base 2 retira o herói 30 da fila de espera e o admite na base.
• no instante 45844 o porteiro da base 2 retira o herói 17 da fila de espera e o admite na base.

45844: ENTRA  HEROI 30 BASE 2 ( 8/ 9) SAI 46101

%6d: ENTRA  HEROI %2d BASE %d (%2d/%2d) SAI %d

Significado: no instante 45844 o herói 30 entra na base 2, que passa a ter 8 presentes e lotação de 9; sua saída da base está agendada para o instante 46101.

46101: SAI    HEROI 30 BASE 2 ( 7/9)

%6d: SAI    HEROI %2d BASE %d (%2d/%2d)

Significado: no instante 46101 o herói 30 sai da base 2, que passa a ter 7 heróis presentes e lotação de 9.

46101: VIAJA  HEROI 30 BASE 2 BASE 6 DIST 6922 VEL 4763 CHEGA 46102

%6d: VIAJA  HEROI %2d BASE %d BASE %d DIST %d VEL %d CHEGA %d

Significado: no instante 46101 o herói 30 inicia uma viagem da base 2 à base 6, com distância 6922 m, velocidade 4763 m/min e chegada prevista no instante 46102.

Cada evento MISSÃO gera várias mensagens:

120037: MISSAO 4150 TENT 1 HAB REQ: [ 0 2 3 4 6 7 8 9 ]
120037: MISSAO 4150 BASE 1 DIST 6461 HEROIS [ 2 6 25 47 48 ]
120037: MISSAO 4150 HAB HEROI  2: [ 0 9 ]
120037: MISSAO 4150 HAB HEROI  6: [ 8 ]
120037: MISSAO 4150 HAB HEROI 25: [ 3 7 ]
120037: MISSAO 4150 HAB HEROI 47: [ 0 1 ]
120037: MISSAO 4150 HAB HEROI 48: [ 6 ]
120037: MISSAO 4150 UNIAO HAB BASE 1: [ 0 1 3 6 7 8 9 ]
...
120037: MISSAO 4150 BASE 7 DIST 9867 HEROIS [ 16 21 22 23 24 31 33 46 ]
120037: MISSAO 4150 HAB HEROI 16: [ 3 4 8 ]
...
120037: MISSAO 4150 HAB HEROI 46: [ 2 ]
120037: MISSAO 4150 UNIAO HAB BASE 7: [ 0 1 2 3 4 5 6 7 8 9 ]
120037: MISSAO 4150 CUMPRIDA BASE 7
 ou (caso não exista base com equipe apta)
120037: MISSAO 4150 IMPOSSIVEL

%6d: MISSAO %d TENT %d HAB REQ: [ %d %d ... ]
%6d: MISSAO %d BASE %d DIST %d HEROIS [ %d %d ... ]
%6d: MISSAO %d HAB HEROI %2d: [ %d ... ]
%6d: MISSAO %d UNIAO HAB BASE %d: [ %d %d ... ]
%6d: MISSAO %d CUMPRIDA BASE %d
 ou
%6d: MISSAO %d IMPOSSIVEL

Significado:

• Linha “TENT 1 HAB REQ”: tentativa 3 de realizar a missão 4150, que requer as habilidades 0, 2, 3, 4, 6, 7, 8 e 9.
• Linha “BASE 1 DIST 6461”: a base 1 está distante 6461 metros da missão 4150 e tem os heróis 2, 6, 25, 47 e 48.
• Linha “HAB HEROI 2”: as habilidades do herói 2 são 0 e 9.
• … (repete para os demais heróis presentes na base 1).
• Linha “UNIAO HAB BASE 1”: a união das habilidades dos heróis na base 1 é 0, 1, 3, 6, 7, 8 e 9.
• … (repetir para as demais bases, até achar uma base apta).
• Linha “CUMPRIDA BASE 7”: a missão 4150 foi cumprida pela equipe da base 7.
• ou
• Linha “IMPOSSIVEL”: não foi encontrada equipe para cumprir a missão 4150 nesta tentativa e ela foi reagendada.

O evento FIM encerra a simulação, gerando um relatório com informações sobre heróis e missões:

525600: FIM
HEROI  0 PAC  32 VEL 3879 EXP  441 HABS [ 2 9 ]
HEROI  1 PAC  52 VEL 2974 EXP  620 HABS [ 5 ]
...
HEROI 49 PAC  84 VEL  522 EXP  510 HABS [ 4 ]
MISSOES CUMPRIDAS: 5236/5256 (99.62%)
TENTATIVAS/MISSAO: MIN 1, MAX 21, MEDIA 2.08

MISSOES CUMPRIDAS: %d/%d (%.2f%%)
TENTATIVAS/MISSAO: MIN %d, MAX %d, MEDIA %.2f

Significado:

• O herói 0 tem paciência 32, velocidade 3879, experiência 441 e possui as habilidades 2 e 9.
• Foram cumpridas 5236 das 5256 missões geradas (99,62% de sucesso).
• As missões tiveram entre 1 e 21 tentativas, a média foi de 2,08 tentativas/missão.

Cada docente irá fornecer um arquivo theboys.tgz contendo os arquivos necessários ao desenvolvimento do projeto.

• *.h: interfaces dos TADs, que não devem ser alterados
• *.c: esqueletos de implementação, a completar
• conjunto.o: arquivo objeto para o TAD conjunto
• makefile: arquivo do Make para a compilação

Além dos arquivos acima, arquivos de teste também podem ser fornecidos para os TADs.

Devem ser entregues todos os arquivos necessários à compilação do projeto, compactados em um arquivo nomeado theboys-entrega.tgz contendo um diretório theboys-entrega:

theboys-entrega.tgz:
    theboys-entrega/
        cjto.c
        cjto.h
        fila.c
        fila.h
        lef.c
        lef.h
        makefile
        theboys.c
        ... (outros arquivos porventura necessários)

Os programas de teste não devem ser entregues!

Organize seu desenvolvimento da seguinte forma:

• Desenvolva os TADs:
  1. Implemente e teste um módulo de TAD por vez
  2. Em cada módulo, implemente e teste uma função por vez
  3. Implemente as funções nesta ordem: imprime_, cria_, insere_, retira_, …
  4. Em cada função, escreva e teste um bloco por vez
  5. Comece sempre pela parte mais simples
  6. Use os programas de teste e o Valgrind para se assegurar que o módulo está correto, antes de iniciar o próximo módulo.

• Desenvolva o programa theboys.c:
  1. Defina as estruturas de dados necessárias
  2. Implemente a criação e destruição dessas estruturas de dados
  3. Implemente a criação dos eventos iniciais
  4. Defina uma função para cada evento, contendo inicialmente apenas um printf do mesmo
  5. Implemente o laço principal de simulação, que chama as funções de eventos
  6. Implemente e teste uma função de evento por vez (deixe a missão por último)
  7. Analise a saída para ver se a sequência de eventos está correta
  8. Use o Valgrind para verificar eventuais problemas de memória

O arquivo makefile, além dos alvos usuais, contém o alvo make entrega, que constrói o pacote para entregar o projeto.

Uma simulação pode processar um grande número de eventos e gerar uma saída enorme. Este arquivo contém um exemplo simplificado de saída, com as primeiras 1.000 linhas e as últimas 1.000 linhas de uma execução cuja saída completa tem 883.461 linhas.

Devido ao seu tamanho, a análise manual de uma saída de simulação completa pode ser inviável. Por isso, aconselha-se o uso de ferramentas do shell UNIX para filtrar as linhas de interesse na saída. O comando grep permite filtrar linhas que contenham uma determinada sequência de caracteres (string).

Por exemplo, para filtrar as linhas da saída que mostrem eventos relacionados ao herói 37, pode-se usar este comando:

$ ./theboys | grep "HEROI 37" | more
  1303: CHEGA  HEROI 37 BASE 7 (10/16) ESPERA
  1303: ESPERA HEROI 37 BASE 7 (10)
  1303: ENTRA  HEROI 37 BASE 7 (11/16) SAI 1928
  1928: SAI    HEROI 37 BASE 7 ( 8/16)
  1928: VIAJA  HEROI 37 BASE 7 BASE 1 DIST 6536 VEL 3082 CHEGA 1930
  1930: CHEGA  HEROI 37 BASE 1 ( 6/25) ESPERA
...

Para filtrar as linhas relativas ao evento CHEGA na base 3:

$ ./theboys | grep ": CHEGA" | grep "BASE 3" | more
     8: CHEGA  HEROI 36 BASE 3 ( 0/29) ESPERA
   174: CHEGA  HEROI 34 BASE 3 ( 1/29) ESPERA
   275: CHEGA  HEROI  9 BASE 3 ( 1/29) ESPERA
   529: CHEGA  HEROI 34 BASE 3 ( 1/29) ESPERA
   593: CHEGA  HEROI 34 BASE 3 ( 1/29) ESPERA
   597: CHEGA  HEROI 44 BASE 3 ( 2/29) ESPERA
...