O fantástico mundo de Natan

Achievement

2010-10-04T18:31:00.000-07:00

Ganhei um achievement. Tomara que venham outros esse ano!!

Legibilidade de código e código fedido!

2010-09-03T06:53:00.000-07:00

Código legível é um assunto meio difícil pois sai da nossa racionalidade matemática e entra na parte mais humana, onde o que é bom para um não necessariamente é bom para outros.

Gostei muito de ler o livro Refactoring: Improving the Design of Existing Code (Martin Fowler, Kent Beck e outros). Há um capítulo que disserta sobre maus cheiros no código e acho que eles são um bom indicativo sobre a qualidade do código. Alguns maus cheiros que o livro cita são: Classes grandes, métodos grandes, números mágicos pelo código.

Há uma frase bem interessante que atribuem ao Donald Knuth mas posteriormente ele disse ser de autoria de outra pessoa que diz: We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Acho esta frase bem interessante e a interpreto como: "prefira legibilidade a pequenas otimizações", porém, isto também é só mais um fator de ilegibilidade.

Participando de projetos um pouco maiores, com mais de 3 ou 4 pessoas trabalhando, começo a perceber que além de otimizações prematuras e maus cheiros, há um outro fator que torna o código
sujo, ilegível ou fedido. O estilo de programação é um fator que influencia tanto empresas grandes como o Google, como projetos open source como o kernel do linux.

Todo programador tem um estilo próprio de produzir código e, quando estamos participando de um projeto grande, precisamos adotar o estilo do projeto. Apesar de adotarmos um estilo diferente, podemos tirar proveito de suas vantagens para melhorar nosso próprio estilo.

Atualmente eu tenho basicamente dois estilos diferentes: um que uso em um projeto na faculdade e outro que uso ao resolver problemas de maratona de programação. Já me deparei com pessoas/empresas que diziam que a maratona estragava a pessoa e a fazia escrever códigos difíceis de entender. Eu sou totalmente contra este tipo de idéia. Acho que na maratona é fundamental ter um estilo e produzir código limpo, caso contrário o resto do time não poderá ajudá-lo sem perder muito tempo. Claro que isto não se aplica a times russos/poloneses que nunca erram. =)

Em suma, acho que esses dois estilos que uso atualmente,se ajudam entre si e me dão a oportunidade de melhorar meu estilo de programação no geral. Na minha opinião, devemos sempre tentar melhorar nosso estilo e não estacionar quando uma prática ou outra nos convém.

Portfólio para trabalhar com games e SP Game Show

2010-07-20T17:22:00.000-07:00

Faz tempo desde minha última postagem. Enfrentei um fim de semestre turbulento, mas aqui estou de volta com algumas impressões que tirei do SP Game Show. O evento foi bem interessante! Ele aconteceu junto com o Anime Frieds, o Comic Fair e o Asian Fest. Desses, eu só conhecia o Anime Friends.

O meu objetivo maior esse ano foi o SP Game Show e eu fui na sexta-feira (16 de Julho). Assisti palestras que me motivaram e também outras que me desmotivaram. Acho que o objetivo maior de um desenvolvedor de jogos é fazer jogos que eles chamavam de triple A, ou seja, os jogos top de linha. Mas no Brasil, pelo que eu percebi, a praia é outra: Temos que nos focar em jogos de celular e redes sociais para conseguir crescer e ganhar maturidade para os grandes. Outras opções frequentes dos brasileiros são os advergames, os games mais casuais e, por fim, um ramo não muito explorado mas promissor pode ser os serious games. Um advergame bem interessante mostrado pela Viviane Werneck na palestra dela foi o Music Score feito para promover a banda Bet Set. Muito bem feito e parece ser bem divertido (fórmula do guitar hero não tem erro =P).

Uma dúvida que eu tinha era a respeito do curso que fiz (bacharelado em ciência da computação). Conversei com o Júlio César da empresa Cooper Games e a resposta foi positiva. Segundo ele, as empresas olham com bons olhos os formados em ciência da computação!

