Suppose you're using a fixed-time-step and a game frame was just rendered and we're at the begin of a new frame. Then, the keyboard input events that were fired are requested and handled before the game logic takes place. What is the problem with this? The problem is that the inputs that are just handled directly without some kind of pre-processing step approaches the game simulation into an event-based application. We all know that games aren't event based applications even if there are game events in the game that are to be fired. This is particularly important when we're using a fixed time step simulation. In this post I'll show you an way for handling keyboard input on Windows and assuming a fixed-time-step game. In order to not go much futher into the subject I'll first describe a solution for the previous problem and after that I'll implement a buffered keyboard input system that runs on two threads using the Win32 API.

Acknowledgments

Thanks to L. Spiro (Shawn Wilcoxen) for sharing his way of handling inputs at GameDev.net, and for the excelent posts at L. Spiro Engine's website on general game engine architecture. His discussions quite inspired me to write this post.

Introduction

Updating the game simulation each frame by the elapsed frame time since the last frame update (that is, a variable time step), means that the game behaviour varies with time. That's the main reason why currently game programmers tend to update their games each frame by fixed time intervals. It is well know that this is efficiently achieved by a the fixed time step. However, its implementation details are off-topic. I'm assuming that the reader is confortable with fixed-time step games or at least understand how they work... I mean... tick. Thus, a single fixed-time step update is the same as a game logical update. A single game logical update updates the current game time by a fixed time interval which is usually 16.6 ms (60 Hz) or 33.3 ms (30 Hz), and it updates our game by n times each frame depending of the current real frame time. Just to enphatize, the basic game loop of a fixed-time step game is written as below. // Game.h #define FIXED_TIME_STEP ( 33333ULL ) // Game.cpp BOOL CGame::Tick() { // Input handling and processing gets here. m_tRenderTime.Update(); UINT64 ui64CurTime = m_tRenderTime.CurTime() while ( ui64CurTime - m_tLogicTime.CurTime() < FIXED_TIME_STEP ) { m_tLogicTime.UpdateBy( FIXED_TIME_STEP ); m_smGameStateMachine.Tick( this ); } } In the implementation above, m_tRenderTime.Update() updates the render time by the elapsed frame time and m_tLogicTime.UpdateBy( FIXED_TIME_STEP ) updates the game logic time by FIXED_TIME_STEP time units. But using the above way, if we press a button at any time during a game logic update, set this button state as pressed in the beginning of the current frame and suddenly release the button during a game logical update then it will be seen by the game as if it got pressed during the entire frame. This is not a problem in the case the game is updating by small steps because it'll jump to the next frame quickly, but if the current frame time is considerably larger than the time step, then this is quite undesirable for in some computers. In order to avoid this issue we need to time-stamp the button when it gets pressed or released, so its duration can be correctly measured, and more importantly: we can synchronize it with the game simulation. After we have time-stamped input events, the game must consume on each game logical update only the input events that occurred up to the current game logical time in order to keep them synchronized with the game simulation. The following example scenario will hopefully illustrate this idea. Current render time = 1000 ms Fixed time-step = 100 ms; Game logic updates = 1000 ms / 100 ms = 10; Game time = 0 ms; Input Buffer: X-down at 700 ms; X-up at 850 ms; Y-down at 860 ms; Y-up at 900 ms; 1st logical update eats 100 ms of input. There are no inputs up to there to be consumed, then go to the next logical update; ... 7st logical update eats 100 ms of input. Because the game logic time was updated 6 times by 100 ms, then the game time is: 600 ms. But there were no inputs up to there, then, continue with the remaining updates; 8st update. The game time is: 800 ms. Then the time-stamped X-down event must be consumed. The current duration of the X button is the current game time subtracted by the time stamp, that is, 800 ms - 700 ms = 100 ms. Now, the game can check if a button is being held for a certain amount of time, which is an usable information. Momentarily, we know that a mechanism could be fired here because is the first time the user presses the X button (in the example, of course, because there was no X-down before). Another thing we could do on this example would be mapping the X button to a game-engine understandable input key, logging it into the input system, and then remapping it into the game; 9st update. Game time = 900 ms. X-up, and Y-down along with its time-stamps can be consumed. The X button was released, then its total duration since it was pressed is the current game time subtracted by its first tap time-stamp, that is, 900 ms - 700 ms = 300 ms. You may want to log this change somewhere in the game-side. Y was pressed, then we repeat for it the same thing we did to X in the last update; (And finally...) 10st update. The current game time is 1000 ms. We repeat the same thing we did to X in the last update for Y and we're done.

