If there were a way to emulate sending key and mouse events, this would actually be fairly straightforward. You would only have to capture what key was pressed or released (or the mouse event), and the time between events.
But... since there isn't (at least that I'm aware of), there is a lot of information you have to capture to playback recorded events. The amount you need to capture is dependent on how much AI is built into the game. If all the objects (except the player of course) follow a set pattern, or simple rules, you only need to track player states and let everything else behave as normal.
You would want to figure out a keyframe system for playback, setting the player states as necessary.
Naturally, as game complexity increases, so would this method.ckelley2012-09-11 05:34:09