Movendo navios entre dois planetas ao longo de um bezier, faltando algumas equações para aceleração

OK, eu já postei isso em math.stackechange.com, mas não obtive nenhuma resposta :(

Primeiro, aqui está uma foto do meu problema, a descrição a seguir:

Então, eu tenho todos os pontos e valores configurados.

A nave começa a se mover pelo planeta esquerdo P1com um S=0.27 Degreesclique de jogo, quando chega Point Aa seguir a curva de bezier até chegar Point D, depois viaja pelo planeta certo P2com o S=0.42 Degreestique de jogo. A diferença Sé que a viagem com o mesmo movimento acelera os planetas.

Até aí tudo bem, eu coloquei isso em funcionamento, agora meu problema.

Quando S P1e S P2diferem muito, o navio salta entre as duas velocidades quando atinge seu destino, o que parece muito ruim. Então, preciso acelerar o navio entre Point Ae Point Dde S P1para S P2.

O que sinto falta está em roxo, são eles:

• Uma maneira de calcular os carrapatos que o navio leva para se mover ao longo do bezier, considerando a aceleração.

• E uma maneira de encontrar uma posição na curva bezier com base em T, considerando novamente a aceleração.

ATM Calculo o comprimento do bezier calculando a distância entre Nseus pontos. Então, o que eu acho que preciso é uma maneira de escalar o que Teu preciso colocar no meu cálculo de bezier de acordo com a aceleração.

OK, eu tenho tudo funcionando, demorou uma eternidade, então vou postar minha solução detalhada aqui.
Nota: Todas as amostras de código estão em JavaScript.

Então, vamos dividir o problema nas partes básicas:

1. Você precisa calcular o comprimento e os pontos entre 0..1na curva de bezier

2. Agora você precisa ajustar a escala do seu Tpara acelerar o navio de uma velocidade para outra

Como acertar o Bezier

É fácil encontrar algum código para desenhar uma curva de Bezier, porém existem várias abordagens diferentes, uma delas é o algoritmo DeCasteljau , mas você também pode usar a equação para as curvas cúbicas de Bézier:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

Com isso, agora é possível desenhar uma curva bezier chamando xe ycom tquais intervalos 0 to 1, vamos dar uma olhada:

Não é realmente uma distribuição uniforme dos pontos, é?
Devido à natureza da curva de Bézier, os pontos 0...1têm diferentes arc lenghts, portanto, os segmentos próximos ao início e ao final são mais longos do que os que estão próximos ao meio da curva.

Mapeamento de T uniformemente na parametrização de comprimento de arco da curva AKA

Então o que fazer? Bem, em termos simples, precisamos de uma função para mapear o nosso Tpara o tda curva, para que os nossos T 0.25resultados no tque é pelo 25%do comprimento da curva.

Como fazemos isso? Bem, nós pesquisamos no Google ... mas acontece que o termo não é tão googleable e, em algum momento, você acessará este PDF . O que com certeza é uma ótima leitura, mas no caso de você já ter esquecido todas as coisas de matemática que aprendeu na escola (ou simplesmente não gosta desses símbolos matemáticos), é bastante inútil.

E agora? Bem, vá ao Google um pouco mais (leia-se: 6 horas) e você finalmente encontrará um ótimo artigo sobre o assunto (incluindo fotos legais! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Fazendo o código real

Caso você não consiga resistir ao download desses PDFs, embora já tenha perdido seu conhecimento matemático há muito, muito tempo (e você conseguiu pular o ótimo link do artigo), agora você pode pensar: "Deus, isso levará centenas de linhas de código e toneladas de CPU "

Não, não vai. Porque fazemos o que todos os programadores fazem, quando se trata de coisas matemáticas:
simplesmente trapaceamos.

Parametrização do comprimento do arco, a maneira preguiçosa

Vamos ser sinceros, não precisamos de precisão infinita em nosso jogo, precisamos? Portanto, a menos que você esteja trabalhando na Nasa e planejando enviar às pessoas o Marte, não precisará de uma 0.000001 pixelsolução perfeita.

Então, como Tmapeamos t? É simples e consiste apenas em 3 etapas:

1. Calcule Npontos na curva usando te armazene o arc-length(também conhecido como comprimento da curva) nessa posição em uma matriz

2. Para mapear Tpara t, em primeiro lugar multiplicar Tpelo comprimento total da curva para obter ue então procurar o conjunto de comprimentos para o índice do maior valor que é menor do queu

3. Se tivermos um resultado exato, retorne o valor da matriz nesse índice dividido por N, se não interpolar um pouco entre o ponto encontrado e o próximo, divida a coisa novamente Ne retorne.

Isso é tudo! Então agora vamos dar uma olhada no código completo:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

Isso inicializa nossa nova curva e calcula o arg-lenghts, ele também armazena o último dos comprimentos como o total lengthda curva, o principal fator aqui é this.lenqual é o nosso N. Quanto mais alto, mais preciso será o mapeamento, pois uma curva do tamanho da figura acima 100 pointsparece ser suficiente; se você precisar apenas de uma boa estimativa de comprimento, algo como 25já fará o trabalho com apenas um pixel de distância em nossa exemplo, mas você terá um mapeamento menos preciso que resultará em uma distribuição não uniforme de Tquando mapeado para t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

O código de mapeamento real, primeiro fazemos um simples binary searchem nossos comprimentos armazenados para encontrar o maior comprimento menor targetLength, depois retornamos ou fazemos a interpolação e o retorno.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

Novamente, isso calcula tna curva.

Tempo para resultados

Agora, usando mxe myvocê obtém uma distribuição uniforme Tna curva :)

Não foi tão difícil, foi? Mais uma vez, acontece que uma solução simples (embora não perfeita) será suficiente para um jogo.

Caso você queira ver o código completo, há um Gist disponível:
https://gist.github.com/670236

Finalmente, acelerando os navios

Então, tudo o que resta agora é acelerar os navios ao longo de seu caminho, mapeando a posição em Tque usamos para encontrar a tcurva.

Primeiro, precisamos de duas das equações de movimento , a saber ut + 1/2at²e(v - u) / t

No código real, seria assim:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Em seguida, reduzimos isso 0...1fazendo:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

E lá vai você, os navios estão agora se movendo suavemente ao longo do caminho.

Caso isso não funcione ...

Quando você está lendo isso, tudo funciona bem e bem, mas inicialmente tive alguns problemas com a parte da aceleração. Ao explicar o problema para alguém na sala de bate-papo do gamedev, encontrei o erro final em meu pensamento.

Caso você ainda não tenha esquecido a imagem na pergunta original, mencionei slá, a svelocidade é em graus , mas as naves se movem ao longo do caminho em pixels e eu esqueci esse fato. Então, o que eu precisava fazer nesse caso foi converter o deslocamento em graus em deslocamento em pixels, mas isso é bastante fácil:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

Então e isso é tudo! Obrigado pela leitura;)