Implementation

The Time Class

At this point you should already know how the computer time works and how to create an appropriate timer class. The timer class stores microseconds as the standard time units in order to avoid numerical drifts. Small intervals can be converted to seconds or miliseconds and stored in doubles or floats but they're not accumulated in our timer class. // CTime.h #ifndef __TIME_H__ #define __TIME_H__ class CTime { public : CTime(); void Update(); void UpdateBy(UINT64 _ui64Ticks); UINT64 CurTime() const { return m_ui64CurTime; } UINT64 CurMicros() const { return m_ui64CurMicros; } UINT64 DeltaMicros() const { return m_ui64DeltaMicros; } REAL DeltaSecs() const { return m_fDeltaSecs; } void SetFrequency(UINT64 _ui64Resolution) { m_ui64Resolution = _ui64Resolution; } void SynchronizeWith(const CTime& _tTime) { m_ui64LastRealTime = _tTime.m_ui64LastRealTime; } protected : UINT64 RealTime() const; UINT64 m_ui64Resolution; UINT64 m_ui64CurTime; UINT64 m_ui64LastTime; UINT64 m_ui64LastRealTime; UINT64 m_ui64CurMicros; UINT64 m_ui64DeltaMicros; REAL m_fDeltaSecs; }; #endif //#ifndef __TIME_H__ // CTime.cpp #include "CTime.h" #include CTime::CTime() : m_ui64Resolution(0ULL), m_ui64CurTime(0ULL), m_ui64LastTime(0ULL), m_ui64LastRealTime(0ULL), m_ui64CurMicros(0ULL), m_ui64DeltaMicros(0ULL), m_fDeltaSecs(0.0f) { ::QueryPerformanceFrequency( reinterpret_cast(&m_ui64Resolution) ); m_ui64LastRealTime = RealTime(); } UINT64 CTime::RealTime() const { UINT64 ui64Ret; ::QueryPerformanceCounter( reinterpret_cast(&ui64Ret) ); return ui64Ret; } void CTime::Update() { UINT64 ui64RealTimeNow = RealTime(); UINT64 ui64DeltaTime = ui64RealTimeNow - m_ui64LastRealTime; m_ui64LastRealTime = ui64RealTimeNow; UpdateBy(ui64DeltaTime); } void CTime::UpdateBy(UINT64 _ui64Ticks) { m_ui64LastTime = m_ui64CurTime; m_ui64CurTime += _ui64Ticks; // 1 s us = 1 * 1000000 s // x s us = x * 1000000 s // Hz = ticks / s // t secs = ticks / Hz // t micros = (ticks / Hz) * (1000000.0 / 1.0) // <=> (ticks * 1000000.0) / (Hz) UINT64 ui64LastMicros = m_ui64CurMicros; m_ui64CurMicros = m_ui64CurTime * 1000000ULL / m_ui64Resolution; m_ui64DeltaMicros = m_ui64CurMicros - ui64LastMicros; m_fDeltaSecs = static_cast( 1.0 / 1000000.0 ) * m_ui64DeltaMicros; } As you can see in the class above, the timer delta seconds (which is usefull for a physics step for instance) is derived after having stored the delta microseconds; the conversion was made with less numerical drift in comparison to sucessor time units.

The Keyboard Buffer

