MAPAS E ROTAS ALEATÓRIAS

UNIVERSIDADE DO SUL DE SANTA CATARINA

MAPAS E ROTAS ALEATÓRIAS

Leonardo Delcastanher

Ademar madeira júnior

Introdução

Segundo Schell (2008), todo jogo se passa em algum lugar do espaço da qual é definido como uma forma de “círculo mágico do jogo”, que define a infinidade de lugares que podem existir e como estes lugares estão relacionados entre si.

Da mesma forma que podem existir mapas simples e discretos, tais como os mapas do “jogo da velha”, ou xadrez, também podem existir mapas um tanto quanto complexos, tais como os utilizados em jogos de Role Playing Game (RPG) eletrônicos. Nestes podem ser encontrados mapas que introduzem, por exemplo, “espaços dentro de espaços”, isso é quando um jogador encontra em um grande mapa uma referência para uma cidade ou floresta e, ao entrar nela, ele é transferido para um novo mapa com as características e visualização deste novo ambiente.

Durante a criação do mapa, alguns elementos devem ser considerados, por exemplo, se o mapa é contínuo ou discreto, quantas dimensões possui, quais são seus limites, se existem ou não os “espaços em espaços” e como estão conectados  Schell (2008).

Percebe-se que diversos jogos podem ter algum tipo de mapa para a visualização do ambiente como forma de auxílio ao jogador na localização espacial, mesmo que virtual, dos elementos do jogo. Para a criação destes ambientes, podem ser utilizados traços discretos, resultando em mapas simples, ou mapas mais complexos, que podem ter outros mapas dentro de si, os “espaços dentro de espaços”. Estes espaços, por sua vez, podem variar de pequenos vilarejos ao lado de um rio, até mega cidades, rodeadas de outras cidades. Estes pontos podem se conectar, havendo interesses comuns entre eles, os pontos comuns destes interesses tendem a se tornar cidades comerciais.

Na criação de um mapa mais realístico, é necessário levar em consideração a maneira com que os humanos interagiram sobre ele. Como afirma Vargas (200, p. 01), Desde o início das civilizações, comércio e cidade têm uma relação de simbiose”, em outras palavras, há uma relação extremamente vantajosa para os dois quando juntos. Muitas vezes cidades surgiram a partir do próprio comércio, “A constituição das cidades na Antiguidade tinha por objetivo ser centro de comércio […]” (Pinto, 2016). Uma cidade bem conhecida pela sua variedade de comércio, era muitas vezes onde mercadores tinham o ponto final de suas viagens, vindo de tudo quanto é ponto do mapa. Citando novamente uma parte do texto de Pinto (2016), “[…] Roma cresceu em importância e desenvolvimento, tornando-se centro comercial e urbano da Europa, convergindo para ela caravanas de diversas regiões”. Isso resultou no surgimento de diversas rotas entre cidades das mais diversas, muitas vezes se encontrando em cidades ou até as formando (Sousa, 2016).

Problemática

De acordo com as fantasias épicas, o mundo é um personagem. Quando se lê as obras de Tolkien, percebe-se que o mundo é extremamente detalhado, cada parte do mundo é descrita como se fizesse parte de um “conto de fadas”. J.R.R. Tolkien é um escritor de fantasia internacionalmente conhecido por sua trilogia do Senhor dos Anéis e O Hobbit (Editors, 2016, p. tradução nossa). Ele era filósofo, fascinado por mitos e levou anos para criar seu mundo, sem nunca antes, em sua vida, publicá-los. Em alguns pontos, inclusive, ele colocava a história em segundo plano, se comparado ao mundo em que ela se passa, almejando a perfeição da criação do mundo, criando, inclusive, idiomas e dialetos para o mesmo (Entrevista – George R. R. Martin: The world of Fire and Ice, 2016, tradução nossa).

J.R.R. Tolkien
J.R.R. TolkienJ.R.R. Tolkien Biography.com Editors (2016)

Segundo Sean Murray (No Man’s Sky Programmer, 2016) nós devemos ter uma história, porém devemos ter lógica, as coisas que vemos estão ali por uma razão, as civilizações que as construíram as construíram ali por uma razão e elas demonstram a cultura desse povo. Quando uma pessoa lê um texto ou olha para um edifício, ela precisa encontrar a consistência dos fatos, isto é não somente criação de histórias, é a criação do mundo (Entrevista – No Man’s Sky: Creating The Lore and Universe – IGN First, 2016, tradução nossa).

Como visto acima, na hora de criar histórias, tanto em jogos digitais quanto em jogos de mesa, um dos passos mais importantes é a criação do mundo em que a história irá se passar e desenrolar. Para que exista um “objetivo” é necessário que exista pelo menos um mundo, um continente, cidades e vida. É necessário que exista lógica em sua formação, rios vindo de geleiras derretendo de montanhas, florestas pertos de água e assim vai. Tanto em jogos para computadores, celulares e tablets quanto jogos de mesa (Board Games, RPG) é dedicado um bom tempo somente ao desenvolvimento do mundo, com uma ferramenta que permita gerar estes mapas, de forma lógica este tempo poderia ser investido em outras áreas do game design, como na história ou no desenvolvimento dos personagens.

Da mesma maneira em que desenrolamos nossa história em cima de um terreno desconhecido, mestres de RPG e criadores de história vão poder fazer o mesmo. Utilizando essa ferramenta terão não só um mapa totalmente aleatório, como cidades espalhadas por ele com caminhos e rotas trazendo ainda mais possibilidades de narrativas e histórias pra se criar.

Objetivo Geral

O presente trabalho tem como objetivo a modelagem e criação de uma ferramenta para auxiliar na criação de mapas para jogos estilo Roleplaying Game (RPG) utilizando técnicas de Inteligência Artificial.

Objetivos Específicos 

Como base para alcançar o objetivo, têm se os seguintes objetivos específicos.

  • Pesquisa bibliográfica sobre metodologia de criação de mapas para jogos.
  • Pesquisa bibliográfica de técnicas de Inteligência Artificial que podem ser utilizadas para a resolução do problema.
  • Modelagem do protótipo.
  • Implementação em linguagem de programação.
  • Testes e validação.
  • Criar as rotas permitindo comunicação entre civilizações.

Justificativa

Conforme apresentado por Tolkien nos capítulos anteriores, o mundo é um personagem, o mundo é detalhado e cada parte é escrita como num conto de fadas, essa breve descrição sobre o que é o mundo, nos deixa claro a complexidade envolvida, Murray, por sua vez, nos apresenta toda a lógica existente por trás do mundo, o que reforça a visão de que este pode ser tratado como um personagem, ele precisa ter uma história, ele precisa ter lógica, com uma ferramenta de fácil uso este trabalho seria reduzido, iniciantes no desenvolvimento de jogos poderiam ganhar tempo para se dedicar ao estudo de seus códigos (Entrevista – George R. R. Martin: The world of Fire and Ice, 2016 e Entrevista – No Man’s Sky: Creating The Lore and Universe – IGN First, 2016).

