"Steering" AI 3D vehicles on a grid/tile map?

I’ve been working on paths for Mercuna’s off-road navigation middleware, so hopefully some of this is applicable for you. Depending on how much detail you want to go in to:

Curve following:

Having a vehicle `follow' a path usually involves choosing one point on the vehicle (e.g. the centre, or the midpoint of an axel) that is going to be fixed to the curve. The orientation then depends on your steering model. If one axel has no steering (e.g. the rear) then the simplest choice is to pick the midpoint of this to follow the curve, and then the orientation of the vehicle will be the direction of the curve. Once you've picked the curve point and vehicle orientation then the wheel placements follow, and the wheel orientations come from things like this (wikipedia).

Splines:

Bezier curves can be combined, you just need to set the final-tangent of the first curve to the start-tangent of the second. Presumably in your case you would set these at the interfaces of your tiles. At some point you are likely to need distance as a function of the curve parameter (e.g. to integrate velocities etc.). Again, depending how deep into this you want to go, you may only need Gaussian quadrature with a couple of points (wikipedia), though if you start making splines with very sharp corners then you'll need to add more. We've been using 2 parabolas sandwiched together at Mercuna, which makes things a little easier.

Peter

www.mercuna.com

Thank you Peter, that are some nice pointers. In the meantime I made some process (I think).

First I tried calculating distances of waypoints (t) but this did only partially work. Some good results but sometimes it got very choppy and with large distances it would bug out. Code looked something like this, I heavily fiddled around with it so it might not work at all. The sprite itself actually moved all over the place but using nextPosition each frame gave me somewhat reliable results.

public void update(){
		float moveAmount = carSpreed * Gdx.graphics.getDeltaTime();

		curves.get(bezierIndex).valueAt(lastPosition, lastPoint);
		curves.get(bezierIndex).valueAt(nextPosition, lastPoint + stepSize);

		double angle = Math.atan2(nextPosition.y - lastPosition.y, nextPosition.x - lastPosition.x);
		
		float distance = nextPosition.dst(sprite.getX() + sprite.getOriginX(), sprite.getY() + sprite.getOriginY());

		while (moveAmount > 0)
		{
			// If next waypoint is closer then amount to move.
			if (distance < moveAmount){
				moveAmount -= distance;
				sprite.setOriginBasedPosition(nextPosition.x, nextPosition.y);

				lastPoint = nextPoint;
				curves.get(bezierIndex).valueAt(lastPosition, lastPoint);


				nextPoint += stepSize;
				curves.get(bezierIndex).valueAt(nextPosition, nextPoint);
			}
			else
			{
				//finalPosition.x += moveAmount * Math.cos(angle);
				//finalPosition.y += moveAmount * Math.sin(angle);
				sprite.translate((float)(moveAmount * Math.cos(angle)), (float)(moveAmount * Math.sin(angle)));

				moveAmount = 0;
			}
		}

But like I said, this didn't yield exactly what I want. I fiddled hours with it and although I seemd very close to a working solution I started today with another method. This method maps positions on the curve and stores it. When looking up values on the curve it uses the mapped points to find a good approximation. I just got this done with great results. It also gives me the total length of the curve, so when the curve is 100 in length and my object needs to travel 40 this frame I can just call curve.findMappedPositionAt(.4f). I still need to find a way to calculate the proper angle/orientation but I guess I can just use the previous vector, next vector or perhaps I need vectors closer to each other on the curve at the current position. Here is the complete code with two additional methods to draw itself and the points at the divisions.

public class Curve
{
	private Vector2 a, b, c, d;
	private int length;
	private float[] arcLengths;
	private float totalLength;

	public Curve(Vector2 a, Vector2 b, Vector2 c, Vector2 d)
	{
		this.a = a;
		this.b = b;
		this.c = c;
		this.d = d;

		// Amount of mapping points.
		length = 100;
		arcLengths = new float[length + 1];
		arcLengths[0] = 0;

		float ox = this.findX(0), oy = this.findY(0);
		float currentLength = 0;

		// Build map for curve, higher length means better prediciton
		for (int i = 1; i <= length; i++){
			float x = findX(i * (1 / (float)length)), y = findY(i * (1 / (float)length));
			float dx = ox - x, dy = oy - y;
			currentLength += Math.sqrt(dx * dx + dy * dy);
			this.arcLengths[i] = currentLength;
			ox = x; oy = y;
		}
		// Set total length now we have it
		totalLength = currentLength;
	}

	/**
	 * Normal bezier curve calculation on 4 points
	 * @param t
	 * @return
	 */
	public float findX(float t){
		return ((1 - t) * (1 - t) * (1 - t)) * a.x
				+ 3 * ((1 - t) * (1 - t)) * t * b.x
				+ 3 * (1 - t) * (t * t) * c.x
				+ (t * t * t) * d.x;
	}

	/**
	 * Normal bezier curve calculation on 4 points
	 * @param t
	 * @return
	 */
	public float findY(float t){
		return ((1 - t) * (1 - t) * (1 - t)) * a.y
				+ 3 * ((1 - t) * (1 - t)) * t * b.y
				+ 3 * (1 - t) * (t * t) * c.y
				+ (t * t * t) * d.y;
	}

	/**
	 * Normal bezier curve calculation on 4 points
	 * @param t
	 * @return
	 */
	public Vector2 findPositionAt(float t){
		return new Vector2(findX(t), findY(t));
	}

	/**
	 * Bezier curve calculation using the mapped positions for linear interpolation of it's length
	 * @param u
	 * @return
	 */
	public Vector2 findMappedPositionAt(float u){
		return new Vector2(findUX(u), findUY(u));
	}

	/**
	 * This finds t for the regular bezier curve calculation using the stored intermediate points
	 * @param u linear position on the curve, 0.5 should return very close to half the curve.
	 * @return returns t to use on a regular bezier calculation
	 */
	public float map(float u){
		float targetLength = u * arcLengths[length];
		int low = 0, high = length, index = 0;

		while (low < high)
		{
			index = low + (((high - low) / 2) | 0);
			if (arcLengths[index] < targetLength)
			{
				low = index + 1;
			} else
			{
				high = index;
			}
		}
		if (arcLengths[index] > targetLength){
			index--;
		}

		float lengthBefore = this.arcLengths[index];
		if (lengthBefore == targetLength) {
			return index / length;
		} else {
			return (index + (targetLength - lengthBefore) / (arcLengths[index + 1] - lengthBefore)) / length;
		}
	}

	public float findUX(float u){
		return findX(map(u));
	}

	public float findUY(float u){
		return findY(map(u));
	}

	/**
	 * Draw curve using normal bezier to reduce calls, if you need it's segments to be equally long use the UX methods that make use of the mapped positions.
	 * @param steps
	 */
	public void drawCurve(int steps){
		float stepSize = 1f / (float)steps;
		for (int i = 0; i < steps; i++){

			DebugDrawer.drawLine(findX(i * stepSize), findY(i * stepSize), findX((i + 1) * stepSize), findY((i + 1) * stepSize), Color.RED);
		}
	}

	/**
	 * Equally divides number of points on the curve.
	 * Use (int i = 1; i < divisions; i++) to display start and end point of the curve
	 * @param divisions
	 */
	public void drawDivisionPoints(int divisions){
		float stepSize = 1f / (float)divisions;
		for (int i = 0; i <= divisions; i++){
			DebugDrawer.drawCircle(findUX(i * stepSize), findUY(i * stepSize), 10, Color.BLUE);
		}
	}

	public float getTotalLength()
	{
		return totalLength;
	}

}

Here are the results on the following (very stretchy) curve:

curve = new Curve(new Vector2(-200, -200),
				new Vector2(-200, -400),
				new Vector2(0, 0),
				new Vector2(400, 300));

I don't think I need the steering wheel geometry, I think I will be fine with static wheels atm. But if I do want some extra detail this looks exactly like what I need to implement it.

I'll post some more results when I get to it.

I got some good results. It works perfectly on X/Z plane but could not get the rotation / quaternion to include Z. I'll try cleaning up some code and refactor a bit because it got messy in the end. Then I post some code, all I actually need is to rotate my model towards the purple line (front wheels). Currently doing this by using a fixed Vector.Y on the axis and calculating the angle between the back wheels and where the front wheel would belong on the path. The quaternion math was slightly off and it bugged out on some lines.