Pelo o que eu entendi, o problema é exatamente a velocidade se maior que um tile por frame.
E se eu entendi bem, vc precisa não só determinar o tile final do movimento mas o conjunto de tiles por onde ele passaria naquele movimento.
A partir dai vc itera por esses tiles, na ordem do movimento, testando se o tile seguinte é sólido. Se não for, vc move. Se for vc sai da iteração, e o player irá ficar na posição correta.
A dificuldade é vc determinar esses tiles, dependendo do angulo do vetor. Vc pode usar seno e co-seno pra isso. Não sei se o que estou falando faz sentido, mas vamos a um pseudo código:
tileAtual = (1, 1)
velocidade = 3
angulo = math.radians(45) #em relação o eixo horizontal
movimentoHorizontal = math.sin(angulo) * velocidade
movimentoVertical = math.cos(angulo) * velocidade
movimentos = []
for i in range(tileAtual[0], tileAtual[0] + movimentoHorizontal):
movimentos.append((tileAtual[0], i))
for i in range(tileAtual[1], tileAtual[1] + movimentoVertical):
movimentos.append((tileAtual[1], i))
for index, movimento in enumerate(movimentos):
if tile(movimentos[index + 1]).solido:
break
player.move(tile(movimento))
Algo assim... é isso que vc precisa ou não tem nada a ver? :D