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:

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