Tag Archive | blowthemall

Representação do mundo de jogos Bomberman-like

Existem aqueles problemas não-imediatos como desempenho, elegância ou outros que apenas ficam no caminho para a primeira solução funcional. Há aqueles que condenam a prática de preocupação prévia e insistem em resultados imediatos. Estou trabalhando no desenvolvimento de um jogo similar ao Bomberman e precisei desenvolver uma solução para representar o mapa onde o mundo do jogo é executado. E, é claro, acabei tendo o luxo de escolher a abordagem de desenvolvimento onde a preocupação com problemas não-imediatos ocorre mais cedo que a entrega do produto.

Introdução

Para que o problema não fique muito abstrato, considere a imagem abaixo, retirada do jogo BlowThemAll.

shot-2015-05-09_14-08-52

O mapa do jogo possui uma implementação similar ao conceito de uma matriz, onde os elementos do mapa possuem uma posição <x, y> tal que essa posição não pode ultrapassar os limites da matriz e os índices x e y são números discretos, naturais. Cada posição no mapa é um tile e cada tile pode conter vários elementos.

O mapa contém elementos imóveis, tais como blocos a serem explodidos, e elementos móveis, tais como bombas e avatares. Avatar é um personagem que representa a conexão do jogador com o mundo virtual de BlowThemAll.

Há ainda blocos eternos, que não podem ser explodidos.

No jogo original, Bomberman, uma bomba explode e a explosão tem o alcance baseado em tiles. Itens aparecem somente em tiles específicos. Há muitas observações que sugerem fortemente o uso de uma matriz como uma representação eficiente para o jogo.

Problema

Jogando-se Bomberman é possível observar que um avatar pode estar entre dois tiles, então você não pode representá-los como um elemento em uma sequência que faz parte de algum tile, pois um avatar pode estar entre dois tiles. Logo, o avatar precisa ser independente dessa matriz e não pode ter sua posição representada por números discretos.

Abordagens iniciais

A primeira abordagem para o problema foi utilizar uma lista separada para esses elementos do mapa que podem assumir posições entre dois tiles e armazenar suas respectivas posições usando valores do tipo double (ou parecidos).

Entretanto, eu não me sinto confortável usando valores do tipo double em um jogo em rede. Primeiro, porque o comportamento de doubles não é trivial, e segundo, porque é difícil garantir reprodutibilidade/previsibilidade usando doubles, então  eu não quero lidar com o problema desses números sendo utilizados numa parte principal de um jogo em rede. Lembrando que o double que você está usando pode nem ser o IEEE floating point. É claro que eu iria ler o “what every computer scientist should know about floating point numbers” caso o projeto precisasse, mas eu queria, ao menos, considerar uma abordagem alternativa.

A minha ideia foi usar números discretos para as posições dos elementos não-fixos no mapa, e fazer numa escala diferente (se o mapa era 13×11 tiles, os elementos não-fixos estariam em uma matriz virtual 130×110) para permitir um valor mais granular (que emularia o fato do avatar poder estar entre dois tiles). Essa abordagem não me contentou, pois ela levantava outras perguntas (ex.: quão granular devo permitir a posição para permitir uma experiência de jogo agradável?), não era elegante e tirava a simplicidade que eu tinha na solução inicial, onde, era barata, a operação de encontrar quais os avatares eram atingidos por uma explosão.

Pensando nas restrições

Eu voltei ao problema inicial para pensar nas restrições que ele apresentava. A depender de suas restrições, o algoritmo poderia resolver um problema menor e mais simples. Foi essa a abordagem que me permitiu desenvolver a libdepixelize com menos código e mais rápido, e é isso que decidi também fazer no BlowThemAll, entender melhor o problema.

Daí, percebi algo enquanto jogava bomberman. O avatar pode sim, estar entre duas posições, mas caso ele esteja entre duas posições, ainda há um “tile principal” ao qual ele pertence. Isto é, ele só é atingido por uma explosão caso apenas um dos tiles, o “tile principal”, seja incendiado. Além disso, há a restrição de que ele só pode estar entre dois tiles, não entre quatro tiles. Todas essas informações me inspiraram o suficiente para pensar numa solução alternativa.

Solução final

