How to do multiple things at once?

[FinalZero]

How do games (on any system) do multiple things at once? For example, take a simple stage in Super Mario Bros. Many things are happening at the same time: Mario is moving/jumping around, multiple enemies are walking around, and music is playing. But most systems (including the NES's 6502) have only a single (and slow, by modern standards) processor, so this must be a façade of some sort. How are all these actors/events synchronized?

My thought is that perhaps there's a main loop that computes and updates only the next immediate state/action/position for each actor/event, and then loops again. Like this:

Code: Select all

main() {
  while(true) {
    updateMario();
    updateEnemy1();
    updateEnemy2();
    updateEnemy3();
    updateMusic();
  }
}

And here's another question that's almost the same as the last, but not really relevant to the NES: How does an operating system implement having separate processes and threads, and how does it stop one process or thread that is stuck in an infinite loop from freezing the whole system?

[tokumaru]

My thought is that perhaps there's a main loop that computes and updates only the next immediate state/action/position for each actor/event, and then loops again.

That's exactly it. Each object (and by object I mean not only game objects, but any entity that takes part in the functioning of the program) gets a chance to update its state, taking into consideration whatever data it deems necessary (i.e. some objects observe the states of other objects in order to make their decisions). Really, it's all just about computing the next step.

How does an operating system implement having separate processes and threads, and how does it stop one process or thread that is stuck in an infinite loop from freezing the whole system?

Can't help you much with that... =P I did have some classes about this in college, but they were very superficial and theoretical.

[tepples]

Operating systems use an interrupt to "preempt" an application, saving all registers and loading those of the next task. Each application has its own stack and heap, and in fact, each executes in a separate bank of RAM.

[FinalZero]

That's exactly it. Each object (and by object I mean not only game objects, but any entity that takes part in the functioning of the program) gets a chance to update its state, taking into consideration whatever data it deems necessary (i.e. some objects observe the states of other objects in order to make their decisions). Really, it's all just about computing the next step.

Getting that right makes me feel better. In theory then, if I ran SMB instruction by instruction, I should see each object move one at a time, right?

The next question then is how things are organized so that the game doesn't go fast when there's few objects on screen, and then slow when there's many, but instead at a constant rate. I suppose that one counts cycles, and makes sure that the cycles always add up to a certain number? This must be tricky to do when branching is included. Do modern games do something different?, because this seems awfully complicated.

And how does one choose what number to count to? Too low and the game's too fast, too high and the game's too slow, but the number must still be high enough for the whole update loop to run.

[Dwedit]

Games wait for vblank. Then they don't care how few objects there are on the screen. You only get a problem with slowdown when there are too many objects.

[Jarhmander]

Regarding the initial OS question, it's basically some sort of timer IRQ that get the CPU out of the current process, save the context of the current process and then execute some kernel code to know which process to run next (a scheduler). My description is severely over-simplified as the details get pretty complex but you get the basic picture.

EDIT: ninja'd by tepples.

[FinalZero]

Games wait for vblank. Then they don't care how few objects there are on the screen. You only get a problem with slowdown when there are too many objects.

1) VBlank happens 60 times per second in NTSC, and 50 times per second in PAL, right?
2) How do you "wait" for it? How long is a single cycle?

[Dwedit]

Once again, interrupts.
On the NES, there are several ways to actually write the code, but here's one of them:

NMI: (this runs when vblank happens)
...
inc vblanked (change the number to something that's not 0)
...

WaitForVblank: (this runs when the code wants to wait for vblank)
lda #0
sta vblanked (set the number to 0)
waitloop:
lda vblanked
beq waitloop (repeatedly check if the number has changed from 0 to something else)

[tokumaru]

1) VBlank happens 60 times per second in NTSC, and 50 times per second in PAL, right?

Yes.

2) How do you "wait" for it? How long is a single cycle?

The PPU generates an NMI interrupt every time VBlank starts. You just have to wait for that to happen. The simplest way to do this is to prepare an NMI handler that changes a flag (it can be as simple as INC VBlankFlag; RTI). Then, after the processing of all game objects, make a loop that waits for this flag to change before looping back and processing all game objects again.

[blargg]

Your question about avoiding infinite loops shows that you're thinking in terms of "cooperative" software, where the OS waits for it to say it's done. Interrupts provide the opposite: a way for something hardware (not software) to forcefully stop the current code and execute something else. With threads, the thing interrupting is a timer, so that the OS can regularly switch to another thread and give them each a slice of time. So it ends up looking like your example where each thing runs for a bit at a time, but without having to arrange for exactly where the switch occurs. It's less predictable, but less work and more reliable since you can't forget to allow the switch.

