With a bit of help from me, a friend of mine has almost finished a TAS of King Colossus, but he says he needs to redo the last half of it, because he found a severe bug that can be used to skip a few levels completely. (As far as I understand, the trick involves interfering some forced owerworld traveling to mess the game so that you arrive in a wrong location. This saves about 10 minutes.) Unfortunately, he can't continue doing it for a while and he also lost a lot of motivation due to some 20 000 useless rerecords. So, here's King Colossus played to the beginning of the last level in 62 minutes:
http://dehacked.2y.net/microstorage.php/info/4857/KCWIP.gmv
I think the gameplay is similar to the NES Startropics games. It feels like a game where almost every aspect is average or better than average, but nothing is truely awesome or terrible. The WIP looks interesting at times and is very well done technically, but the game is quite long, so some people might get bored watching it. Lots of luck manipulation is involved to make the enemies behave nicely and it looks like the player has total control over nearly everything.
The full name of the game is "Tougi-Ou: King Colossus" and it's been released only in Japan. Luckily, a very high quality English translation hack exists (but the movie won't work with it, obviously).
