# Math to steer a car

I'm in the early stages of a city driving simulation project, and I'm having trouble with the math to determine how the AI should steer the cars. My car model is very simple, with nothing like physical wheels or friction; the AI simply sets a turning radius (FLT_MAX means drive straight) and an acceleration each frame. My question is, given a starting position and direction, how do I work out the turning radius each frame to have the car arrive at a destination position and direction? As an example, think of a car stopped at a stop sign ready to turn right around the corner. The car should follow a curve so that is is pointing along the road onto which it is turning when it arrives at the "start" of that road.

I think Bezier curves would be helpful, since they can be used to create smooth curves that are tangent to my initial and final directions, but I can't work out exactly how to pick a point a little way ahead along the curve to aim for. I also open to completely different ideas.

Here's my car update code for reference.

mSpeed += mAcceleration * deltaTime;
float distance = mSpeed * deltaTime;
float theta = distance / mTurningRadius;

mPosition += mTurningRadius * sin(theta) * mDirection + mTurningRadius *(1.0f - cos(theta)) * mLeft;

mDirection = rotate(mDirection, theta * 180.0f / PI, mUp);
mLeft = -cross(mDirection, mUp);

• I think it's important to highlight that the AI (the part that makes the decisions about what to do next) should be separate from the NPC (the part that carries out the will of the AI in the game world). To that end it would be good to remove the ai tag from your question; You're struggling with how to make an NPC move rather than how it should think. Oct 5 '13 at 21:07
• Also, check out OpenSteer. I haven't used it myself but it seems quite popular and might give you some ideas. Oct 5 '13 at 21:10

Assumed your Ackermann drive simulation model is correct, you can do the following for the usual driving situations (where primarily only need to steer direction):

• Simulate (projection) multiple (e.g. in steps of 20 degrees) possible steering directions, statically. That means: You assume, the driver would put the steering wheel in is fixed position and then just drive forward.
• Simulate (projection) the borders of your car. Stop the simulation as soon as the borders of the car collide with any borders of the lane (or any other obstacle) -OR- if very long time has passed. Measure the time until the collision would happen.
• Select the direction with longest simulation time. If there are multiple of them with the same value (because the timeout was reached) take the average of the angles.
• Optional: Repeat simulation and selection for +/- 10 degrees in smaller steps, to refine the result.
• Simulate (execution) the real simulation for the next time step.

This works as a first approach, but still causes several "problems". The steering may oscillate and lead to unrealistic, quick movement. The reduce this effect, do the following: * Project the next steering direction like above * Calculate the difference between the current and the projected steering direction and reduce it, if it is above a given change-threshold (maximum speed a realistic driver would be able to turn the wheel in a time slice).

You can optimize the refinement by divide and the conquer algorithm (http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm). Meaning: you set a min and a max for the steering direction and then recursively split that range in half and further investigate only the better performing range (left or right half of the old range).

For changing the lane you must allow your car to use both lanes (border of "lane" for collission detection). But, to force the car to actually change lane and not to driving in the middle of both, you have to limit how long the time until which the car must have changed lane (e.g. 10 seconds in future). You can convert this time into a distance using the current speed. Then just let the lane "end" with a straight line (orthographic to the lanes direction) at this distance. Project the lane change, with other cars continuing their current plans. If this works (no collissions, no driving rules are breached) execute the lane change. If not, continue driving on that lane.

For an axis aligned 90 degree turn, the turning radius is simply the minimum of the x and y differences in the positions as long as you start and stop turning at the correct point.

If it isn't axis aligned you can always do a rotation to fix that before doing the calculation as it doesn't affect the radius.

For non-90-degree corners it's a bit more complicated to construct the circle, but the idea is the same.

• I'm looking for a more general solution to get from one position and direction to another position and direction. Unfortunately, there are many situations where a single circular arc will not work. One example of this is changing lanes, where you need to first steer one way to turn into the lane, then the other way to orient the car with the lane.
– Jeff
Oct 6 '13 at 0:25
• I also saw cs.uky.edu/~cheng/PUBL/Paper_Quad_Bezier2.pdf but it seemed to be overkill at the time. Maybe it's actually more like what you're after.