Como calcular caminhos para objetos com aceleração limitada?

Por exemplo, digamos que eu tenho um carro e um carro tenha um raio de giro mínimo específico e desejo dirigir esse carro do ponto a ao ponto b, mas o carro não está voltado para o ponto b. Como computo um caminho para o ponto b? Ser capaz de especificar a orientação no ponto b também seria bom (digamos que você queira dirigir até a garagem e depois estacionar na garagem - não é muito bom se você chegar à entrada da casa dirigindo pelo gramado. e estão de lado :)

Um ponteiro para a documentação (ou mesmo apenas um nome) seria perfeitamente adequado - estou tendo problemas para encontrar alguma coisa.

Nas minhas tentativas, eles funcionam em casos simples, mas falham miseravelmente em situações como quando o ponto b está mais próximo de a do que o raio de giro mínimo.

Por exemplo, como você determinaria um caminho semelhante a este (o caminho em negrito):

edit: No meu problema real, existem algumas restrições simples de percurso, mas eu já tenho um algoritmo A * que funciona, mas ele permite que as coisas façam alterações instantâneas de rumo, então parece bobo ver um carro fazer uma curva de 90 graus em um centavo quando chegar a um ponto de viragem.

Ainda não resolvi as equações completas para isso, mas aqui estão alguns recursos visuais para ajudar a entender o problema. Tudo se resume a alguma geometria:

( Ícones de carros via Kenney )

A partir de qualquer ponto de partida e orientação, podemos desenhar dois círculos com o raio de viragem mínimo - um à esquerda e outro à direita. Eles descrevem os pontos do começo mais estreito possível ao nosso caminho.

Podemos fazer o mesmo para qualquer posição final e orientação desejadas. Esses círculos descrevem o fim mais apertado possível do nosso caminho.

Agora, o problema se reduz a encontrar um caminho que une um dos círculos iniciais a um dos círculos finais, beijando cada um ao longo de sua tangente.

(Isso pressupõe que não precisamos encontrar obstáculos intermediários, que não foram mencionados na pergunta. A resposta do Stormwind aborda como podemos usar as informações do gráfico de navegação para esses tipos de problemas. Depois que tivermos a sequência de nós para passar, podemos aplicar o método abaixo para cada segmento do plano.)

Se, por simplicidade, usamos linhas retas, obtemos algo assim:

Isso nos dá o caso limitante. Depois de encontrar um caminho por esse método, você pode aumentar artificialmente um ou ambos os círculos inicial e final para obter um caminho menos direto, porém mais suave, até o ponto em que os dois círculos se beijam.

Computando esses caminhos

Vamos elaborar os casos para uma direção de virada - digamos que começamos nosso caminho virando à direita.

O centro do nosso círculo de viragem à direita é:

startRightCenter = carStart.position + carStart.right * minRadius

Vamos chamar o ângulo da seção reta do nosso caminho (medido a partir do eixo x positivo) pathAngle

Se desenharmos um vetor a partir rightCenterdo ponto em que deixamos o círculo giratório (nesse ponto, devemos estar de frente para pathAngle), então esse vetor será ...

startOffset = minRadius * (-cos(pathAngle), sin(pathAngle))

Isso significa que o ponto em que deixamos o círculo deve ser ...

departure = startRightCenter + startOffset

O ponto em que reintroduzimos um círculo de viragem depende se pretendemos terminar com uma curva à esquerda ou à direita:

// To end with a right turn:
reentry = endRightCenter + startOffset

// To end with a left turn: (crossover)
reentry = endLeftCenter - startOffset

Agora, se nós fizemos nosso trabalho direito, a linha que une departurea reentrydeveria ser perpendicular à startOffset:

dot(reentry - departure,  startOffset) = 0

E resolver esta equação nos dará o (s) ângulo (s) em que isso é verdade. (Eu uso um plural aqui, porque tecnicamente existem dois desses ângulos, mas um deles envolve dirigir em marcha à ré, o que geralmente não é o que queremos)

Vamos substituir a curva da direita para a direita como exemplo:

dot(endRightCenter + startOffset - startRightCenter - startOffset, startOffset) = 0
dot(endRightCenter - startRightCenter, startOffset) = 0
pathAngle = atan2(endRightCenter - startRightCenter)

O caso do crossover é mais complicado - ainda não resolvi toda a matemática. Vou postar a resposta sem por enquanto, caso seja útil para você enquanto trabalho nos detalhes restantes.

Edit: Destino dentro do raio de giro mínimo

