Corrida de vetores, agora mais nerd

Quando eu estava no colegial, adorava jogar com meus colegas um joguinho meio matemático, entre nós conhecido como Corrida de Vetor.  É um jogo bastante popular, simples e divertido, bom para o tempo passar mais rápido naquelas aulas de chatas de Geografia. Tem uma versão online aqui.

Esses dias apareceu no meu Google Reader (share do ricbit) um post explicando um algoritmo para encontrar o caminho mínimo, dada a pista. Resumindo o post, o algoritmo é bem simples, usa apenas um grafo com todos os estados possíveis e uma busca em largura.

Cada vértice do grafo representará a posição na pista em x em y, e a velocidade em x e em y. Pra montar o grafo com todos os estados, é assim:

  • Começar o grafo com um vértice, que é a posição de largada com velocidade zero e colocá-lo na fila de vértices a processar.
  • Enquanto ainda tiver vértices na fila a processar:
    • Processar o próximo vértice na fila de vértices a processar. Colocar os novos vértices resultantes no fim da fila.

OK, mas o que significa este “processar o vértice” ? Significa gerar todos os vértices alcançaveis a partir do atual, ou seja, os vértices que são atingidos partindo do vértice atual com a velocidade que ele tem e todas as possíveis variações na velocidade (combinação de +1, 0 ou -1 na horizontal com +1, 0 ou -1 na vertical).

Tendo o grafo com todos os possíveis estados do jogo, o caminho mais curto tem que estar no grafo. Como todas as arestas tem o mesmo peso, nem precisamos usar o algoritmo de Dijkstra para achar o caminho mais curto. Ele será o primeiro a ser encontrado usando uma busca em largura. Na verdade, nem precisamos gerar todos os estados, podemos parar ao achar o fim da corrida, que é como eu implementei.

Como eu gostava muito do joguinho, fiz um programinha que lê uma pista em um arquivo texto, calcula o caminho mais curto e gera um gráfico com o caminho e uma representação das velocidades. O gráfico (tosquinho, eu sei), é assim:

Resultado do programa

Os quadrados vermelhos representam os pontos onde o jogador decide o que fazer e o tom de vermelho representa a velocidade, quanto mais escuro mais rápido.

Podemos ver que até o algoritmo “rouba” no jogo, passando pela grama pra evitar algumas curvas muito fechadas. Acho que isso até era permitido na regra sim.

Código-fonte e arquivo de pista

Dependências: PIL, python-graph

Anúncios
Publicado em Misc, Python. Tags: . 1 Comment »

Streets of Rage Remake e algumas descobertas

Primeiro, quero recomendar a todos que eram viciados em Streets of Rage (Megadrive) que baixem imediatamente o Streets of Rage Remake. É uma obra-prima. A jogabilidade está muitissimo fiel, a maior parte do jogo é baseada no Streets of Rage 2, mas há alguns elementos de SoR1 e SoR3 e também novas idéias como finais alternativos, novas fases, o Mr. X e Shiva como personagens secretos entre outras novidades.

Procurando sobre como destravar os personagens e modos secretos, achei num fórum: “I love the people who made this and if ever they need an organ transplant I have several superflous family members I would be happy to sacrifice.” Hahaha 🙂

Vamos às descobertas agora:

Descobri que o bolo na foto abaixo:

Axel e o bolo

NÃO É BOLO! Eu sempre pensei que fosse! Veja só o que aparece quando eu como:

Maçã

Ah uma maçã. Claaaro.

Assim como em Rock and Roll Racing, outro clássico, o que na figura abaixo parece ser uns pregos:

Graxa na pista

Nada de pregos. Graxa. O branco é o reflexo da luz. E não sou eu que sou maluco não, eu jogava RRR com meus amigos quando criança (e depois de crescido também) e ninguém percebeu que era graxa.

Ainda bem, porque prego não devia fazer rodar. 🙂

Damas resolvido :(

Acharam a estratégia infalível pra jogar Damas. Se ambos jogarem com a
mesma estratégia, dá empate (ou seja, o jogo não privilegia nem as
brancas nem as pretas)…

http://dsc.discovery.com/news/2007/07/19/checkers_tec.html?category=technology&guid=20070719140030

Esses malditos computólogos vão acabar com a graça de todos os jogos mesmo?

Publicado em Misc. Leave a Comment »

Que linguagem de programação é você?

Descaradamente copiado do blog do Roberto de Almeida. Morra de inveja, eu sou o Javascript! 🙂

You are javascript. People often think you are somebody else. You tend to be annoying to most people, but it's not your fault. You just get used.
Which Programming Language are You?

Publicado em Misc. 1 Comment »

Blog de volta

Depois de me encher de cuidar do meu próprio WordPress e passar por todas as instabilidades do meu antigo servidor, descobri que o próprio pessoal do WordPress está hospedando blogs! Isso é ótimo! Então, aqui está de volta meu humilde blog, desta vez muito mais estável.

Assim como antes, este blog não é um diário pessoal. Dificilmente vou falar da minha vida por aqui. Na verdade, o principal objetivo é ter um lugar para postar sobre coisas interessantes sobre tecnologia (em geral) que eu achei na internet ou que eu mesmo tenha criado.

Com o tempo vou repostando coisas do meu antigo blog aqui.

Abraços
Leandro Lameiro

Publicado em Misc. Leave a Comment »