A 6502 lisp compiler, sprite animation and the NES/Famicom

For our new project "what remains", we're regrouping the Naked on Pluto team to build a game about climate change. In the spirit of the medium being the message, we're interested in long term thinking as well as recycling e-waste - so in keeping with a lot of our work, we are unraveling the threads of technology. The game will run on the NES/Famicom console, which was originally released by Nintendo in 1986. This hardware is extremely resilient, the solid state game cartridges still work surprisingly well today, compared to fragile CDROM or the world of online updates. Partly because of this, a flourishing scene of new players are now discovering them. I'm also interested that the older the machine you write software for, the more people have access to it via emulators (there are NES emulators for every mobile device, browser and operating system).

Our NES with everdrive flashcart and comparatively tiny sdcard for storing ROMs.

These ideas combine a couple of previous projects for me - Betablocker DS also uses Nintendo hardware and although much more recent, the Gameboy DS has a similar philosophy and architecture to the NES. As much of the machines of this era, most NES games were written in pure assembly - I had a go at this for the Speccy a while back and while being fun in a mildly perverse way, it requires so much forward planning it doesn't really encourage creative tweaking - or working collaboratively. In the meantime, for the weavingcodes project I've been dabbling with making odd lisp compilers, and found it very productive - so it makes sense to try one for a real processor this time, the 6502.

The NES console was one of the first to bring specialised processors from arcade machines into people's homes. On older/cheaper 8 bit machines like the Speccy, you had to do everything on the single CPU, which meant most of the time was spent drawing pixels or dealing with sound. On the NES there is a "Picture Processing Unit" or PPU (a forerunner to the modern GPU), and an "Audio Processing Unit" or APU. As in modern consoles and PCs, these free the CPU up to orchestrate a game as a whole, only needing to sporadically update these co-processors when required. You can't write code that runs on the PPU or APU, but you can access their memory indirectly via registers and DMA. One of the nice things we can do if we're writing a language for a compiling is building optimised calls that do specific jobs. One area I've been thinking about a lot is sprites - the 64 8x8 tiles that the PPU draws over the background tiles to provide you with animated characters.

Our sprite testing playpen using graphics plundered from Ys II: Ancient Ys Vanished. The sprites are controlled by 256 bytes of memory that you copy (DMA) from the CPU to the PPU each frame. There are 4 bytes per sprite - 2 for x/y position, 1 for the pattern id and another for color and flipping control attributes. Most games made use of multiple sprites stuck together to get you bigger characters, in the example above there are 4 sprites for each 16x16 pixel character - so it's handy to be able to group them together.

Here's an example of the the compiler code generation to produce the 6502 assembly needed to animate 4 sprites with one command by setting all their pattern IDs in one go - this manipulates memory which is later sent to the PPU.

(define (emit-animate-sprites-2x2! x) (append (emit-expr (list-ref x 2)) ;; compiles the pattern offset expression (leaves value in register a) (emit "pha") ;; push the resulting pattern offset onto the stack (emit-expr (list-ref x 1)) ;; compile the sprite id expression (leaves value in a again) (emit "asl") ;; *=2 (shift left) (emit "asl") ;; *=4 (shift left) - sprites are 4 bytes long, so = address (emit "tay") ;; store offset calculation in y (emit "iny") ;; +1 to get us to the pattern id byte position of the first sprite (emit "pla") ;; pop the pattern memory offset back from the stack (emit "sta" "$200,y") ;; sprite data is stored in $200, so add y to it for the first sprite (emit "adc" "#$01") ;; add 1 to a to point to the next pattern location (emit "sta" "$204,y") ;; write this to the next sprite (+ 4 bytes) (emit "adc" "#$0f") ;; add 16 to a to point to the next pattern location (emit "sta" "$208,y") ;; write to sprite 2 (+ 8 bytes) (emit "adc" "#$01") ;; add 1 to a to point to the final pattern location (emit "sta" "$20c,y"))) ;; write to sprite 4 (+ 12 bytes)

The job of this function is to return a list of assembler instructions which are later converted into machine code for the NES. It compiles sub-expressions recursively where needed and (most importantly) maintains register state, so the interleaved bits of code don't interfere with each other and crash. (I learned about this stuff from Abdulaziz Ghuloum's amazing paper on compilers). The stack is important here, as the pha and pla push and pop information so we can do something completely different and come back to where we left off and continue.

The actual command is of the form:

(animate-sprites-2x2 sprite-id pattern-offset)

Where either arguments can be sub-expressions of their own, eg.:

(animate-sprites-2x2 sprite-id (+ anim-frame base-pattern))

This code uses a couple of assumptions for optimisation, firstly that sprite information is stored starting at address $200 (quite common on the NES as this is the start of user memory, and maps to a specific DMA address for sending to the PPU). Secondly there is an assumption how the pattern information in memory is laid out in a particular way. The 16 byte offset for the 3rd sprite is simply to allow the data to be easy to see in memory when using a paint package, as it means the sprites sit next to each other (along with their frames for animation) when editing the graphics:

You can find the code and documentation for this programming language on gitlab.