AI: selecting immediate acceleration/rotation to get to a final point

Question

I'm working on a game where on each update of the game loop, the AI is run. During this update, I have the chance to turn the AI-controlled entity and/or make it accelerate in the direction it is facing. I want it to reach a final location (within reasonable range) and at that location have a specific velocity and direction (again it doesn't need to be exact) That is, given a current:

• P₀(x, y) = Current position vector
• V₀(x, y) = Current velocity vector (units/second)
• θ₀ = Current direction (radians)
• τ_max = Max turn speed (radians/second)
• α_max = Max acceleration (units/second^2)
• |V|_max = Absolute max speed (units/second)
• P_f(x, y) = Target position vector
• V_f(x, y) = Target velocity vector (units/second)
• θ_f = Target rotation (radians)

Select an immediate:

• τ = A turn speed within [-τ_max, τ_max]
• α = An acceleration scalar within [0, α_max] (must accelerate in direction it's currently facing)

Such that these are minimized:

• t = Total time to move to the destination
• |P_t-P_f| = Distance from target position at end
• |V_t-V_f| = Deviation from target velocity at end
• |θ_t-θ_f| = Deviation from target rotation at end (wrapped to (-π,π))

The parameters can be re-computed during each iteration of the game loop. A picture says 1000 words so for example given the current state as the blue dude, reach approximately the state of the red dude within as short a time as possible (arrows are velocity):

Pic http://public.blu.livefilestore.com/y1p6zWlGWeATDQCM80G6gaDaX43BUik0DbFukbwE9I4rMk8axYpKwVS5-43rbwG9aZQmttJXd68NDAtYpYL6ugQXg/words.gif

Assuming a constant α and τ for Δt (Δt → 0 for an ideal solution) and splitting position/velocity into components, this gives (I think, my math is probably off):

Equations http://public.blu.livefilestore.com/y1p6zWlGWeATDTF9DZsTdHiio4dAKGrvSzg904W9cOeaeLpAE3MJzGZFokcZ-ZY21d0RGQ7VTxHIS88uC8-iDAV7g/equations.gif

_{(EDIT: that last one should be θ = θ0 + τΔt)}

So, how do I select an immediate α and τ (remember these will be recomputed every iteration of the game loop, usually > 100 fps)? The simplest, most naieve way I can think of is:

1. Select a Δt equal to the average of the last few Δts between updates of the game loop (i.e. very small)
2. Compute the above 5 equations of the next step for all combinations of (α, τ) = {0, α_max} x {-τ_max, 0, τ_max} (only 6 combonations and 5 equations for each, so shouldn't take too long, and since they are run so often, the rather restrictive ranges will be amortized in the end)
3. Assign weights to position, velocity and rotation. Perhaps these weights could be dynamic (i.e. the further from position the entity is, the more position is weighted).
4. Greedily choose the one that minimizes these for the location Δt from now.

Its potentially fast & simple, however, there are a few glaring problems with this:

• Arbitrary selection of weights
• It's a greedy algorithm that (by its very nature) can't backtrack
• It doesn't really take into account the problem space
• If it frequently changes acceleration or turns, the animation could look "jerky".

Note that while the algorithm can (and probably should) save state between iterations, but P_f, V_f and θ_f can change every iteration (i.e. if the entity is trying to follow/position itself near another), so the algorithm needs to be able to adapt to changing conditions.

Any ideas? Is there a simple solution for this I'm missing?

Thanks, Robert

Answer 1

sounds like you want a PD controller. Basically draw a line from the current position to the target. Then take the line direction in radians, that's your target radians. The current error in radians is current heading - line heading. Call it Eh. (heading error) then you say the current turn rate is going to be KpEh+d/dt EhKd. do this every step with a new line.

thats for heading

acceleration is "Accelerate until I've reached max speed or I wont be able to stop in time". you threw up a bunch of integrals so I'm sure you'll be fine with that calculation.

I case you're wondering, yes I've solved this problem before, PD controller works. don't bother with PID, don't need it in this case. Prototype in matlab. There is one thing I've left out, you need to have a trigger, like "i'm getting really close now" so I should start turning to get into the target. I just read your clarification about "only accelerating in the direction we're heading". that changes things a bit but not too much. that means to need to approach the target "from behind" meaning that the line target will have to be behind the real target, when you get near the behind target, follow a new line that will guide you to the real target. You'll also want to follow the lines, rather than just pick a heading and try to stick with it. So don't update the line each frame, just say the error is equal to the SIGNED DISTANCE FROM THE CURRENT TARGET LINE. The PD will give you a turn rate, acceleration is trivial, so you're set. you'll need to tweak Kd and Kp by head, that's why i said matlab first. (Octave is good too)

good luck, hope this points you in the right direction ;)

pun intended.

EDIT: I just read that...lots of stuff, wrote real quick. this is a line following solution to your problem, just google line following to accompany this answer if you want to take this solution as a basis to solving the problem.

Answer 2

I would like to suggest that yout consider http://en.wikipedia.org/wiki/Bang%E2%80%93bang_control (Bang-bang control) as well as a PID or PD. The things you are trying to minimise don't seem to produce any penalty for pushing the accelerator down as far as it will go, until it comes time to push the brake down as far as it will go, except for your point about how jerky this will look. At the very least, this provides some sort of justification for your initial guess.