I remember "Another Story". Somewhat poor tileset use and level design, but the story was the main strong point in the series.

Still think this is a great idea