Primeiramente, uma breve paráfrase do nosso colega Dilbert:
GAAAH!
Em um acidente de percurso, perdi todo o código-fonte da interface gráfica do editor. Ele tinha botões, checkboxes, janelas com “drag-and-drop”, tudo OO e fácil de usar. Era lindo.
Era.
Voltando à programação normal, vamos conversar um pouco sobre engines de plataforma. Mais especificamente, engines baseadas em tiles. A questão é: como mover o personagem e detectar colisões entre ele e o cenário?
Uma abordagem simples seria, a cada atualização, mover o personagem D pixels na direção desejada. Se a posição for inválida, o personagem é reposicionado.
Mas… e se o movimento foi tão acentuado que impossibilitou a detecção?
Uma solução é, dada uma reta entre o ponto de origem do personagem e o ponto de destino, testar a colisão com todos os blocos cuja intersecção com a reta não seja nula. Note que, para esse método funcionar, os blocos devem ser ordenados por ordem de intersecção.
Esse cara resolveu esse problema. Ele diz que o algoritmo é simples, rápido, etc etc (e realmente é!). Depois de relembrar as aulas de geometria vetorial, parti para implementar o algoritmo em Python. Vocês já devem imaginar o resultado. Embora deveria, ainda não trabalhei em uma implementação em C para comparar a performance, mas creio que isso não seja realmente necessário 
Entretanto, é suficiente. No meu teste, executei o algoritmo para 1000 pares de pontos de origem em destino, contidos entre (0,0) e (1000,1000). Isso seria como ter 1000 objetos se movendo a uma velocidade de até 1000 pixels por atualização de lógica. Com 30 atualizações de lógica por segundo, daria uns 30000 pixels por segundo. É um bocado, e provavelmente não vai acontecer. O resultado?
0.127067825659 segundos
Mudando para um cenário menos megalomaníacio: pontos entre (0,0) e (16,16), 128 objetos:
0.00307580991439 segundos
E mesmo se acontecer de se tornar um gargalo de desempenho, posso partir para a ignorância e usar artifícios com o psyco e bibliotecas como o mpmath.
Em breve faço um post com o código-fonte.
