I'm surprised this article has no mention of things like visual novels which are generally considered video games, but pretty much work just like novels.

Also, Trails in the Sky (and the trails series in general) have a pretty solid story.