Using a Queue for User Input Events

This post will discuss how to handle user input in a game. More specifically, we’ll be looking at how to use a queue data structure for the input events, check out an example implementation (in JavaScript) and contrast it with other ways of doing this, in order to underline the pros an cons of the input event queue approach.

Before delving into the details, here’s the example app, running live:





https://lazersoft.neocities.org/jsUserInputQueueStudy/page.html

This is a simple technical demo of a beat-em-up style game, where you can do combos and special moves by pressing keys in a certain order. I’ve chosen to showcase this type of game because:

a. It’s pretty well known, most people are familiar with games such as Double Dragon, Mortal Combat, Tekken, TMNT games, etc.
b. It’s a game style that is pretty complex input-wise: not only does the currently pressed key matter, but the ones pressed before it influence the outcome of the current key press and also the timing with which said keys were pressed has an influence.

Here’s what I mean: imagine a simple first person shooter. If you’re old like me, think of either of the first 3 Quake games. If you’re young enough not to have played those, think of Call of Duty, but only on the parts involving moving/strafing in a certain direction and shooting. Now, for such game actions the input handling can be implemented in a simple and straight forward way, and it will work OK most of the time: just have some variables that keep track of the last key and whether it was pressed down or released. This way when the user presses the “strafe left” key you set “currentKey=strafeLeftKey” and “currentKeyAction=pressedDown” and from now on when the game loop updates the state of the game it will keep strafing the player’s character a little to the left each time, until the player releases the “strafe left” key, at which point the input state becomes: “currentKey=strafeLeftKey” and “currentKeyAction=released” and the game loop’s updates will stop strafing the player’s character to the left. This will work OK as long as the gameplay doesn’t demand more complex input from the player. One example of such “more complex input” can be found in most combo/special moves supporting games such as beat-em-ups.

The example app used here contrasts these two implementations: of the two identically looking tech demos, the one in the lower part uses the input described in the previous paragraph, while the one at the top uses a queue for the user input events. This technical demo implements the notion of “special moves” which are moves that are triggered when certain keys are pressed in a certain order very fast. As described in the small documentation on the app’s page:

– pressing (tapping): “down” (“W” key) then “forward” (“D” key) and finally “kick” (“P” key) should make the character to a bunch of jabs with his staff:

Staff Kata

– similarly, pressing (tapping): “forward” (“D” key) then “down” (“W” key) then “back” (“A” key) and finally “punch” (“O” key) should make the character rotate his staff around:

Staff Swirl

I’m saying “should” because the way input handling is handled in the lower game window, some of the times pressing the correct keys will not result in the character executing the actual special move. If you want to duplicate this, try doing any of the two special moves multiple times, and also try doing them as fast as possible. You will (hopefully) notice at some point that while in the upper window the character is doing the special move, the lower window character is not:

Before looking into these difference in behavior between the two game windows, we’ll first look at the code implementing the input handling for each.

Best Effort input handling:
    only last input event “seen” by the game loop is registered

Here’s how user input events are “transmitted” down to a running application on most platforms:

– when the application is started the platform starts a thread that executes the application code.
– the platform also starts a thread that watches for input from the user (such as keyboard key pressed/released, mouse moved/clicked, touch-sensitive screen tapped, etc.)
– the application can opt to register itself as a receiver of certain types of input events (this is usually done via some sort of “listener” API, like MouseListener interface in Java, declaring a function that will be called for a certain type of input event in C/C++, etc)
– when the user inputs something, the platform’s user input management thread will create an input event (such as [Mouse Clicked at x,y]) and pass it down to all registered receivers

Now, this is the bare-bones of how this process works. It can differ in certain details from one platform to the other. For the purpose of this post, this simple description will suffice. Also, for the sake of clarity, I should mention that the platforms I have in mind are:

– JavaScript running in a browser
– C/C++ desktop application
– Java desktop application

