Where on an NES cartridge is all this graphics data stored?

Question

I've successfully emulated the (slightly alternated) 6502 core for the Nintendo Entertainment System, and now I'm a little stuck on the PPU emulation.

In various documents it is noted that the PPU has 0x4000 (16KB) bytes of memory available. Only 2KB of that is internal RAM, while the rest is on the cartridge (or something along those lines). The thing I don't get is, the PPU makes use of pattern tables, name tables, attribute tables, a background palette and a sprite palette (off the top of my head). Where are all these things stored? I know that a CHR memory bank has a size of 8KB, so even if the ROM has multiple banks of graphics memory, how does the PPU know in which bank, which of these tables/palettes to find? And some games don't even have CHR memory, and everything is stored in the PRG memory. How can I figure out where everything graphical is stored for the purpose of emulation?

EDIT: I've added my own explanation as an answer, since I now have much more experience with the inner workings of the NES.

Answer 1

Since I asked this question, I've learned a ton of new things about the NES PPU, so I'll be answering this question myself.

To start off, the memory map of the PPU looks like this:

$0000 - $0FFF Pattern table 0 
$1000 - $1FFF Pattern table 1 
$2000 - $23BF Nametable 0
$23C0 - $23FF Attribute table 0
$2400 - $27BF Nametable 1
$27C0 - $27FF Attribute table 1
$2800 - $2BBF Nametable 2 
$2BC0 - $2BFF Attribute table 2 
$2C00 - $2FBF Nametable 3 
$2FC0 - $2FFF Attribute table 3
$3000 - $3EFF [0x2000 - 0x2EFF] mirror
$3F00 - $3F09 Background palette
$3F10 - $3F19 Sprite palette
$3F20 - $3FFF Palette mirror 

Other than that, there is a $FF (256) byte area called OAM, and there's a $20 (32) byte area called Secondary OAM.

How are they written to?

The pattern tables are used to hold graphics data of the NES in patterns, i.e. whatever is stored in here shows the shape of sprites used. These are generally stored in CHR ROM on a cartridge, but they can be written to the PPU memory by the programmer of the game as well. The way this happens will be explained below.

Other than the pattern tables, everything other than OAM and Secondary OAM is written by the programmer of the game into the PPU memory. This happens by using registers $2006 and $2007. How?

Whenever the programmer wants to write to a certain address in PPU memory, he can do so by storing (sta, stx, sty, and maybe other instructions as well) the address he wants to access by writing to $2006 twice through the CPU like he does in normal assembly. An example would be:

LDA #$20
STA $2006
LDA #$00
STA $2006

The user writes the high byte of the address first, and then the low byte. Now, a PPU internal 15 bit latch (not sure if latch is the right word) has the PPU address $2000 stored in it. Whenever the programmer wants to write to this address, (which, in this case, is the starting address of the first nametable) he can do so normally by writing the value he wants to store in this memory area to memory address $2007. When writing to this address, the written value will be put into the address in the 15 bit latch, and the latch will be incremented by either 1 or 32 (decided by bit 2 of the value in address $2000). That's basically how simple it is.

Of course, it's not that simple. Addresses $2000 - $2007 are called the PPU's Memory Mapped Registers, and they're called that because they're in the CPU's memory. They're located there because the CPU and the PPU can't access each other's memory directly, so the CPU has to find some gateway to the PPU's memory, and those addresses are it. There are a lot of strange exceptions and quirks to these registers, and they're all explained here.

Other than those, there's still the aforementioned OAM and Secondary OAM, but those are a whole different thing, and should be explained thoroughly by reading actually viable sources, rather than a quick explanation.

It's better to read it from the mentioned source (again, here) to get a full understanding, but this is just a quick explanation for those who were curious and actually have a basic understanding of this kind of stuff.

Answer 2

A game cartridge contains an integrated circuit which can contain many ROM chips. These will be accessed through the wires along the connecting edge. Aside from being hot-swappable, they work just like a ROM or RAM chip that's permanently in the computer. It's accessed by sending the right signals at it, usually mediated by a bus-controller chip, and a clock pulse. An address (in binary) is presented to it's address-wires and a certain number of clock-pulses later, it produces the desired data on its data-wires, which then flows down the bus to the cpu or a dma controller.

The physical locations will somewhat dictated by the hardware (a lot of memory chips had RAM and ROM portions that could be mapped to the same range). But it is largely under control of the program. Calculate pointer value, then use it. Fairly straightforward in assembly.