nice smooth paths

[metanet]

hey,
a different thread prompted me to hunt down and port a game programming gem: a type of curve called a catmull-rom spline.

this curve looks to be quite useful, i wish i had found it earlier

an attempt at an explanation:

a simple "straight line" path works something like this:

you know 2 points, the point behind (where you were) p1 and the point in front of (where you're going) p2. given a parameter u, 0 <= u <= 1, you get a path which moves from p1 to p2 as you increase u from 0 to 1.

the formula is simply:
currentPosition = (1-u)*p1 + u*p2;

this is also known as linear interpolation between two points.

catmull-roms need 2 extra points: the point "behind" p1 (call it p0) and the point "in front of" p2 (call it p3).

given these points and a parameter u, you'll get a nice smoooth path which moves between p1 and p2 as u goes from 0 to 1.

the formula is:
currentPosition = 0.5 *( (2*p1) + (-p0 + p2)*u + (2*p0 - 5*p1 + 4*p2 - p3)*(u*u) + (-p0 + 3*p1 - 3*p2 + p3)*(u*u*u));

i have _no_ idea how this works, it just does. also, it may look scary but it's just a few multiplies.

aaanyway.. here's some code that will produce a test app demonstrating this. use the left and right arrows to move amongst the points:

//catmull-rom spline, from GPG1 3.4
function vec2(x,y)
{
	this.x = x;
	this.y = y;
}
function DrawPlus(mc, x,y, r)
{
	mc.moveTo(x+r, y);
	mc.lineTo(x-r, y);
	mc.moveTo(x, y+r);
	mc.lineTo(x, y-r);
}

pList = new Array();
pList.push(new vec2(50, 250));
pList.push(new vec2(100, 300));
pList.push(new vec2(150, 200));
pList.push(new vec2(200, 250));
pList.push(new vec2(250, 300));
pList.push(new vec2(180, 350));
pList.push(new vec2(80, 320));

var sbuf = _root.createEmptyMovieClip("staticBuffer", 100);
sbuf.clear();
sbuf.lineStyle(0, 0x000000, 100);

for(var i in pList)
{
	var v = pList[i];
	DrawPlus(sbuf, v.x, v.y, 2);
}

var dbuf = _root.createEmptyMovieClip("dynamicBuffer", 200);

P_INDEX = 0;
U_PARAM = 0.4;
function DoStuff()
{
	if(Key.isDown(Key.LEFT))
	{
		U_PARAM -= 0.02;
		UpdatePos();
	}
	else if(Key.isDown(Key.RIGHT))
	{
		U_PARAM += 0.02;
		UpdatePos();
	}
}

function UpdatePos()
{
//wrap point indices	
	if(U_PARAM < 0)
	{
		//we moved into the next segment, backwards
		P_INDEX = ((P_INDEX - 1)+pList.length)%pList.length;
		U_PARAM = 1 + U_PARAM;
	}
	else if(1 < U_PARAM)
	{
		//we moved into the next segment, forwards
		P_INDEX = (P_INDEX + 1)%pList.length;
		U_PARAM = U_PARAM - 1;
	}	
//-----


	//get the 4 points to interpolate between
	var p0 = pList[P_INDEX];
	var p1 = pList[(P_INDEX + 1)%pList.length];
	var p2 = pList[(P_INDEX + 2)%pList.length];
	var p3 = pList[(P_INDEX + 3)%pList.length];


	var u = U_PARAM;//get parametric position between p1 and p2


	//calculate weights given u
	var uu = u*u;
	var uuu = uu*u;
	var w0 = -0.5*uuu + uu - 0.5*u;
	var w1 = 1.5*uuu - 2.5*uu + 1;
	var w2 = -1.5*uuu + 2*uu + 0.5*u;
	var w3 = 0.5*uuu - 0.5*uu;

	var x = p0.x*w0 + p1.x*w1 + p2.x*w2 + p3.x*w3;
	var y = p0.y*w0 + p1.y*w1 + p2.y*w2 + p3.y*w3;

	//this is "the long version"
	//var x = 0.5 *((2 * p1.x) +  (-p0.x + p2.x)*u + (2*p0.x - 5*p1.x + 4*p2.x - p3.x)*uu + (-p0.x + 3*p1.x - 3*p2.x + p3.x)*uuu);
	//var y = 0.5 *((2 * p1.y) +  (-p0.y + p2.y)*u + (2*p0.y - 5*p1.y + 4*p2.y - p3.y)*uu + (-p0.y + 3*p1.y - 3*p2.y + p3.y)*uuu);
	

	//draw the result
	dbuf.clear();
	dbuf.lineStyle(0, 0x228822, 100);
	DrawPlus(dbuf, x, y, 4);
}
UpdatePos();
_root.onEnterFrame = DoStuff;

this could be used for many things: if you don't want to use it to generate an object's current position, you could (instead) take a very coarse set of points, use the above to generate some nice in-between points, then use your normal linear interpolator to move between the generated points.

the one problem with the above is that you aren't guaranteed constant velocity, like you are with the linear version. however, if the samples are evenly spaced it's not too bad, and the "slowing down at sharp corners" is quite pleasing.

aaaaaaaanyway..
raigan

[VENGEANCE MX]

It can be scary how much you know sometimes. I practically fell into a coma when I played N.

[Phlook]

Are you psychic?! i was just contemplating last night what i could do to make a smooth path

[metanet]

Originally posted by VENGEANCE MX
It can be scary how much you know sometimes.

not really -- like i said, i've got absolutely no idea what the formula is doing, or why

i just found it in a book and copied it verbatim into actionscript.

but.. having said that, i think it's important for people to consider researching/finding/understanding existing tools/solutions as an important skill, possibly more important than coming up with solutions from scratch, because in terms of games in actionscript, all the problems you're likely to face have already been faced in the past 10 years by people programming for pc, snes, etc..

whoever mr/mrs. catmull and rom are, THEY are crazy smart. it's amazing to me that you just plunk the number in and you get a smooth curve that ALWAYS passes through the points. it makes me wish i had payed attention more to some math classes

raigan

[dogtown08]

Thats amazing. It doesnt seem to be completely perfect though. If you slow it down a little and zoom in, you can clearly see that at certain points, it will jump a pixel or two left and right over and over before it reaches the point. I guess that would just be because flash is rounding all the floating point numbers a tiny bit.

Maybe one day I will understand what that formula does

[metanet]

i think it might just be problems with my code, not the formula in particular but the logic for when the parameter goes <0 or >1.. at least, there were some bugs in that stuff that i fixed before posting.

raigan

[DancingOctopus]

That's amazing. From just looking at the code, i'm baffled as to how it works.

Something like this could come in handy.

[>flashl!ght<]

That's very nice! you can consider yourself the 1337 actionscipter

Now, while not nearly as elegant as this, I have in the past just used rotation and standard accel/decay formulas for manuvering curves around points... but here is the real issue with 'smooth paths' of any time ive always wondered about:
in a game, say one that uses some node based path finding, when an AI player is going from point to point using 'smooth paths', how do you predict(and adjust to avoid) the fact that in tight areas, overshooting may result in collisions? It might sounds confusing, but what I mean is going through a node at a curve may result in colliding with a wall(unless the corridor happens to perfectly match the curve). This can be especially bad since the AI may get stuck and not be able to proceed to the next node.
The only way I can think of to avoid this is to make 'fat' node paths, then you could easily calculate, based on the players manuevering abilities(rotation speed, max speed, decel, accel) when approaching a node when it will have to slow down, and when it can begin to turn, in order to keep it within the fat paths radius.

But what about when using a formula like the above? I suppose could calculate on the fly the projected path, then check the projected path for collisions, but that seems pretty heavy, and what do you do when a collision is detected?

Maybe this is all overkill for Flash... but it sure is fun to think about

[metanet]

i know what you mean.. the only solution i've ever heard of was to use something like your "fat" nodes: pathfinding nodes are never placed closer than a certain distance "r" from a wall, and objects can always turn in a radius smaller than "r".

i don't think that the above curves are great for pathfinding, it was mostly just to demonstrate that there are tons of cool solutions out there..

raigan

[DancingOctopus]

Originally posted by metanet
i don't think that the above curves are great for pathfinding, it was mostly just to demonstrate that there are tons of cool solutions out there..

raigan

My initial thought was that it would be a good method for creating set paths for some enemies in a vertical/side scrolling space shooter type game. A few small mods to make the object rotate to the direction it moved and it would be perfect for it.

I'm almost tempted to start a new project to see how it goes...

[metanet]

just thought you might be interested in this:

http://www.cubic.org/~submissive/sourcerer/hermite.htm

raigan

[metanet]

hey,
i just added variable "tension" (straight from the site); if anyone wants to muck about with adding bias/etc., please do.. i'm too bit busy+lazy to finish porting the rest of the ideas on that site..

//catmull-rom spline, from GPG1 3.4
function vec2(x,y)
{
	this.x = x;
	this.y = y;
}
function DrawPlus(mc, x,y, r)
{
	mc.moveTo(x+r, y);
	mc.lineTo(x-r, y);
	mc.moveTo(x, y+r);
	mc.lineTo(x, y-r);
}

pList = new Array();
pList.push(new vec2(50, 250));
pList.push(new vec2(100, 300));
pList.push(new vec2(150, 200));
pList.push(new vec2(200, 250));
pList.push(new vec2(250, 300));
pList.push(new vec2(180, 350));
pList.push(new vec2(80, 320));

var sbuf = _root.createEmptyMovieClip("staticBuffer", 100);
sbuf.clear();
sbuf.lineStyle(0, 0x000000, 100);

for(var i in pList)
{
	var v = pList[i];
	DrawPlus(sbuf, v.x, v.y, 2);
}

var dbuf = _root.createEmptyMovieClip("dynamicBuffer", 200);

P_INDEX = 0;
U_PARAM = 0.4;
function DoStuff()
{
	if(Key.isDown(Key.LEFT))
	{
		U_PARAM -= 0.02;
		UpdatePos();
	}
	else if(Key.isDown(Key.RIGHT))
	{
		U_PARAM += 0.02;
		UpdatePos();
	}
}

function UpdatePos()
{
//wrap point indices	
	if(U_PARAM < 0)
	{
		//we moved into the next segment, backwards
		P_INDEX = ((P_INDEX - 1)+pList.length)%pList.length;
		U_PARAM = 1 + U_PARAM;
	}
	else if(1 < U_PARAM)
	{
		//we moved into the next segment, forwards
		P_INDEX = (P_INDEX + 1)%pList.length;
		U_PARAM = U_PARAM - 1;
	}	
//-----


	//get the 4 points to interpolate between
	var p0 = pList[P_INDEX];
	var p1 = pList[(P_INDEX + 1)%pList.length];
	var p2 = pList[(P_INDEX + 2)%pList.length];
	var p3 = pList[(P_INDEX + 3)%pList.length];


	var u = U_PARAM;//get parametric position between p1 and p2
	var uu = u*u;
	var uuu = uu*u;

/*
	//calculate weights given u
	var w0 = -0.5*uuu + uu - 0.5*u;
	var w1 = 1.5*uuu - 2.5*uu + 1;
	var w2 = -1.5*uuu + 2*uu + 0.5*u;
	var w3 = 0.5*uuu - 0.5*uu;

	var x = p0.x*w0 + p1.x*w1 + p2.x*w2 + p3.x*w3;
	var y = p0.y*w0 + p1.y*w1 + p2.y*w2 + p3.y*w3;
*/

/*	
	//this is "the long version"; more than one .x and .y lookup per vector
	var x = 0.5 *((2 * p1.x) +  (-p0.x + p2.x)*u + (2*p0.x - 5*p1.x + 4*p2.x - p3.x)*uu + (-p0.x + 3*p1.x - 3*p2.x + p3.x)*uuu);
	var y = 0.5 *((2 * p1.y) +  (-p0.y + p2.y)*u + (2*p0.y - 5*p1.y + 4*p2.y - p3.y)*uu + (-p0.y + 3*p1.y - 3*p2.y + p3.y)*uuu);
*/	

	//lets' try using a generic cardinal spline with tension
	//(from http://www.cubic.org/~submissive/sourcerer/hermite.htm)
	
	var h0 =  2*uuu - 3*uu + 1;          // calculate basis function 1
	var h1 = -2*uuu + 3*uu;              // calculate basis function 2
	var h2 =   uuu - 2*uu + u;         // calculate basis function 3
	var h3 =   uuu -  uu;              // calculate basis function 4
	
	//use p0 and p3 to calculate tangents at p1 and p2
	var a = 0.5;//tension; 0 is linear, 0.5 is catmull-rom, >1 is a bit weird..
	var t1x = a*(p2.x - p0.x);
	var t1y = a*(p2.y - p0.y);
	var t2x = a*(p3.x - p1.x);
	var t2y = a*(p3.y - p1.y);
	
	var x = h0*p1.x + h1*p2.x + h2*t1x + h3*t2x;
	var y = h0*p1.y + h1*p2.y + h2*t1y + h3*t2y;

	//draw the result
	dbuf.clear();
	dbuf.lineStyle(0, 0x228822, 100);
	DrawPlus(dbuf, x, y, 4);
}
UpdatePos();
_root.onEnterFrame = DoStuff;

raigan

[metanet]

hey,
um.. i'm not sure about the angles thing.

if you need constant velocity then my suggestion above of "use this to generate some points, then use your normal constant-velocity straight-line pathing" is probably the best thing -- it's simple and you know it will work: just start at the first point in your original list of points, then (stepping along the parameter at a constant rate) get a point on the curve and store it in a list of "points on the curve". then, use this second list with your straight-line algo instead of the first "coarse" list when moving people around.

trying to figure out how to move along a curve at constant velocity sounds like a huge headache to me. if you must, there are papers on this -- specifically, many 3D games use splines to move the camera around during cutscenes, and i'm positive i've read at least one paper on how to get constant-velocity movement over splines in realtime. but it's not likely to be cheap or easy..

raigan

[strille]

Interesting thread metanet.

Originally posted by metanet
hey,
trying to figure out how to move along a curve at constant velocity sounds like a huge headache to me. if you must, there are papers on this -- specifically, many 3D games use splines to move the camera around during cutscenes, and i'm positive i've read at least one paper on how to get constant-velocity movement over splines in realtime. but it's not likely to be cheap or easy..

raigan

This example moves along a path at constant speed using Lagrange interpolation. The calculations are very cheap once the path has been calculated. Try it with 50 balls and it should still run smoothly.