Why are people so much wanting to stick with the stupid and ugly old AVR tiny/mega MCUs? These are pure crap, in terms of year 2017 performance and peripheral equipment. Move at least to the atXmega series. These are at least competitive products. Much more flexible peripherals, DMA, etc...
Yes, you can generate a real time video and sprites on an 8bit PIC. But, hell, tell me why would one want to do it? May be as an extreme assembly language exercise?
You have to decide yourself, if you want just crazy asm exercise, or to make game console.
There is a metric shit ton of better suited MCUs with out-of-the box RGB image support, like for example the STM32F429, and many others. You can make a very decent looking true color graphics at respectable image resolutions, even running a basic pseudo-3D like wolfenstein. You can output on an LCD-TFT directly, or convert the RGB data to anything like VGA, DVI or even HDMI, even PAL.