If you're running Windows(R), you probably know that the pre-processed input events are pooled by the O.S. into the Win32 API message queue. It is mandatory to keep the event listening in the same thread that the window was created, but is not mandatory to keep the game simulation running on another. In order to separate the input processing from the game logic, we can let the message queue running on the main thread while the game simulation and rendering is on another. Here, for simplicity, we'll assume the rendering runs on the game-thread, so we won't need any syncronization. I'll write below an window procedure just to remember how looks like processing keyboard events. // Win32Window.cpp LRESULT CALLBACK CWin32Window::WindowProc(HWND _hWnd, UINT _uMsg, WPARAM _wParam, LPARAM _lParam) { switch (_uMsg) { case WM_KEYDOWN : { BufferKeyboardEvent( _wParam, GetCurrentMicroseconds() ); break; } case WM_KEYUP : { BufferKeyboardEvent( _wParam, GetCurrentMicroseconds() ); break; } // The rest of the messages goes here. } } For responsibility purposes, we'll create a thread-safe keyboard buffer class that stores keyboard input events to be consumed later on another thread. Of course we'll must give to the window wrapper class above an instance of that class. // CKeyboardBuffer.h class CKeyboardBuffer { public : enum K_KEYS { KK_BACKSPACE = VK_BACK, KK_TAB = VK_TAB, KK_CLEAR = VK_CLEAR, KK_ENTER = VK_RETURN, KK_SHIFT = VK_SHIFT, KK_CONTROL = VK_CONTROL, KK_ALT = VK_MENU, KK_PAUSE = VK_PAUSE, KK_CAPITAL = VK_CAPITAL, KK_KANA = VK_KANA, KK_HANGUEL = VK_HANGUL, KK_JUNJA = VK_JUNJA, KK_FINAL = VK_FINAL, KK_HANJA = VK_HANJA, KK_KANJI = VK_KANJI, KK_ESCAPE = VK_ESCAPE, KK_CONVERT = VK_CONVERT, KK_NON_CONVERT = VK_NONCONVERT, KK_ACCEPT = VK_ACCEPT, KK_MODE_CHANGE = VK_MODECHANGE, KK_SPACEBAR = VK_SPACE, KK_PAGE_UP = VK_PRIOR, KK_PAGE_DOWN = VK_NEXT, KK_END = VK_END, KK_HOME = VK_HOME, KK_LEFT = VK_LEFT, KK_RIGHT = VK_RIGHT, KK_UP = VK_UP, KK_DOWN = VK_DOWN, KK_SELECT = VK_SELECT, KK_PRINT = VK_PRINT, KK_EXECUTE = VK_EXECUTE, KK_SNAPSHOT = VK_SNAPSHOT, KK_INSERT = VK_INSERT, KK_DELETE = VK_DELETE, KK_HELP = VK_HELP, KK_0 = 0x30, KK_1 = 0x31, KK_2 = 0x32, KK_3 = 0x33, KK_4 = 0x34, KK_5 = 0x35, KK_6 = 0x36, KK_7 = 0x37, KK_8 = 0x38, KK_9 = 0x38, KK_A = 0x41, KK_B = 0x42, KK_C = 0x43, KK_D = 0x44, KK_E = 0x45, KK_F = 0x46, KK_G = 0x47, KK_H = 0x48, KK_I = 0x49, KK_J = 0x4A, KK_K = 0x4B, KK_L = 0x4C, KK_M = 0x4D, KK_N = 0x4E, KK_O = 0x4F, KK_P = 0x50, KK_Q = 0x51, KK_R = 0x52, KK_S = 0x53, KK_T = 0x54, KK_U = 0x55, KK_V = 0x56, KK_W = 0x57, KK_X = 0x58, KK_Y = 0x59, KK_Z = 0x5A, // (...) KB_TOTAL_KEYS }; CKeyboardBuffer(); void OnKeyDown(UINT32 _ui32Key); void OnKeyUp(UINT32 _ui32Key); protected : friend class CIntermediateKeyboardBuffer; struct KB_KEY_EVENT { UINT64 ui64Time; KB_KEY_EVENTS keEvent; }; void UpdateIntermediateKeyboardBuffer(CIntermediateKeyboardBuffer& _ikbBuffer, UINT64 _ui64MaxTimeStamp); CCriticalSection m_csCritic; CTime m_tTime; std::vector m_keKeyEvents[KB_TOTAL_KEYS]; }; // CKeyboardBuffer.cpp CKeyboardBuffer::CKeyboardBuffer() { for (UINT32 I = 0; I < KB_TOTAL_KEYS; ++I { m_keKeyEvents.resize( 4 ); } } void CKeyboardBuffer::OnKeyDown(UINT32 _ui32Key) { CLocker lLocker(m_csCritic); m_tTime.Update(); KB_KEY_EVENT keEvent; keEvent.keEvent = KE_KEYDOWN; keEvent.ui64Time = m_tTime.CurMicros(); m_keKeyEvents[_ui32Key].push_back(keEvent); } void CKeyboardBuffer::OnKeyUp(UINT32 _ui32Key) { CLocker lLocker(m_csCritic); m_tTime.Update(); KB_KEY_EVENT keEvent; keEvent.keEvent = KE_KEYUP; keEvent.ui64Time = m_tTime.CurMicros(); m_keKeyEvents[_ui32Key].push_back(keEvent); } The keyboard buffer class holds an array for each possible keyboard key. This way we assure no inputs will be missed in the main thread. By preallocating key events initially, let's say, 4 elements for each key array, we can avoid a potentially memory allocation slowdown that occurs when keys get pressed. The keyboard buffer now can be used by the CWin32Window class to store time-stamped keyboard events. // CWin32Window.h LRESULT CALLBACK CWin32Window::WindowProc(HWND _hWnd, UINT _uMsg, WPARAM _wParam, LPARAM _lParam) { switch (_uMsg) { case WM_KEYDOWN : { m_kbKeyboardBuffer.OnKeyDown( _wParam ); break; } case WM_KEYUP : { m_kbKeyboardBuffer.OnKeyUp( _wParam ); break; } // (...) };

