Estou muito interessado no mercado de jogos, além disto estou participando de um grupo de desenvolvimento de jogos da USP, o que me faz buscar várias referências literárias sobre o assunto. Minha outra paixãozinha é a maratona de programação, uma competição onde são dados alguns problemas e temos que fazer um código (geralmente em C, C++ ou JAVA) que passe nos casos de testes de um juíz.
Apresento-lhes um dos meus problemas favoritos, uma mistura de jogo com a maratona: https://br.spoj.pl/problems/ZAK/. Este problema foi dado em uma prova regional aqui no Brasil.
Para resumir a história, temos um mago que deseja atravessar uma masmorra infestada de inimigos, sabemos quais são as magias do mago e o problema consiste em descobrir o mínimo de mana necessária para atravessar a masmorra.
Um sub-problema que encontramos aqui é: como matar um inimigo com o menor custo de mana possível. Como os inimigos são simples, ou seja, não têm resistências ou fraquezas, se soubermos matar um inimigo com x de vida, conseguiremos matar qualquer um com x de vida.
Sabemos também que os inimigos têm no máximo 1000 de vida, ou seja, se usarmos um algoritmo parecido com o algoritmo de programação dinâmica usado no problema da mochila (http://en.wikipedia.org/wiki/Knapsack_problem), resolveremos o problema de um modo satisfatório.
Um pseudocódigo com a idéia da mochila:
Claro que podemos usar uma tabela para memorizar esta função. Se chamarmos ela para todos os valores de 1 até 1000 teremos a tabela inteira preenchida no final e conseguiremos fazer consultas de modo bem eficiente quando precisarmos saber quanto de mana gastaremos para um determinado monstro.
to be continued...
Quem estudar na USP e estiver interessado no grupo de jogos que eu citei no começo, mande um email para mim (lima ponto natan arroba gmail ponto com) que podemos conversar. Precisamos de músicos, desenhistas, roteiristas e também programadores.
Apresento-lhes um dos meus problemas favoritos, uma mistura de jogo com a maratona: https://br.spoj.pl/problems/ZAK/. Este problema foi dado em uma prova regional aqui no Brasil.
Para resumir a história, temos um mago que deseja atravessar uma masmorra infestada de inimigos, sabemos quais são as magias do mago e o problema consiste em descobrir o mínimo de mana necessária para atravessar a masmorra.
Um sub-problema que encontramos aqui é: como matar um inimigo com o menor custo de mana possível. Como os inimigos são simples, ou seja, não têm resistências ou fraquezas, se soubermos matar um inimigo com x de vida, conseguiremos matar qualquer um com x de vida.
Sabemos também que os inimigos têm no máximo 1000 de vida, ou seja, se usarmos um algoritmo parecido com o algoritmo de programação dinâmica usado no problema da mochila (http://en.wikipedia.org/wiki/Knapsack_problem), resolveremos o problema de um modo satisfatório.
Um pseudocódigo com a idéia da mochila:
Mata_monstro( Inteiro vida){
variável mínimo = infinito
Se vida <= 0
devolva 0
Para cada magia M disponível
aux = (Mata_monstro(vida - dano de M) + custo de M)
mínimo = menor entre mínimo e aux
devolva mínimo
}
Claro que podemos usar uma tabela para memorizar esta função. Se chamarmos ela para todos os valores de 1 até 1000 teremos a tabela inteira preenchida no final e conseguiremos fazer consultas de modo bem eficiente quando precisarmos saber quanto de mana gastaremos para um determinado monstro.
to be continued...
Quem estudar na USP e estiver interessado no grupo de jogos que eu citei no começo, mande um email para mim (lima ponto natan arroba gmail ponto com) que podemos conversar. Precisamos de músicos, desenhistas, roteiristas e também programadores.
0 comentários:
Postar um comentário