O War Legacy - Parte 2 - TimeStep

Olá pessoal, aqui é o Lince. Bem vindos de volta.
Como vocês estão?

Quanto tempo hein? Minha casa tá cheia de poeira, me desculpem aí. Tenho passado uma temporada bastante ruim com o resto da minha vida, então fiquei evitando receber visitas aqui com a cara toda bagunçada hehe.
Eu sei que, provavelmente por causa do título, vocês vieram aqui para saber sobre o War Legacy, mas eu quero falar sobre umas coisinhas antes. Rapidinho.

O Pequeno Lince: Mais uma vez (acho que já disse isso antes), não são tirinhas de humor. Apesar de que na maioria delas possui um certo humor distorcido, obscuro e subvertido presente, e que algumas delas já fizeram pessoas rir (vide comentários), não fiz/faço elas com esse intuito. Meu objetivo com as tirinhas é contar uma história, talvez com mais tempo a história fique mais clara e/ou faça mais sentido para os quem a lê. To planejando uma tirinha bem legal para essa semana =).

Enfim, de volta ao War Legacy (WL). Caso você não saiba, o War Legacy é um projeto que comecei há dois anos atrás com o objetivo de aprender mais sobre programação para jogos. A ideia era simples, tudo que eu estudasse sobre o assunto eu tentaria aplicar no WL, devo dizer que vem dado bastante certo de lá pra cá e que eu aprendi bastante. O projeto acabou se tornando muito maior do que eu esperava, então resolvi transformar ele num jogo de verdade. Eu criei essa série aqui "O War Legacy" para dividir um pouco do conhecimento que adquiri nesses anos estudando programação para jogos.

E no episódio de hoje: Timestep!

Timestep é a forma com que a engine do seu jogo controla a passagem de frames, esta pode ser feita principalmente de três formas diferentes:

Forma Intuitiva

É a forma mais fácil de fazer o laço do jogo, simplesmente porque não existe controle da passagem de frames. A taxa de Frames por Segundo (FPS) do seu jogo é totalmente dependente da máquina onde ele está rodando.
Esse tipo de implementação pode vir a calhar quando se tratar de um jogo que não possua física, como jogos puzzle, point-and-click, tabuleiro, etc. Digo isso porque mensurar quantos cálculos por segundo seu sistema de física faz é extremamente importante para manter a consistência e evitar lag e delay.

Lag é o que acontece quando os estímulos são mandados ou recebidos pelo jogo numa taxa mais lenta do que a desejada.
Delay é quando os estímulos enviados pelo jogo não correspondem ao estado atual do jogo, mas a algum estado anterior.
Adendo: Estímulos que falo aqui são imagens mostradas na tela, sons, música de fundo, botões apertados nos controles, etc. Ou seja, o que é usado para estabelecer comunicação entre o jogo e o jogador.

Pseudocódigo Intuitivo

enquanto ( jogo_rodando ) { update(); render(); }

A função update() atualiza o estado dos objetos do jogo.
A função render() desenha o estado atual do jogo na tela.

TimeStep Variável

Nesse caso, a atualização do estado do seu jogo é dependente do "tempo passado desde a ultima atualização" e, por isso, também dependente do FPS do jogo.
Usando este método, os objetos do seu jogo teriam atributos de movimentação informando a distancia que ele percorre por segundo (D/S). Portando, a cada segundo passado de movimentação deste objeto, ele deve se mover uma distância D, porém a posição do objeto é atualizada a cada frame, e para saber a distância que o objeto deve percorrer a cada frame deve-se calcular quanto tempo se passou desde a ultima atualização (DeltaTime) e fazer a transformação:
novaPosicao = posicaoAtual + distanciaPorSegundo * DeltaTime;
Considerando que este DeltaTima é a fração de segundo desde a ultima atualização. Por exemplo, se passou 0.3s desde a ultima atualização do estado do jogo, precisamos saber o quanto o objeto se moveu de acordo com sua velocidade que é 25 pixels/segundo. Então, neste frame, o objeto se moveu 25p/s * 0.3s = 7.5 pixels.

Pseudocódigo Variável

enquanto( jogo_rodando ) { tick_anterior = tick_atual; tick_atual = getTickAtual(); update(tick_atual - tick_anterior); render(); }