Time Synchronization

Importantly, in order for in another thread to request input events from the keyboard buffer up to some specific time and assuming this specific time is some time in the keyboard buffer timer itself, the keyboard buffer timer must be synchronized with the another thread's timer so the buffer time-stamps are relative to the same timer and we can read the correct input events. This is the key for all our asynchronous scheme work correctly! Hence, all it needs to be done is writing a simple function in the time class which will internally copy one timer's last real time into another's. // CTime.h // (..) void CTime::SynchronizeWith(const CTime& _tTime) { m_ui64LastRealTime = _tTime.m_ui64LastRealTime; } // (...) The function above only holds true for two timers measuring real time intervals. But since the timer class I've described is really generalized, it doesn't hurt to extend the function for the case when two timers with fixed frequencies must be synchronized. The function above turns into the following lines. // CTime.h // (..) void CTime::SynchronizeWith( const CTime& _tTime ) { m_ui32Resolution = _tTime.ui64Resolution; m_ui64LastRealTime = _tTime.m_ui64LastRealTime; m_ui64CurTime = _tTime.m_ui64CurTime; } // (...) Now we can synchronize the real timers living in different threads. The following code snippet shows how this can be done assumming the CGame:Init() function is called before the game (or the game engine) start. INT32 CGame:Init() { CKeyboardBuffer* pkbKeyboardBuffer = CEngine::GetWindow()->GetKeyboardBuffer(); pkbKeyboardBuffer->m_tTime.SyncronizeWith( m_tRenderTime ); m_tLogicTime.SetFrequency( 1000000ULL ); } Note that the game logic timer's frequency must be one microsecond in seconds, so we get the right amount of microseconds, seconds, or miliseconds. Since the game logic timer gets updated by a fixed time interval, we don't want the interval to be divided by the real frequency; all it needs to be done is set the game logic timer frequency to 1000000 (1 us = 1 / 1000000 s) as already implemented above. Now that we have time-stamped events, we put the main thread to listen for input events on the background and can't interfere the game directly. But after that we still do need to process these events in order to actually use them on the game. INT32 CWin32Window::ReceiveWindowMsgs() { ::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_HIGHEST); MSG mMsg; while ( m_bWindowIsOpen ) { ::WaitMessage(); while (::PeekMessage(&mMsg, m_hWnd, 0U, 0U, PM_REMOVE) ) { ::TranslateMessage(&mMsg); ::DispatchMessage(&mMsg); } } return static_cast(mMsg.wParam); }

