Here's a video discussing about doing smooth animation, multiple characters, and game play in Prince of Persia in 4 colors and 48k of memory for Apple 2e. Might give some inspiration.