Esse é o pseudocódigo básico de como seria um sistema baseado em TimeStep Variável.
A função getTickAtual() retorna o valor de um contador de milissegundos do sistema.
A função update() atualiza o estado dos objetos do jogo. Note que ela toma como parâmetro a diferença entre o tick_atual e o tick_anterior, ou seja, a quantidade de milissegundos passados desde a ultima atualização.
A função render() desenha o estado atual do jogo na tela.
Mais detalhadamente vamos usar um exemplo em que um certo objeto do jogo se move a 25 pixels/segundo, vejamos a que passo ele se movimentaria de acordo com a taxa de atualização:
A 25 p/s e começando no ponto 0 (zero), devemos esperar que no final de 1 (um) segundo ele estará no ponto 25.

Começamos no tempo 0 (zero) e o primeiro frame demorou 0.2 segundos para acontecer, vamos calcular onde o objeto deve estar neste frame:
Velocidade(pixels por segundo) * tempo(desde a última atualização) = Movimento(do frame atual)
25 p/s * 0.2 s = 5 p
Ou seja, no momento 0.2s o objeto se moveu do ponto 0 até o ponto 5:

O segundo frame demora 0.4s para acontecer, ou seja, ele é processado no tempo 0.6s, calculando onde o objeto deve estar temos:
25 p/s * 0.4 s = 10 p
Então, no momento 0.6s o objeto se moveu do ponto 5 até o ponto 15:

O terceiro frame não demorou a vir e aconteceu no tempo 0.7s, ou seja, 0.1s de diferença do último. Vamos calcular:
25 p/s * 0.1 s = 2.5 p

Como devem ter percebido, a posição do objeto aproxima-se a passos variáveis da posição em que prevemos que ele deveria estar no decorrer de 1 segundo.

Finalmente:

Prós	Contras
Renderização suave	Difícil de gravar/repetir cenas já que cada segundo tem uma quantidade variável de ações
Sem interpolação, código "mais fácil"	Erros de física estranhos e difíceis de prever

TimeStep Fixo

Neste ultimo caso, a atualização do jogo é feita "a cada período fixo de tempo". Ou seja a taxa de Frames por Segundo do jogo é preferencialmente fixa.
Para calcular movimentos de objetos estes precisam informar sua velocidade expressa em Distância percorrida a cada Frame. Então o calculo é dado por:
novaPosicao = posicaoAtual + distanciaPorFrame;
Se a velocidade estiver expressa em Distância por Segundo, a conversão é feita de forma fácil pois a taxa de Frames por Segundos é conhecida e fixa.
V(DistPorFrame) = V(DistanciaPorSegundo) / FramePorSegundo
Dois pontos importantes precisam ser levados em conta quando se trabalha com esta técnica: Framerate máximo e Interpolação
Framerate máximo acontece porque a quantidade de atualizações por segundo que o jogo fará já está escrito em código, e quando a máquina na qual o jogo está rodando possui um poder de processamento que o permita rodar numa taxa maior do que essa, ocorre uma perda de desempenho. Não porque o jogo não está rápido como deveria estar, mas porque não está rápido como poderia estar.
É aqui que entra Interpolação. Ela serve para cobrir esses buracos entre cada atualização na hora de renderizar o jogo. Na verdade a interpolação é uma técnica aconselhada sempre que se usar TimeStep fixo, mas o problema do Framerate máximo é um bom exemplo prático de sua utilização. A ideia é fazer o jogo rodar bem em máquinas lentas, mas ainda assim aproveitar os recursos de uma máquina rápida.
Interpolação é o cálculo (ou estimativa) de como o estado do jogo estaria se ele estivesse sido atualizado num certo frame. Ela é feita como uma regra de três, observe o pseudocódigo abaixo:

Pseudocódigo Fixo

enquanto( jogo_rodando ) // Laço principal { enquanto( getTickAtual() > prox_game_tick) // Laço de atualização { update(); prox_game_tick += PULAR_TICKS; } interpolacao = (GetTickAtual() + PULAR_TICKS - prox_game_tick) / PULAR_TICKS ; render( interpolacao ); }