A ideia-chave da solução que acabei adotando é armazenar os elementos na “matriz”, como estava inicialmente planejado, porém adicionar um atributo “filled”, que representava o quanto  daquele tile o elemento ocupa, e um atributo direção, que representa qual o próximo tile a ser ocupado, quando o elemento atual chegar no limite de desocupação do tile atual.

Conceitualmente, 1 representa o estado onde o elemento está ocupando somente aquele tile, 0 representa o estado onde ele não está ocupando nada daquele tile e temos também todos os valores intermediários (como ocorre em contas de probabilidade). Entretanto, queremos usar valores discretos, então usamos inteiros simples e usamos seus limites (0 e 255) para representar os limites conceituais (0 e 1).

Um elemento é transferido para o próximo tile, quando, conceitualmente, ele desocupa mais da metade do tile atual. Se mapearmos o comportamento conceitual para o comportamento em código, então haverá um desperdício de bits, pois o valor de filled nunca seria inferior a 127. Assim sendo, o valor 255 continua representando o conceitual 1, mas o valor 0 representa o conceitual 1/2.

E a solução ficou bem legal até, mas eu ainda queria mais. Uma granularidade de 256 valores possíveis parecia um desperdício para mim e eu queria usá-los para mais informações. Foi então que eu decidi separar preenchimento/ocupação/”filled” por dimensão. “dir” se transformou nos atributos “is_up” e “is_left”, enquanto “filled” se transformou nos atributos “y_filled” e “x_filled”. Usando campos de bits, consegui armazenar toda essa informação em um único byte.

Os atributos “is_up” e “is_left” podem lembrar o bit de sinal da representação de inteiros por complemento de 1, que desperdiça um valor possível, porém eu quero preservar a simetria, então esse desperdício é aceitável.

Essa separação por dimensão, entretanto, faz com que o objeto sempre assuma uma direção para cada dimensão. Se antes as opções de direção eram norte, sul, leste e oeste, agora as direções são nordeste, noroeste, sudeste, sudoeste. Essa característica não é um problema, mas é preciso manter ela em mente quando for implementar funcionalidades que dependem da direção do personagem (socos, por exemplo).

Outra consequência da separação é que o jogo volta a apresentar a possibilidade inicial onde um personagem pode assumir uma posição de estar entre quatro tiles. Essa é uma característica positiva, pois impõe menos restrições e dá mais liberdade artística aos autores de mapas. Essa possibilidade também está presente no jogo Bomberman Tournament e eu não quero fazer menos que os competidores.

E, assim, eu fiquei satisfeito, e surgiu o código do BlowThemAll para tratar mapas. É claro que eu não acho que usaria essa solução para um jogo estilo “The Legend of Zelda: A Link to the Past“, mas eu acho que ficou bem adequada a um jogo ao estilo de Bomberman. Pode ser que você ache interessante pesquisar também sobre Quadtree Collision detection.

Programação em tempo real

Caso não fosse um jogo em rede e que possui algumas características que eu não detalhei, eu estaria também mantendo a preocupação de fazer uma solução para programação em tempo real, afinal, é um jogo e queremos previsibilidade nos tempos de respostas máximos. Sem essa preocupação, a única modificação que pensei para melhorar a previsibilidade nos tempos de resposta seria usar a função vector::reserve para pré-alocar um pouco de memória para a lista de elementos em cada tile.

Final

E para acabar o post, deixo um vídeo de alguns segundos demonstrando o resultado:

Anúncios

BlowThemAll e o GIIEditor

Estou trabalhando no desenvolvimento de um jogo online open source do mesmo gênero que Bomberman chamado BlowThemAll. Recentemente consegui finalizar o editor que será utilizado para a criação de personagens, blocos e bombas (sim, o jogo será completamente customizável).

Antes de falar sobre o editor, acho que devo discutir sobre o problema que ele ajuda a resolver.

O problema

No jogo é possível encontrar vários objetos (personagens, bombas e blocos) que possuem animações. No entanto, existem alguns problemas em criar as animações para o jogo, pois elas possuem características próprias. Nessa seção vou detalhá-las.

O caso de animação mais simples entre os objetos do jogo é a bomba, que segue a mesma lógica de um GIF animado, uma animação estática, em que existe uma sequência de imagens que são processadas sequencialmente, com um intervalo definido entre uma imagem e outra.

