Puis-je passer de A à B?

Je fais de l'IA rudimentaire pour mon défilement latéral et j'ai besoin de savoir si une unité AI peut atteindre le point B à partir du point A simplement en faisant un saut.

La trajectoire de vol de mes personnages est un peu inhabituelle car ils peuvent appliquer une force dans les airs (comme dans Jazz Jackrabbit 2 par exemple), donc contrairement à la trajectoire classique d'un projectile qui est d'environ ...

trajectoire qu'un projectile lancé ou lancé prendra (...) sans propulsion.

... Je suppose que mon problème concerne davantage un projectile à propulsion (par exemple une fusée).

Pour illustrer cela, voici à quoi ressemble la courbe de vol pour mon personnage si je saute et appuie continuellement sur le "bouton gauche" (ça a l'air différent à l'extrémité gauche, c'est là que je faisais des manœuvres en l'air):

La force appliquée pendant le vol est toujours parallèle à l'axe X, donc elle est F = (-f, 0) si je maintiens "gauche" et elle est F = (f, 0) si je maintiens "droite".

Il peut bouger comme un sauteur à ski:

Elle diffère donc beaucoup de la trajectoire classique qui est tout simplement une parabole (source: wikipedia ):

Pour le rendre plus difficile, je simule une simple résistance à l'air afin que mes personnages ne puissent accélérer que jusqu'à une certaine valeur de vitesse maximale.

Cela se fait en appliquant une petite force dans la direction opposée de la marche :

b2Vec2 vel = body->GetLinearVelocity();
float speed = vel.Normalize(); //normalizes vector and returns length
body->ApplyForce( AIR_RESISTANCE_MULT * speed * speed * -vel, body->GetWorldCenter() );

L'AIR_RESISTANCE_MULT est une constante qui dans mon cas est égale à 0,1.

Supposons que mon personnage soit un point infiniment petit.

Et je ne prends PAS en considération les obstructions, alors ma question va comme ça ...

Comment déterminer (au moins de façon fiable), étant donné la vitesse initiale V, une impulsion J = (0, -j) que j'applique au personnage au saut, la gravité G = (0, g) , la force F = (+ -f , 0) appliqué continuellement pendant le vol et AIR_RESISTANCE_MULT si nous décidons vraiment de prendre en compte la résistance de l'air (ceci est facultatif) , si un point se trouve en dessous de la courbe tracée par le chemin que mon personnage prendra?

Je n'ai littéralement aucune idée par où commencer avec les calculs et en fait, je ne suis pas nécessairement intéressé par une réponse exacte; un hack / approximation qui fonctionne bien serait génial car l'IA n'a nullement besoin d'agir parfaitement.

edit: J'ai décidé de résoudre ce problème en utilisant la simulation comme le suggère Jason, mais comment gérer un tel cas?

Dois-je dessiner un segment de C à D et vérifier si le point souhaité se trouve en dessous de ce segment?

Ou dois-je rechercher en binaire les pas de temps entre C et D pour rechercher le point qui est assez proche de la distance horizontale du point souhaité, et ensuite seulement vérifier la différence verticale? (me semble un peu exagéré)

