Another little challenge for my gaming world was to create a smooth route for a given node (eg a soldier). Using an A* algorithm gives very awkward turns (ofter 90 degrees) between two cells. What would be nice is to make the soldier turn in increments between the two cells. The more increments you have, the smoother the turn.
Let's say you have two points p1 and p2. You would like to find the smooth curve point halfway (0.5) between them. In order to do this with a Catmull Rom Spline curve, you're also going to have to provide the point before(p0) and after (p3).
Here's the method:
public float q(float t) {
return 0.5f * ((2 * p1) +
(p2 - p0) * t +
(2*p0 - 5*p1 + 4*p2 - p3) * t * t +
(3*p1 -p0 - 3 * p2 + p3) * t * t * t);
}
So let's start with a one-dimensional curve. The four values:
p0 = 1
p1 = 2
p2 = 2
p3 = 1
We want a point a point halfway (t=0.5). Plugging this into our method call q(0.5f), it returns a value of 2.125. Smoothing further:
q(0.25) = 2.171875
q(0.5) = 2.125
q(0.75) = 2.171875
Lovely, so we could potentially break this up an infinite number of times, but that would clearly take an infinite of time to run. You'll want to play with your implementation
You're probably already wondering how this can be configured for a 2D (or maybe 3D) A* algorithm. It's very simple actually, you just need to perform the algorithm for the x values and y values (or indeed, z values) on their own. I'm including all of the source code below, and I'll leave you to figure out how you might implement a CatmullRomSpline3D (I hope you can see it's really easy!). There are three Java classes below. I had some issues pasting them in, so please separate them by each "package".
By the way, if this is the first point in your A* route, then you're not going to have a previous point, so specify p0 = p1 (ie double-up on the value). If it's the last point on your route, then set p3 = p2.
Using the CatmullRomSplineUtils class (below) I as able to create a much smoother path (above diagram) around a particularly tricky route. I also noticed that it is blindingly fast. I haven't given it a thorough soaking yet, but this 13 point route with 5 subdivisions (which amounts to 121 new points) did not register a single milisecond in duration.
I can see that this could be workable for a racing game. The computer car ai calculations can be quickly recalculated if it got knocked off course.
package catmullrom;
public class CatmullRomSpline {
private float p0, p1, p2, p3;
public CatmullRomSpline(float p0, float p1, float p2, float p3) {
this.p0 = p0;
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
}
return 0.5f * ((2 * p1) +
(p2 - p0) * t +
(2*p0 - 5*p1 + 4*p2 - p3) * t * t +
(3*p1 -p0 - 3 * p2 + p3) * t * t * t);
}
/**
* Example implementation
*/
public static void main(String[] args) {
CatmullRomSpline crs = new CatmullRomSpline(1f, 2f, 2f, 1f);
System.out.println(crs.q(0f));
System.out.println(crs.q(0.25f));
System.out.println(crs.q(0.5f));
System.out.println(crs.q(0.75f));
System.out.println(crs.q(1f));
}
/**
* @return the p0
*/
public float getP0() {
return p0;
}
/**
* @param p0 the p0 to set
*/
public void setP0(float p0) {
this.p0 = p0;
}
/**
* @return the p1
*/
public float getP1() {
return p1;
}
/**
* @param p1 the p1 to set
*/
public void setP1(float p1) {
this.p1 = p1;
}
/**
* @return the p2
*/
public float getP2() {
return p2;
}
/**
* @param p2 the p2 to set
*/
public void setP2(float p2) {
this.p2 = p2;
}
/**
* @return the p3
*/
public float getP3() {
return p3;
}
/**
* @param p3 the p3 to set
*/
public void setP3(float p3) {
this.p3 = p3;
}
}
package catmullrom;
public class CatmullRomSpline2D {
private CatmullRomSpline splineXVals, splineYVals;
public CatmullRomSpline2D(Point2D p0, Point2D p1, Point2D p2, Point2D p3) {
assert p0 != null : "p0 cannot be null";
assert p1 != null : "p1 cannot be null";
assert p2 != null : "p2 cannot be null";
assert p3 != null : "p3 cannot be null";
splineXVals = new CatmullRomSpline(p0.getX(), p1.getX(), p2.getX(), p3.getX());
splineYVals = new CatmullRomSpline(p0.getY(), p1.getY(), p2.getY(), p3.getY());
}
public Point2D q(float t) {
return new Point2D(splineXVals.q(t), splineYVals.q(t));
}
}
package catmullrom;
public class Point2D {
private float x, y;
public Point2D() {
this(0f, 0f);
}
public Point2D(float x, float y) {
this.x = x;
this.y = y;
}
/**
* @return the x
*/
public float getX() {
return x;
}
/**
* @param x the x to set
*/
public void setX(float x) {
this.x = x;
}
/**
* @return the y
*/
public float getY() {
return y;
}
/**
* @param y the y to set
*/
public void setY(float y) {
this.y = y;
}
}
package catmullrom;
public class CatmullRomSplineUtils {
/**
* Creates catmull spline curves between the points array.
*
* @param points The current 2D points array
* @param subdivisions The number of subdivisions to add between each of the points.
*
* @return A larger array with the points subdivided.
*/
public static Point2D[] subdividePoints(Point2D[] points, int subdivisions) {
assert points != null;
assert points.length >= 3;
Point2D[] subdividedPoints = new Point2D[((points.length-1) * subdivisions) + 1];
float increments = 1f / (float)subdivisions;
for (int i = 0; i < points.length-1; i++) {
Point2D p0 = i == 0 ? points[i] : points[i-1];
Point2D p1 = points[i];
Point2D p2 = points[i+1];
Point2D p3 = (i+2 == points.length) ? points[i+1] : points[i+2];
CatmullRomSpline2D crs = new CatmullRomSpline2D(p0, p1, p2, p3);
for (int j = 0; j <= subdivisions; j++) {
subdividedPoints[(i*subdivisions)+j] = crs.q(j * increments);
}
}
return subdividedPoints;
}
public static void main(String[] args) {
Point2D[] pointArray = new Point2D[4];
pointArray[0] = new Point2D(1f, 1f);
pointArray[1] = new Point2D(2f, 2f);
pointArray[2] = new Point2D(3f, 2f);
pointArray[3] = new Point2D(4f, 1f);
Point2D[] subdividedPoints = CatmullRomSplineUtils.subdividePoints(pointArray, 4);
for (Point2D point : subdividedPoints) {
System.out.println("" + point);
}
}
}
No comments:
Post a Comment