Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

August 4, 2021
August 4, 2021
Press Releases
August 4, 2021
Games Press
If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# A Practical Use for Recursion in Game Development

by Harold Bowman-Trayford on 09/04/18 10:31:00 am

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

### 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.

### Related Jobs

Mountaintop Studios — San Francisco, California, United States
[08.03.21]

Data Engineer
Mountaintop Studios — San Francisco, California, United States
[08.03.21]

Senior Gameplay Engineer
Mountaintop Studios — San Francisco, California, United States
[08.03.21]

Senior Engine/Systems Engineer
Vicarious Visions / Activision — Albany, New York, United States
[08.03.21]

Tools Engineer