Perguntei também se a falta de conhecimento em determinadas tecnologias atrapalhava. Só para explicar a intenção da pergunta, o curso que eu fiz no IME-USP tem uma abordagem bem teórica sobre ciência da computação, muitas vezes deixando parte da tecnologia atual um pouco de lado e o mercado muitas vezes exige que dominemos tecnologias específicas, como Flash, Java, OpenGL. Eu concordo que são tecnologias básicas e fundamentais na área de games, mas creio que o curso dê o conhecimento necessário para sermos versáteis e aprendermos com facilidade tecnologias atuais e futuras. A resposta de Júlio novamente foi positiva: ele me disse que o curso cobria diversas áreas importantes no desenvolvimento de jogos, como física e álgebra linear, apesar do gosto das empresas pelo conhecimento em tecnologia.

Para entrar no mundo das empresas de games ele me deu uma dica bem interessante: a criação de um portfólio. Ele disse que poderia ser um portfólio simples, com jogos como tetris ou pac-man, algum joguinho usando OpenGL também não faria mal.

Já fiz alguns joguinhos simples e atualmente estou em um projeto maior com um grupo de estudantes da USP, mas ainda não "documentamos" nada. Em breve, pretendo começar a criar um portfólio bem legal e ir postando a situação dos jogos! Uma sequência bem conhecida para começar a programar jogos é: Primeiro alguma cópia do tetris, em seguida uma cópia de Arkanoid e depois Pac-man. Essa ordem é sugerida pois a dificuldade para criá-los é diferente e eles acabam abrangendo grande parte do que jogos mais avançados usam.

Políticas de commit para projetos grandes

2010-05-28T04:28:00.000-07:00

Participando de projetos grandes começamos a perceber a importância de certas atitudes que não colocamos em prática sempre. Respeitar alguma política ao commitar é uma delas.

Encontrei na internet a política de commits do KDE e concordei com muitos itens, então, irei traduzir uma parte dela e adicionar comentários pessoais.

Pense duas vezes antes de commitar

Commitar algo pelo controle de versão tem várias consequências. Todos os desenvolvedores pegarão suas mudanças e se estas quebram alguma coisa, quebrará para todos. Todos os commits serão públicos no repositório para sempre.

Por outro lado, o controle de versão permite recuperações de versões antigas, possibilitando eventuais consertos de commits errados. O trabalho de recuperação é simples quando é necessário mudar poucos arquivos, mas pode ser trabalhoso quando são commitados grandes mudanças.

Nunca commite código que não compile

Corrija os erros e compile o código antes de commitar. Certifique-se que os arquivos novos foram adicionados e serão commitados. Se forem esquecidos, podem fazer o projeto compilar localmente, mas para o resto do grupo não compilará.

Faça testes e certifique que eles passem

Rode a aplicação e veja se a parte afetada pela sua mudança funciona como esperado. Caso o projeto tenha testes de unidade ou testes de regressão, rode-os e certifique-se de que eles passem. Se não o fizer, quando outras pessoas fizerem mudanças no projeto, verão o teste quebrado e pensarão que quebraram algo, perdendo tempo com depuração.

Cheque mais de uma vez o que irá commitar

Faça update e diffs antes de commitar. Leve a sério mensagens de conflito e de arquivos desconhecidos que o controle de versão emitir. Geralmente há várias ferramentas que mostram exatamente o que você está commitando. Cheque se é isso mesmo que você deseja commitar.

Sempre escreva mensagens de log descritivas.

Mensagens de log devem ser compreendidas por alguém que olhe apenas para o log. Elas não dependem de informações fora do contexto do commit.

Em particular, coloque toda informação relevante que não podem ser vistas no diff na mensagem de log.

Respeite políticas de commit definidas nos planos de lançamento

Evite commitar novas funcionalidades e código pouco antes do lançamento. Além disto, controles de versão não substituem a comunicação entre os desenvolvedores.

Seja responsável pelos seus commits

