¿Puedo saltar de A a B?

Estoy haciendo una IA rudimentaria para mi desplazamiento lateral y necesito saber si una unidad de IA puede llegar al punto B desde el punto A simplemente dando un salto.

La trayectoria de vuelo de mis personajes es un poco inusual, ya que pueden aplicar fuerza en el aire (como en Jazz Jackrabbit 2 por ejemplo), a diferencia de la trayectoria clásica de un proyectil que trata sobre ...

camino que tomará un proyectil lanzado o lanzado (...) sin propulsión.

... Supongo que mi problema es más sobre un proyectil con propulsión (por ejemplo, cohete).

Para ilustrar esto, así es como se ve la curva de vuelo para mi personaje si salto y presiono continuamente el "botón izquierdo" (se ve diferente en el extremo izquierdo, aquí es donde estaba haciendo algunas maniobras en el aire):

La fuerza aplicada durante el vuelo siempre es paralela al eje X, por lo que es F = (-f, 0) si mantengo "izquierda" y es F = (f, 0) si mantengo "derecha".

Se puede mover mucho como un saltador de esquí:

Por lo tanto, difiere mucho de la trayectoria clásica, que es simplemente una parábola (fuente: wikipedia ):

Para hacerlo más difícil, estoy simulando una resistencia al aire simple para que mis personajes puedan acelerar solo hasta cierto valor de velocidad máxima.

Esto se hace aplicando una pequeña fuerza en la dirección opuesta de desplazamiento :

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

AIR_RESISTANCE_MULT es una constante que en mi caso es igual a 0.1.

Asumamos que mi personaje es un punto infinitamente pequeño.

Y NO estoy tomando en cuenta las obstrucciones, así que mi pregunta es así ...

Cómo determinar (al menos conjetura confiable), dada la velocidad inicial V, un impulso J = (0, -j) que aplico al personaje al saltar, gravedad G = (0, g) , fuerza F = (+ -f , 0) aplicado continuamente durante el vuelo y AIR_RESISTANCE_MULT si realmente decidimos tener en cuenta la resistencia del aire (esto es opcional) , si un punto se encuentra debajo de la curva dibujada por el camino que tomará mi personaje?

Literalmente no tengo idea de por dónde comenzar con los cálculos y, de hecho, no estoy necesariamente interesado en una respuesta exacta; un hack / aproximación que funcione bien sería genial, ya que la IA de ninguna manera necesita actuar perfectamente.

editar: He decidido resolver esto usando la simulación como Jason sugiere, pero ¿cómo manejar este caso?

¿Debo dibujar un segmento de C a D y verificar si el punto deseado se encuentra debajo de este segmento?

¿O debería buscar binariamente los pasos de tiempo entre C y D para buscar el punto que está lo suficientemente cerca en la distancia horizontal del punto deseado, y solo entonces verificar la diferencia vertical? (me parece un poco exagerado)

Como usted dice, la mejor opción es aproximarse, en este caso utilizando un esquema numérico. Divida el tiempo en pasos de tiempo grandes (digamos 100-300ms), y use la aproximación parabólica para cada paso de tiempo. Las fuerzas son las mismas en todas partes excepto la resistencia al aire. La trayectoria parabólica es básicamente para una aceleración constante, pero con la resistencia del aire, la aceleración cambia porque la fuerza depende de la velocidad. Una aproximación razonable es tratar la resistencia del aire como constante en cada paso de tiempo. Pero usar una aproximación cuadrática (es decir, parabólica) cuando se integra le permite manejar pasos de tiempo mucho más largos. Luego solo calcula hasta que una parábola cruza el punto deseado en la dirección horizontal, y luego compara las alturas.

EDITAR: Un poco más de detalles sobre la comparación. Sabes que a lo largo del paso del tiempo (que podrían ser muchos en los marcos del juego), el jugador cruza el objetivo <targetx,targety>. Su camino se describe por la posición <ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy>donde:

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