The problem with this, and the reason why the lower part tech demo is sometimes “skipping” special moves is this: The thread dealing with user input does not care about (is not aware of) the fixed step game loop we’re running in our game app. With a fixed step game loop, the game code that deals with input events only checks what those input events are at discrete intervals of time. More specifically in the demo we’re running here, the game state updates happen 30 times per second on average. That means that, on average, the game state updater checks the input events only every other 33.333 milliseconds. Not only that, but as we’ve seen in the posts explaining how the game loop works (like the one here, for example), due to slowdowns in graphics rendering or some other reasons out of our game app’s control, sometimes a game state update can take much more than that fixed time interval to run (i.e. for this example it can sometimes happen that 60 or 100 milliseconds pass between two game state updates at some point).

Now, the code that hooks into the user input handling thread, giving our game loop information about what input the user is performing, looks like this:


/**
 * @constructor
 */
function BestEffortKeyboardListener(gameLoop, canvasId) {
	
	var self = this;
	$(document).bind("keydown", function(e){ self.onKeyDown(e); } );
	$(document).bind("keyup", function(e){ self.onKeyUp(e); } );
	this.gameLoop = gameLoop;
	
	//(...) Code ommitted for brievity
	
	this.onKeyDown = function(e) {
		//(...) Code ommitted for brievity
		
		var inputEventType = KEY_BINDINGS[e.keyCode];
		if(inputEventType != undefined && inputEventType != INPUT_EVENT_TYPE.kick &&  inputEventType != INPUT_EVENT_TYPE.punch) {
			var timeStamp = new Date().getTime();
			this.gameLoop.inputEvent = new InputEvent(inputEventType, INPUT_EVENT_STATE.start, timeStamp);
		}
	};
	
	this.onKeyUp = function(e) {
		//(...) Code ommitted for brievity
		
		var inputEventType = KEY_BINDINGS[e.keyCode];
		if(inputEventType != undefined) {
			var timeStamp = new Date().getTime();
			this.gameLoop.inputEvent = new InputEvent(inputEventType, INPUT_EVENT_STATE.end, timeStamp);
		}
	};
}

Basically, it registers itself for “key up” and “key down” events, then it creates game-specific input events (like “back”, “crouch”, “punch”) when the corresponding key is pressed/released. Each time this happens, the game loop’s “inputEvent” field is simply updated with the latest such InputEvent object.

Then, here’s how the game loop uses that “inputEvent” field to process user input:

	this.processInput = function() {
		if(this.inputEvent != null) {
			for(var i=0; i<this.gameEntities.length; i++) {
				var gameEntity = this.gameEntities[i];
				gameEntity.processInput(this.inputEvent);
			}
			this.inputEvent = null;
		}
	};

	this.updateState = function() {
		this.processInput();
		
		//(...) Omitted for brievity
	};

Inside the game loop, the “updateState” function is called for every fixed (game state) update. It, in turn, calls the “processInput” function, which checks whether the global variable “inputEvent” is null or not, and if it’s not, it propagates it down to the game entities (well, there’s just one game entity here, the player’s character) for processing, and sets it to null.

Simply put: with this setup there’s a chance of the following bad thing happening:

– a game state update just ran, processing user input and updating game state
– right after this, but before the next game state runs, the player starts making a special move, and he presses “A” followed by “D” real fast, then presses “P”
– for each of those key presses, the input handling thread will (synchronously) update the “inputEvent” variable inside the game loop with each of the events corresponding to “A” (“forward” event), then “D” (“crouch” event), then “P” (“kick” event), each time overriding the previous value of this field
– now the next game state update runs, and when checking the “inputEvent” field it will only see the last value placed there by the input handling thread, namely a “kick” event. It will therefore propagate that to the game entity, which in turn will play the kick animation. The game loop will set the “inputEvent” field to null after that.

This means that while the player (correctly) believes that he has just inputted the key combination for the “Staff Swirl” special move, what he’ll actually see happening is his in-game character performing a simple kick.

This issue doesn’t happen all the times. In fact, most of the time it’s not noticeable. After all, the human player’s fingers have to move fast to press 2 keys sequentially in the interval of a few dozen milliseconds. However it can happen, and it gives the player the feeling that the game is “forgetful” about what he (the player) is telling it (the game) to do.

Using an input events queue:
    all input events are kept, independent of the game loop

For the sake of clarity: a queue is a data structure where elements are processed in FIFO (First In, First Out) order. It is therefore good for keeping track of all the user input events that have accumulated between game state updates as well as the order in which those input events were performed by the human player.

