Czy mogę przejść z A do B?

Tworzę podstawową sztuczną inteligencję dla mojego side-scrollera i muszę wiedzieć, czy jednostka AI może dotrzeć do punktu B z punktu A po prostu wykonując skok.

Trajektoria lotu moich postaci jest nieco nietypowa, ponieważ mogą one zastosować siłę w powietrzu (jak na przykład w Jazz Jackrabbit 2), więc w przeciwieństwie do klasycznej trajektorii pocisku, która polega na ...

ścieżka, którą rzucony lub wystrzelony pocisk przejdzie (...) bez napędu.

... Przypuszczam, że mój problem dotyczy raczej pocisku z napędem (np. Rakiety).

Aby to zilustrować, tak wygląda krzywa lotu dla mojej postaci, gdy skaczę i ciągle naciskam „lewy przycisk” (wygląda inaczej na lewym końcu, tutaj robiłem manewry w powietrzu):

Siła przyłożona podczas lotu jest zawsze równoległa do osi X, więc jest to F = (-f, 0), jeśli trzymam „lewy”, a F = (f, 0), jeśli trzymam „prawy”.

Potrafi poruszać się bardzo jak skoczek narciarski:

Więc bardzo różni się od klasycznej trajektorii, która jest po prostu parabolą (źródło: wikipedia ):

Aby to utrudnić, symuluję prosty opór powietrza, aby moje postacie mogły przyspieszyć tylko do pewnej maksymalnej prędkości.

Odbywa się to poprzez zastosowanie niewielkiej siły w przeciwnym kierunku jazdy :

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 jest stałą, która w moim przypadku wynosi 0,1.

Załóżmy, że moja postać jest nieskończenie małą kwestią.

I NIE biorę pod uwagę przeszkód, więc moje pytanie brzmi tak ...

Jak określić (przynajmniej niezawodnie zgadnąć), biorąc pod uwagę prędkość początkową V, impuls J = (0, -j), który przykładam do postaci podczas skoku, grawitację G = (0, g) , siłę F = (+ -f , 0) stale stosowane podczas lotu i AIR_RESISTANCE_MULT, jeśli naprawdę zdecydujemy się uwzględnić opór powietrza (jest to opcjonalne) , czy punkt leży poniżej krzywej wyznaczonej przez ścieżkę, którą podąży moja postać?

Nie mam dosłownie pojęcia, od czego zacząć od obliczeń, a tak naprawdę niekoniecznie jestem zainteresowany dokładną odpowiedzią; dobrze działający hack / aproksymacja byłaby świetna, ponieważ AI w żadnym wypadku nie musi działać idealnie.

edycja: Zdecydowałem rozwiązać ten problem za pomocą symulacji, jak sugeruje Jason, ale jak sobie poradzić z takim przypadkiem?

Czy powinienem narysować odcinek od C do D i sprawdzić, czy pożądany punkt znajduje się poniżej tego odcinka?

A może powinienem binarnie przeszukiwać przedziały czasowe między C i D, aby znaleźć punkt, który jest wystarczająco blisko w odległości poziomej do żądanego punktu, a dopiero potem sprawdzić różnicę pionową? (wydaje mi się to trochę przesadne)

Jak twierdzisz, najlepszym wyborem jest przybliżenie, w tym przypadku za pomocą schematu numerycznego. Podziel czas na duże kroki czasowe (powiedzmy 100–300 ms) i użyj parabolicznego przybliżenia dla każdego kroku czasowego. Siły są takie same, z wyjątkiem oporu powietrza. Ścieżka paraboliczna służy zasadniczo do stałego przyspieszenia, ale przy oporze powietrza przyspieszenie zmienia się, ponieważ siła zależy od prędkości. Rozsądnym przybliżeniem jest traktowanie oporu powietrza jako stałego w każdym kroku czasowym. Ale zastosowanie kwadratowej (tj. Parabolicznej) aproksymacji podczas integracji pozwala na obsługę znacznie większych kroków czasowych. Następnie wystarczy obliczyć, aż parabola przekroczy pożądany punkt w kierunku poziomym, a następnie porównać wysokości.

EDYCJA: Trochę więcej szczegółów na temat porównania. Wiesz, że z upływem czasu (który może być wiele w klatkach gry) gracz przekroczy cel <targetx,targety>. Ich ścieżkę opisuje pozycja, w <ax*t^2 + bx*t + cx, ay*t^2 + by*t + cy>której:

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

