A las buenas, mojons!
Por si os sirve de ayuda, Invasion of the Zombie Monsters utiliza un motor muy similar al que estáis hablando, limitado también a 256 patrones 8x8. Supongo que en vuestro caso tendréis una zona de RAM donde se guardan dichas "tiles" que luego, en base al buffer de 768 bytes de la matriz de pantalla, hace que la pantalla se actualice.
El caso es que yo, además, hago que 9 de esas 256 tiles (las que conforman el gráfico de Ned) sean dinámicas: es decir, los graficos de la pantalla actual, marcadores y enemigos de la pantalla en la que nos encontramos, así como los disparos, explosiones e items, si están dentro de esos 256, pero los frames de Ned no: en cambio, hay 9 tiles reservadas para tal fin, y cada frame de juego lo que hago es "redefinir" dichas 9 tiles dependiendo del estado de Ned antes de lanzar toda la pantalla.
De esta forma me evito reservar tantísimas tiles para el personaje, que realmente se guardan en otro buffer de 256 tiles exclusivas para el personaje, que sirven para actualizar esas 9 tiles del set "general". Bueno, además de eso, en el IOTZM volteo horizontalmente cada frame y en tiempo de ejecución el gráfico de Ned, de esta forma solo tengo que guardar sus gráficos mirando hacia la derecha (los que miran a la izquierda se recalculan a tiempo real cada frame). Que si no no me entraba el juego en los speccy 48KB...
Así es a grandes rasgos, como funciona. Bueno, sin contar los scrolles a varias capas y demás mandangas: además para la redefinición de Ned utilizo un doble buffer para que en MSX no cante la redefinición directamente a la VRAM, etc, etc... pero básicamente lo hago así. Es decir, que merece la pena poder reservar en vuestro motor una zona de "tiles dinámicas", que os puede servir tanto para ahorrar espacio cara a los gfx de un personaje prota, que consume mucho, como para hacer tiles animadas, del tipo "antorchas", "monedas que giran" y demás.
En fin, just my 2 cents, por si estáis ahora mismo con el motor y mi visión os puede ayudar mínimamente.
Go, mojons!