Comme vous le dites, le meilleur choix est d'approximer, dans ce cas en utilisant un schéma numérique. Divisez le temps en grands pas de temps (disons 100-300 ms) et utilisez l'approximation parabolique pour chaque pas de temps. Les forces sont les mêmes partout, sauf la résistance de l'air. Le chemin parabolique est essentiellement pour une accélération constante, mais avec la résistance de l'air, l'accélération change parce que la force dépend de la vitesse. Une approximation raisonnable consiste à traiter la résistance de l'air comme constante à chaque pas de temps. Mais l'utilisation d'une approximation quadratique (c'est-à-dire parabolique) lors de l'intégration vous permet de gérer des pas de temps beaucoup plus grands. Ensuite, vous calculez jusqu'à ce qu'une parabole traverse le point souhaité dans le sens horizontal, puis comparez les hauteurs.

EDIT: Un peu plus de détails sur la comparaison. Vous savez qu'au fil du temps (qui pourrait être nombreux dans les cadres de jeu), le joueur franchit la cible <targetx,targety>. Leur chemin est décrit par la position <ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy>où:

ax = 1/2 * accel.x
bx = velocity.x
cx = position.x

test le temps à travers le timestep ( 0 <= t <= dt) et de même pour y. Donc, quand t=0le personnage est à la position précédente, et quand t=dt, ils sont à la position suivante. Notez qu'il s'agit essentiellement de la mise à jour d'Euler avec dtremplacé par tafin que nous puissions calculer n'importe où le long de la trajectoire. Maintenant, nous savons que la position x est une fonction quadratique, nous pouvons donc résoudre ax*t^2 + bx*t + cx = targetx et obtenir (jusqu'à) deux fois au cours de l'étape au cours de laquelle le personnage est directement au-dessus ou en dessous de la cible. Ensuite, nous jetons toutes les solutions qui ne sont pas dans la plage [0,dt], car ceux-ci ne sont pas dans le pas de temps actuel. (Pour la robustesse, ajoutez une petite constante aux extrémités de la plage afin de ne pas avoir de problèmes d'arrondi). Maintenant, nous ne pouvions pas avoir de solutions (après filtrage), auquel cas nous n'atteignons pas la cible ce pas de temps. Sinon, nous évaluons ay*t^2 + by*t + cyles solutions et comparons ce y avec targety. Notez que vous pourriez être au-dessus de la cible à un moment donné de votre trajectoire, et en dessous plus tard (ou vice-versa). Vous devrez interpréter ces situations en fonction de ce que vous voulez faire.

Il est beaucoup plus facile de considérer un tas de pas de temps que de trouver une solution analytique au problème d'origine, et beaucoup plus flexible car vous pouvez changer le modèle de mouvement et cela fonctionnera toujours grosso modo.

Points bonus pour l'utilisation de pas variables, par exemple, 100 ms pour la première seconde (dix points), 200 ms pour les deux suivants (dix points de plus), 400 ms sur 4 secondes, etc. En fait, lorsque votre personnage approche de la vitesse terminale, la variation de la résistance diminue et vous n'avez pas besoin de plus grands pas de temps de toute façon. De cette façon, vous pouvez gérer de très longs sauts sans trop de traitement, car la complexité pour T secondes est O (log T) plutôt que O (T).

Vous pouvez également simuler ce qui se passe lorsque le personnage arrête de booster à mi-chemin de son saut, ou commence à booster dans l'autre sens. Avec l'astuce ci-dessus, la complexité est O ((log T) ^ 2), ce qui n'est pas trop mal.

Yay! Je l'ai fait!

J'utilise une simulation simple qui prend la première position pour atterrir derrière l'axe vertical du point cible - à partir de là, je prends la position simulée précédente et crée un segment. Maintenant, je vérifie si le point cible est en dessous de ce segment. Si c'est le cas - nous pouvons y sauter.

C'est un personnage contrôlé par le joueur sur le gif. Le rose est la trajectoire prédite, les segments jaunes sont les positions de progression ultérieures prédites et le segment final devient blanc si le point cible se trouve en dessous, rouge sinon. La courbe rouge est la trajectoire de vol réelle. Il y a quelques légères inexactitudes dues à l'interpolation d'état physique activée.

Les calculs se sont révélés étonnamment faciles, mais faire fonctionner mon environnement de la même manière que ces calculs purs ... était une douleur énorme dans le cul. Au moins, j'ai résolu de graves bugs, donc c'était un exercice utile après tout.

Voici le code complet dans Lua utilisé pour résoudre le problème d'origine (le code suppose que vous avez votre propre routine "debug_draw" et votre propre classe vectorielle avec des méthodes de base comme "length_sq" (longueur au carré), "normaliser" ou opérateurs +, * :

function simple_integration(p, dt)
    local new_p = {}

    new_p.acc = p.acc
    new_p.vel = p.vel + p.acc * dt 
    new_p.pos = p.pos + new_p.vel * dt
    -- uncomment this if you want to use quadratic integration
    -- but with small timesteps even this is an overkill since Box2D itself uses traditional Euler
    -- and I found that for calculations to be accurate I either way must keep the timesteps very low at the beginning of the jump
     --+ p.acc * dt * dt * 0.5

    return new_p
end

function point_below_segment(a, b, p)
    -- make sure a is to the left
    if a.x > b.x then a,b = b,a end

    return ((b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x)) < 0
end

-- returns true or false
function can_point_be_reached_by_jump
(
gravity, -- vector (meters per seconds^2)
movement_force, -- vector (meters per seconds^2)
air_resistance_mult, -- scalar
queried_point, -- vector (meters)
starting_position, -- vector (meters)
starting_velocity, -- vector (meters per seconds)
jump_impulse, -- vector (meters per seconds)
mass -- scalar (kilogrammes)
)

    local my_point = {
        pos = starting_position,
        vel = starting_velocity + jump_impulse/mass
    }

    local direction_left = movement_force.x < 0
    local step = 1/60

    while true do           
        -- calculate resultant force
        my_point.acc = 
        -- air resistance (multiplier * squared length of the velocity * opposite normalized velocity)
        (vec2(my_point.vel):normalize() * -1 * air_resistance_mult * my_point.vel:length_sq()) / mass
        -- remaining forces
        + gravity + movement_force/mass

        -- I discard any timestep optimizations at the moment as they are very context specific
        local new_p = simple_integration(my_point, step)

        debug_draw(my_point.pos, new_p.pos, 255, 0, 255, 255)
        debug_draw(new_p.pos, new_p.pos+vec2(0, -1), 255, 255, 0, 255)

        if (direction_left and new_p.pos.x < queried_point.x) or (not direction_left and new_p.pos.x > queried_point.x) then
            if point_below_segment(new_p.pos, my_point.pos, queried_point) then
                debug_draw(new_p.pos, my_point.pos, 255, 0, 0, 255)
                return true
            else
                debug_draw(new_p.pos, my_point.pos, 255, 255, 255, 255)
                return false
            end
        else 
            my_point = new_p
        end
    end

    return false
end

Accepter va à Jason pour m'avoir mis dans la bonne direction! Merci!

Vous voudrez peut-être "simplement calculer" la réponse, mais je suis sûr que vous la trouverez insuffisante une fois que vous l'avez en raison de la nature hautement interactive de votre physique de "chute libre".

Envisagez d'utiliser une approche différente: la recherche. Voici comment cela se fait pour Super Mario AI: http://aigamedev.com/open/interview/mario-ai/

La recherche de chemins possibles pour aller de A à B permet une interactivité illimitée dans les airs tout en étant efficace sur le plan des calculs.