Level Design é definido como criação de ambientes, cenários ou missões em um jogo, tradicionalmente, level design envolve a criação de Real Time Strategy games (RTS) e First Person Shooters (FPS), porém agora é necessário em todas as formas de jogos (Novak, 2012, p. 214, tradução Nossa).

A estrutura do nível de um jogo é a base do gameplay, quando o design não providencia pequenas aventuras ou distrações os jogadores acabam por perder cedo seu interesse. Os níveis são criados para controlar a forma que os jogadores tem acesso às informações que eles precisam para dar continuidade ao jogo (Novak, 2012, p. 219, tradução nossa)
.

Novamente conforme Schell (2008), todo jogo toma algum lugar no espaço. Considerando o jogo “twenty questions” (Vinte perguntas), neste jogo, um dos jogadores pensa num objeto, enquanto isso, os outros jogadores fazem perguntas de “sim ou não”, neste caso não existe um tabuleiro, não existem peças a serem movimentadas, no jogo não existe um espaço físico. Na imagem 1.0 é capaz de representar este ambiente, no caso, a mente do jogador que pensou o objeto (mind of the answerer) é o ponto que se encontra o prêmio, as perguntas representam o caminho (conversation space) e a mente de quem pergunta representa o ponto de partida (mind of the questioner).

Mapa para jogos imaginários
Mapa para jogos imagináriosOs autores (2016)

Estrutura do documento 

O primeiro capítulo deste documento apresenta uma introdução do objetivo, problemática e justificativa do desenvolvimento de uma ferramenta que possa gerar mapas com inteligência artificial.

O segundo capítulo deste documento apresenta a referência bibliográfica utilizada para o desenvolvimento da ferramenta.

O terceiro capítulo apresenta o cronograma a ser seguido para concluir a

ferramenta dentro do prazo necessário

 O quarto capítulo deste documento apresenta a modelagem da ferramenta que estará sendo desenvolvida.

Revisão Bibliográfica

O mapa é uma maneira de se representar uma ideia sobre um espaço geográfico. É uma maneira tão antiga como a própria civilização humana. Considerada mais antiga que a própria linguagem escrita! Sabendo dessa informação dita por Matias (1996, p. 39) em sua dissertação, podemos tomar consciência de quão importante é um mapa na hora de criar uma história, e de como ele tem que representar tudo que há nele. Nos seguintes capítulos será abordado algumas técnicas que serão utilizadas para desenvolver um mapa único, porem complexo.

Jogos e Entretenimento

Des dos primórdios dos tempos o ser humano vem procurando maneiras diferentes de se entreter. De esportes a criações artísticas, brinquedos caseiros a equipamentos caros, o entretenimento sempre foi presente em nossa vida. Em 1986, aproximadamente 30 anos atrás, foi estimado que os Norte Americanos gastam 160 bilhões de horas acomuladas todos os anos em entretenimento  (Vogel, 2015, p. xix, com adaptações), e esse número vem crescendo drasticamente ao longo dos anos. Os jogos, tanto de mesa quanto os eletrônicos, são ambos meios muito utilizados de entretenimento, chamando atenção de seu público com cores e visuais diferenciados, regras cativantes e rejogabilidade, os fazendo durar por anos. Porém um jogo é muito mais que apenas uma distração, como o  Vogel (2015, p. xix Tradução Nossa) descreve em seu livro:

Porem entretenimento pode ser algo muito maior que uma mera diversão. É algo universalmente interessante e atraente, pois quando ele faz o que ele tinha a intenção de fazer, ele nos mexe emocionalmente. Como a palavra latina tenare sugere, ele te agarra: Ele toca sua alma.

Para a computação, os jogos eletrônicos se tornaram uma área de real importância, tanto para o caráter técnico quanto para o caráter econômico.

Após discussões entre historiadores, chegou-se a um consenso onde o primeiro jogo eletrônico criado teria surgido em 1958, o objetivo deste jogo era rebater uma pequena bola com uma barra que ficaria no inferior da tela, o jogo em si, seria uma simulação de tenis, recebendo o nome “Tennis Programming”.

Com o passar dos anos os jogos foram se desenvolvendo e, em 1972 surgiu o primeiro vídeo game da história, o “Odyssey 100”

Em 1983 a Nintendo lançou o console “Famicon” (Family Computer), em 1985 este mesmo console chegou aos Estados unidos com o nome de “Nintendo Entertainment System” (NES), esse console foi um sucesso e pode ser usado como referência para a terceira geração de vídeo games, onde tivemos lançamentos incríveis como “Zelda”, “Metroid” e “Mario 3”, que até os dias atuais são utilizados como referência de jogabilidade (Batista et al., 2007).

De acordo com Salen e Zimmerman um jogo é “um sistema no qual os jogadores se envolvem em um conflito artificial, definido por regras, que implica um resultado quantificável” (Apud DIAS, 2015 – As regras do jogo, 2012).

Schell (2008, p. 40) define quatro elementos como sendo os principais de um jogo, estes quatro elementos a tétrade elementar de um jogo, ou seja, os quatro elementos principais que o compõem: estética, narrativa, mecânica e tecnologia.

Logo, conforme Schell:

  • Estética: Estética é como o jogo se parece, soa e cheira. A estética é uma parte incrivelmente importante do game design, já que ela tem a mais direta relação com a experiência do jogador.
  • Narrativa: É a sequência de eventos que desdobra o jogo. A narrativa pode ser linear e pré-escrita, ou pode ser abrangente e emergente. 
  • Mecânica: Regras e procedures do jogo, a mecânica descreve o objetivo do jogo e as formas que o jogador pode e não pode tentar alcançar o objetivo.
  • Tecnologia: Qualquer material e/ou interação que permita ao jogo existir, como lápis e papel. 

A indústria de jogos está cada vez maior, tomando conta do mercado sem queda. Em 2008 já havia passado a receita de Boxoffice de Hollywood, e está quase cobrindo a de música, como informado no livro Changing the Game (EDERYMOLLICK, 2008, p. 5, tradução nossa). Em 2011, apenas 3 anos depois, de acordo com uma pesquisa feita pelo CBS News dos Estados Unidos, a indústria de Videogames já superou e passou a indústria de música e de filmes juntas. “A indústria de música fez $6.9 bilhões em vendas ano passado. A de filmes fez $10.6 bilhões no box office. As vendas de videogames fez um total de $23 bilhões” (SIEBERG, 2011, p. 01, tradução nossa).