Se suas mudanças quebraram algo ou apresentam efeitos colaterais em código alheio, se responsabilize por arrumar e ajudar a arrumar os problemas.

Não mande código que você não entenda

Evite frases como "Eu não sei porque dá esse erro, mas quando faço isso ele funciona", ou "Não tenho certeza que funciona, mas pra mim tá funcionando".

Se não encontrar solução para algum problema, discuta com outros desenvolvedores.

Não commita código se outra pessoa discorda

Se existe divergência de opiniões, discuta em listas de e-mail ou em particular, mas não force um código por commit para os outros.

Não adicione arquivos gerados automaticamente ao repositório.

Arquivos gerados em tempo de compilação não devem ir ao repositório pois podem causa conflitos. Apenas arquivos com código fonte devem estar no repositório. Uma excessão são arquivos gerados por ferramentas como cmake ou scripts necessários para a compilação.

Commitar conjunto de mudanças completos.

Geralmente controles de versão têm a habilidade de submeter vários arquivos por vez. Sempre commite todas as mudanças feitas e diretórios criados no mesmo commit. Desta maneira você garante que o repositório continue em um estato compilável antes e depois de um commit.

Não misture mudanças de formatação com mudanças no código.

Mudar formatação, como espaços e identação, faz os diffs ficarem mais extensos e fica mais difícil achar mudanças de código se elas estão misturadas com
re-identações e coisas similares, tanto no log como nos diffs.

Acabei omitindo algumas e mudando o conteúdo de outras, mas basicamente está tudo aí. No caso do KDE, eles usam SVN como controle de versão então há bastante referência ao SVN, mas as idéias servem para qualquer projeto usando qualquer controle de versão.

Creio que são dicas até meio óbvias, mas geralmente não colocamos em prática algumas delas em projetinhos pequenos, trabalhos de faculdade e etc. Porém, são dicas bem úteis para um projeto um pouco maior e até mesmo para estes projetos.

Coloquem em prática a maioria delas e contem a experiência.

Design pattern Strategy para fazer a IA nos jogos

2010-05-26T10:39:00.000-07:00

Recentemente tive que entregar um trabalho em que o objetivo principal era comparar inteligência artificial superficial e inteligência artificial aparente. Não há uma definição muito formal desses tipos de inteligência artificial. Vejam a palestra que o professor Flávio Soares Corrêa da Silva (que passou o trabalho) apresentou sobre o assunto na Campus Party. Basicamente, inteligência artificial aparente é a inteligência usada nos games.

Para o trabalho tivemos que implementar um jogo não jogável, onde existe duas partículas: uma é a partícula perseguida e a outra a perseguidora. No caso como era um projetinho rápido, a perseguida anda pelo labirinto de maneira aleatória. Para a perseguidora, tivemos que implementar duas inteligências: uma utilizando apenas A* e indo atrás da perseguida e outra que apenas vai atrás da perseguida quando a enxerga.

Como tenho estudado alguns conceitos de programação orientada a objetos, decidi fazer o trabalho em Action Script e usar o design pattern Strategy para implementar a parte da inteligência artificial.

Primeiro, decidi que a inteligência seria bem simples: ela apenas recebe um ponto do mapa (a posição da partícula) e decide para qual posição irá. Sendo assim criei uma interface Strategy:


public interface Strategy{
     function execute(point:Point):Point;
}

Nas classes referentes às partículas, basta ter uma instância de alguma classe que implemente a interface e chamar o execute quando for necessário uma atualização da posição. Cada partícula deveria ter um tempo diferente de atualização então coloquei isso na classe das partículas também.

As classes relacionadas a inteligência ficaram bem modularizadas e fáceis de programar. O uso do design pattern valeu a pena!

Eis o resultado final:

Use a tecla 'a' para gerar blocos aleatórios na tela.
Use a tecla '0' e clique para colocar uma partícula que se move aleatoriamente sem colidir com as paredes.
Use a tecla '1' e clique para colocar uma partícula que usa o algoritmo A* para pegar a partícula gerada acima.
Em vez de '1', use a tecla '2' para colocar uma partícula que persegue a partícula aleatória apenas se esta for visível.