The Keyboard Interface

The responsibility of the keyboard buffer is buffer keyboard presses and releases so we can read them in the game-thread. In the game-thread, more specifically before a game tick, we will only consume the input events up to the current game logical time, and we'll generate another set of input events that will be consumed in a linear fashion. This is needed since events that can't be consumed in the current tick need to be kept in the array so it can be consumed later in a next game tick. We'll call the second keyboard buffer as the intermediate keyboard buffer. // CIntermediateKeyboardBuffer.h #include "CKeyboardBuffer.h" class CIntermediateKeyboardBuffer { public : CIntermediateKeyboardBuffer(); void UpdateKeyboard(CKeyboard& _kKeyboard, UINT64 _ui64CurTime) { protected : friend class CKeyboardBuffer; std::vector m_keKeyEvents[CKeyboardBuffer::KB_TOTAL_KEYS]; }; The keyboard buffer update method that updates intermediate buffer is implemented below. Note that the key events that can't be read yet are kept in the keyboard buffer for a next game tick, and those which were read are removed. The rest of the code is commented so basically it doesn't need explanation. // CKeyboardBuffer.cpp void CKeyboardBuffer::UpdateIntermediateKeyboardBuffer(CIntermediateKeyboardBuffer& _ikbOut, UINT64 _ui64MaxTimeStamp) { CLocker lLocker(m_csCritic); // Enter in the critical section. for (UINT32 I = 0; I < KB_TOTAL_KEYS; ++I) { std::vector& vKeyEvents = m_keKeyEvents; for (std::vector::iterator J = vKeyEvents.begin(); J != vKeyEvents.end();) { const KB_KEY_EVENT& keEvent = *J; if (keEvent.ui64Time < _ui64MaxTimeStamp) { // Eat key event. _ikbOut.m_keKeyEvents.push_back( keEvent ); J = vKeyEvents.erase( J ); } else { ++J; } } } } // Leave the critical section. Now we can use the intermediate keyboard buffer to update a keyboard class we we'll create which will contain keyboard key states and their durations in order to be acessed by the game. This keyboard class is responsable for answering questions such: a) "For how long this key was pressed?"; or b) "What is the current duration of this key?". // CKeyboard.h #include "CKeyboardBuffer.h" class CKeyboard { public : CKeyboard(); BOOL KeyIsDown(UINT32 _ui32Key) const { return m_kiCurKeys[_ui32Key].bDown; } UINT64 KeyDuration(UINT32 _ui32Key) const { return m_kiCurKeys[_ui32Key].ui64Duration; } protected : friend class CKeyboardBuffer; struct KB_KEY_INFO { /* The key is down.*/ BOOL bDown; /* The time the key was pressed. This is needed to calculate its duration. */ UINT64 ui64TimePressed; /* This should be logged but is here for simplicity. */ UINT64 ui64Duration; }; KB_KEY_INFO m_kiCurKeys[CKeyboardBuffer::KB_TOTAL_KEYS]; KB_KEY_INFO m_kiLastKeys[CKeyboardBuffer::KB_TOTAL_KEYS]; }; Now the keyboard is able to be used as our final keyboard on the game, and we still do need to transfer the data coming from the intermediate keyboard buffer into it. // CKeyboardBuffer.cpp void CIntermediateKeyboardBuffer::UpdateKeyboard(CKeyboard& _kKeyboard, UINT64 _ui64CurTime) { for (UINT32 I = 0; I < KB_TOTAL_KEYS; ++I) { CKeyboard::KB_KEY_INFO& kiCurKeyInfo = _kKeyboard.m_kiCurKeys; CKeyboard::KB_KEY_INFO& kiLastKeyInfo = _kKeyboard.m_kiLastKeys; std::vector& vKeyEvents = m_keKeyEvents; for (UINT32 J = 0; J < vKeyEvents.size(); ++J) { const KB_KEY_EVENT& keEvent = *J; if ( keEvent.keEvent == KE_KEYDOWN ) { if ( kiLastKeyInfo.bDown ) { // The key is being held. } else { // Compute the time that the key was pressed. kiCurKeyInfo.bDown = true; kiCurKeyInfo.ui64TimePressed = keEvent.ui64Time; } } else { // Compute the total duration of the key event. kiCurKeyInfo.bDown = false; kiCurKeyInfo.ui64Duration = keEvent.ui64Time - kiCurKeyInfo.ui64TimePressed; } kiLastKeyInfo.bDown = kiCurKeyInfo.bDown; kiLastKeyInfo.ui64TimePressed = kiCurKeyInfo.ui64TimePressed; kiLastKeyInfo.ui64Duration = kiCurKeyInfo.ui64Duration; } if ( kiCurKeyInfo.bDown ) { // The key it's being held. Update its duration. kiCurKeyInfo.ui64Duration = _ui64CurTime - kiCurKeyInfo.ui64TimePressed; } // Clear the buffer for the next request. // This method won't erase the vector capacity. vKeyEvents.clear(); } } Now that we have readable inputs, we can use them in the game logical update.