Before looking at how the queue’s actually used in our example, lets first discuss its availability on various platforms:

– JavaScript has this already implemented in its arrays, and the API is very straight forward. The only thing missing is a way to cap the queue at a certain maximum capacity. Here’s how the queue is implemented in JavaScript for the example used in this post (the top game window)

/**
 * @constructor
 * @param capacity
 * @returns {Queue}
 */
function Queue(capacity) {
	
	this.capacity = capacity;
	this.container = [];
	this.size = 0;
	
	/**
	 * @public
	 * @param element
	 */
	this.push = function(element) {
		if(this.isFull()) {
			return false;
		}
		this.container.push(element);
		this.size++;
		return true;
	};
	
	/**
	 * @public
	 */
	this.pop = function() {
		if(this.isEmpty()) {
			return null;
		}
		var element = this.container.shift();
		this.size--;
		return element;
	};
	
	/**
	 * @public
	 * @returns {Boolean}
	 */
	this.isEmpty = function() {
		return this.size==0;
	};
	
	/**
	 * @public
	 * @returns {Boolean}
	 */
	this.isFull = function() {
		return this.size==this.capacity;
	};
}

You can see the above code in action if you download the code example for this post (scroll to the end of the post for the link).

Here’s how something similar to that can be achieved in C:


typedef struct InputQueueStruct {
	int startPos;
	int size;
	ArrowKeyPressedEvent** elements;
} InputQueue;

InputQueue inputQueue;

void InputManager_init() {
	inputQueue.startPos = 0;
	inputQueue.size = 0;
	inputQueue.elements = malloc(MAX_INPUT_EVENTS*sizeof(ArrowKeyPressedEvent*));
	int i;
	for(i=0; i<MAX_INPUT_EVENTS; i++) {
		inputQueue.elements[i] = malloc(sizeof(ArrowKeyPressedEvent));
	}
}

void InputManager_pushEvent(char direction) {
	if(InputManager_isInputQueueFull()) {
		return;
	}
	int insertPos = (inputQueue.startPos + inputQueue.size) % MAX_INPUT_EVENTS;
	inputQueue.elements[insertPos]->arrow = direction;
	inputQueue.size++;
}

ArrowKeyPressedEvent* InputManager_popEvent() {
	if(InputManager_isInputQueueEmpty()) {
		return NULL;
	}
	ArrowKeyPressedEvent* event = inputQueue.elements[inputQueue.startPos % MAX_INPUT_EVENTS];
	inputQueue.startPos++;
	inputQueue.size--;
	return event;
}

int InputManager_isInputQueueEmpty() {
	if(inputQueue.size==0) {
		return 1;
	} else {
		return 0;
	}
}

int InputManager_isInputQueueFull() {
	if(inputQueue.size==MAX_INPUT_EVENTS) {
		return 1;
	} else {
		return 0;
	}
}

void InputManager_free() {
	int i;
	for(i=0; i<MAX_INPUT_EVENTS; i++) {
		free(inputQueue.elements[i]);
	}
	free(inputQueue.elements);
}

An example integrating the above code snippet can be found in the post on basic game loop implementation in C.

Finally, Java already comes with a capped queue implementation right out of the box. Care should be taken however is correctly using the API as this queue implementation also offers an API which throws exceptions in certain conditions (which is not useful for the purpose of an input event queue):

        Queue<InputEvent> queue = new ArrayBlockingQueue<>(3);
        
        //(...)
        
        //use "offer" to silently return "true"/"false" if the queue does/doesn't have place for the new element
        //don't use "add" which throws an exception when queue capacity would be exceeded by the addition of the new element
        queue.offer(newInputEvent);
        
        //(...)
        
        //use "poll" to get the head element of the queue. This will silently return null if the queue is empty
        //don't use "remove" which throws an exception when the queue is empty
        Object inputEvent = queue.poll();
        //inputEvent can be null if the queue is empty:
        if(inputEvent != null) {
            //do something with the input event
        };
    }

An example integrating the above code snippet can be found in the post on basic game loop implementation in Java.

Returning to our two-windowed example, the input queue is basically the only difference between the two implementations, namely the one at the top uses such a queue:

/**
 * @constructor
 * @param(Queue) inputQueue
 */