Se quiser dar uma olhada no código para ver como implementei as inteligências e outras coisas do projeto pode baixá-lo em: projeto

Double dispatch no tratamento de colisões em jogos

2010-05-07T06:54:00.000-07:00

É recorrente em algumas aulas de programação orientada a objetos, meu professor dizer que é uma heresia perguntar a classe de um objeto.

Participo de um grupo de jogos e chegamos em um determinado ponto em que precisamos tratar as colisões. O problema aqui é um problema de engenharia mesmo, não algorítmico. Sabendo que existe colisão entre dois objetos, como fazemos para tratá-lo.

Vamos supor que temos as classes Jogador, Inimigo, Tiro e BonusDeVida. No caso todas essas classes herdam de uma classe em comum chamada ObjetoDeJogo.

Mostrarei um exemplo de como poderia ser a classe Jogador em C++ com uma solução não muito bonita.

class Jogador : public ObjetoDeJogo{
   public:
   virtual void trataColisao(ObjetoDeJogo* obj){
      if((Inimigo *inimigo = dynamic_cast<<Inimigo> *>( obj )) != NULL){
         cout << "Colidiu com inimigo!" << endl;
      }
      if((Tiro *tiro = dynamic_cast<<Tiro> *>( obj )) != NULL){
         cout << "Colidiu com tiro!" << endl;
      }
      if((BonusDeVida *bonus = dynamic_cast<<BonusDeVida> *>( obj )) != NULL){
         cout << "Colidiu com bonus!" << endl;
      }
   }
};

Deste modo funciona, porém estamos cometendo a heresia de perguntar a classe do objeto em que o Jogador está colidindo. É um método bem simples de resolvermos o problema, porém vai contra alguns princípios de orientação a objetos. Pela falta de polimorfismo desta abordagem, sofreríamos no futuro com algumas desvantagens.

Existiriam várias classes implementando esses métodos que tratam colisões e com o passar do tempo, os métodos ficariam bem grandes com a adição de novos tipos de colisão.
O tratamento de colisão não está muito bem encapsulado, caso fizessemos métodos para cada tipo de colisão, ainda assim teríamos que mexer no conjunto de "ifs" sempre que quisessemos adicionar uma nova colisão.

Uma solução interessante para o problema é o uso de double dispatch, a página da wikipedia explica bem a técnica e há uma implementação em C++, mas para completar a postagem vou mostrar como ficaria a classe Jogador usando a técnica de double dispatch.

class Jogador : public ObjetoDeJogo{
   public:
   virtual void trataColisao(ObjetoDeJogo* obj){
      obj->trataColisao(this);
   }
   virtual void trataColisao(Inimigo* obj){
      cout << "Colidiu com inimigo!" << endl;
   }
   virtual void trataColisao(Tiro* obj){
      cout << "Colidiu com tiro!" << endl;
   }
   virtual void trataColisao(BonusDeVida* obj){
      cout << "Colidiu com bonus!" << endl;
   }
};

O C++ não implementa double dispatch nativamente, por isso devemos tomar alguns cuidados. Por exemplo, todos os tipos possíveis da função trataColisao devem existir na classe ObjetoDeJogo para que este método funcione do jeito esperado.

Após as classes terem sido criadas, podemos usar os objetos no loop principal do jogo, da seguinte maneira:

vector<ObjetoDeJogo *> objetosDeJogo;
objetosDeJogo.push_back(new Jogador());
objetosDeJogo.push_back(new Inimigo());
objetosDeJogo.push_back(new BonusDeVida());

for(int i = 0;i < objetosDeJogo.size();i++){
   for(int j = i+1;j < objetosDeJogo.size();j++){
      objetosDeJogo[i]->trataColisao(objetosDeJogo[j]);
      objetosDeJogo[j]->trataColisao(objetosDeJogo[i]);
   }
}

