Tuesday, October 21, 2014

Kernels, enemies dying, and bankswitching

So for the past couple weeks, I've been putting off working on Atari Anguna because I've been up against a bug that sounded difficult and boring to solve: whenever I killed an enemy, it messed up my kernel logic, and everything went haywire.

What's supposed to happen, is that every frame, I sort my enemies by Y position, and then compare all their Y values, select the right kernel mode, then draw them in order. If an enemy is dead, I'd sort it to the end, and select kernel modes that ignored that enemy. But it wasn't working.

I sat down to tackle this today, and happily, it only took about 10 minutes. It was a simple logic error in my sorting routine, which occasionally caused a dead enemy to get sorted to the front of the list.

(Tangent time! I ended up using a *gasp* Bubble Sort for sorting these enemies. Why? Because I realized that for N=3, which is my case, Bubble Sort only requires 3 comparisons (a/b, b/c, a/b again). So it's a really simple sort to implement, and if I'm guaranteed constant time, then hey, why not. The bug I ran into was that if the enemy in the first position of a comparison was dead, I'd always swap, but I forgot to check if the enemy in the 2nd position was dead, and refuse to swap in that case.)

So tonight I also realized that my kernel was working for 3 enemies as long as 2 of them overlapped, but I never had gotten around to implementing my kernel mode for 3 completely separate enemies. That's really simple and straightforward, but requires a good bit of compiled-code, as I'm using macros instead of subroutines (I can't afford the 6 cycles for the JSR and 6 more cycles for the RTS during my kernels!), so in the compiled code, there's tons of repetition. Well, this created a new problem: I've now almost used up my entire 4K of ROM.

Now the geniuses back in the 80's solved this problem with bankswitching, which is what I now have to figure out. Basically, there are 2 entirely separate blocks of ROM that you can switch in and out of actual ROM. This gives you double the space, but gets tricky. For example, as soon as you give the command to switch banks, it immediately switches. Meaning the instruction pointer is now pointing to the memory location of the next command, but in the other bank. So you have to make sure to line up your code just right, so that when you toggle banks, the code in the new bank picks up and runs where you left off. (And when you power on the Atari, you don't know which bank you're in. So both banks have to have identical initialization routines, so you can get yourself into a known state!)

I think I've got the basics working now:
In both banks, I have an almost-identical routine where I manually load a target address (the target address of a routine in the other bank that I want to execute) onto the stack, simulating what would happen if I had jumped to a subroutine with JSR. Then I toggle banks, and immediately RTS, which makes the Atari try to return from the subroutine, and jump to the target routine in the new bank:

    ORG $D009    ;Bank 0 uses a "pretend" address of $D000
    RORG $F009   ;but a "real" address of $F000
                 ;(The actual Atari ROM is always $F000) 

    LDA BANK_2   ;Reading this register switches banks
    RTS          ;and then jump to the location on the stack


    ORG $E009    ;Now the same thing for Bank 1
    RORG $F009    

    LDA BANK_1   


; And then a macro to make it easier to set up
; and call the JumpToOtherBank routine

        MAC BankJump 
            LDA #>{1}   ;push the target's MSB onto the stack
            LDA #<{1}-1 ;push the LSB (minus one*) onto the stack
            JMP JumpToOtherBank ;then call the magic routine


* I spent a good while fighting this code until I realized I needed the "minus one" on the least-significant-bit. Turns out JSR pushes one less than the address of the next command, and then RTS pulls that from the stack, and increments it. So I was 1 byte off when I'd try to RTS, which was breaking everything horribly.

I still need to actually break my code up into the different banks now. I'm hoping to fit the kernels and graphics data in bank 1, and everything else in bank 0. But we'll see.

And I still need to actually test my full kernel for 3 separate enemies. And do the enemy-wall collisions that I've been planning for weeks. But bank switching is more fun.....


sverx said...

Bubble sort isn't always bad. Yes, I know it's O(n^2) but if you compare some k*n^2 efficient algorithm to a some k'*n*log(n) you might find that in some cases (small n) the first is faster. People tend to forget the constant...

Nathan Tolbert said...

Hi Sverx! Didn't know you read my blog! That puts me up to somewhere around 4 readers, I think!

Anyway, yeah, I agree. I actually came really close to using a Bubble Sort in GBA Anguna as well, in the same way -- to sort my enemies according to Y value. In that case, I reasoned that the vast majority of the time, they'd be already sorted. Occasionally (once every 120 frames or so?) 2 of them would swap places with each other. In that case, Bubble Sort seemed like a perfect choice, as it would only require one pass the vast majority of the time.

I was finally convinced away from that idea when I had a few rooms with ghosts that randomly appeared in different places. Those would require a full sort, so I went with a merge sort, which was going to have more reliable performance (not as fast as the optimal bubble sort situation, but not quite as slow as the worst)

And in both cases, I was usually only sorting at most 12 enemies. Just about any sort would work with numbers that small.