Bill & Ted NES map ripper

a.c

/***

bill & ted nes map ripper
written by karmic, jul 10-11, 2021
slightly improved jan 16-17, 2022

requires libpng (compile with "-lpng")

rom must be in the working directory and called "Bill & Ted's Excellent Video Game Adventure (U) [!].nes"

***/



#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>

#include <png.h>
#include <zlib.h>

/*
note on perspective:

the game operates on this axis:
 w   n
  \ /
   .
  / \
 s   e

therefore, this is the vertical perspective:
 | | | |  /
 o | | | /
 u | | |/
 t | | /
 s | |/
 i | /
 d |/
 e /   inside
 |/
 /

and this is the horizontal perspective:
\  | | | | |
 \ | | | o |
  \| | | u |
   \ | | t |
    \| | s |
     \ | i |
      \| d |
       \ e |
 inside \| |
         \ |
          \

north/east means a higher coordinate value. coordinates are arranged like so:

hi --------> lo
zzzzyyyy yyyyyyyy xxxxxxxx

z = level region
y = actual position
x = fractional part

sometimes the lowest byte is completely omitted

the coordinates actually operate in 2-pixel units



ram map:
    $26 - level id:
        $00 - egyptian world
        $01 - medieval world 1
        $02 - medieval world 2
        $03 - colonial world
        $04 - western world
        $05 - modern world
    
    $38-$39 - horz nametable copy dest #1
    $3a - horz nametable copy size #1
    $3b-$3c - horz nametable copy dest #2
    $3d - horz nametable copy size #2
    
    $45-$46 - vert nametable copy dest #1
    $47 - vert nametable copy size #1
    $48-$49 - vert nametable copy dest #2
    $4a - vert nametable copy size #2
    
    $f0 - ppuctrl
    $f1 - ppumask
    $f2 - ppuscroll x
    $f3 - ppuscroll y






rom map (note: game uses fixed $8xxx and configurable $cxxx):
    $02:$cf56 - level pointer table


level format:
can have a maximum of 16 entries indexed by upper nybble of $d7 (i.e. the "region" number)
access routine at $af10

for each region ($10 bytes):
    word - screen map pointer (in bank 2) -> $e4
    byte - -> $da
            bit 7 - 0: vertical, 1: horizontal
            bits 0-6 - amount of screens
    word - per-frame commands (in bank 2) -> $06e9
    byte - amount of per-frame commands -> $06e8
    word - pointer (in bank 2) -> $06eb
    byte - max coordinate hi -> $df
    byte - max coordinate lo -> $de
    byte - min coordinate hi -> $e1
    byte - min coordinate lo -> $e0
    word - pointer -> $e2
    word - palette pointer -> $ee


$06 is for historical bait?

$08 is the important command that handles crossroads (that transition from region to region)
    byte - src coordinate hi
    byte - src coordinate lo
    byte - ?
    byte - dest coordinate hi
    byte - dest coordinate lo

$09/$0a is for enterable doors
$0b is for "blocked" doors that kick you out




level screen map format:

each level is divided into any amount of "regions", then any amount of screens, then 8 columns, then 8 (outside)/16 (inside) rows, then metatiles

a column is 4 tiles wide and a row is 2 tiles high

metatiles are 9 bytes long, arranged row by row, then with the additional attribute byte
    bits 0-1: left side palette id
    bits 2-3: right side palette id
both nybbles should be the same


for each:
    byte -  bits 0-2: screen bank
            bits 3-7: screen set
    byte - screen outside arrangement id
    byte - screen inside arrangement id

valid bank/set values are:
    $03 - inside long building, vertical
    $0b - inside small building, vertical
    $13 - western world, vertical
    $1b - western world, horizontal
    $23 - egyptian world, vertical
    $2b - egyptian world, horizontal
    $04 - medieval world villages, vertical
    $0c - medieval world villages, horizontal
    $14 - medieval world castles, vertical
    $1c - medieval world castles, horizontal
    $24 - colonial(?) world, vertical
    $2c - colonial(?) world, horizontal
    $34 - modern(?) world, vertical
    $3c - modern(?) world, horizontal

as can be seen, sets are separated by the look of the area and the perspective
there may not be any more than 8 sets within a bank


the set infos are at the start of the bank. all data is words
$c000 - palette pointers
$c010 - background chr banks
$c020 - metatile data pointers
$c030 - outside column data pointers
$c040 - inside column data pointers
$c050 - outside column map pointers
$c060 - inside column map pointers




*/


const uint32_t palette[] = { 0xFF666666, 0xFF002A88, 0xFF1412A7, 0xFF3B00A4, 0xFF5C007E, 0xFF6E0040, 0xFF6C0600, 0xFF561D00, 0xFF333500, 0xFF0B4800, 0xFF005200, 0xFF004F08, 0xFF00404D, 0xFF000000, 0xFF000000, 0xFF000000, 0xFFADADAD, 0xFF155FD9, 0xFF4240FF, 0xFF7527FE, 0xFFA01ACC, 0xFFB71E7B, 0xFFB53120, 0xFF994E00, 0xFF6B6D00, 0xFF388700, 0xFF0C9300, 0xFF008F32, 0xFF007C8D, 0xFF000000, 0xFF000000, 0xFF000000, 0xFFFFFEFF, 0xFF64B0FF, 0xFF9290FF, 0xFFC676FF, 0xFFF36AFF, 0xFFFE6ECC, 0xFFFE8170, 0xFFEA9E22, 0xFFBCBE00, 0xFF88D800, 0xFF5CE430, 0xFF45E082, 0xFF48CDDE, 0xFF4F4F4F, 0xFF000000, 0xFF000000, 0xFFFFFEFF, 0xFFC0DFFF, 0xFFD3D2FF, 0xFFE8C8FF, 0xFFFBC2FF, 0xFFFEC4EA, 0xFFFECCC5, 0xFFF7D8A5, 0xFFE4E594, 0xFFCFEF96, 0xFFBDF4AB, 0xFFB3F3CC, 0xFFB5EBF2, 0xFFB8B8B8, 0xFF000000, 0xFF000000 };

png_color pngpal[0x41];
png_byte pngtrns[0x41];



uint8_t *prg = NULL;
uint8_t *chr = NULL;

uint8_t *bmp = NULL;
unsigned bmpwidth;
unsigned bmpheight;


uint8_t *getprg(uint8_t bank, uint16_t addr)
{
    return prg+(bank*0x4000)+(addr&0x3fff);
}


uint16_t getlittle(uint8_t *p)
{
    return *p | *(p+1) << 8;
}

uint16_t getbig(uint8_t *p)
{
    return *p << 8 | *(p+1);
}

uint16_t getprglittle(uint8_t bank, uint16_t addr)
{
    uint8_t *p = getprg(bank,addr);
    return *p | *(p+1) << 8;
}

uint16_t getprgbig(uint8_t bank, uint16_t addr)
{
    uint8_t *p = getprg(bank,addr);
    return *p << 8 | *(p+1);
}



void writetile(unsigned x, unsigned y, uint8_t bank, uint8_t tile, uint8_t *pal)
{
    uint8_t *tp = chr+(bank*0x1000)+(tile*0x10);
    
    for (int yf = 0; yf < 8; yf++)
    {
        for (int xf = 0; xf < 8; xf++)
        {
            uint8_t pi = (tp[yf] & (0x80 >> xf)) ? 1 : 0;
            pi |= (tp[yf+8] & (0x80 >> xf)) ? 2 : 0;
            
            bmp[((y+yf)*bmpwidth)+x+xf] = pal[pi];
        }
    }
}


void writemetatile(unsigned x, unsigned y, uint8_t bank, uint8_t *mt, uint8_t *pal)
{
    uint8_t leftpali = mt[8] & 3;
    uint8_t rightpali = (mt[8]>>2) & 3;
    
    for (unsigned xt = 0; xt < 4; xt++)
    {
        for (unsigned yt = 0; yt < 2; yt++)
        {
            writetile(x+(xt*8), y+(yt*8), bank,
                      mt[(yt*4)+xt],
                      pal+((xt<2 ? leftpali : rightpali)*4)
                      );
        }
    }
}



void fput16(uint16_t v, FILE *f)
{
    fputc(v & 0xff, f);
    fputc((v>>8) & 0xff, f);
}

void fput32(uint32_t v, FILE *f)
{
    fputc(v & 0xff, f);
    fputc((v>>8) & 0xff, f);
    fputc((v>>16) & 0xff, f);
    fputc((v>>24) & 0xff, f);
}



int main(int argc, char *argv[])
{
    if (argc != 4)
    {
      puts("usage: a world sector outname");
      return EXIT_FAILURE;
    }
    
    uint8_t level = atoi(argv[1]);
    uint8_t region = atoi(argv[2]);
    if (level > 6) puts("bad world");
    if (region > 0x0f) puts("bad sector");
    
    uint8_t nesheader[0x10];
    FILE *f = fopen("Bill & Ted's Excellent Video Game Adventure (U) [!].nes", "rb");
    if (!f)
    {
        puts(strerror(errno));
        return EXIT_FAILURE;
    }
    fread(nesheader, 1, 0x10, f);
    if (memcmp(nesheader, "NES\x1a", 4) || !nesheader[4] || !nesheader[5])
    {
        fclose(f);
        puts("Bad header");
        return EXIT_FAILURE;
    }
    
    
    for (int i = 0; i < 0x40; i++)
    {
      png_byte r = (palette[i]>>16)&0xff;
      png_byte g = (palette[i]>>8)&0xff;
      png_byte b = (palette[i]>>0)&0xff;
      
      pngpal[i].red = r;
      pngpal[i].green = g;
      pngpal[i].blue = b;
    }
    memset(pngtrns,0xff,0x40);
    pngtrns[0x40] = 0;
    
    
    size_t prgsize = nesheader[4] * 0x4000;
    size_t chrsize = nesheader[5] * 0x2000;
    prg = malloc(prgsize);
    chr = malloc(chrsize);
    fread(prg, 1, prgsize, f);
    fread(chr, 1, chrsize, f);
    fclose(f);
    
    uint8_t *levelbase = getprg(2, getprglittle(2, 0xcf56+level*2));
    uint8_t *regionbase = levelbase + (region*0x10);
    
    uint8_t *screenmapbase = getprg(2, getlittle(regionbase));
    uint8_t persp = regionbase[2] & 0x80;
    const char validscreensets[] = "\x03\x0b\x13\x1b\x23\x2b\x04\x0c\x14\x1c\x24\x2c\x34\x3c";
    uint8_t maxscreens = regionbase[2] & 0x7f;
    uint8_t screens = 0;
    while (screens < maxscreens && strchr(validscreensets, screenmapbase[screens*3])) screens++;
    uint16_t palptr = getlittle(regionbase+0x0e);
    uint8_t *palbase = palptr ? getprg(2,palptr) : NULL;
    
    bmpwidth = screens * 256;
    bmpheight = (0x10*16)+(0x08*16)+(16*8*screens);
    size_t bmpsize = bmpwidth*bmpheight*sizeof(*bmp);
    bmp = malloc(bmpsize);
    memset(bmp, 0x40, bmpsize);
    
    
    /* we always traverse the screens from left to right, but 
     * the top/bottom sides depend on the perspective
     *
     * each metatile is 4x2 (32px*16px)
     */
    unsigned y;
    int ydiff;
    if (persp) /* horizontal */
    {
        y = 0;
        ydiff = 16;
    }
    else /* vertical */
    {
        y = 16*8*screens;
        ydiff = -16;
    }
    unsigned x = 0;
    for (unsigned screen = 0; screen < screens; screen++)
    {
        uint8_t screenbank = screenmapbase[screen*3] & 7;
        uint8_t screenset = (screenmapbase[screen*3] & 0xf8) >> 2;
        uint8_t screenout = screenmapbase[screen*3 + 1];
        uint8_t screenin = screenmapbase[screen*3 + 2];
        
        uint8_t *screensetbase = getprg(screenbank, 0xc000 + screenset);
        
        uint8_t *screenpal = getprg(screenbank, getlittle(screensetbase+0));
        uint8_t chrbank = screensetbase[0x10];
        uint8_t *screenmetatiles = getprg(screenbank, getlittle(screensetbase+0x20));
        uint8_t *screenoutcoldata = getprg(screenbank, getlittle(screensetbase+0x30));
        uint8_t *screenincoldata = getprg(screenbank, getlittle(screensetbase+0x40));
        uint8_t *screenoutcolmaps = getprg(screenbank, getlittle(screensetbase+0x50));
        uint8_t *screenincolmaps = getprg(screenbank, getlittle(screensetbase+0x60));
        
        for (unsigned column = 0; column < 8; column++)
        {
            uint8_t outcolid = screenoutcolmaps[screenout*8 + column];
            uint8_t incolid = screenincolmaps[screenin*8 + column];
            
            /* out */
            for (unsigned row = 0; row < 8; row++)
            {
                uint8_t metatileid = screenoutcoldata[outcolid*8 + row];
                writemetatile(x, y+(row*16), chrbank, screenmetatiles+(metatileid*9), palbase ? palbase : screenpal);
            }
            
            /* in */
            for (unsigned row = 0; row < 0x10; row++)
            {
                uint8_t metatileid = screenincoldata[incolid*0x10 + row];
                writemetatile(x, y+((row+8)*16), chrbank, screenmetatiles+(metatileid*9), palbase ? palbase : screenpal);
            }
            
            
            x += 32;
            y += ydiff;
        }
    }
    
    
    
    
    
    
    f = fopen(argv[3], "wb");;
    
    png_structp png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
    png_infop info_ptr = png_create_info_struct(png_ptr);
    
    if (setjmp(png_jmpbuf(png_ptr)))
    {
       puts("Error in png export");
    }
    else
    {
        png_init_io(png_ptr, f);
        
        png_set_IHDR(png_ptr,info_ptr,bmpwidth,bmpheight,8,PNG_COLOR_TYPE_PALETTE,PNG_INTERLACE_NONE,PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
        
        png_set_compression_level(png_ptr, Z_BEST_COMPRESSION);
        
        png_set_PLTE(png_ptr,info_ptr, pngpal, 0x41);
        png_set_tRNS(png_ptr,info_ptr, pngtrns,0x41, NULL);
        
        png_bytep row_pointers[bmpheight];
        for (int i = 0; i < bmpheight; i++)
        {
            row_pointers[i] = (png_bytep)(bmp+(i*bmpwidth));
        }
        
        png_set_rows(png_ptr, info_ptr, row_pointers);
        
        png_write_png(png_ptr, info_ptr, 0, NULL);
        
    }
    png_destroy_write_struct(&png_ptr, &info_ptr);

    
    fclose(f);
    
    
    free(prg);
    free(chr);
}