Acontece que esse método geralmente funciona imediatamente, mesmo quando o destino está mais próximo do que a nossa distância mínima de giro. Pelo menos parte de um dos círculos de reentrada acaba fora do raio de virada, permitindo-nos encontrar um caminho viável, desde que não nos importemos com a aparência de um pretzel ...

Se não gostarmos do caminho que seguimos dessa maneira (ou se não for viável - não verifiquei todos os casos exaustivamente - talvez existam impossíveis), sempre podemos seguir em frente ou voltar até encontrar uma solução adequada. beijando o contato entre um círculo inicial e final, conforme diagrama acima.

Isso depende muito do restante do seu modelo de dados para a navegação. Ou seja. quais dados você tem à mão, quais você pode adicionar facilmente e como os consome.

Tomando um cenário semelhante a partir de um sistema de tráfego na água, e assumindo que

• você está em um loop de jogo
• você tem um sistema de caminho do nó
• seus carros se comportam como objetos autônomos que se controlam "por dentro", usando força e direção próprias
• seus carros não se movem como nos trilhos

você poderia ter algo como abaixo (perdoe-me pela aparência infantil das fotos)

(Os quadrados vermelhos são os nós, as linhas vermelhas são as interconexões dos nós. Suponha que você tenha usado um solucionador de busca de caminhos que forneceu os nós 1-9 para percorrer; nós 4-9 vistos na imagem e você deseja percorrer os nós indicados pela linha verde , para a garagem no nó # 9; no entanto, você não deseja ir com precisão para a linha verde, permaneça naturalmente na faixa do lado direito e faça manobras suaves).

Cada nó teria metadados que contêm, por exemplo, um raio, ou múltiplos, para vários propósitos. Um deles é o círculo azul, que fornece orientações objetivas para os carros .

Em qualquer ocasião , o veículo precisa estar ciente dos próximos dois pontos de nó P (próximo) e P (próximo + 1) e suas posições. Naturalmente, o carro também tem uma posição. Um carro aponta para a tangente do lado direito do círculo azul de metadados de P (próximo). O mesmo acontece com carros indo na direção oposta, portanto eles não colidirão. Mirar na tangente significa que o carro pode se aproximar do círculo de qualquer direção e manter-se sempre à direita. Este é um princípio básico aproximado, que pode ser aprimorado de várias maneiras.

P (próximo + 1) é necessário para determinar a distância - à medida que o carro alcança P (próximo) ou fica dentro de um raio de seus metadados, ele pode ajustar o ângulo de direção, dependendo da distância que P (próximo + 1) está. Ou seja. se estiver perto, vire muito, se estiver longe, vire pouco. Aparentemente, também precisa haver outras regras e condições de borda, por exemplo, cálculo de uma distância entre o carro e uma linha de ajuda com base nas tangentes do lado direito de P (próximo) e P (próximo + 1), e uma correção por isso - vontade de permanecer na linha tracejada (foto acima) e pontilhada (foto abaixo).

De qualquer forma, quando o carro passa por um nó , ele o esquece e começa a observar os próximos dois .

Para sua pergunta. Aparentemente, ao atingir o nó 7 (na foto acima, visto como o nó 2 na figura abaixo), ele não pode girar o suficiente .

Uma solução possível: construir algumas linhas de ajuda e manter uma meta o tempo todo , e depois fazer o carro seguir suas próprias configurações físicas (acelerar a uma taxa especificada, reverter mais devagar, levar em consideração os limites de velocidade dos metadados do nó, freios a um dado ou calculado G, etc.). Como dito, o carro é um objeto autônomo, autoexplicativo e auto-transportador neste cenário.

Tenha as linhas de ajuda verdes 1,2,3 . Quando o carro atinge o círculo magenta , ele começa a virar à direita. Neste ponto, você já pode calcular que não terá êxito (você sabe a taxa máxima de rotação e pode calcular a curva e pode ver que ela cruzará as linhas de apoio 2 e 3). Gire a direção totalmente para a direita e deixe-a dirigir à frente (por incrementos da física) e reduza a velocidade quando alcançar a linha de ajuda 3 (se aproxima dos limites de uso, f (distância da linha de apoio) etc). Quando estiver na linha de ajuda 3, entre no modo reverso , gire a direção no sentido oposto . Deixe-o inverter até alcançar a linha de ajuda 4(a linha de conexão entre o nó 1 e 2 - google para "ponto ao lado do algoritmo de linha"). Desacelere, quando o alcançar, entre novamente no modo de avanço , gire o volante. Repita até que a estrada esteja limpa - aparentemente foi suficiente com 1 manobra extra dessa vez.

Esta é a ideia geral: durante o ciclo do jogo ou ao verificar o sistema de tarefas de jogos:

• Verifique a posição, velocidade, ângulo etc. do carro em relação aos limites e objetivos atuais da borda ,
• Se ainda não foi alcançado , continue com o que estava fazendo (deixe a física movê-lo; o carro tem uma rotação e uma marcha). Insira uma nova verificação no seu sistema que, por exemplo, 0,1 s.
• Se alcançado , calcule novas condições, defina os dados e comece . Insira uma nova verificação para ocorrer no sistema que, por exemplo, 0,1 s.
• Complete o ciclo do loop - continue, repita.

Ao fornecer dados suficientes aos nós e aos carros, haverá movimento e continuação.

Edit: E adicionando: Isso naturalmente precisa de ajuste fino. Seu comportamento de simulação pode exigir diferentes linhas de ajuda, metadados, círculos, qualquer coisa. Isso daria uma idéia de uma solução possível.

Acabei fazendo o que o DMGregory sugeriu e funciona bem. Aqui está um código relevante (embora não autônomo) que pode ser usado para calcular os dois estilos de tangentes. Tenho certeza de que esse código não é eficiente e provavelmente nem está correto em todas as situações, mas está funcionando para mim até agora:

bool Circle::outer_tangent_to(const Circle & c2, LineSegment & shared_tangent) const {
    if (this->direction != c2.direction) {
        return false;
    }
    if (this->radius != c2.radius) {
        // how to add it: http://mathworld.wolfram.com/Circle-CircleTangents.html
        // just subtract smaller circle radius from larger circle radius and find path to center
        //  then add back in the rest of the larger circle radius
        throw ApbException("circles with different length radius not supported");
    }

    auto vector_to_c2 = c2.center - this->center;
    glm::vec2 normal_to_c2;
    if (this->direction == Circle::CW) {
        normal_to_c2 = glm::normalize(glm::vec2(-vector_to_c2.y, vector_to_c2.x));
    } else {
        normal_to_c2 = glm::normalize(glm::vec2(vector_to_c2.y, -vector_to_c2.x));
    }

    shared_tangent = LineSegment(this->center + (normal_to_c2 * this->radius),
                                 c2.center + (normal_to_c2 * this->radius));
    return true;
}


bool Circle::inner_tangent_to(const Circle & c2, LineSegment & tangent) const {

    if (this->radius != c2.radius) {
        // http://mathworld.wolfram.com/Circle-CircleTangents.html
        // adding this is non-trivial
        throw ApbException("inner_tangents doesn't support circles with different radiuses");
    }

    if (this->direction == c2.direction) {
        // inner tangents require opposing direction circles
        return false;
    }

    auto vector_to_c2 = c2.center - this->center;
    auto distance_between_circles = glm::length(vector_to_c2);

    if ( distance_between_circles < 2 * this->radius) {
//      throw ApbException("Circles are too close and don't have inner tangents");
        return false;
    } else {
        auto normalized_to_c2 = glm::normalize(vector_to_c2);
        auto distance_to_midpoint = glm::length(vector_to_c2) / 2;
        auto midpoint = this->center + (vector_to_c2 / 2.0f);

        // if hypotenuse is oo then cos_angle = 0 and angle = 90˚
        // if hypotenuse is radius then cos_angle = r/r = 1 and angle = 0
        auto cos_angle = radius / distance_to_midpoint;
        auto angle = acosf(cos_angle);

        // now find the angle between the circles
        auto midpoint_angle = glm::orientedAngle(glm::vec2(1, 0), normalized_to_c2);

        glm::vec2 p1;
        if (this->direction == Circle::CW) {
            p1 = this->center + (glm::vec2{cos(midpoint_angle + angle), sin(midpoint_angle + angle)} * this->radius);
        } else {
            p1 = this->center + (glm::vec2{cos(midpoint_angle - angle), sin(midpoint_angle - angle)} * this->radius);
        }

        auto tangent_to_midpoint = midpoint - p1;
        auto p2 = p1 + (2.0f * tangent_to_midpoint);
        tangent = {p1, p2};

        return true;
    }
};

Aqui estão dois filmes do código acima em ação:

Aqui está um caminho "externo": http://youtube.com/watch?v=99e5Wm8OKb0 e aqui está um caminho "cruzado": http://youtube.com/watch?v=iEMt8mBheZU

Se esse código ajudar, mas você tiver dúvidas sobre algumas das partes que não são mostradas aqui, basta postar um comentário e eu devo vê-lo em um dia ou dois.