A questão é que um navio não seguiria essa trajetória naturalmente. Portanto, mesmo com o funcionamento perfeito, ainda não parecerá correto.

Se você deseja simular a transição suave entre planetas, eu sugeriria realmente modelá-lo. As equações são muito simples, pois você tem apenas duas forças significativas: gravidade e impulso.

Você só precisa definir suas constantes: massa de P1, P2, navio

Com cada jogo-tick (time: t) você está fazendo 3 coisas

1. Calcule a gravidade de p1 no navio e p2 no navio, adicione os vetores resultantes ao vetor de empuxo.

2. Calcule sua nova velocidade com base na sua nova aceleração da etapa 1

3. Mova a nave de acordo com sua nova velocidade

Pode parecer muito trabalho, mas pode ser feito em uma dúzia de linhas de código e parecerá muito natural.

Se precisar de ajuda com a física, me avise.

Encontrei um excelente artigo explicando uma possível solução para esse problema com um exemplo de código escrito em javascript. Ele funciona "empurrando o valor t" na direção certa.

Em vez disso, podemos usar o fato de que o comprimento médio da perna d_avg para qualquer distribuição de pontos é quase idêntico ao comprimento da perna que os pontos com espaçamento uniforme produziriam (essa similaridade aumenta à medida que n aumenta). Se calcularmos a diferença d_err entre o comprimento real da perna d e o comprimento médio da perna d_avg, o parâmetro de tempo t correspondente a cada ponto pode ser ajustado para reduzir essa diferença.

Essa pergunta já tem muitas respostas legais, mas achei que vale a pena notar essa solução.

Obrigado pela excelente página que descreve como você resolveu esse problema. Eu fiz algo um pouco diferente de você em um detalhe, pois estava com muita memória restrita: não construo uma matriz ou tenho que procurá-la pelo 'segmento' certo com uma pesquisa binária. Isso é porque eu sempre sei que estou passando de uma extremidade da minha curva de Bezier para outra: Portanto, simplesmente me lembro do segmento 'atual' e, se perceber que vou sair dos limites desse segmento para calcular minha próxima posição, eu calculo o próximo (ou anterior) segmento (com base na direção da viagem). Isso funciona muito bem para o meu aplicativo. A única falha que tive que resolver foi que, em algumas curvas, o tamanho dos segmentos era tão pequeno que minha próxima plotagem a apontar foi - em momentos raros - mais de um segmento à frente do atual, então, em vez de apenas ir ao '

Não sei se isso faz sentido, mas isso certamente me ajudou.

