Key combinations on poll-based input

So assume you have an input system that is based on polling

void update()
{
if( Keyboard[ 'A' ] )
// A is down
}


Say you want to be able to recognize 3 to 8 length key combinations (like down, down-forward, forward, A for hado-ken)

How would you best create a generic (easily modifiable/programmable) key combination input system on polled input?

Fundamentally, you can't. Key combinations require an ordering, and an ordering requires events.

What you can do is turn polling into events by comparing the key states each frame and generating post-hoc keyup/keydown events from the differences. It's not as reliable because you lose the timestamping and other intra-frame ordering that "native" event systems provide, but it will allow you to detect and order at least one key per frame.

Once you have those ordered events, you can use a finite state machine or other tool to match them against your move lists and execute the correct one.

• It's a little misleading to say that you can't do this without events. Technically, events are just a way to call a method or list of methods when some condition is met. In that sense, you need events. However, I can apply the word events (improperly) to many programming tasks that fit that description. I've added an answer that solves the problem in the way that I usually do it, which does not use what most programmers tend to think of as "events". – Olhovsky May 5 '11 at 20:57
• Your code does exactly what I said to do without events, but ignores the caveats - which is that you lose intra-frame ordering. When you get events from e.g. the Win32 message loop, you get them in an order with more granularity than a glob per frame. When you compute deltas yourself, you lose that. For a fighting game where players might input several parts of a combo in a single frame, you need to know if those were in or out of order. – user744 May 5 '11 at 22:06
• Fair enough. Provided that we're polling at 60hz, I doubt we want to distinguish between presses that are less than the 16ms apart that 60Hz polling provides (assuming our players are humans). – Olhovsky May 6 '11 at 1:01
• We do. Skilled fighting game players can enter a hadouken/shoryuken stick command in less than three frames, meaning we must distinguish between them. – user744 May 6 '11 at 6:33
• Then you need to poll more often than 60hz. – Olhovsky May 6 '11 at 7:39

One way is to store the current and previous input states, and compare them every time that you poll the input.

For each key that can be pressed, store an object that has a timestamp of the last time that the key switched from a down state to an up state.

Update these objects by doing this at every poll:

void update(){
some_key_has_been_pressed = false;
foreach(key in keys){
if(previous_input[key].Down && current_input[key].Up){
keys[key].up_timestamp = current_time();
}

if(current_input[key].Down){
keys[key].down_timestamp = current_time();
some_key_has_been_pressed = true;
}
}
}


Now you can pattern match your combos against the contents of keys.

Have a combo object for each combo, and call update() on each combo object at each poll.

A combo object's update() method will pattern match the combo, checking if all necessary conditions for the combo are satisfied at this poll. I.e. all keys timestamps for the combo so far are in order, and no other key that would break the combo has been pressed this frame. For each condition met, increment a counter in the combo object to the next condition to check. When all conditions are met in a combo, call the method that the combo should perform. If some_key_has_been_pressed == true but the key that is the next condition for the combo has not been pressed, then reset the combo's satisfied condition counter to 0.

The above is my preferred method, as it is simple to implement, easy to maintain, efficient, and highly modular.

However for another good method, check out the XNA input sequence sample, which is written in C#, and the logic is likely transferrable to the language you're using.

• In the second if-statement, if(current_input[key].down){, wouldn't you also want to check if the key was up in the previous_input state? As written, I think it would continuously update a held key's down_timestamp. – Jeff Jenkins Aug 19 '12 at 2:09
• Continuously updating the down timestamp is the intended behavior. This allows you to compare the up_timestamp and down_timestamp of any key, to check how long it was held for. If you continuously hold a key, you are not changing the up_timestamp, so (down_timestamp - up_timestamp) still gives you the duration it was held for. – Olhovsky Aug 19 '12 at 17:58
• thanks for the clarification. I was thinking the opposite, where up_timestamp - down_timestamp is the duration of a held key. – Jeff Jenkins Aug 19 '12 at 20:39

Make a stack of the last X key events, for each key event add an object with the key and time of the press/release, then check if the last members of the stack match a special pattern and if those keys were pressed fast enough to count as a combination. Finally remove the oldest object from the stack.

• A stack that you can remove the bottom object from is not really a stack ;) – Olhovsky May 5 '11 at 1:46
• An ordered bunch of data entities, a list might be the correct term. – aaaaaaaaaaaa May 5 '11 at 1:49
• deque ;) O(1) enq/deq ftw. – michael.bartnett May 5 '11 at 6:23
• An ordered sequence where objects are put onto one end and removed from the other is most properly called a queue. – user744 May 5 '11 at 9:33
• You can make a ring-buffer (BufferLength >= longest command) and write keys to it (Position = Number MOD BufferLength). No adding/removing will be required at all – Kromster May 5 '11 at 10:33