Acompanhando os cenários acima, desde o desenvolvimento dos primeiros jogos e vídeo games, até os atuais, podemos perceber a grande evolução nos gráficos, juntamente com os cenários de desenvolvimento, incluindo seus mapas, os mundos onde estas histórias se passam, dos jogos mais simples, onde o jogo acontecia em um espaço vazio e apenas movimentava-mos uma barrinha que representaria o personagem, até trabalhos magníficos como vistos em jogos como Skyrim, Divinity, World of Warcraft, entre outros.

É perceptível o esforço necessário para se produzir um material de qualidade superior a cada novo lançamento nesta indústria.

Inteligência Artificial

De acordo com Ludger a Inteligência Artificial pode ser definida como o ramo que se ocupada da automação do comportamento inteligente. Fazendo parte da computação, a inteligência artificial deve ser baseada em princípios teóricos e aplicados sólido neste campo. Estes princípios incluem estrutura de dados, algoritmos, linguagem e técnicas de programação usadas em sua implementação (Luger, 2013, p. 1).

Segundo Ceci (2016, p. 11) o primeiro passo para entender a inteligência artificial é definir a perspectiva que irá se estudar.O termo em questão foi utilizado pela primeira vez em 1956, porém, na época já existiam estudos na área da computação e da matemática que tinham por objetivo resolver problemas comuns ao dia a dia, o Teste de Turing (teste onde o objetivo era que uma pessoa tivesse de realizar perguntas via terminal e, através da resposta, tentar identificar qual resposta seria de uma máquina e qual resposta seria de uma pessoa) é um dos maiores exemplos.

Um tipo de jogo bastante conhecido é o jogo de tabuleiro, nele são utilizados dados para alcançar um comportamento aleatório, este método também é utilizado em jogos de RPG, no qual toda a sua mecânica é baseada em lançamentos de dados ou sorteio de cartas (Ceci, 2016, p. 33).

Dragonfire D&D cartas e fichas
Dragonfire D&D cartas e fichasDRAGONFIRE DECKBUILDER GAME Game Labs ()

Por consequência da possibilidade de aleatoriedade proporcionada pela inteligência artificial, ve-se necessário o seu uso para que se possa ser criado um ambiente aleatório que se permita utilizar como mapa de jogo.

O Objetivo do Teste de Turing (proposto por Alan Turing em 1950), é prover uma definição operacional satisfatória sobre o que é inteligência artificial. Para Turing, inteligência é o “nível humano” de performance em todas as tarefas cognitivas, suficientes para convencer um interrogador de que este está falando conversando com uma pessoa (RussellNorvig, 1995).

O primeiro sistema inteligente, R1, iniciou suas operações em 1982, este programa ajudou a configurar novos sistemas e gerou uma estimativa de economia de quarenta milhões de dólares por ano, em 1988 quase toda grande empresa dos Estados Unidos tinha sua própria equipe de Inteligência pesquisando ou desenvolvendo sistemas inteligentes (RussellNorvig, 1995).

Quando o pensamento passou a ser considerado uma forma de cálculo a mecanização desta forma de pensamento era uma próxima etapa previsível. Gottfried Wilhem Von Leibniz introduziu o primeiro sistema de lógica formal, além de propor uma máquina para automatizar suas tarefas. Leonhard Euler, no século XVIII introduziu o estudo das representações que podem capturar de forma abstrata a estrutura de relacionamentos do mundo, bem como as distintas etapas dos cálculos entre estes relacionamentos, dando origem a teoria dos grafos (Luger, 2013, p. 8).

Geração procedural de conteúdo (GPC) 

Antes de falar sobre o GPC vamos ao seu significado. De acordo com Shaker, Togelius e Nelson (2016, p. 98, tradução nossa) o GPC “[…] é a criação algorítmica de conteúdo de jogo com entrada de usuário limitada ou indireta”. Utilizando assim apenas o necessário, como será explicado mais à frente. O PGC que “Segundo Togelius et al [23], geração procedural de conteúdo (em inglês, Procedural Content Generation, PCG).”  (Duarte, 2012, p. 15) apresenta não só redução dos custos do projeto como também é capaz de reduzir a necessidade de potência do processador e da placa de vídeo do computador, por ter uma forma de armazenamento consideravelmente comprimida. O processo de geração procedural é dividido em duas etapas, gerar proceduralmente um plano para o cenário, e realizar este plano, sendo a primeira um documento de informações que chamaremos de “modelo do jogo” que, como saída, produz a segunda. Para poder gerar o algoritmo é preciso entender a criação dos cenários que deve-se criar, estes podem ser mapas lineares ou abertos, no caso, estaremos trabalhando com mapas de mundo aberto. O projeto deve ser analisado para garantir que todo cenário seja resolvível, garantindo assim a sua jogabilidade, por isso precisamos definir o plano em que o mapa é criado e, a partir disto, criar as heurísticas de criação (Duarte, 2012).

Diferença de Geração procedural e Geração procedural de conteúdo

Por outro lado, também de acordo com  Andrew Doull, Geração Procedural de Conteúdo (PCG – procedural content generation) , é a área da geração procedural que trabalha a criação de objetos do mapa, estes objetos devem afetar de alguma forma a jogabilidade, por exemplo, uma pedra que permite ao jogador acessar um caminho mais acima, um túnel escondido que o leva a outro ponto do mapa ou um lago que permita pesca e acabe por gerar rios que o personagem deva atravessar, por outro lado, Geração Procedural, apesar de também ser uma série de objetos gerados de forma aleatória, não afeta a jogabilidade (Doull, 2012).

Como estamos trabalhando com mapas que apresentarão ao usuário um continente, estes objetos seriam, como mencionado no parágrafo acima, irregularidades naturais, tais como montanhas, rios, florestas ou túneis criados por outras civilizações, cenários que serão possíveis abrir um “espaço dentro de espaço”, como citado nos parágrafos anteriores.

O caminho mais curto

Segundo Barrico (1998, p. 23)c, os problemas de “caminho mais curto” são muito comuns quando se trata de transportes

Existem três tipos de problemas quando se trata de “caminho mais curto”, são eles:

  • Do ponto inicial para o ponto final.
  • Do ponto inicial para vários pontos finais.
  • Entre todos os pontos.