Esse tipo de modelagem é estranho e pode produzir resultados ilógicos estranhos. Especialmente se a velocidade inicial dos planetas for realmente lenta.

Modele os navios com um poder de empuxo.

Quando os navios estiverem em sua última órbita no planeta inicial, acelere com força total.

Quando a nave chegar a uma certa distância, use o impulso reverso para diminuir a velocidade da órbita do planeta alvo.

Editar: faça a simulação inteira de uma só vez quando um nó estiver prestes a sair da órbita. envie todos os dados ou envie apenas alguns vetores de movimento em intervalos e interpole entre eles.

Se eu entendi direito, seu problema está excessivamente restrito.

Acredito que você deseja que a nave espacial viaje ao longo de um caminho especificado entre as órbitas em algum tempo t e também que acelere da velocidade s1 para a velocidade s2 no mesmo tempo t . Infelizmente, você não pode (em geral) encontrar uma aceleração que satisfaça essas duas restrições simultaneamente.

Você precisará relaxar um pouco o seu problema para torná-lo solucionável.

Eu me deparei com essa resposta porque estou procurando distribuir pontos uniformemente ao longo de um caminho svg que usa uma curva mais bezier.

Apesar do MDN dizer que está obsoleto, você pode usar o path.getPointAtLengthpara obter o resultado correto. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

Atualmente, ele funciona no Chrome / Safari / Firefox e deve funcionar no IE / Edge também, mas não os verifiquei 2.

O problema com a solução aceita

Como Bezier é uma função exponencial , esperamos diferentes taxas de avanço em diferentes áreas da curva.

Como a solução da Ivo interpola linearmente entre esses exponenciais iniciais amostras , as imprecisões serão fortemente influenciadas pelas extremidades / meio da curva (geralmente cúbica) onde esses deltas são maiores; portanto, a menos que a taxa de amostragem Naumente bastante, como ele sugere, os erros são aparentes e, em algum nível de zoom, sempre serão aparentes para um dado N, ou seja, o viés é intrínseco a esse algoritmo. Não é bom para, por exemplo, gráficos baseados em vetores em que o zoom pode ser ilimitado.

Viés de combate através de amostragem guiada

Uma solução alternativa é remapear linearmente distancepara tdepois de combater o viés natural que a função Bezier produz.

Supondo que é isso o que idealmente queremos:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

mas é isso que obtemos da função de posição de Bezier:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Observando as Namostras coletadas, podemos ver onde os deltas de distância são maiores e reamostrar ("dividir") a meio caminho entre as duas distâncias adjacentes, aumentando Nem 1. Por exemplo, dividindo em t=0.9(que está no meio do delta maior), podemos pegue:

0.8    5.81
0.9    7.39
1.0    10.00

Repetimos esse processo para o próximo maior intervalo de distância até que o delta máximo entre duas distâncias em todo o conjunto esteja abaixo de algumas minDistanceDeltae, mais especificamente, a menos do que epsilondistância das distâncias específicas das quais queremos mapear as etapas t; podemos mapear linearmente o desejadot passos para distances correspondentes . Isso produz um hashtable / mapa que você pode acessar de forma barata e cujos valores você pode ler entre, em tempo de execução, sem preconceitos.

À medida que o conjunto cresce N, o custo para repetir isso aumenta, então, idealmente, faça isso como um pré-processo. Cada vez que Naumenta, adicione os dois novos intervalos resultantes a uma intervalscoleção enquanto remove o intervalo único antigo que eles substituíram. Essa é a estrutura na qual você trabalha para encontrar o próximo maior intervalo a ser dividido em dois. Manter a intervalsclassificação por distância facilita as coisas, pois você pode simplesmente sair do próximo item de trabalho e dividir etc.

Acabamos com algo parecido com o que idealmente queríamos:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Como adivinhamos a cada passo, não obteremos exatamente as distâncias exatas 2,4 etc., desejávamos, mas, através da repetição da iteração, eles se aproximam o suficiente dos valores de distância desejados para que você possa mapear seus tpassos com precisão razoável, eliminando o viés devido amostragem quase equidistante.

Você pode recuperar t=0.5, por exemplo , como Ivo faz em sua resposta, ou seja, interpolando entre os dois valores mais próximos acima ( 3.9998132e 6.00703).

Conclusão

Na maioria dos casos, a solução do Ivo funcionará bem, mas nos casos em que o viés deve ser evitado a todo custo, verifique se seus distances estão o mais dispersos possível e, em seguida, mapeados linearmente parat .

Observe que a divisão pode ser feita de forma estocástica, em vez de ser dividida no meio de cada vez, por exemplo, podemos dividir o intervalo do primeiro exemplo em t=0.827vez de em t=0.9.