Mas não podemos usar imagens GIFs, pois nem todas as animações do jogo seguem a mesma lógica. Como exemplo há os blocos, que, diferente das bombas, se mantêm estáticos, até o momento em que são explodidos e então uma animação ocorre. Diferente das bombas, a animação do bloco é dinâmica, pois pelo menos uma de suas propriedades (nesse caso o tempo em que ele fica estático), só pode ser conhecida depois que o jogo inicia.

Ainda no exemplo do bloco, podemos dizer que sua animação, apesar de dinâmica, é até simples, pois ela é linear, já que sempre segue a mesma sequência. Mas nem todos os objetos do jogo possuem animações que possuem essas características. Há o personagem, por exemplo, cuja animação segue uma sequência não-linear (em um dado momento ele pode estar em um estado de animação que simule o movimento na direção norte, e em outro momento um estado que simule o movimento em outra direção). Normalmente seria possível simular uma animação não-linear com uma animação linear, mas no caso do objeto do personagem, essa parte da animação também é dinâmica, eliminando essa possibilidade.

Princípios que a solução deve seguir

Além de resolver o problema, a solução que devemos adotar deve cumprir algumas promessas, que a adeque as regras de desenvolvimento utilizadas no jogo. Alguns pontos importantes em nosso caso são:

  • Lógica e funcionalidade devem ser separadas de arte e design: Então quando o desenvolvimento iniciar, o designer/artista deve ter liberdade de mudar muitos aspectos da animação sem que seja necessário esforço em conjunto dos desenvolvedores
  • As animações devem utilizar imagens vetoriais e padrões aberto: Queremos que o jogo rode nas principais plataformas disponíveis hoje, então devemos favorecer o uso de padrões abertos. Além disso, o uso de imagens vetoriais é interessante para permitir que o jogo funcione bem em diferentes resoluções de forma eficiente.
  • Deve ser possível armazenar, enviar e trocar o conjunto de animações para cada objeto: Assim cada jogador pode criar um personagem com identidade própria e usar essa identidade visual ao jogar durante as partidas, sejam elas locais ou online.

A solução

A solução que eu criei se apoia em três recursos. O primeiro é um esquema para arquivos INI descreverem o conjunto de animações do objeto. Para descrever essas animações, estados são definidos, e cada estado tem sua própria sequência de imagens, período de transição e ação ao término da animação (que é sempre uma referência a um novo estado ou começo dele próprio). Para permitir o dinamismo necessário no jogo, os estados possuem nomes, permitindo que acontecimentos no jogo mudem o estado do objeto usando esse nome como referência.

O segundo é um conjunto é um conjunto de arquivos de imagens vetoriais armazenadas no formato SVG.

O empacotamento do arquivo INI e dessas imagens compõe o terceiro recurso. O formato de empacotamento que utilizaremos no jogo é o rcc.

A implementação para essa solução foi algo rápido e seu código já encontra-se no repositório do jogo. O vídeo abaixo demonstra o uso dessa tecnologia:

O editor

Para o artista, porém, é algo inconveniente usar técnicas com as quais o programador está acostumado. Eu não conheço muitos artistas que gostariam de trabalhar editando arquivos descritivos e de marcação e usando programas que possuem uma interface de linha de comando para gerar o resultado final.

Para resolver esse outro problema, eu criei um editor com interface gráfica que possui, entre outras, as seguintes características:

  • Gerencia as imagens que serão incluídas no arquivo final
  • Gerencia os estados dos objetos, permitindo que vários estados sejam abertos simultaneamente, agrupados em abas
  • Pré-visualiza a animação do estado particular
  • Suporte a zoom
  • Além de compilar o resultado final, permite criar e salvar projetos
  • Permite criar um projeto vazio ou usando um dos modelos incluídos como base
  • Possui uma interface bastante intuitiva

Um vídeo que eu havia feito durante um dos estágios de desenvolvimento da ferramenta:

Caso queira utilizar essa ferramenta, baixe o código e compile-o usando os comandos:

Em breve devo colocar no repositório AUR para facilitar a vida dos usuários do Archlinux e algum dos outros desenvolvedores deve compilar uma versão para windows e distribuir o executável.

Para quem usa Archlinux: Coloquei o giieditor no AUR: http://aur.archlinux.org/packages.php?ID=51991.

NOTA: Para a funcionalidade “compilar” funcionar, você deve ter o rcc (aplicativo distribuído junto com o Qt) instalado e acessível pelo PATH.

%d blogueiros gostam disto: