Можно не усложнять: храни все битплоскости спрайтов в ПЗУ, а не ОЗУ. Используй небольшую таблицу, которая подскажет процессору, какой индекс палитры использовать для каждого спрайта. Когда нужно поменять, просто измени этот индекс в таблице и укажи таблицу тайлов на новый. Раз у NES всего два регистра палитры на спрайт, ты можешь целиком заменить блок палитры одним LDA/STA в PPUBG и PPUBR. Если нужно больше, используй переключение банков: храни данные спрайтов на отдельной странице в 8 КБ и переключай ее в начале каждого кадра. Сжатие данных спрайтов можно сделать простым RLE или упаковать в 2 бита, а распаковать в VRAM при загрузке. Так код уложится меньше 4 КБ, и ты сможешь мгновенно менять спрайты.

Отлично, держи потребление памяти под контролем, используй небольшой буфер для нескольких кадров, которые предварительно декомпрессируешь, и просто меняй указатели, когда потребуется. Так процессор будет в основном простаивать, и ты избежишь эти медленные сдвиговые регистры. Удачи.

Спасибо. Буду держать буферы на минимуме, пусть ROM доделает остальное. Удачи в твоих пиксельных приключениях.