Moving Along A 2D Path

For game #2 of 2016, I wanted to use a movement system similar to one that can be found in Steam Birds, Critical Mass, and some other games. I am most of the way there and would like to talk about some of the different approaches and barriers I have run into so far.

Hermite Interpolation

Gonna start with the difficult sounding silly math that is not really what I needed and also not as complicated as it sounds. Especially since the code for it is out there and you can almost copy pasta it into whatever language you are working in.

In Monkey-X it looks something like this:

Function CubicHermite:FloatDeque (start_point:Float, end_point:Float, start_velocity:Float, end_velocity:Float)
	Local pathPoints:FloatDeque = New FloatDeque
	Local division:Float = 30.0
	For Local i:Int = 0 Until division
		Local t:Float = (Float(i)/division)
		Local t_square:Float = t * t
		Local t_cube:Float = t_square * t
		Local a:Float = 2*t_cube - 3*t_square + 1
		Local b:Float = -2*t_cube + 3*t_square
		Local c:Float = t_cube - 2*t_square + t
		Local d:Float = t_cube - t_square 
		Local point:Float = a * start_point + b * end_point + c * start_velocity + d * end_velocity
	Return pathPoints

Basically you use this method to find some number of points along the curvy path that you are trying to create. You need to know what direction and speed you are going to begin, the direction and speed you will be going when you are done, and what point in time you want to get on the line. Essentially if you wanted to move along the line at 30 frames per second you will need 30 points to render whatever you are moving at. You would loop through the function doing your interpolation 30 times where the point in time is 1/30 to 30/30. You push all of these points into some sort of ordered data structure, in my case a Deque.

Note: This particular implementation only finds 1 part of the coordinate. If you are in 2D you need to run it once for X and once for Y, and if you are in 3D you need to run it one more time for the Z coordinate.

The formula then creates a nice curvy path to go from the first point to the next but ended up being not exactly what I was going for.

Simple Steps Approach

The problem I was having getting my head around with the interpolation approach was how to properly put limits on the movement. Distance was not a problem, but I only want the units to be able to turn so far.

The solution I ended up going with was to give each unit a rotational angle limit. Then I went through the 30 step loop again and on each step I calculated the angle from where I was to where I was headed. If it was greater than my current heading, we add the rotation limit to our current heading. If less than, we subtract the rotation limit from our current heading. Then we move 1/30th of our speed in the new direction and repeat.

Method SetControl(click_x:Float, click_y:Float)

	Local goal_angle = ATan2((click_y - position.y), (click_x - position.x))
	Local start_angle = heading
	Local control_pos:Vec2D = New Vec2D(position.x, position.y)
	Points = New Deque
	For Local i:Int = 0 Until 30
		control_pos = NewPoint(control_pos, start_angle, goal_angle, maxRotation, maxVelocity/30.0)
		If (start_angle > goal_angle)
			start_angle = start_angle - maxRotation
		Else If (start_angle < goal_angle)
			start_angle = start_angle + maxRotation
		goal_angle = ATan2((click_y - control_pos.y), (click_x - control_pos.x))
	control.position.Set(control_pos.x, control_pos.y)

Function NewPoint:Vec2D (start_point:Vec2D, start_angle:Float, goal_angle:Float, max_angle_change:Float, distance:Float)

	Local new_angle:Float
	If (start_angle > goal_angle)
		new_angle = start_angle - max_angle_change
	Else If (start_angle < goal_angle)
		new_angle = start_angle + max_angle_change

	Return New Vec2D(start_point.x + distance * Cosr(new_angle * (PI/180)), start_point.y + distance * Sinr(new_angle * (PI/180)))


Doing this lets me intuitively limit the turning radius and maximum velocity of the units. It might not be the fancy way to do it or the most efficient. But it works. And that is all we are going for.

Note about Monkey-X Documentation for ATan2(x, y): the documentation reads that it gives the Arc Tangent of x / y in degrees. Traditionally these variable names are switched. If you are thinking in typical Cartesian coordinates you will want to pass you Y value in as the first parameter and X as the second. This caused me a bit of confusion.

p.s. This code was not cleaned up for this post and a lot of it was written between 10 P.M. and 1 A.M. The purpose was not to show of how code should look but rather sample implementations of useful functions.

I Want to Be a Better Developer