There's even a NES multithreading demo that implements multiple threads using the timer interrupt approach above, if you want to see the rudiments of how this works in an OS. The two threads move objects at different speeds across the screen, each one an infinite loop acting as if it's the only thing running on the NES, using a plain delay loop to set the object's movement speed.

[FinalZero]

Yes.

Okay.

The PPU generates an NMI interrupt every time VBlank starts. You just have to wait for that to happen. The simplest way to do this is to prepare an NMI handler that changes a flag (it can be as simple as INC VBlankFlag; RTI). Then, after the processing of all game objects, make a loop that waits for this flag to change before looping back and processing all game objects again.

How does the PPU know when to generate an interrupt? Do NTSC and PAL NES's have different hardware? The NES doesn't read something from the television, does it?

With threads, the thing interrupting is a timer, so that the OS can regularly switch to another thread and give them each a slice of time. So it ends up looking like your example where each thing runs for a bit at a time, but without having to arrange for exactly where the switch occurs.

Okay, so I was somewhat right about threads too. I was thinking that perhaps the OS lets process/thread A run for x ms, then process/thread B for x ms, then the OS itself for x ms (so the user can close programs, start new ones, etc), then looping on this.

[FinalZero]

There's even a NES multithreading demo that implements multiple threads using the timer interrupt approach above, if you want to see the rudiments of how this works in an OS. The two threads move objects at different speeds across the screen, each one an infinite loop acting as if it's the only thing running on the NES, using a plain delay loop to set the object's movement speed.

Thank you! I will definitely look at this.

Also, going back to my Mario example, there must also be a spawnEnemies() event/object, that spawns an enemy at a given location depending on Mario's X and Y, and a despawnEnemies() event/object, that despawns an enemy depending on Mario's X and Y? And in SMB3, where you can go backwards and forwards through the stage, it must also remember whether the enemy is dead (so don't spawn it again).

[Dwedit]

The PPU's job is to make a TV picture out of what it sees in its memory.
It's making 240 visible scanlines of picture, and 26 lines of Vblank between the frames. (there's also some horizontal and vertical sync pulses in there too)
It knows which scanline it's processing, and what it's doing. When it finishes drawing the 240 lines of picture, it starts making vblank for the TV. One scanline later it generates a non-maskable interrupt (NMI).
That's the interrupt that the game uses.

[cpow]

In theory then, if I ran SMB instruction by instruction, I should see each object move one at a time, right?

That would be true if the game only had enough cycle time to update one object's state per frame. I'm not sure but I believe SMB has ample time to update the state of all objects per frame. Since the CPU's execution of instructions is only marginally tied to the PPU's "execution" of a frame, the answer to your question is no. Updating mario's position, for example, updates a value in CPU RAM. That value in RAM is calculated by the "mario object" "task" [code related to mario's behavior], then the CPU updates the OAM shadow copy in RAM. Then during VBLANK the CPU initiates sprite DMA to copy the sprite positions [including mario's updated position] to the PPU. Then the PPU, while rendering the next frame, will display mario in his changed state.

[FinalZero]

The PPU's job is to make a TV picture out of what it sees in its memory.
It's making 240 visible scanlines of picture, and 26 lines of Vblank between the frames. (there's also some horizontal and vertical sync pulses in there too)
It knows which scanline it's processing, and what it's doing. When it finishes drawing the 240 lines of picture, it starts making vblank for the TV. One scanline later it generates a non-maskable interrupt (NMI).
That's the interrupt that the game uses.

I don't understand.

What's the difference between a vblank and a frame? I thought that both happened 60 or 50 times per second.

The PPU generates an NMI interrupt every time VBlank starts. You just have to wait for that to happen. The simplest way to do this is to prepare an NMI handler that changes a flag (it can be as simple as INC VBlankFlag; RTI). Then, after the processing of all game objects, make a loop that waits for this flag to change before looping back and processing all game objects again.

So, the loop basically looks like this?:

Code: Select all

main() {
  while(true) {
    updateMario();
    updateEnemy1();
    updateEnemy2();
    updateEnemy3();
    updateMusic();
    
    waitForVBlank();
    resetVBlankCounter();
    writePictureToTV();
  }
}

How does writePictureToTV() work though? Does the PPU do that automatically?