How does Galaga work?

[FinalZero]

Galaga was originally an arcade game, but a NES port was eventually made. For those who don't know, it's basically an evolution of space invaders.

Anyways, it impresses me for a NES game; I'm not sure how it does a few things (though some of these things that I wonder about aren't extant in only the NES version):
1) How does it compute the division of shots_hit / shots_fired? It certainly isn't using a table, and you can even get over 100% because you can hit multiple enemies with a single shot.
2) How does it store stages? (Each stage seems to have multiple waves, each of which a) has a group of enemies (there are many kinds), b) follows a pattern to appear on the screen, c) and then retreats to the top of the screen.) It must use some kind of timer to judge when the next wave should appear, since they appear whether you shoot or not. It seems more complicated to model than something like dragon warrior or mario.
3) How does it compute these patterns that enemies follow before retreating?

[rainwarrior]

1. Doing a division once when the player game overs isn't any kind of performance concern, it only really matters when you're trying to do it multiple times per frame. There are standard 6502 division algorithms you can look up.

2. I don't know exactly what it does, but it looks like enemies mostly follow very fixed patterns, repeating over and over. Probably there are a bunch of paths stored that get applied to the enemies. I would probably write the path data like this:

Table of 16 direction pairs (vectors): x per frame, y per frame
Maybe something like:
0 = 0, 2 (down)
1 = 1, 2 (down-down right)
2 = 2, 2 (down right)
3 = 2, 1 (down right-right)
4 = 2, 0 (right)
5 = 2, -1 (up right-right)
...

Then path lists: direction, frames to continue in direction

Path A = 0 (down), 5 frames, 1 (down-down right), 5 frames, 2 down right), 10 frames...
Path B = 0 (down), 4 frames, 15 (down-down left), 6 frames, 14 (down left), 8 frames...

That way I could make a set of arbitrary paths and apply them to any of the characters as needed. You could make character positions 16 bit and make the direction vectors 16 bit if you need more accuracy (taking the top bits as their onscreen position). All you do is add the current path direction to the character's position each frame.

Enemy AI is probably just a matter of waiting a random or predetermined amount of time, then playing a path. At the end of the path it returns to the enemy grid (or disappears, in a bonus stage) then waits again to play another path.

[Movax12]

I would be interested in seeing how they are rendering all those enemies with the 8 sprite per scanline limitation.

[Gilbert]

I haven't really played the game, but I think they just become background tiles when they're "locked in place" and become sprites when they're flying in some paths. (I suppose Space Invader is done the same way.)

[lidnariq]

I know that Galaxian does what Gilbert suggested

[tokumaru]

I would be interested in seeing how they are rendering all those enemies with the 8 sprite per scanline limitation.

This is easy to check in any emulator that offers PPU debugging, like FCEUX or Nintendulator. Open the Name Table viewer and you can easily see the contents of the background. Whatever isn't there, is rendered with sprites, so you can easily see when enemies switch from background to sprites and vice-versa.

[Movax12]

Yep, I'm going to verify this when I get a chance. I've been busy all day but I played a bit of Galaga on my phone and noticed the lack of flickering. Really, there is no other explanation than that it is done with tiles, but it is done very well.

[Sik]

I know that Galaxian does what Gilbert suggested

Even worse, not only Galaxian uses the tilemap for locked enemies, the starfield is actually made with sprites o_O;

[tokumaru]

That's a pretty good use for sprites actually, because we don't find it weird when stars flicker.

EDIT: I checked both games and they do things pretty much the same way: stars are sprites, enemies in formation are background. The only difference I could spot is that Galaga modifies the name table in order to move enemies sideways, while Galaxian does this by modifying the scroll mid-frame.