O loop principal continua o mesmo nos dois casos, usando dynamic_cast e double dispatch, porém com double dispatch aproveitamos melhor o polimorfismo que orientação a objetos nos oferece. Com double dispatch, se adicionarmos uma classe nova colidível, precisaríamos escrever uma assinatura nova do método trataColisão na classe ObjetoDeJogo e também implementar os métodos necessários nas classes que mudam algo com a colisão deste objeto de jogo novo.

O que você acha de double dispatch? Sabe resolver este problema de um jeito melhor?

Maratona de programação e Jogos continuação

2010-04-24T12:22:00.000-07:00

Anteriormente no fantástico mundo de Natan, eu contei sobre o problema ZAK GALOU, para resumir, temos um mago que quer ir de uma sala à outra em uma masmorra e precisa matar os monstros no caminho e também ensinei a matar os monstros. Contarei como resolvi o próximo problema, o de atravessar a masmorra.

Para representar a masmorra podemos usar um grafo, os vértices deste grafo serão as salas da masmorra e as arestas são representações dos corredores entre as salas (vértices). O custo de cada aresta vw será o custo mínimo de mana necessária para matar todos os monstros do vértice w.

Para calcular o custo mínimo de mana necessária usada no vértice w basta usarmos o seguinte algoritmo:


custo_vertice(vertice V){
   para todo monstro M no vértice V
       soma = soma + mata_monstro(M)
   devolva soma
}

Deste modo temos um grafo com custo nas arestas e podemos usar o algoritmo de Dijkstra para calcular o menor caminho entre os dois vértices pedidos.

Como estou envolvido em alguns projetos de jogos no momento, comecei a pesquisar alguns algoritmos de busca, eu conhecia os mais clássicos como BFS, DFS e Dijkstra, e já tinha ouvido falar bastante do A*, porém nunca tinha parado para pensar sobre ele. Em jogos é incomum o uso de BFS ou DFS, a BFS não funciona quando temos custos nas arestas e a DFS pode nos devolver caminhos bem estranhos então eu gostaria de fazer uma comparação entre o algoritmo de Dijkstra e o algoritmo A*.

Assintoticamente os dois algoritmos são parecidos (Se a função heurística for descente), porém, para a maioria das aplicações práticas em jogos, o algoritmo A* parece ser melhor do que o algoritmo de Dijkstra. Por que??

O algoritmo de Dijkstra não pressupõe nada sobre o destino, ele não faz uso desta informação para procurar o melhor caminho, ou seja, quando ele finalmente chega ao destino, potencialmente o algoritmo já visitou todos os vértices que tenham distância menor ou igual ao destino. Enquanto isso, no lustre do castelo, temos o A* que usa alguma informação extra como heurística para chegar ao destino. Esta informação depende da representação do grafo, por exemplo, em um grid poderíamos usar a distância de manhattan ou a distância euclideana produzindo caminhos possivelmente diferentes.

Se você ficou interessado mas não tem idéia do que estou falando, pode começar pelos seguintes links:

Algoritmo de Dijkstra
Algoritmo A*

Sim, eu gosto da wikipedia =)

Maratona de programação e Jogos

2010-04-23T06:51:00.000-07:00

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:


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.

Prólogo

2010-04-21T18:54:00.000-07:00

O título do blog foi idéia da minha namorada. Eu não lembrava muito bem do desenho "O fantástico mundo de Bob". Como faço com quase todos os assuntos que não sei ou não lembro muito bem, fui a wikipedia para dar uma olhada no artigo e li a seguinte frase: "It was about the daily life of Bobby Generic and his very overactive imagination on how he sees the world".

Fiquei bastante impressionado pois passei a amar o título do meu blog, ele descreve fielmemente o que quero passar. Vou reformular a frase em português para definir meu blog formalmente: Este blog apresentará minha vida (talvez não diariamente) e minha imaginação fértil ao ver o mundo. Voilà.

to be continued ...