tes el tiempo a través del paso de tiempo ( 0 <= t <= dt) y de manera similar para y. Entonces, cuando t=0el personaje está en la posición anterior, y cuándo t=dt, está en la siguiente posición. Tenga en cuenta que esta es básicamente la actualización de Euler con dtreemplazado por tpara que podamos calcular en cualquier lugar a lo largo de la trayectoria. Ahora sabemos que la posición x es una función cuadrática, por lo que podemos resolver ax*t^2 + bx*t + cx = targetx y obtener (hasta) dos veces durante el paso en el que el personaje está directamente arriba o debajo del objetivo. Luego descartamos cualquier solución que no esté en el rango [0,dt], ya que estos no están en el paso de tiempo actual. (Para mayor robustez, agregue una pequeña constante a los extremos del rango para que no tenga problemas de redondeo). Ahora no podríamos tener soluciones (después del filtrado), en cuyo caso no alcanzamos el objetivo este paso de tiempo. De lo contrario, evaluamos ay*t^2 + by*t + cyen las soluciones y comparamos esto con targety. Tenga en cuenta que podría estar por encima del objetivo en un punto de su trayectoria y más abajo (o viceversa). Tendrá que interpretar tales situaciones de acuerdo con lo que desea hacer.

Considerar un montón de pasos de tiempo es mucho más fácil que encontrar una solución analítica al problema original, y es mucho más flexible, ya que puede cambiar el modelo de movimiento y esto seguirá funcionando más o menos.

Puntos de bonificación por usar pasos variables, por ejemplo, 100 ms para el primer segundo (diez puntos), 200 ms para los siguientes dos (diez puntos más), 400 ms durante 4 segundos, etc. De hecho, a medida que su personaje se acerca a la velocidad terminal, la variación en la resistencia disminuye y, de todos modos, no necesita mayores intervalos de tiempo. De esta manera, puede manejar saltos realmente largos sin demasiado procesamiento, ya que la complejidad durante T segundos es O (log T) en lugar de O (T).

También puedes simular lo que sucede cuando el personaje deja de aumentar a medio camino a través de su salto, o comienza a aumentar de otra manera. Con el truco anterior, la complejidad es O ((log T) ^ 2), que no es tan malo.

¡Hurra! ¡Lo hice!

Estoy usando una simulación simple que toma la primera posición para aterrizar detrás del eje vertical del punto objetivo; desde allí, tomo la posición simulada anterior y hago un segmento. Ahora verifico si el punto objetivo está debajo de este segmento. Si es así, podemos saltar allí.

Es un personaje controlado por el jugador en el gif. El rosa es el camino predicho, los segmentos amarillos se predicen en las siguientes posiciones de paso, y el segmento final se vuelve blanco si el punto objetivo se encuentra debajo de él, rojo de lo contrario. La curva roja es la ruta de vuelo real. Hay algunas pequeñas inexactitudes debido a la interpolación de estado físico activada.

Los cálculos resultaron ser sorprendentemente fáciles, sin embargo, hacer que mi entorno funcione de la misma manera que estos cálculos puros ... fue un dolor enorme en el trasero. Al menos resolví algunos errores graves, así que fue un ejercicio útil después de todo.

Aquí está el código completo en Lua utilizado para resolver el problema original (el código asume que tiene su propia rutina "debug_draw" y su propia clase de vectores con métodos básicos como "length_sq" (longitud al cuadrado), "normalizar" u operadores +, * :

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

¡Acepta va a Jason por ponerme en la dirección correcta! ¡Gracias!

Es posible que desee "calcular" la respuesta, pero estoy seguro de que la encontrará insuficiente una vez que la tenga debido a la naturaleza altamente interactiva de su física de "caída libre".

Considere utilizar un enfoque diferente: buscar. Así es como se hace para Super Mario AI: http://aigamedev.com/open/interview/mario-ai/

La búsqueda de posibles rutas para pasar de A a B permite una interactividad ilimitada en el aire sin dejar de ser computacionalmente eficiente.