tto czas upływający przez timestep ( 0 <= t <= dt) i podobnie dla y. Więc kiedy t=0postać znajduje się na poprzedniej pozycji i kiedy t=dt, jest na następnej pozycji. Zauważ, że jest to w zasadzie aktualizacja Eulera z dtzastąpioną przez t, abyśmy mogli obliczyć w dowolnym miejscu wzdłuż trajektorii. Teraz wiemy, że pozycja x jest funkcją kwadratową, więc możemy rozwiązać ax*t^2 + bx*t + cx = targetx i uzyskać (maksymalnie) dwa razy podczas etapu, w którym postać znajduje się bezpośrednio powyżej lub poniżej celu. Następnie wyrzucamy wszelkie rozwiązania, które nie są w zakresie [0,dt], ponieważ nie są one w bieżącym czasie. (Aby uzyskać wytrzymałość, dodaj małą stałą na końcach zakresu, aby nie występowały problemy z zaokrąglaniem). Teraz nie możemy mieć żadnych rozwiązań (po filtrowaniu), w którym to przypadku nie osiągniemy celu w tym czasie. W przeciwnym razie oceniamy ay*t^2 + by*t + cyrozwiązania i porównujemy to z targety. Zauważ, że możesz być powyżej celu w jednym punkcie swojej trajektorii, a poniżej niego później (lub odwrotnie). Będziesz musiał interpretować takie sytuacje zgodnie z tym, co chcesz zrobić.

Rozważenie kilku kroków czasowych jest znacznie łatwiejsze niż znalezienie analitycznego rozwiązania pierwotnego problemu i znacznie bardziej elastyczne, ponieważ możesz zmienić model ruchu, a to nadal będzie mniej więcej działało.

Punkty bonusowe za użycie zmiennych kroków, na przykład 100ms przez pierwszą sekundę (dziesięć punktów), 200ms przez następne dwa (dziesięć kolejnych punktów), 400ms przez 4 sekundy itp. W rzeczywistości, gdy twoja postać zbliża się do prędkości końcowej, zmiana w opór maleje i i tak nie potrzebujesz dłuższych czasów. W ten sposób możesz obsługiwać naprawdę długie skoki bez nadmiernego przetwarzania, ponieważ złożoność T sekund to O (log T) zamiast O (T).

Możesz także zasymulować, co się stanie, gdy postać przestanie zwiększać w trakcie skoku lub zacznie działać w drugą stronę. W przypadku powyższej sztuczki złożoność wynosi O ((log T) ^ 2), co nie jest takie złe.

Tak! Ja to zrobiłem!

Używam prostej symulacji, która zajmuje pierwszą pozycję, aby wylądować za pionową osią punktu docelowego - stamtąd biorę poprzednią symulowaną pozycję i robię segment. Teraz sprawdzam, czy punkt docelowy znajduje się poniżej tego segmentu. Jeśli tak - możemy tam wskoczyć.

Jest to kontrolowana przez gracza postać w gifie. Różowa jest przewidywaną ścieżką, żółte segmenty są przewidywanymi kolejnymi krokami, a końcowy segment zmienia kolor na biały, jeśli punkt docelowy leży poniżej niego, w przeciwnym razie czerwony. Czerwona krzywa to rzeczywista ścieżka lotu. Występują niewielkie niedokładności wynikające z włączonej interpolacji stanu fizyki.

Obliczenia okazały się zaskakująco łatwe, jednak sprawienie, że moje środowisko działało tak samo jak te czyste obliczenia ... było ogromnym bólem w tyłek. Przynajmniej rozwiązałem kilka poważnych błędów, więc było to w końcu przydatne ćwiczenie.

Oto kompletny kod w Lua użyty do rozwiązania pierwotnego problemu (kod zakłada, że ​​masz własną procedurę „debug_draw” i własną klasę wektorową z podstawowymi metodami, takimi jak „length_sq” (długość do kwadratu), „normalizacja” lub operatory +, * :

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

Zaakceptuj jedzie do Jasona za ustawienie mnie we właściwym kierunku! Dzięki!

Być może zechcesz „tylko obliczyć” odpowiedź, ale jestem pewien, że okaże się ona niewystarczająca, gdy już ją uzyskasz, ze względu na wysoce interaktywny charakter fizyki „swobodnego spadania”.

Rozważ zastosowanie innego podejścia: Wyszukiwanie. Oto jak to jest zrobione dla Super Mario AI: http://aigamedev.com/open/interview/mario-ai/

Wyszukiwanie możliwych ścieżek w celu przejścia z punktu A do punktu B pozwala na nieograniczoną interaktywność w powietrzu, przy jednoczesnym zachowaniu wydajności obliczeniowej.