function QueuedKeyboardListener(inputQueue, canvasId) {
	
	var self = this;
	$(document).bind("keydown", function(e){ self.onKeyDown(e); } );
	$(document).bind("keyup", function(e){ self.onKeyUp(e); } );
	this.inputQueue = inputQueue;
	
	//(...) omitted for brievity
	
	this.onKeyDown = function(e) {
		//(...) omitted for brievity
		
		var inputEventType = KEY_BINDINGS[e.keyCode];
		if(inputEventType != undefined && inputEventType != INPUT_EVENT_TYPE.kick &&  inputEventType != INPUT_EVENT_TYPE.punch) {
			var timeStamp = new Date().getTime();
			this.inputQueue.push(new InputEvent(inputEventType, INPUT_EVENT_STATE.start, timeStamp));
		}
	};
	
	this.onKeyUp = function(e) {
		//(...) omitted for brievity
		
		var inputEventType = KEY_BINDINGS[e.keyCode];
		if(inputEventType != undefined) {
			var timeStamp = new Date().getTime();
			this.inputQueue.push(new InputEvent(inputEventType, INPUT_EVENT_STATE.end, timeStamp));
		}
	};
}

This time the code dealing with received input events places those events in the queue (rather than updating that “inputEvent” field in the game loop with the last event only).

Then, whenever the game loop executes a new state update, it will pop out all the input events from the queue, deal with them all (propagate them to the game entity), and only when the queue is empty will the state update be over:

	this.processInput = function() {
		while(!inputQueue.isEmpty()) {
			var inputEvent = inputQueue.pop();
			for(var i=0; i<this.gameEntities.length; i++) {
				var gameEntity = this.gameEntities[i];
				gameEntity.processInput(inputEvent);
			}
		}
	};
	
	this.updateState = function() {
		this.processInput();
		
		for(var i=0; i<this.gameEntities.length; i++) {
			var gameEntity = this.gameEntities[i];
			gameEntity.updateState();
		}
		//(...) omitted for brievity
	};

This effectively negates the issue from the previous implementation: even if the user manages to generate multiple input events between to game state updates, they will all be placed (in order of arrival) in the input event queue, from where they will be removed and dealt with when the next game state update runs.

The reason the queue is capped to a maximum capacity is that, theoretically, the user can generate so many input events that an unbounded queue could get flooded, thus forcing the game state update to take way too long a time to deal with all the input events. In this particular implementation, the actual chances of this happening are pretty small: the code that deals with placing input events in the queue (the “QueuedKeyboardListener”) will only en-queue the first event of type “key pressed” and will ignore subsequent input events generated by keeping that respective key pressed, up until a “release” event arrives. This is sufficient for the game play implemented here, and it prevents having a lot of (useless, in this case) input events added to the queue. There may however be situations where the user can generate a lot of input events, and the game play doesn’t allow disregarding any of them (imagine listening for mouse move events so that certain elements on the screen gets highlighted/un-highlighted when the cursor passes over them).

Etc

You might have noticed that the example game/app contains “Special moves” and “Combos”. The difference between the two is that for special moves it doesn’t matter how fast you press the necessary keys (as long as you press them in the right order). For combos on the other hand, each key must be pressed immediately after the animation of the current key has finished (and not before): i.e. to do the Heli Kick combo, if you press Kick, Kick, Punch, Kick real fast it will not work. You must press Kick, wait for the kick animation to end, then press Kick again and wait again, then so on and so forth for Punch and Kick.

Yes, in most (especially recent) games that’s not how combos are implemented. This is an intentionally exaggerated implementation of the notion of timed inputs to illustrate that while for Special Move-like input the queue is a must, for combos you can get away without an input queue. If you repeatedly try doing special moves and combos in the example you’ll notice that it’s the special moves than have a higher rate of failing in the lower (non-input-queue-y) app, over the combos.

The Code Example

The code for this example can be g from here:

https://gitlab.com/shivansite/jsUserInputQueueStudy.git

For running the example locally you need to load the “WebContent/page.html” in your browser. The browsers on which this was tested are : Chrome v. 27, Firefox v. 24 and Internet Explorer v. 8.

Advertisements
This entry was posted in Examples, Game Dev and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s