A função getTickAtual() retorna o valor de um contador de milissegundos do sistema.
A função update() atualiza o estado do jogo. (Note que dessa vez ela não recebe parâmetros)
Dê uma atenção especial a forma que o código calcula quando o jogo deve ser atualizado.
A variável interpolacao é uma fração representando o quanto tempo se passou desde a ultima atualização. Por exemplo, se o jogo deve ser atualizado a cada 6 segundos e passaram-se 3 segundos desde a ultima atualização, interpolacao terá o valor 1/2.
A função render() desenha o estado do jogo na tela, recebendo como parâmetro a interpolacao para fazer os devidos ajustes na hora de apresentar o estado do jogo. Digo, se interpolacao tem o valor 1/2, o estado do jogo deve ser mostrado 1/2 do caminho a frente do estado atual.
Escrevi um pequeno código em C++ para simular o pseudocódigo e nos mostrar os valores de tickAtual e interpolacao, o resultado foi o seguinte:

Código fonte (c++):

#include 
#include 

int tickAtual = 1;

int getTickAtual()
{
    return tickAtual++;
}

int update()
{
    printf("update:: ");
    printf("tickAtual: %d\n", tickAtual);
    tickAtual++;
}

int render(float interpolacao)
{
    printf("render:  ");
    printf("tickAtual: %d ", tickAtual);
    printf("interp: %f\n", interpolacao);
    tickAtual++;
}

int main()
{
    bool jogoRodando = true;
    int prox_game_tick = 0;
    int PULAR_TICKS = 15;
    float interpolacao;
    
    while ( jogoRodando ) // Laço principal
    {
        while ( getTickAtual() > prox_game_tick) // Laço de atualização ++
        {
            update(); // ++
            prox_game_tick += PULAR_TICKS;
        }
        interpolacao = float((getTickAtual() + PULAR_TICKS - prox_game_tick)) / float(PULAR_TICKS) ; // ++
        render( interpolacao ); // ++
        
        if (getTickAtual() > 50) jogoRodando = false; // ++
    }
    
    system("pause");
    return 0;
}

Note que, num código "de verdade", o tickAtual não seria uma variável que manipularíamos dessa forma. Ela seria uma variável do sistema que só teríamos acesso em forma de consulta. Eu criei ela nesse código apenas para ficar mais fácil fazer testes, assim eu posso controlar precisamente quando e quanto ela incrementa.
Também note que o código foi escrito em c++ simplesmente porque a linguagem me dá algumas vantagens em relação ao c apesar de não ter usado nenhum conceito de Orientação a Objeto no código. Ou seja, ele poderia ser reescrito para funcionar perfeitamente em c, mas eu sou um tanto preguiçoso. Fica de tarefa pra você, aliás. E não saia por aí dizendo que estou perpetuando más práticas de programação por causa disso! =)

Propositalmente fiz a engine chamar a função render() várias vezes entre os intervalos de cada update() para ficar claro o papel da interpolação nesse caso. Note como a cada chamada de render() (que imprime "render: tickAtual: x interp: y") o valor de interp aumenta proporcionalmente, com o objetivo de gerar uma renderização continua e suave do movimento, mesmo que o objeto não tenha sido atualizado há algum tempo.
Para melhor ilustrar a situação, analise o gráfico a seguir. O quadrado azul é o nosso objeto de acordo com sua posição em memória, o quadrado vermelho é o mesmo objeto na posição que ele seria mostrado na renderização com interpolação:

E finalmente:

Prós	Contras
A física é bem previsível	Necessidade de usar interpolação para evitar Framerate máximo e, em alguns casos, lag
Possível facilidade de sincronizar com jogadores via internet	Dificuldade para trabalhar com frameworks que assumem TimeStep Variável

Como já me estendi bastante, vou parar por aqui. Esperem uma conclusão desse assunto e os comentários a respeito do WL na próxima visita!

Então é isso, espera que tenham gostado e aprendido alguma coisa, deixa um comentário aí. E como sempre vocês podem me encontrar no tuiter @LinceAssassino para qualquer dúvida, sugestão, crítica ou simplesmente se quiser trocar uma ideia.
Abraços do Lince.

Fontes:
Glenn Fiedler's Fix Your TimeStep!
deWiTTERS Game Loop

Tweetar