2. Background
2.4 Petri Net
Para planejar o interior de uma sala usando intenções, as salas devem ser vistas como uma grade de células, assim como ilustrado na Figura 4.12 . O planeja- mento consiste em definir um caminho conectando todas as portas da sala. Essa definição deve conter informação suficiente para possibilitar sua futura geração visual.
Figura 4.12: Exemplo de sala vista como grade de células.
É interessante que o processo de definição deste caminho nunca gere ciclos, o que descarta uma implementação trivial em que uma nova direção é escolhida aleatoriamente à cada passo. Por este motivo, usaremos um outro processo.
Assumiremos que, na ausência de obstáculos, o layout das salas deve ser simples e permitir movimentação rápida, o que é até desejável neste gênero, uma vez o jogador deve via de regra atravessar uma mesma sala diversas vezes. Assim, o primeiro passo deve ser estabelecer um conjunto de pontos de conexão entre as linhas da sala. Os pontos de conexão estabelecem regiões em que o jogador deve ser capaz de transitar entre diferentes linhas da grade correspondente à sala. A Figura 4.13 mostra um exemplo de pontos de conexão.
Num segundo momento, é preciso criar um mapa de intenções com base nos pontos de conexão. O mapa de intenções possui um formato semelhante à grade de células da sala, e as intenções são representadas por direções. Cada célula no mapa de intenções pode ter até quatro direções ao mesmo tempo: norte, sul, leste e oeste.
Para criar o mapa de intenções, cada ponto de conexão deve adicionar uma intenção sul em sua célula e norte na célula imediatamente abaixo (Figura 4.14a). Isto representa que naquela região deverá haver uma conexão vertical. Além disso, todas as células que possuem portas adicionam intenções na mesma direção das portas, como ilustrado na Figura 4.14b.
53 4.4. Usando Intenções
Figura 4.13: Exemplo de pontos de conexão marcando as células de transição de nível.
(a) (b)
Figura 4.14: Exemplo ilustrando a marcação de intenções nos pontos de conexão (Figura 4.14a) e nas portas (Figura 4.14b).
A partir daí, para cada linha da grade, cada porta da linha deve emitir um fluxo de intenções lateral até que tal fluxo encontre um ponto de conexão. Caso não haja portas numa dada linha, usa-se os próprios pontos de conexão como partida. A direção das intenções é determinada da seguinte maneira: caso seja
a primeira intenção do fluxo, a direção é lateral, no sentido do fluxo; caso seja intermediária, a intenção tem direção dupla; caso seja a última, a direção é contrária ao sentido do fluxo. Um exemplo deste processo é dado na Figura 4.15.
Figura 4.15: Exemplo de construção dos fluxos de intenção.
Uma vez construído o mapa de intenções, é preciso marcar nos fluxos de intenção os intervalos de obstáculos. Intervalos de obstáculos determinam as regiões em que um obstáculo pode ser inserido. Eles são úteis para prevenir que o obstáculo de uma porta interfira no caminho de outras portas.
Os intervalos de obstáculos podem ser calculados por meio de um processo de três fases. Na primeira fase, escolhemos uma célua que faça parte do mapa de intenções para atuar como “centro”. Num segundo momento, partimos da célula de cada porta que possui obstáculo e seguimos o caminho inverso do fluxo de intenções até atingir o “centro”; as células visitadas são adicionadas ao intervalo de obstáculo correspondente, e caso seja visitada uma célula que já contém infor- mação de obstáculo, o processo para. Por fim, partimos da célula de cada porta que não possui obstáculos e percorremos o caminho até o centro, removendo as informações de obstáculos do caminho. No exemplo da Figura 4.16, as estrelas azuis representam o obstáculo de corda, enquanto a estrela verde representa o obstáculo de parede de pedra.
Apos a definição do mapa de intenções e dos intervalos de obstáculos, as regiões que não foram marcadas por intenções são consideradas neutras e podem
55 4.4. Usando Intenções
Figura 4.16: Exemplo de marcação dos intervalos de obstáculos.
ter qualquer representação visual. Na Figura 4.17 estas áreas são representadas por hachuras.
Figura 4.17: Definição de áreas neutras, exibidas em hachura.
Nesse ponto, os elementos que fazem parte do jogo, como portas, paredes, pisos, rampas, grades e caixas, são usados para cumprir as intenções em cada célula, como visto nas Figuras de 4.18a a 4.18c.
Como, nesta abordagem, os elementos atômicos de cenário são as células de uma sala, o uso de intenções pode ser usado como uma forma de planejamento
(a) (b)
(c)
Figura 4.18: Exemplo completo de geração visual de sala usando intenções. As barras em vermelho representam portas, e ambas as portas possuem obstáculos. A porta da primeira linha requer o uso de cordas, e a da última é selada com pedras.
para a abordagem de chunks descrita na Seção 4.1, pois garante a geração dos interiores e a colocação de obstáculos. Neste caso, tanto as possíveis ações do jogador quanto os possíveis obstáculos devem ser traduzidos em chunks.
Os resultados obtidos com a implementação desta técnica são discutidos no Capítulo 5.
Capítulo 5
Resultados
Vimos no Capítulo 4 diversas formas de geração visual de cenários, em diferentes graus de complexidade. Neste capítulo, analisamos os cenários produzidos pelo protótipo implementado com as etapas de planejamento do Capítulo 3 e a técnica da Seção 4.4 do Capítulo 4. Abaixo seguem as principais informações sobre esta implementação:
• Implementado como um aplicativo para iOS 5.0. • Implementado nas linguagens C++ e Objective-C. • Compilado com o Apple LLVM 3.0.
• Aproximadamente 2800 linhas de código. • Renderização em OpenGL ES 2.0.
Neste protótipo, os objetivos poderiam ter um dos seguintes tipos: ‘skill’, ‘skill_usage’,‘key’, ‘locked_door’, ‘boss’, ‘secret_passage’ e ‘end’. Objetivos do tipo ‘skill’ introduzem soluções, e objetivos do tipo ‘skill_usage’ introduzem obs- táculos que requerem o uso de uma determinada habilidade. Da mesma forma, objetivos do tipo ‘key’ são recíprocos aos do tipo ‘locked_door’. Objetivos do tipo ‘boss’ indicam um evento de confronto com algum inimigo chefe. Objetivos do tipo ‘secret_passage’ indicam a necessidade de se haver, em algum momento, uma porta camuflada e/ou escondida, e objetivos do tipo ‘end’ marcam o fim do cenário.
Além do seu tipo, os objetivos nesta implementação também apresentavam um tema, um buffer de dados e um campo de bits. O tema dos objetivos deter- mina o seu mapeamento de chunks e um conjunto de probabilidades usadas na etapa de geração visual. Já o buffer de dados genérico foi usado para armazenar informações como o tipo da habilidade em objetivos do tipo ‘skill_usage’ ou a identificação do inimigo em objetivos do tipo ‘boss’. Além disso, a fim de obter maior representatividade, introduzimos um campo de bits nos objetivos para in- dicar se um determinado objetivo era de secreto, o que se deveria refletir numa mudança visual; ou se deveria continuar no caminho anterior, de modo a usar como ponto de partida a última sala adicionada e não uma sala aleatória.
Consideramos a existência de quatro tipos de salas: TRANSIT_ROOM, COMBAT_ROOM, ACTION_ROOM e GOAL_ROOM. O propósito era in- troduzir variedade no cenário utilizando parâmetros distintos para gerar cada um destes tipos de salas. Salas de trânsito servem apenas para o jogador se locomover dentro do cenário; salas de combate oferecem desafios baseados em conjuntos de inimigos para o jogador; salas de ação requerem o uso de habilida- des adquiridas anteiormente para sua transposição, e salas de objetivo demarcam o local para se adicionar um objetivo. Além do tipo, as salas possuem posição, tamanho (representados por valores inteiros) e um conjunto de portas.
Uma sala pode possuir tantas portas quanto o tamanho do seu perímetro. Cada porta, por sua vez, pode ter um dos seguintes tipos: REGULAR_DOOR, LOCKED_DOOR, OBSTACLE_DOOR, CONTINOUS_DOOR e SECRET_DOOR. Portas regulares são normalmente representadas; portas trancadas podem ser abertas apenas por meio de chaves, obtidas em objetivos anteriores; portas com obstáculos são consequências de objetivos do tipo ‘skill_usage’; portas contínuas são um mecanismo para aumentar a variedade dos cenários gerados fazendo com que determinadas portas não sejam representadas, criando a ilusão de salas com design não exclusivamente retangular; o fato de uma porta ser secreta indica que ela deve estar escondida e camuflada junto aos elementos do cenário.
Para este protótipo, fixamos o game design e variamos apenas o level de- sign e o visual design. O game design determinado consiste da seguinte lista de objetivos:
59
1. Passagem secreta.
2. Chave. Objetivo secreto e que continua no mesmo caminho do anterior. 3. Porta trancada.
4. Chefe. Continuando no mesmo caminho do anterior.
5. Habilidade de míssil. Continuando no mesmo camiho do anterior. 6. Uso de habilidade de míssil, para destruir uma parede.
7. Chefe 2. Continuando no mesmo caminho do anterior. 8. Fim. Continuando no mesmo caminho do anterior.
Para a geração de visual design, utilizamos a abordagem de chunks com pla- nejamento baseado em intenções. Implementar a geração de cenário com base em chunks significava introduzir nos temas um mapeamento de intenções para coordenadas de textura. Para tanto, usamos uma mecânica de referência à coor- denadas de textura por índice, de modo que apenas um índice inteiro era sufuci- ente para representar as coordenas de textura de um determinado chunk. Para representar chunks em mais de uma textura, os índices de chunks foram des- locados para a esquerda em 4 bits e este espaço extra foi usado para indicar a textura de cada chunk, de modo a possibiliar que chunks em texturas distintas fizessem parte do mesmo tema. Desse modo, para cada possível configuração de intenções em uma célula, há ao menos um índice no mapa de chunks do tema em vigor. As Figuras 5.1 e 5.2 mostram exemplos de bibliotecas de chunks usadas no protótipo.
Graças ao uso de chunks, foi possível obter variedade na geração de visuais e ainda garantir sua corretude, como pode ser visto nas figuras de 5.1 a 5.4, que mostram exemplos de cenários gerados pelo protótipo. As figuras de 5.4a a 5.3f ilustram diferentes situações construídas pelo algorítmo, de modo a demonstrar sua versatilidade visual. Já as figuras 5.3g, 5.4 e 5.5 apresentam exemplos de cenários completos gerado com base na lista de objeivos anteiormente descrita.
Figura 5.1: Mapa de chunks usado na geração dos cenários da Figura 5.3. Com base nas figuras, é possível notar que a organização estrutural dos cená- rios gerados se assemelha à dos jogos de plataforma/aventura, graças às etapas de game design e level design.
Apesar de permitir a combinação do planejamento procedural com visuais feitos por artistas e garantir a corretude dos cenários gerados, a técnica proposta partilha de alguns dos problemas das abordagens baseadas em chunks. Em espe- cial, da necessidade de se ter uma grande quantidade de chunks para representar todas as possíveis situações.
Isto é especialmente crítico em jogos de plataforma/aventura, cujo gameplay é fortemente orientado à habilidades, uma vez que para cada habilidade distinta deve haver uma série de chunk para representar seu uso em diversas situações.
61
Figura 5.2: Mapa de chunks usado na geração dos cenários das figuras 5.4 e 5.5. Como consequência, e em virtude do tempo restante, não foi possível im- plementar no protótipo a renderização de portas ou obstáculos, visto que seria necessário uma quantidade sensivelmente maior de chunks para tanto. Isto se re- flete na ausência de elementos para representar portas ou obstáculos nas figuras de 5.3g a 5.5. Apenas a geração da geometria básica das salas foi pssível de ser gerada. Ainda assim, sua localização estava prevista no planejamento do interior de salas.
Além disso, os caminhos simples estabelecidos pelo uso de intenções conferem um visual semelhante a corredores para as salas, como visto na Figura 5.3, o que em muitos casos não é desejável. Este problema também poderia ser reduzido com uma maior biblioteca de chunks.
(a) (b)
(c) (d)
(e) (f)
(g)
63
(a)
(b)
(a)
(b)
Capítulo 6
Conclusão e Trabalhos Futuros
Neste trabalho, investigamos técnicas para a geração procedural de conteúdo em jogos de plataforma/aventura. Dividimos a geração de cenários em etapas de planejamento e geração de visuais.
O modelo de planejamento orientado a objeitivos, obstáculos e soluções do game design se mostrou suficiente para capturar a mecânica básica dos jogos de plataforma/aventura, e a etapa de geração de salas do level design se mostrou eficiente para capturar a estrutura básica dos cenários de jogos do gênero. Além disso, apesar de passíveis de falha (não conseguir gerar o plano eventualmente), as etapas de planejamento definidas garantem a corretude dos planos gerados do ponto de vista da lógica e do encadeamento de objetivos.
Uma vez definidas as etapas de planejamento de cenário, experimentamos di- versas abordagens para a realização visual dos planos. As abordagens exploradas buscaram obter mais diversidade usando progressivamente menos recursos em troca de maior complexidade. Eventualmente as lições aprendidas foram usa- das para se propor uma etapa de planejamento de interior de salas orientada a intenções, a ser usada com a abordagem de chunks.
Os resultados da implementação evidenciam que o uso de intenções e chunks é de fato suficiente para gerar cenários referentes às etapas anteriores. Contudo, a grande quantidade de chunks necessária para se representar as diversas situações pode inviabilizar o seu uso com um grande número de habilidades. Uma possível linha de pesquisa futura seria seria usar uma abordagem algorítmica, semelhante
à da Seção 4.2 do Capítulo 4, de modo a se compor chunks algorítmicamente por meio de construções menores, reduzindo a necessidade de recursos externos.
Em comparação à outros trabalhos da área, acreditamos que a relevância deste se econtra na tentativa de adaptar técnicas anteriores para o gênero de jogos de plataforma/aventura, e na introdução dos conceitos de planejamento orientado a objetivos.
Referências Bibliográficas
[1] Ernest Adams. Replayability part 2: Game mechanics. de Gama- sutra, http://www.gamasutra.com/view/feature/3059/replayability_ part_2_game_.php, July 2010. Online; último acesso em 12/02/2011. [2] Blizzard. Diablo. http://us.battle.net/d3/pt/. Online; último acesso
em 22/10/2011.
[3] Kate Compton and Michael Mateas. Procedural level design for platform games.
[4] Joris Dormans. Adventures in level design: generating missions and spaces for action adventure games. In Proceedings of the 2010 Workshop on Pro- cedural Content Generation in Games, PCGames ’10, pages 1:1–1:8, New York, NY, USA, 2010. ACM.
[5] Square ENIX. Dragon quest. http://www.square-enix.com/na/title/ dragonquest/. Online; último acesso em 20/02/2012.
[6] Square ENIX. Final fantasy. http://www.square-enix.com/na/title/ finalfantasy/. Online; último acesso em 20/02/2012.
[7] Runic Games. Torchlight. http://www.torchlightgame.com/. Online; último acesso em 22/10/2011.
[8] Kris Graft. Budgets for games going in ‘reverse direction’. http://www.gamasutra.com/view/news/30075/EA_Budgets_For_Games_ Going_In_Reverse_Direction.php, August 2010. Online; útimo acesso em 09/10/2011.
[9] Jason Gregory. Game Engine Architecture, pages 25–28. A K Peters, 2009. [10] G. Gygax and D. Arneson. Dungeons and dragons. http://www.wizards.
com/dnd/. Online; último acesso em 22/10/2011.
[11] Tom Ivan. Ubisoft: Development costs to double next gen. http://www. next-gen.biz/news/ubisoft-development-costs-double-next-gen, June 2009. Online; útimo acesso em 08/10/2011.
[12] Martin Jennings-Teats, Gillian Smith, and Noah Wardrip-Fruin. Polymorph: dynamic difficulty adjustment through level generation. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games, PCGames ’10, pages 11:1–11:4, New York, NY, USA, 2010. ACM.
[13] Konami. Castlevania - symphony of the night. http://www.konami.com/. Online; último acesso em 22/10/2011.
[14] Atanas Laskov. Level generation system for platform games based on a rein- forcement learning approach. Master’s thesis, The University of Edinburgh, 2009.
[15] P. Mawhorter and M. Mateas. Procedural level generation using occupancy- regulated extension. In Computational Intelligence and Games (CIG), 2010 IEEE Symposium on, pages 351 –358, aug. 2010.
[16] Nintendo. Super metroid. http://www.metroid.com/. Online; último acesso em 22/10/2011.
[17] J. Parish. Metroidvania. http://www.gamespite.net/toastywiki/index. php/Games/Metroidvania. Online, de Gamespite; último acesso em 22/10/2011.
[18] C. Pedersen, G. Togelius, and G. N. Yannakakis. Optimization of platform game levels for player experience. In Proceedings of Artificial Intelligence and Interactive Digital Entertainment, 2009.
[19] Markus Persson. Infinite mario bros. http://www.mojang.com/notch/ mario/. Online; último acesso em 22/10/2011.
69 Referências Bibliográficas [20] Gillian Smith, Mee Cha, and Jim Whitehead. A framework for analysis of 2d platformer levels. In Proceedings of the 2008 ACM SIGGRAPH symposium on Video games, Sandbox ’08, pages 75–80, New York, NY, USA, 2008. ACM.
[21] Gillian Smith, Mike Treanor, Jim Whitehead, and Michael Mateas. Rhythm- based level generation for 2d platformers. In Proceedings of the 4th Internati- onal Conference on Foundations of Digital Games, FDG ’09, pages 175–182, New York, NY, USA, 2009. ACM.
[22] N. Sorenson and P. Pasquier. The evolution of fun: Automatic level de- sign through challenge modeling. International Conference on Computer Creativity, jan 2010.
[23] J. Togelius, G.N. Yannakakis, K.O. Stanley, and C. Browne. Search-based procedural content generation: A taxonomy and survey. Computational Intelligence and AI in Games, IEEE Transactions on, 3(3):172 –186, sept. 2011.
[24] Michael Toy, Glenn Wichman, Ken Arnold, and Jon Lane. Rogue. http: //pcg.wikidot.com/pcg-games:rogue, 1986. Online; último acesso em 12/02/2011.
[25] Dereck Yu. Spelunky. http://spelunkyworld.com/. Online; último acesso em 22/10/2011.