Estes tipos de problemas apresentam algumas observações:

  • O comprimento do caminho sempre será maior que o comprimento de seus subcaminhos.
  • Qualquer subcaminho de um caminho mais curto, é ele próprio um caminho mais curto (princípio da optimalidade).
  • Para uma rede de N nós, qualquer caminho mais curto tem no máximo n-1 nós (em um caminho não existem nós repetidos.

Existem vários algoritmos para definir o caminho mais curto, porém os mais famosos são Dijkstra, Ford e Floyd, sendo Dijkstra e Ford algoritmos para um único ponto inicial (Barrico, 1998).

Pathfinding

Apesar das informações apresentadas no parágrafo anterior, optamos por dar prioridade ao Pathfinding com A * por conta da quantidade de conteúdo disponível na internet, permitindo um melhor entendimento do mesmo.

Assumindo-se que temos um objeto A que deve percorrer um caminho até um objeto B, a primeira coisa que precisamos fazer é simplificar a área de busca, para isso, delimita-se um espaço a ser analisado, este espaço pode ser dividido em “quadrados”, arrays ou outras formas de medida e cada item definido como “passável” ou “não passável”, para unir os dois objetos é necessário identificar quais seriam os “quadrados passáveis” que estariam entre os os pontos analisados. Depois que a área de busca tem um espaçamento “simplificado” podemos começar a busca em si, no geral, costuma-se ir para o quadrado da frente e, a partir deste, validamos os espaços “passáveis” em volta, repetindo o movimento anterior, até que se chegue no quadrado de destino. O caminho segue uma graduação que pode ser expressada por F = G +H, onde G é o custo do movimento do ponto inicial para o quadrado da próxima malha e H o custo deste novo quadrado até o ponto final, esta fórmula pode obter diversos valores, a menor distância equivale ao menor F (Lester, 2004).

Tendo em mão as rotas mais curtas e aplicando as irregularidades (elementos que vão influenciar na velocidade e tempo entre pontos) no mapa, temos que calcular quais rotas tomar para ir do ponto A ao B. Como explica Elvis Rodrigues:

Talvez o mais conhecido algoritmo de busca de melhor caminho em grafos seja o Algoritmo de Dijkstra [Dij59], um algoritmo de estratégia gulosa [CLR+01] que resolve o problema de busca de melhor caminho para grafos direcionados e valorados. O algoritmo funciona apenas para arestas com pesos positivos, característica que normalmente é verdadeira no problema de roteamento (da Silva, 2007, p. 14).

Pathfinding Dijkstra example
Pathfinding Dijkstra exampleThe Exterior Memory The Exterior Memory ()

Dijkstra

Edsger Wybe Dijkstra é considerado um gigante intelectual da informática, graças a todas as suas contribuições de lógica e matemática. 

Dr. Dijkstra era conhecido por várias razões, porem suas obras que mais se destacavam são: o algoritmo de caminho mais curto, e sua participação na criação da língua de programação Algol 60. Esse seu algoritmo de pathfinding, o qual é utilizado para desenvolver a ferramenta proposta nessa monografia, é utilizado por vários softwares em nossa dia a dia, como nos Sistemas de Posicionamento Global (GPS) ou em inúmeros planejadores de rota. De acordo com Dijkstra, essa ideia lhe surgiu em 1956 enquanto tomava café. Lhe demorou três anos para publicar esse método, o qual é conhecido muitas vezes apenas como “Algorítimo de Dijkstra”.

Infelizmente após alguns anos lutando contra o câncer, em 6 de Agosto de 2002 Edsger Wybe Dijkstra acabou falecendo, se eternizando em suas descobertas na informática (Markoff, 2002).

A ideia principal do algoritmo de Dijkstra é aplicar um cálculo de “custo e ganância” para o problema do caminho mais curto. Basicamente, com estes cálculos é possível fazer um sistema que incremente o número de ramificações de um ponto A para N pontos. Quando se utiliza o algoritmo para definir o melhor caminho, todas as possibilidades do ponto A para os N pontos são avaliadas, registrando seus custos, a partir disto os custos do ponto A para o ponto objetivo são calculados e é selecionado o caminho com o custo mais baixo. Este é portanto um método simples e poderoso para identificar o melhor caminho entre dois pontos, motivo pelo qual foi selecionado para ser utilizado no desenvolvimento de nossa ferramenta

(GOODRICHTAMISSIA,2001, p.342).

Como apresentado nos parágrafos anteriores, este algoritmo pode ser empregado em diversos contextos, do estudo de uma cadeia de produção até as rotas de um carteiro que não deve passar duas vezes na mesma rua, os pesos trabalhados podem ser compostos de fatores entre os vértices (pontos de interesse do algoritmo), desde que mensuráveis. Estes pontos podem assumir diferentes tipos de pontos de interesse, como cidades, bairros e estados (BarrosPamboukianZamboni, 2007, p. 960).

As figuras abaixo ilustram um grafo e uma matriz com seus respectivos pesos:

Ilustração Grafo de Dijkstra com seus Pesos
Ilustração Grafo de Dijkstra com seus PesosOs autores (2017)

Ilustração Matriz de Dijkstra
Ilustração Matriz de DijkstraOs autores (2017)

Para entendermos melhor, iremos definir um “ponto de origem” (u0) e um “ponto final” (uf) na matriz. Neste exemplo, utilizaremos como ponto inicial o vértice 4 (u0 = 4) e ponto final o vértice 8 (uf = 8). Tendo estes valores, definiremos dois grupos de vértices, os “vértices marcados” (M) e os “vértices desmarcados” (D), utilizaremos um vetor de booles para fazer esta marcação (sendo true os valores marcados e false os valores desmarcados). Tendo essas informações, precisamos definir novos dois vetores, os “comprimentos acumulados” (L) e o “vértice anterior” (A), estes vetores guardam são os responsáveis pelas informações do nó atual.

  • No primeiro momento, o vetor (L) deve ter valor máximo e o vetor (A) deve apontar para null.
  • A partir disso, uma série de rotinas irá somar os pontos do vetor (D) até atingir o ponto final (F).
  • Para o exemplo apresentado, teremos os vetores 4;1;2;3;8 ou 4;9;10;11;8, ambos como uma das possíveis rotas finais, somando o peso total de 14. 

Metodologia

O tipo de pesquisa caracteriza a forma metodológica da pesquisa, é necessário que o pesquisador tenha conhecimentos sobre como utilizar os instrumentos corretos para encontrar as respostas para o problema que tenha sido levantado. O instrumento ideal deve ser utilizado pelo pesquisador para alcançar os objetivos almejados do estudo que está realizando (KauarkManhãesMedeiros, 2010, p. 26).

O capítulo seguinte apresenta a metodologia utilizada para o desenvolvimento deste documento, apontando a natureza da pesquisa, as atividades necessárias para o desenvolvimento, a descrição do objeto de estudo, delimitações e recursos utilizados.

 No apêndice encontra-se o cronograma de desenvolvimento para as atividades metodológicas listadas neste capítulo.

Tipos de pesquisa

Existem várias formas de se classificar o tipo de uma pesquisa, com base em sua natureza, abordagem, propósito e meios utilizados para alcançar os dados necessários (KauarkManhãesMedeiros, 2010, p. 26).

De modo resumido, os tipos de pesquisas abordados no livro “Metodologia da Pesquisa” (2010), definem as pesquisas como:

Natureza Básica: Tem o objetivo de gerar novos conhecimentos úteis para o avanço da ciência sem aplicação prática prevista.

Natureza Aplicada: Tem o objetivo de gerar novos conhecimentos úteis para o avanço da ciência, porém com aplicação prática, dirigida à solução de problemas específicos.

Nosso trabalho será portanto, de natureza aplicada, onde pretendemos criar uma ferramenta capaz de diminuindo o tempo investido sobre a criação de mapas.

Pesquisa qualitativa: Tem como base a relação dinâmica entre o mundo real e o sujeito, um vínculo que não possa ser traduzido em números.

Pesquisa quantitativa: A pesquisa quantitativa, por outro lado, tem como base fatos que possam ser traduzidos em números, opiniões para classificá-las e analisá las.

Portanto, a abordagem do nosso problema será de natureza qualitativa, já que iremos analisar a qualidade das rotas criadas para interligar as cidades (KauarkManhãesMedeiros, 2010, p. 26).

Caracterização

Segundo Gil (2002), trabalhos desenvolvidos à partir do estudo de material já elaborado, tendo como principais fontes livros e artigos científicos é caracterizado como uma uma pesquisa bibliográfica.

Fonseca (2002) afirma que pesquisas que estabelecem metas de acordo com os requisitos de desenvolvimento, qualificando os aspectos desenvolvidos natureza qualitativa.

Atividades metodológicas

O subcapítulo a seguir apresenta as atividades metodológicas e os procedimentos realizados para o desenvolvimento deste trabalho de conclusão de curso
.

  • Estudo de ferramentas para utilização no desenvolvimento.
  • Levantamento e análise de requisitos.
  • Modelagem do banco de dados
  • Selecionar o algoritmo utilizado para a criação de mapas e de rotas.
  • Selecionar a linguagem utilizada para desenvolvimento da ferramenta.
  • Desenvolver o protótipo ferramenta.
  • Desenvolver o tópico explicando o desenvolvimento da ferramenta.

Definidas as etapas apresentadas às descrições de cada etapa serão apresentadas a seguir:

Estudo de ferramenta: Nessa primeira etapa iremos realizar o levantamento dos algoritmos disponíveis para o desenvolvimento da ferramenta, onde será levada em consideração a complexidade para a nossa ferramenta.

Levantamento e análise de requisitos: Na segunda etapa da lista de atividades será descrito quais funcionalidades devem ser contempladas na ferramenta e quais características devem ser consideradas para o funcionamento ideal da mesma.

Modelagem do banco de dados: Apesar de o foco da ferramenta não ser o armazenamento do banco de dados, na terceira etapa da nossa lista será apresentado o modelo do banco de dados, para o entendimento do armazenamento das estruturas geradas.

Selecionar o algoritmo: Antes de selecionar a linguagem que será implementada, devemos levar em consideração os algoritmos existentes para alcançar o objetivo do projeto, de modo que possa ser simplificado o processo de desenvolvimento.

Selecionar a linguagem: Com base no algoritmo analisado, será selecionada a linguagem de programação que mais pode-se adequar às necessidades do projeto em conjunto com o conhecimento dos desenvolvedores.

Desenvolver o protótipo da ferramenta: Após o filtro de algoritmo e linguagem que será utilizado, será encaminhado o desenvolvimento do protótipo.

Explicar o desenvolvimento da ferramenta: Com a finalização do protótipo e correções necessárias, será apresentado o funcionamento e desenvolvimento da ferramenta.

Delimitação do projeto

Devido a complexidade deste trabalho e a escassez de tempo, este trabalho teve que ser delimitado. Esta ferramenta tem o objetivo de criar mapas inteligentes, com o objetivo de auxiliar desenvolvedores e jogadores na criação de mapas para seus seus jogos, o projeto em si não se trata da criação de um jogo nem do processo a ser realizado para criá-lo.

A ferramenta deve ter capacidade de ser transferida para dispositivos móveis, mas não tem a necessidade de ser responsiva neste momento, ficando aberto como projeto futuro a ser considerado.

A ferramenta não irá desenvolver mapas altamente detalhados, com irregularidades e níveis de altura diferenciado, os mapas gerados terão um aspecto simples, onde o objetivo é unicamente auxiliar desenvolvedores e jogadores, não sendo portanto, o produto final.

A ferramenta desenvolvida irá gerar somente mapas em 2D.

Orçamento do projeto

Para o desenvolvimento da ferramenta não será necessário investimento, visto que o mesmo está sendo desenvolvido pelos alunos envolvidos, portanto o único gasto necessário para a conclusão desta ferramenta será baseado no tempo investido.

modelagem

O capítulo seguinte apresenta o passo a passo para o desenvolvimento deste projeto.

Requisitos não funcionais 

Para o desenvolvimento do sistema, foram levados em consideração os seguintes requisitos:

  • O sistema deve ser executado via web.
  • O sistema deve ser compatível com o Firefox 51.0.1.
  • O sistema deve ser compatível com o Google Chrome 55.0.2883.
  • O sistema não tem a necessidade de ser responsivo.
  • O sistema não tem a necessidade de ser compatível com dispositivos mobile.
  • O sistema deve ser desenvolvido de modo que permita futuramente a adaptação ao responsivo e aos aparelhos mobile.

Requisitos funcionais

Este subcapítulo trata dos requisitos necessários para que o projeto atenda os objetivos apresentados no primeiro capítulo.

  • Cada irregularidade deve ter um Ponto Central como referência.
  • Irregularidades como Montanhas, Lagos e Florestas terão o resto de sua área preenchida ao redor do Ponto Central.
  • A ordem de alocação de objetos no mapa deve ser: Lagos > Continente > Montanhas > Lagos > Rios > Florestas > Cidades e Rotas, por conta da lógica necessária.
  • As montanhas podem tomar posições aleatórias dentro do continente.
  • Os lagos devem tomar posição relativa às montanhas dentro do continente.
  • Os rios serão originados das montanhas que estejam dentro de uma margem de até 25 pixels do oceano.
  • As florestas devem ser originadas a partir dos rios.
  • Cidades devem ser alocadas somente após todos os objetos listados acima.
  • Após a alocação das cidades deve-se utilizar o algoritmo de caminho mais curto para identificar o caminho mais curto de todas as cidades para todas as cidades.
  • É utilizado um algoritmo de cálculo de peso para definir os pesos de cada rota.
  • Existem pesos diferentes para rotas mais rápidas e mais seguras.
  • É utilizado o Algoritmo de Dijkstra para definir quais rotas devem ser utilizadas de um ponto A para um ponto B.

 Descrição de estruturas

Os tópicos deste capítulo tem o como objetivo explicar a estrutura dos objetos trabalhados para criar os mapas e as rotas do nosso projeto.

Oceano

  • Tamanho base: 1000 pixels de largura por 600 pixel de altura.

Continente 

  • Não foram trabalhadas irregularidades no continente.
  • O tamanho do continente depende de um valor aleatório a ser gerado.

Montanhas 

  • Montanhas não possuem um requisito específico para serem alocadas.
  • As montanhas são compostas por 121 células. 11 de altura, 11 de largura.
  • Sua posição é definida pelo ponto central.

Rios 

  • Sempre surgem a partir de montanhas.
  • Os rios são compostos por N células, de acordo com o posicionamento da montanha.
  • Sua posição é definida a partir de uma lógica de aleatoriedade iniciado no ponto central da montanha.
  • Rios irão surgir somente de montanhas dentro de 25 células a partir das bordas do continente.
  • Rios irão criar seus caminhos de acordo com a posição da montanha, sendo definidos por norte, sul, leste e oeste.

Lagos

  • Estão sempre próximos das montanhas.
  • Os lagos são compostos por 441 células. 21 de altura, 21 de largura.
  • Sua posição é definida pelo ponto central.
  • Lagos podem surgir de qualquer montanha, a partir de um algoritmo de aleatoriedade.

Florestas 

  • Florestas ficarão sempre ao redor dos rios.
  • As florestas serão desenvolvidas juntamente com os rios, seguindo seu sentido e direção.
  • As florestas são compostas por 441 células. 21 de altura, 21 de largura.

Cidades 

  • As cidades serão alocadas de modo aleatório.
  • Cidades serão as penúltimas estruturas alocadas no mapa
    .

Rotas 

  • Cada célula utilizada no mapa deverá ter um valor de tempo (quanto maior, mais tempo demora para atravessar a célula).
  • Cada célula utilizada no mapa deverá ter um valor de periculosidade (quanto maior, mais perigosa é a célula).
  • Serão calculadas rotas entre todas as cidades, cada rota com seu próprio peso.
  • Quanto maior o peso da rota, mais ele irá influenciar no algorítimo de Dijkstra.
  • Quando for solicitado pelo usuário que seja gerada a rota mais curta, o sistema deverá considerar a menor quantidade de células entre os dois pontos.
  • Quando for solicitado pelo usuário que seja gerada a rota mais segura, o sistema deverá utilizar todas as rotas para gerar a rota mais segura entre elas.

Modelagem do banco 

Neste momento não foi desenvolvida conexão e armazenamento dos dados gerados pela ferramenta, mas foi desenvolvida a modelagem que o sistema deve seguir para funcionar adequadamente.

A imagem da modelagem pode ser encontrada no apêndice B.

Diagrama de Fluxo

O diagrama de fluxo de dados é utilizado pra ilustrar o fluxo de dados num sistema de
O diagrama (Bassani et al., 2006, p. 8) de fluxo de dados é utilizado pra ilustrar o fluxo de dados num sistema de
informação.

Diagrama de Fluxo de Dados
Diagrama de Fluxo de DadosDiagrama de Fluxo de Dados

PROTOTIPAÇÃO

Há um limite ao que uma pessoa consegue compreender com descrições de uma interface, para avançar esse limite basta mostra-lo um protótipo da interface, acrescentando seu compreensão (Sommerville, 2007, p. 253).

Mockup Interface Inicial TCC
Mockup Interface Inicial TCCElaboração dos Autores

DESENVOLVIMENTO

Nesse capítulo será abordado as ferramentas e tecnologias utilizadas para desenvolver o projeto, o histórico de desenvolvimento e o projeto em si.

Ferramentas e tecnologias usadas 

Aqui iremos apresentar as ferramentas e linguagens utilizadas para elaborar a ferramenta apresentada em nosso trabalho

PHP 

Para o backend de nossa ferramenta foi utilizado PHP, já que este é uma das linguagens que mais dominamos, além da alta quantidade de conteúdo disponível para estudo na internet e da compatibilidade com javascript.

Javascript

Para o frontend foi utilizado o javascript, por já ser nativo do browser e ser uma língua já dominada por nos. Informações entre PHP e Javascript são trocadas com facilidade, auxiliando no desenvolvimento dessa ferramenta.

AngularJs

o AngularJs é um framework de Javascript para o frontend, facilitando a conexão entre o Javascript e o HTML. Com ele podes associar variáveis entre o HTML e o Javascript, na mudança de valor de uma variável, tanto em uma parte quanto na outra seu valor é alterado.

Lodash

O Lodash é uma biblioteca que pega ações básicas do Javascript e os deixa mais otimizadas, consumindo menos processamento. Ele também contem várias funções que facilitam a manipulação de arrays (os quais são muito utilizados em nossa ferramenta), tornando inúmeras linhas de código para percorre-las em apenas 3 linhas.

 

IDE

O IDE, do inglês Integrated Development Environment ou Ambiente de Desenvolvimento Integrado é um programa onde nele se escreve o código para desenvolver sua ferramente. Existem inúmeros IDEs, cada um dedicado a uma língua e com o seu próprio diferencial. 

Netbeans

Devido ao grande foco dado pelos professores no começo de nosso curso, um dos programas que mais temos afinidade é o Netbeans, por conta disso, este foi o software utilizado para desenvolver o backend de nosso projeto. 

PHPStorm

Para o frontend foi utilizado o PHPStorm da InjelliJ, ele traz uma interação entro o HTML e o CSS, facilitando na criação das telas, além de ter um ótimo auxilio nos códigos sendo digitados, tanto em PHP quanto em Javascript.

Histórico de Desenvolvimento 

 Aqui iremos apresentar as etapas do desenvolvimento da ferramenta
, não foi utilizado nenhum conceito concreto na hora de se organizar.

A primeira parte do processo para desenvolver nossa ferramenta foi o levantamento de requisitos, onde nos encontramos para apontar todas as funcionalidades necessárias para que a ferramenta ficasse como planejamos.

 Assim que o documento foi elaborado, chegamos a conclusão de que a primeira parte que será criada é o continente, onde suas dimensões terão tamanhos estáticos. A partir deste continente, sera gerado aleatoriamente cinco montanhas, que acionam a lógica que define se as montanhas devem gerar rios ou lagos, onde dai os rios acionam a lógica para definir se as florestas devem ser geradas.

 Depois que as irregularidades apresentadas no continente são geradas, é definido onde ficam as civilizações em nosso mapa, estas civilizações são os pontos principais para criar as rotas entre todas elas. Cada civilização é representada por uma letra, a partir disso surge o caminho mais curto de todas as cidades para todas as cidades, somando através da lógica criada, o peso para cada rota, com base na quantidade de células atravessando rios, lagos, florestas ou montanhas, estes pesos são diferenciados para caminho mais rápido e para caminho mais seguro.

Dentro deste processo, um dos problemas encontrados foi o de buscar a melhor rota, levando em consideração seu peso. Para resolver essa dificuldade utilizamos o algoritmo de Dijkstra.

Após gerar as irregularidades, cidades e rotas, encontramos a dificuldade de percorrer todos os arrays no PHP para criar as variações de rotas. As passando para o frontend e utilizando a biblioteca Lodash, foi possível manipular todos os arrays com facilidade criando todos os tipos de rota.

Apresentação dA Ferramenta 

Nossa ferramente foi reduzida para uma única tela, onde em cada novo carregamento da tela, todos os objetos são gerados novamente, sempre seguindo as regras apresentadas neste documento e apresentados ao usuário.

Nesta tela, o usuário tem a opção de selecionar, através de botões, quais objetos ele quer ocultar. Estes objetos são as montanhas, rios, lagos, florestas, civilizações e todas as rotas mais curtas entre todas as cidades.

As outra opção apresentadas ao usuário é de selecionar o tipo de rota entre as duas cidades escolhidas, na qual os botões selecionados irão alterar a cor da rota desejada para vermelho.

Tela Inicial
Tela InicialTela inicial de nossa ferramenta, mostrando os botões e mapa

Mapa com elementos ocultados
Mapa com elementos ocultadosTela inicial com elementos ocultados no mapa

Mapa Rota Curta
Mapa Rota CurtaMapa com todos seus elementos, e com a rota mais curta entre cidade A e E

Mapa Rota Segura
Mapa Rota SeguraMapa com todos seus elementos, e com a rota mais segura entre cidade A e E

Conclusões e Trabalhos Futuros

No capítulo a seguir iremos apresentar as conclusões obtidas durante o desenvolvimento deste projeto, juntamente com as pretensões futuras para o aprimoramento desta ferramenta.

Conclusões 

Consideramos desenvolver nosso criador de mapas aleatório, com rotas baseadas em inteligência artificial, por conta da necessidade que encontramos enquanto jogávamos RGP de mesa. Neste período percebemos que para se criar um mapa para uma sessão de RPG era necessário muito tempo, após pesquisar concluímos que para se criar um mapa de qualquer outro jogo se tinha o mesmo trabalho, só que com mais complexidade. Iria facilitar muito se tivesse uma ferramenta que pudesse auxiliar neste processo, de modo que diminuísse o tempo investido.

Com relação ao tema do trabalho, conforme o andamento do projeto o sistema foi adquirindo as funcionalidades esperadas pelos autores deste trabalho, porém por conta da complexidade envolvida, muitas coisas tiveram que ser alteradas e adaptadas, ou até adiadas para os projetos futuros, no entanto mantendo as suas funcionalidades principais.

As tecnologias utilizadas para desenvolver este projeto, PHP, AngularJs, jQuery e Javascrip, foram de grande ajuda, facilitando o desenvolvimento e agilizando o processo.

Trabalhos futuros 

Quanto às possibilidades de futuros projetos, muitas ideias surgiram durante o desenvolvimento, cogitamos a ideia de executar a ferramenta em servidores REST e em Microservices, para deixá-lo modular. 

 Por conta do escasso tempo, os objetos gerados ficaram com uma aparência muito simples, portanto gostaríamos de deixá-lo mais característico, detalhando melhor estes objetos e criando irregularidades.

 Pretendemos também criar uma interface para o usuário, onde ele pode definir quais características o continente deve ter, como tamanho, nível tecnológico, escassez de água e outras possibilidades a serem discutidas, bem como a integração com bancos de dados, para poder armazenar o conteúdo gerado.

Referências

BarricoCarlos Manuel Chorro SimõesUma Abordagem ao Problema de Caminho Mais Curto Multiobjectivo: Aplicação ao Problema de Encaminhamento em Redes Integradas de Comunicações. Coimbra, 1998. 155 p.  Dissertação (Gestão da Informação)Universidade da Beira Interior, 1998 Disponível em: <http://www.di.ubi.pt/~cbarrico/Mestrado/Downloads/Tese_Mestrado.pdf>. Acesso em: 21 Nov. 2016.

BarrosEdson A. R.PamboukianSergio V. D.Zamboni Lincoln C.ALGORITMO DE DIJKSTRA: APOIO DIDÁTICO E MULTIDISCIPLINAR NA IMPLEMENTAÇÃO, SIMULAÇÃO E UTILIZAÇÃO COMPUTACIONAL. São Paulo, Brasil: ICECE, 2007. 1200 p.

BassaniPatricia Scherer et alEm busca de uma proposta metodológica para o desenvolvimento de software educativo colaborativo : Novas Tecnologias na Educação. Rio Grande do Sul: CINTED-UFRGS, v. 4, 2006. 10 p.

BatistaMônica de Lourdes Souza et alUM ESTUDO SOBRE A HISTÓRIA DOS JOGOS ELETRÔNICOS. Minas Gerais, 2007. 24 p.  TCC ( Sistemas de Informação)Faculdade Metodista Granbery, 2007

CeciFlávioInteligência Artificial. Palhoça: UNISUL, 2016. 97 p. Disponível em: <https://dl.dropboxusercontent.com/u/3025380/ceci-livro-ia.pdf>. Acesso em: 22 Nov. 2016.

da SilvaElvis RodriguesUma Arquitetura Orientada a Serviços para Roteamento Personalizado. Campina Grande, 2007. 117 p.  Dissertação (CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA)UNIVERSIDADE FEDERAL DE CAMPINA GRANDE, 2007 Disponível em: <http://docs.computacao.ufcg.edu.br/posgraduacao/dissertacoes/2007/Dissertacao_ElvisRodriguesdaSilva.pdf>. Acesso em: 25 Mai. 2017.

DiasJéssica DavidDesenvolvimento de Serious Game Para Auxílio ao Enfrentamento da Obesidade Infantil. São Carlos, 2015. 137 p.  Dissertação (Enfermagem)UNIVERSIDADE FEDERAL DE SÃO CARLOS Disponível em: <https://repositorio.ufscar.br/bitstream/handle/ufscar/3280/6508.pdf?sequence=1&isAllowed=y>. Acesso em: 21 Nov. 2016.

Doull AndrewInterview: Andrew Doull on Procedural Games. Game of Design. 2012. Disponível em: <https://dankline.wordpress.com/2012/03/04/interview-andrew-doull-on-procedural-games/>. Acesso em: 21 Nov. 2016.

DuartePhilip MichelGeração Procedural de Cenários Orientada a Objetivos. Natal, 2012. 81 p.  Dissertação (Sistema de Informação)UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE, 2012 Disponível em: <https://repositorio.ufrn.br/jspui/bitstream/123456789/18044/1/PhilipMD_DISSERT.pdf>. Acesso em: 21 Nov. 2016.

EDERYDavidMOLLICKEthan Changing the Game: How Video Games Are Transforming the Future of Business. Cambridge, Massachusetts: Ft Press, 2008. 240 p.

EditorsBiography.comJ.R.R. Tolkien Biography. The Biography.com website. England, 2016. Disponível em: <http://www.biography.com/people/jrr-tolkien-9508428>. Acesso em: 30 Mar. 2017.

FonsecaJoão José Saraiva daMetodologia da Pesquisa Científica. Ceará, 2002. 127 p.  Trabalho de Disciplina (Especialização em Comunidades Virtuais de Aprendizagem)UNIVERSIDADE ESTADUAL DO CEARÁ, 2002 Disponível em: <http://www.ia.ufrrj.br/ppgea/conteudo/conteudo-2012-1/1SF/Sandra/apostilaMetodologia.pdf>. Acesso em: 21 Nov. 2016.

Game LabsCatalyst  (Org)DRAGONFIRE: DECKBUILDER GAME. Dungeons & Dragons. 2017. Disponível em: <http://dnd.wizards.com/products/tabletop-games/board-games/dragonfire>. Acesso em: 25 Mai. 2017.

George R. R. Martin: The World of Ice and Fire. George R. R. Martin. 2016. Documentário (154min). Disponível em: <https://www.youtube.com/watch?v=351pUIf0Fu8>. Acesso em: 21 Nov. 2016.

GilAntônio CarlosComo Elaborar Projetos de Pesquisa. 4. ed. São Paulo: Atlas S.A., 2002. 176 p.

GoodrichMichael T.TamissiaRobertoAlgorithm Design:: Foundations, Analysis, and Internet Examples. 1. ed. California: John Wiley & Sons, Inc., 2001. 720 p.

KauarkFabiana da SilvaManhãesFernanda CastroMedeirosCarlos HenriqueMETODOLOGIA DA PESQUISA:: UM GUIA PRÁTICO. Itabuna / Bahia: VIA LITTERARUM EDITORA, 2010. 89 p. Disponível em: <http://197.249.65.74:8080/biblioteca/bitstream/123456789/713/1/Metodologia%20da%20Pesquisa.pdf>. Acesso em: 30 Mai. 2017.

LesterPatrickA * Pathfinding para Iniciantes. policyalmanac. 2004. Disponível em: <http://www.policyalmanac.org/games/aStarTutorial_port.htm>. Acesso em: 21 Nov. 2016.

LugerGeorge F.INTELIGENCIA ARTIFICIAL. 6. ed. Pearson, 2013. 776 p.

MarkoffJohnEdsger Dijkstra,: 72, Physicist Who Shaped Computer Era. The New York Times. New York, 2002. Disponível em: <http://www.nytimes.com/2002/08/10/us/edsger-dijkstra-72-physicist-who-shaped-computer-era.html>. Acesso em: 4 Jun. 2017.

MatiasLindon FonsecaPOR UMA CARTOGRAFIA GEOGRÁFICA – UMA ANÁLISE DA REPRESENTAÇÃO GRÁFICA NA GEOGRAFIA. São Paulo, 1996. 476 p.  Dissertação (Geografia)UNIVERSIDADE DE SÃO PAULO Disponível em: <http://www.ige.unicamp.br/geoget/acervo/teses/Por%20uma%20Cartografia%20Lindon.pdf>. Acesso em: 22 Nov. 2016.

No Man’s Sky: Creating The Lore and Universe. IGN First. IGN. Florianópolis: IGN, 2016. Documentário (6min). Disponível em: <https://www.youtube.com/watch?v=B4mSWTnkdDY>. Acesso em: 21 Nov. 2016.

NovakJeannieGAME DEVELOPMENT ESSENTIALS: AN INTRODUCTION. 3. ed. New York: Delmar, Cengage Learning, v. 3, 2012. 514 p. Disponível em: <https://launchpadlibrarian.net/187759298/Game%20Development%20Essentials.pdf%20-%20Jeannie%20Novak.pdf#page=243&zoom=auto,-125,675>. Acesso em: 21 Nov. 2016.

PintoTalesEVOLUÇÃO DAS CIDADES. Brasil Escola. 2016. Disponível em: <http://brasilescola.uol.com.br/historia/evolucao-das-cidades.htm>. Acesso em: 17 Nov. 2016.

RussellStuart J.NorvigPeterArtificial Intelligence: A Modern Approach. New Jersey: Prentice Hall, 1995. 75 p.

SchellJesseThe Art of Game Design:: A Book of Lenses. Burlington: Morgan Kaufmann Publishers, 2008. 34 p.

ShakerNoorTogeliusJulianNelsonMark J.Procedural Content Generation in Games. Estados Unidos: Springer, 2016. 224 p. Disponível em: <http://pcgbook.com/>. Acesso em: 21 Nov. 2016.

SIEBERGDANIELVideo game ratings made by anonymous panel. CBS Interactive Inc, ano 2011, 27 Jun. 2011.CBS NEWS. Disponível em: <http://www.cbsnews.com/news/video-game-ratings-made-by-anonymous-panel/>. Acesso em: 21 Nov. 2016.

SommervilleIanEngenharia de Software. 8. ed. Pearson Addison-Wesley, 2007.

SousaRainerA ROTA DA SEDA. Brasil Escola. 2016. Disponível em: <http://brasilescola.uol.com.br/curiosidades/a-rota-seda.htm>. Acesso em: 17 Nov. 2016.

The Exterior MemoryDisjoint Path Finding. The Exterior Memory. Disponível em: <http://www.macfreek.nl/memory/Disjoint_Path_Finding>. Acesso em: 25 Mai. 2017.

VargasHeliana CominCOMÉRCIO E CIDADE: UMA RELAÇÃO DE ORIGEM. LabCom. São Paulo, 200. 5 p. Disponível em: <http://www.labcom.fau.usp.br/wp-content/uploads/2015/08/2000.-Com%C3%A9rcio-e-Cidade.-Uma-rela%C3%A7%C3%A3o-de-origem.pdf>. Acesso em: 17 Nov. 2016.

VogelHarold L.Entertainment Industry Economics: A Guide for Financial Analysis. 9. ed. New York: Cambridge University Press, 2015. 680 p.

APÊNDICE A — Cronograma

Cronograma

AtividadesNOVDEZJANFEVMARABRMAIOJUN
Selecionar o algoritmo utilizado para a criação de rotas.X      Entrega
Selecionar a linguagem utilizada para desenvolvimento da ferramenta.X      Entrega
Definir a utilização de servidores para executar a ferramenta.    X  Entrega
Definir o método de conexão aos servidores.    X  Entrega
Desenvolver o modelo UML da ferramenta.XXX    Entrega
Desenvolver o modelo do banco de dados para a ferramenta.XXX    Entrega
Desenvolver o protótipo ferramenta  XXXX  
Desenvolver o tópico explicando o desenvolvimento da ferramenta.      X 

Os autores (2016)

ANEXO A — Subtitítulo do anexo

Anexos são elementos que dão suporte ao texto, mas que não foram elaborados pelo autor.

feito

Use agora o Mettzer em todos
os seus trabalhos acadêmicos

Economize 40% do seu tempo de produção científica