The Final Game Loop

I'm aware how much a game must be agnostic about input management. But We won't get into design detals here, and for simplicity we'll give to the game class an instance of the intermediate keyboard and the keyboard classes. With this the final game-thread loop with can be written. // CGame.h class CGame { // (...) protected : CIntermediateKeyboardBuffer m_ikbKeyboardBuffer; CKeyboard m_kKeyboard; // (...) }; // CGame.cpp BOOL CGame::Tick() { pkbKeyboardBuffer = CEngine::GetWindow()->GetKeyboardBuffer(); m_tRenderTime.Update(); // Update by the real timer. UINT64 ui64CurMicros = m_tRenderTime.CurMicros(); while (ui64CurMicros - m_tLogicTime.CurTime() > FIXED_TIME_STEP) { m_tLogicTime.UpdateBy( FIXED_TIME_STEP ); UINT64 ui64CurGameTime = m_tLogicTime.CurTime(); // Use the window keyboard buffer to update the intermediate keyboard buffer. pkbKeyboardBuffer->UpdateIntermediateKeyboardBuffer( m_ikbKeyboardBuffer, ui64CurGameTime ); // Use the intermediate keyboard buffer to update the final keyboard interface. m_ikbKeyboardBuffer.UpdateKeyboard(m_kKeyboard, ui64CurGameTime); // Now we can use m_kKeyboard now at any time in a game-state. UpdateGameState(); } // (...) }

Conclusion

What we did in this article was creating a small input system that is synchronized with our logical game simulation and it runs asynchronously. After the game has all the input information then it can start mapping and logging it. There are open doors for optimization. But for the moment, what matters is that it is synchronized with the logical game update, and the game is able to interface with it losing minimum input events. Note that this way of managing inputs can add some complexity to your current code base. For small demos or simple applications using the old polling it still can be an advantage in favor of simplicity. That's all. I hope this post helps.

References

http://irlans.wordpress.com/2015/01/16/asynchronous-keyboard-input/ http://www.gamedev.net/blog/355/entry-2250186-designing-a-robust-input-handling-system-for-games/ http://www.gamedev.net/topic/664810-player-input-system/ http://www.gamedev.net/topic/664362-time-stamped-buffered-input-system/ http://www.gamedev.net/topic/576309-design-of-input-system/ http://www.gamedev.net/topic/664831-handling-input-via-windows-messages-feedback-requested/page-2