A Practical Use for Recursion in Game Development

INTRODUCTION

Pick up any serious book on algorithms or programming and you are certain to find a section on recursion.  The author will tout how important and powerful this technique is and then explain the theory and practice using a factorial as an example.  Factorials are a great place to start in a discussion of recursion because they are simple to understand and the applicability of recursive techniques is pretty obvious.  Unfortunately, factorials are not terribly useful in game development.

RECURSION - A LOOSE DEFINITION (A DETAILED DEFINITION)

Generally speaking, for recursion to be useful, you need a problem which can be solved by repetitive application of the same algorithm, each iteration getting you one step closer to a case which is either trivial or which can be solved without further applications.  

I have attempted to use recursion in game development on multiple occasions, but have always given up and found another solution.  Certainly a key component to this repeated outcome is my relative inexperience with finding recursive solutions, but another is that they tend to be mind-bendingly difficult to debug.  Any particular iteration of the algorithm should be easy enough to wrap your head around, and if you can stay focused on a single iteration you're well on your way.  I, however, find this to be quite challenging and regularly find myself going in circles or continuously trying to peek into the next iteration to see what the answer is.

BACKGROUND

On August 26th, I pitched G-Type, a side-scrolling SHMUP, at a Gamkedo™ Club meeting to propose the game for development by members.  There was some enthusiasm for the game so development is moving forward.  One week in, here’s the progress of the game:

APPLICATION

A requirement for the game is that we need to be able to specify the movement of an enemy spacecraft using a path defined by an array of points.  The entity has a starting position (which may or may not be the same location as the first point on the path) and it moves some distance (as determined by its speed and the time which has elapsed since the last time its position was updated) toward the next point in the path.  This continues for as long as the entity exists even if this causes the entity to travel beyond the end of the path (maintaining the speed/direction of travel of the final leg of the path).  

Because there is no guarantee the entity's position will land directly on any of the points which define the path, during any step there may be 'unconsumed' distance which must be traveled along the 'next' leg of the path.  Additionally, because the path points can be arbitrarily close (relative to the distance traveled), there is no guarantee the entity will finish the current iteration on either the current leg or then next leg of the path.

This situation lends itself nicely to a recursive solution because some (or all) of the available distance traveled is consumed during each iteration.  Eventually all of the distance is consumed and the result calculated can be returned.

SOLUTION

The trivial case for this scenario is when the unconsumed distance is less than the distance to the next point in the path.  Special cases which need to be accounted for are when the current position is between the start and the first point on the path and when the new position is beyond the final point of the path.  For the normal case, calculate the distance to the next point on the path and compare that to the currently unconsumed distance, if the path distance is greater, you’re at the trivial case and you can return.  If the path distance is less than the unconsumed distance, you need to subtract the distance to the next point from the unconsumed distance, increment to the next leg of the path and call the function again with the new (smaller) unconsumed distance.