Monday, August 8, 2011

Galaga Formation Patterns Explained

Back in March I was able to successfully recreate galaga style enemy patterns using pattern tables and some custom motion code. But there was one problem with the implementation: dual side-by-side formations were wrong--at certain points the inner and outer formation paths intersect.

Why do the formations intersect? Each formation is following the same pattern table commands but the outer formation adds an additional offset to the (x, y) position of outer formation ship to keep the formations apart. Now, imagine two formations following the same circular path where the outer path (in this case the red circle) is offset by some (x, y) position. Eventually at some time t (or some radian theta) the two circular paths will intersect as demonstrated below:

It is pretty obvious that the inner and outer formations can not use the same circle. But what if we increase the radius of the outer circular path by a few units keeping the two paths separated by some distance D defined by D = | R1 - R0 | (where R0 and R1 are the radius of the inner and outer circles). Ok now we have two formations each following a circular path which gives the illusion that the formations are mirroring one another. Imagine the red dots are ships following the circular paths as demonstrated below:

Great. So we can stop the formations from intersecting if they are all circular paths. But not all paths in Galaga (or any other SHMUP) are just circles. Enemy ships fly around in all sorts of complex curving patterns. Ok. So if rather than separately specifying the outer formation path what if the inner formation path is used to create the outer formation. Starting from the circle path example above. Geometrically it is obvious that one should be able to find R1 from R0--simply add some offset to R0 to get R1 and use the same cos/sin equation.

Ok. But what about any sort of curve. From calculus we know that given the equation for any curve we can get the tangent to the curve and the normal of the curve at any point. Using the normal we could then calculate a point at any distance from the curve along the direction of the normal. Visualized below:

So the same idea can be applied to the equations representing motion in Galaga. Somehow we need to use the inner formation position and direction of travel to generate the outer formation positions and orientations.

In Galaga the motion of the ships can be represented by a 2D rotation and translation matrix or these equivalent equations:

X' = V * cos(theta) + X
Y' = V * sin(theta) + Y

where V is the velocity of a ship. The theta in this case represents the direction of travel in radians on the cartesian plane. This means that the direction of travel is given by the unit vector:

dir = < cos(theta) , sin(theta) >

by changing theta using pattern tables one can achieve all sorts of complex pattern maneuvers.

So for any ship all we need to do is rotate its direction vector by PI/2 or -PI/2 radians to get a vector perpendicular to it. Which we can use like the normal to the curve to get some point to the left or to the right relative to the direction the ship is traveling as visualized below:

So to position the red triangle (follower) the following equation is used:

follower_x_pos = R * cos( theta_leader +/- PI/2 ) + leader_x_pos
follower_y_pos = R * sin( theta_leader +/- PI/2 ) + leader_y_pos

where R is the constant distance between the leader and follower. This results in the follower always being positioned to the left or to the right relative to the leader. Finally to get the follower to orient in the same direction simply apply the theta_leader to the final orientation of the follower once its position has been calculated.

Demo (click on image to open):

Source Code: