Hands-on A* : How to implement and optimize

This post discusses a proposed architecture and implementation of the A* algorithm.

For a discussion on the definition of the A* algorithm, please see my earlier post on this:

https://shivansite.wordpress.com/2013/12/06/the-basics-of-astar-pathfinding-part-1

Also, Wikipedia has an excellent article on this:

https://en.wikipedia.org/wiki/A*_search_algorithm

The code and documentation for this project can be found here :

https://lazersoft@gitlab.com/shivansite/jsFastAstar.git

Live demos are available here:

Goals
The functional goals of this implementation are:

• finding the shortest path between 2 points on a grid where movement is allowed in 8 directions (straight and diagonal). What this means is that the implementation will not make any compromises such that a path that is not the shortest possible one will be found, even if this may imply higher performance. In fancy words, this translates to having an A* implementation that has an “admissible” heuristic
• support for 8 directions of movement: in this implementation, the grid is partitioned in equal squares, and movement between 2 squares can be made in straight as well as diagonal directions.
• as an extra feature, not strictly related to A*, a “flood” option has been implemented as well. This allows finding of all the possible paths (towards all reachable destinations) from a given starting point (faster then if using individual A* calls for each of those paths). This functionality is based on the Dijkstra algorithm, which in this implementation is treated as a special case of A* (where the heuristics are ignored)

The technical goals of this implementation are:

• Low memory consumption: since A*’s main advantage over other algorithms consists in trying to explore as few nodes (cells) as possible when searching for a path, so this implementation tries to use as little memory as possible when resolving a path search. While in trivial benchmarks it may result that using more memory gives some performance boost, this may also prove to be false in certain real “live” usages, where performing many path searches in a short period of time may result in large quantities of memory being used, and needing to be cleared, which in turn may degrade performance.
• using optimal data structures for the various data that needs to be stored when running the algorithm. This mainly refers to implementing the Open Nodes data structure using a binary heap which uses a hash table internally in order to support all the functionalities required by the open list in an optimal fashion.
• code readability, in order to allow easy extension of the existing code base. While it’s highly probable that making more highly tuned, but also more cryptic coding would have resulted in some extra performance boost, these kind of code optimizations have been kept to a minimum for multiple reasons: having readable code is always useful, while on the other hand, making code more terse for the sake of probable (and debatable) performance boosts does not guarantee success. As such, all the chosen data structures are well known ones (binary heap, hash table, etc.). Also, the over-all coding has been written (also) with this goal in mind.

Purpose
This implementation was specifically made for the demands of a game I’m developing. It’s a turn based squad game against a computer controlled team. I’ll try to showcase this game in a later article, once I get it to a more stable and finished form.

The reason I’m mentioning this is because I believe that any implementation, even one of a somewhat generic library such as this one, should still have a clear set of goals/use-cases for which it is tailored. What I mean is that, while many more features could have potentially added to this implementation, this risked making the implementation bloated. As such, I’ve chosen the alternate solution, where only the specific path-finding goals demanded by my game are supported by my library and, at the same time, I’ve tried making the code as modular and simple as possible, such that potential future extensions to this library can be easily added at a later time.

For example: the A* algorithm also specifies the possibility of making terrain more or less walk-able (aside from just the simplified floor/wall option). This is however not supported by the A* implementation discussed here. Since in the game I’m developing I have no notion of semi-walk-able locations, I felt that adding this feature to the library will only increase code complexity, increase development time, possibly decrease the library’s performance. I’ve chosen instead to store the terrain as a set of booleans in a simple hash table (true if wall, false if floor). I’ve also isolated and made simple the code that calculates the distances between cells, and the cost to reach them. This way, the code can easily be updated to support this feature.

What my game does demand is that the path are always the shortest possible. This is because combat happens in turns, on a somewhat small map. In such a situation, the human player can easily notice when a less than optimal path has been chosen.

Another path-finding demand was to have the calculation time as small as possible. In the game I’m making, this directly influences how “smart” the A.I. is: in order to use some fancy algorithm to decide what’s the best move for the computer, he must first determine what the next moves are. This means calculating a lot of paths to various locations. The faster the A* implementation is, the faster the game A.I. will “think”.

As such, the implementation goals for this A* library are the ones mentioned above.

Next, we’ll discuss the actual code. We’ll do this by splitting the discussion on some specific areas of the code base.

Obstacle data storage
As mentioned above, obstacles (wall, non-walk-able cells, etc.) are stored as booleans, with true for non-walk-able and false for walk-able. All this is stored in the “SHIVANSITE.AStarMap” class. Disclaimer: since all this is coded in JavaScript, what I mean by class is “customized prototype of a base object”. But since that’s quite the mouthful, I’ll use (some what colloquially) “class” instead to refer to these.

The API for this class is pretty straight forward:

setObstacle: function(x, y)

isObstacle: function(x, y)

clearObstacle: function(x, y)

Internally, this class (as well as others in this project), use a hash table, implemented in the class “SHIVANSITE.AStarNodeHashmap()”. The customization comes from the fact that this hashmtable can only store information associated with a set of 2 numbers, representing the x and y geometric coordinates of a location (on a cell map).

As such, this class’s API accepts “keys” as 2 parameters representing the x and y value, and a 3rd parameter representing the actual value that we want to store for those coordinates. In the case of “SHIVANSITE.AStarMap”, the internal hashmtable stores boolean “true” values for the x and y coordinates that represent obstacles.

Internally, the hash table uses a 2 dimensional array to store and retrieve this information:

SHIVANSITE.AStarNodeHashmap = function() {
this.storage = new Array();
};

SHIVANSITE.AStarNodeHashmap.prototype.add = function(x, y, value) {
if(!this.storage[x]) {
this.storage[x] = new Array();
}
this.storage[x][y] = value;
};

SHIVANSITE.AStarNodeHashmap.prototype.getValue = function(x, y) {
if(!this.storage[x]) {
return null;
}
if(!this.storage[x][y]) {
return null;
}
return this.storage[x][y];
};

SHIVANSITE.AStarNodeHashmap.prototype.remove = function(x, y) {
if(!this.storage[x]) {
return;
}
this.storage[x][y] = undefined;
};

Taking advantage of the fact that, in A*’s context, we’ll always want to place values associated with x/y values, this hash table will never have bucket collisions, and is generally fast, compact, and concise in its implementation.

Distance calculation heuristic

During the execution of the A* algorithm, we can separate the use of the distance calculation in 2 separate situations:

• when estimating the distance between the currently explored location and the destination
• when calculating the distance between a given location (cell), and all of its neighboring cells.

This article will only discuss this aspect in the context given here, where we want to have 8 directions of movement, and also want to have a higher (or at least different) cost of movement for a diagonal movement as opposed to a straight-line movement.

For a more in-depth discussion on various other ways to use and implement distance calculation for A*, check out this excellent article:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps

Getting back to our distance calculation implementation: the most accurate way to calculate distance for an A* grid that allows 8 directions of movement is to use the special case of “Diagonal distance” (also known as Chebyshev distance), namely the Octile distance. Its formula is, as implemented in JavaScript:

getDistance: function(n1, n2) {
var dx = Math.abs(n1.x - n2.x);
var dy = Math.abs(n1.y - n2.y);
return this.d * (dx + dy) + this.d2MinusTwoTimesD * Math.min(dx, dy);
}

Officially, the Octile distance uses values d=1 and d2 = Math.sqrt(2). For simplification of computations, the default values for these have been rounded up to 10 and 14 respectively. However, the implementation for this, which is contained in the class “SHIVANSITE.AStarChebyshevDistanceCalculator”, allows for passing of custom values for d and d2 in its constructor:

SHIVANSITE.AStarChebyshevDistanceCalculator = function(d, d2) {
this.d = d === undefined ? 10 : d;
this.d2 = d === undefined ? 14 : d2;

this.d2MinusTwoTimesD = (this.d2 - 2 * this.d);
//...

A note on having an admissible heuristic. Ideally, the best values to use from a precision point of view are 1 and sqrt(2) respectively for d and d2. However, the admissibility property still holds if instead of sqrt(2) we use 1.4. Then, if we multiply the two parameters d and d2 by 10, we obtain the values d=10, d2 = 14. What this does is that it might make the algorithm explore a few more cells than necessary when searching for certain paths. However, as far as I can tell from my benchmarks, the extra overhead of exploring those extra nodes is payed off by the fact that we only use integer values for the distance (and hence, for all of the g, h, and f scores). Moreover these values are configurable, so one can always use the precise values, if desired.

The other things this class does are: getting the neighboring nodes of a given node (with their “g” score calculated). Also various caching for some values are performed here. When a neighbor of a given node is obtained, that neighbor’s g score is trivial to calculate: just get the g score of the parent node, and add to it either the d or the d2 values, if this neighbor is an orthogonal or diagonal neighbor respectively.

(Node) Closed “list”

For the purpose of pure A*, the Closed Nodes data structure only needs to hold information about whether a set of cell coordinates is in it or not. If it is, the node corresponding to those coordinates is treated as “closed”. As such, for the A* computations done by this library, the Closed Node “list” is simply an instance of the “SHIVANSITE.AStarNodeHashmap” that holds boolean values.

For the path flooding option, a “SHIVANSITE.AStarNodeHashmap” containing actual Node instances is used, but more on this will be detailed further down in the article.

(Node) Open “list”

The Node Open list is the most complex data structure in the A* algorithm. Before discussing its technical implementation, let’s first quickly recap what it needs to do:

• We need to add nodes to the open list
• At any moment, we need to remove from the list the node with the lowest f score
• At any moment, we need to retrieve from the list the Node instance for a given set of x/y coordinates (search Node by position)
• At any moment, we need to be able to update a node that already exists in the Open List. This actually comes down to:
• for a given set of x/y coordinates, for which a node already exists in the Open List, having a “new” node, with a different g (and implicitly, f) score and parent node
• This update will only happen when, for a given set of x/y coordinates, we find a node with a better g (and implicitly, f) score than the one already present in the list

The first two operations give us a hint as to what type of standard data structure might be well suited for this: some kind of min-heap.

One heap that would seem to be able to do all of the 4 needed operations, and most of them with very good time complexity is the Fibonacci Heap. However, this heap is a lot more complicated to implement that other types of heaps. What’s more, anecdotal evidence (basically, various articles I’ve googled about the subject) might seem to suggest that in practice, especially for not-too-large number of elements, the Binary Heap might be faster than Fibonacci.

What’s more, the binary heap is very easy to implement. It’s basically an array, and a few extra lines of code to implement the add and get operations on top of it (we’ll detail this in a moment).

The problem with binary heap is that it doesn’t support (at least, not with good time complexity / performance), the other 2 operations needed by the Open list: search by position, and update. However, the performance for these can easily be improved by using a hash table containing the Node instances that are placed in the binary heap. And since we already have such a kind of hash table, this become the best choice for this situation, taking into account: decent performance and simplicity of implementation.

Let’s now look at how the binary heap was actually implemented for this project. Its code can be found in the “SHIVANSITE.AStarNodeHeap” class.

Let’s first look at the parts of the code that contain only “true” binary heap behavior:

var index = this.internalArray.length;
this.internalArray[index] = n;
//...
this.sortUp(index);
}

And, the “sortUp” (sometimes called “bubble up”) binary heap behavior:

sortUp: function(index) {
var currentIndex = index;
var parentIndex = ~~((currentIndex - 1) / 2);

while(true) {
var currentNode = this.internalArray[currentIndex];
var parentNode = this.internalArray[parentIndex];
if(parentNode !== undefined && (parentNode.f > currentNode.f || (parentNode.f == currentNode.f && parentNode.g < currentNode.g))) {
this.swap(parentIndex, currentIndex);
currentIndex = parentIndex;
parentIndex = ~~((currentIndex - 1) / 2);
} else {
break;
}
}
}

What the above code does is standard binary heap add functionality: when a new element needs to be added, we append it to the end of the binary heap’s backing array. Then we keep comparing it with its current parent node, and if the heap property is not met (if the parent does NOT have a lower f score than the newly added node), we swap the 2 nodes (we place each in the other’s position in the array). We keep doing this until the currently added node satisfies the heap property.

Analogously, a function for “sortDown” exists in this class. That function is used by the “remove” function of the heap.

Now, in order to satisfy the other demands of the Open List A* structure, a hash table is used as follows:

The “Node” instances have a field called “openListHeapIndex”. This represents the index where they are positioned in the heap’s backing array.

Then, inside the “Heap” class, we have an hash table that uses the coordinates of the node as key, and the node itself as value.

This way, when a node is demanded via its coordinates, we just get it and return it from this internal hash table.

Similarly, when a node update is requested, we first retrieve the (existing) node object from the internal hash map, get its index in the heap’s internal array, and then update it’s g and f scores with the values of the node that came in as an update.

Then, all we have to do is to use the heap’s “sortUp” functionality, to make sure than the node is in the right place in the heap. This is the same “sortUp” functionality that the heap uses when adding a new element. The only difference when doing an update of an existing one, is that instead of sorting up from the last element in the array, you start doing this from the index of the updated element:

update: function(n) {
var oldNode = this.hashmap.getValue(n.x, n.y);
var oldNodeIdx = oldNode.openListHeapIndex;

oldNode.g = n.g;
oldNode.f = n.g + n.h;
oldNode.parent = n.parent;

//at this point, due to how AStar works, we know that the new node, n, has a lower F score than the old node its replacing because:
//it has the same coordinates, so same h, and it has a lower g (otherwise we wouldn't update it).
//so this node can at most be somewhere higher in the heap than its previous version
this.sortUp(oldNodeIdx);
}

Path flooding

Path flooding works like this:

//chose a starting point:
var startX = 10;
var startY = 12;

//calculate all possible paths from that starting point:
var floodResult = aStar.flood(startX, startY, aStarMap, distanceCalculator);

//obtain path to various destinations, from the selected starting point:
var endX1 = 30;
var endY1 = 34;
var path1 = floodResult.getPath(endX1, endY1);

//obtain another path to various destinations, from the selected starting point:
var endX2 = 20;
var endY2 = 23;
var path2 = floodResult.getPath(endX2, endY2);

The “AStar.flood(…)” function does all the heavy lifting. Calling this function might take from a few hundred milliseconds to a few seconds, depending on the size of the map, and how fast your machine is.

Afterwards, obtaining any path from a fixed start point to any reachable point on your map is done instantly, by using the FloodResult object.

Internally, this is achieved by using a full-fledged Closed Nodes List: Instead of storing just true/false for a node’s coordinates in order to remember if that node is closed or not, we are now storing the actual node, as it was discovered when the algorithm was ran.

This means, that each node in the closed list will have a reference to some other node, called “parent”, and that one will also have a parent, and so on and so forth, until we get to the starting node (which has no parent). Nodes in closed list also store the cost of getting to them from the starting node (it’s they “g” score).

So, we start by implementing the Closed Nodes “List” as hash table that stores data based on x/y coordinates, but this time the data is actual A* node objects, and not just true/false.

We then do an A* run, with a few tweaks: we don’t have any destination. Each time a new node is processed, we only check if the Open nodes list still has nodes in it, as a condition on whether to keep going or not.

Also, no heuristic is needed (sine there’s no actual destination), effectively transforming this in Dijkstra’s algorithm.

When all nodes are explored and stored in the hash table, this hasth table is wrapped in a FloodResult object, for easy obtaining of a given path (to a given destination):

var openList = this.newOpenList(aStarMap);
var closedList = this.newClosedList(aStarMap);

var startNode = new SHIVANSITE.AStarNode(startX, startY, 0, 0);

var currentNode = null;

while(!openList.isEmpty()) {
currentNode = openList.removeLowestFNode();
if(currentNode.g <= maxDistance) {
this.processSucessors(currentNode, openList, closedList, null, aStarMap);
}
}

return new SHIVANSITE.AStarFloodResult(startX, startY, closedList);

The advantage with this is that the path are calculated faster then by using individual A* to obtain each possible path from a fixed start location to all possible destinations.

One practical way to use this is the following: of you have a somewhat small map (maybe 50×50, or so), and you have some obstacles on it which are static (they will never change, like indestructible walls, ravines, etc), you can easily calculate all paths, from all locations on the map, to all possible destinations. That way, if you want to make some real time path operations on the map, like move stuff between obstacles, you can get these static, pre-calculated paths, first with practically 0 compute time. Then, depending on your setup, you might want to check that the path doesn’t go through some dynamic obstacle (like a new unit that just moved in the way), and only in this situation do an actual, real-time, A* run.

The basics of the Minimax algorithm

Well, looks like I won’t have time anytime soon to finish this post, so I’m just gonna publish the draft already, as the example apps are all in beta. Enjoy playing Reversi and Tic Tac Toe!

Reversi example app

Coming soon…

Using A* with Dynamic Obstacles

We’ll look at how to effectively use A* to make an implementation where multiple moving units have to reach a destination while dynamic obstacles appear/disappear in/from their way (and having the moving units themselves represent obstacles as well).

A simplified Real-Time Strategy Game tech-demo

The discussion will revolve around a JavaScript example app:

Before getting into actual implementation details, a few words about how the example works. This is all pretty straight forward: you have a top-down view of a game area where there’s some soldiers on one side of it and some skeleton warriors on the other. Clicking the “Move” button in the upper right will make everyone start moving towards the other side of the screen. More precisely, each unit starts moving towards a destination which is on the same height (y value) as the unit itself, but horizontally (x value) it is on the other side of the game area (from where the unit is now):

Simply clicking the “Move” button without doing anything else beforehand will make all units traverse the “map” in horizontal lines until they all switch sides. Obstacles can be added by dragging with the mouse while holding the left mouse button. This will generate grey rocks which the units need to avoid. Dragging with the mouse while holding the right mouse button will erase already placed obstacles to make the area passable again. This can be done at any time, be it when the units are standing still, or while they are moving.

Implementation

This is most of all a didactic example. It’s main goal is to have straight-forward, simple code that shows how to manage multiple units’ path-finding. It certainly isn’t the most optimized way to do this, meaning that it might work decently for small areas, a handful of units, but will not scale too well (nor it will try to compensate too well for its shortcomings) when dealing with something like a map 50 times as big as this, having up to (let’s say) 400 units all moving around. Here are some of the main points of this implementation.

Each unit’s logic for dealing with its path in represented in a Finite State Machine. The code for it is contained in the file: “js/game/MovingUnitFiniteStateMachine.js” (check out the end of this post for how to get the sources of the example). Here’s a state of the art diagram of it, representing the states and conditions for flowing between them:

When one or more unit needs to move (like, when the “Move” button is clicked), it will calculate a full best path to the respective destination for each of those units, one at a time. Effectively, at the code level, this means that once a “Move-button-clicked” event is popped from the input queue by a game state update iteration, that iteration will be used to calculate best paths for everyone for the state the map (and its obstacles) are at that moment. Here’s a code snippet from the Finite State Machine that does this:

function MovingUnitCalculatePathState(unit) {

\$.extend(this,new MovingUnitBaseState(unit));

this.aStar = new AStar();

this.init = function() {
this.setStandAnimation();
};

var path = this.aStar.getPath(this.unit.currentX / this.unit.cellSize, this.unit.currentY / this.unit.cellSize,
this.unit.destinationCellX, this.unit.destinationCellY,
this.unit.area, DISTANCE_CALCULATOR, 3);
this.unit.totalPathCalculatingDurationMs += path.computeTimeMs;
};
}

This works, and it’s simple enough, but it’s not really the best way to do things. Here’s where it’s at its worst: if the destination is unreachable for many (or all) of the units, A* will do a lot of heavy calculation (it will inspect every node reachable for each of the units, as discussed in the article on the bases of A*). When it’s also made so as to do this for all units in only one game state update, the chances that that game state update will take way longer than it’s desired are very high. By “way longer that it’s desired” we mean that to the human player this will look like the running game just had a “hiccup” of a few seconds in which nothing was happening or responsive. This depends strongly also on platform and machine performance: the effect may be less visible on a browser with a fast JavaScript engine and/or on a machine with a powerful CPU. However, this doesn’t deny the fact that, strictly from an optimization point of view, the implementation is not the best one. This can be easily tested by making a “vertical” wall of obstacles from the very top to the very bottom of the map, and then hitting the “Move” button. Especially on IE, watch as the units stare blankly at you for 1-3 seconds before they actually start moving:

Duhhh…

And this may also happen, on a smaller scale, if the destination is theoretically reachable, but there’s just a small gap through which all units need to go (but can’t at the same time). This is also because, the way the implementation is made, if, while walking on a pre-calculated path (which was valid at the time when it was obtained) a unit hits an obstacle mid-way through, it will do a new A* path calculation from its current position to the destination, in order to obtain a new shortest path to it. The Finite State Machine code that does this looks like this (file: “js/game/MovingUnitFiniteStateMachine.js”, object: MovingUnitEvaluatePathAdvancementState):

if(this.isAtDestination()) {
//DEBUG_CONSOLE.toConsole("This guy spent on path (re)calculation: "+this.unit.totalPathCalculatingDurationMs+" ms.");
this.unit.manager.onGameEntityReachedDestionation(this.unit);
return this.getStandState();
} else if(this.isAtLastPathNode()) {
if(!this.hasWaitedForBetterPath) {
this.hasWaitedForBetterPath = true;
return this.getWaitForBetterPathState();
} else {
this.hasWaitedForBetterPath = false;
this.recalculatePathCount++;
//TODO quit after 3 path recalculations for the same starting position
return this.getCalculatePathState();
}
} else if(this.isNextNodeAtLeastSomewhatPassable()) {
var currentNode = this.path.nodes[this.currentNodeIdx];
this.currentNodeIdx++;
var destinationNode = this.path.nodes[this.currentNodeIdx];
return this.getMoveBetweenPathNodesState(currentNode, destinationNode);
} else if(!this.isNextNodeAtLeastSomewhatPassable()) {
if(!this.hasWaitedForBetterPath) {
this.hasWaitedForBetterPath = true;
return this.getWaitForBetterPathState();
} else {
this.hasWaitedForBetterPath = false;
//TODO max recalculations;
return this.getCalculatePathState();
}
}
};

More to the point, what this code does is: if an obstacle has been hit whilst being mid-way through a previously valid path, first wait a bit to see if it will clear, and if after waiting it’s still blocked, do a new A* path recalculation from the current location to the destination.

This can be improved by keeping the original (but now blocked) path, and just recalculating a new path for the portion that now contains the obstacle, in order to go around it. Let’s say an initial path has 10 cells. When the unit reaches cell 3, it discovers that cell 4 is now blocked. Instead of calculating a new path from cell 3 all the way to the original destination, it will only calculate one from 3 to 5 (or the next non-blocked cell in the original path). This simplifies the calculations, as there’s a strong chance that the new go-around sub-path is shorter than the one from current cell to destination. The problem with this is that, if we take into consideration the unit’s whole path from original start position, going around the dynamic obstacle it just encountered, and reaching the original destination, this new way of doing things will not always result in an overall shortest path.

Then there’s the notion of how each unit keeps track of the other units, in term of the dynamic obstacles they represent and how it deals with avoiding them. The way this is implemented in the example is: When standing around, a unit occupies once cell, aka, the cell it stands on is deemed as impassable obstacles for the other units. When the unit moves, it marks the current path cell and the next path cell (the one from where it’s currently moving and the one towards where it is moving) and marks them as impassable obstacles for the other units. This can be seen in action if the “Move” button is pressed and then the “Debug” check-box is ticked:

In debug mode, the units are represented as blue and red arrows, and the squares marked as obstacles are rendered in grey. It’s noticeable that each moving unit has a grey cell behind her, and one in front. This is a simple way to make sure that once a unit chose to move to a certain adjacent cell, no other unit can move by there.

The thing that might be considered suboptimal with this approach is the fact that none of the units take into consideration where the other units want to go, i.e. they don’t also take into consideration the other units’ remaining path. This can be bad in situations where there are multiple choke points, and all units will first rush to the closest one and will only go for the other choke points when this one is actually (currently) blocked by some other unit(s). Of course, not all in-game scenarios would allow for a given unit to know the current paths of all other units, for example, in a real-time strategy game, one of player A’s units might be aware of the other units from player A, but shouldn’t know the paths taken by the enemy’s units (player B). Still, there’s still benefits in a unit being aware of at least its allied units’ paths when calculating its own path.

One way to achieve this with A* is to have a unit mark the cells of its current path as “somewhat passable, but not as passable as clear terrain”. This will make other units avoid those cells in favor of cells which are in no one’s potential way. This can become problematic in terms of memory consumption: it’s no longer enough to simply have one copy of the area (with its obstacles) for all units to use, you’ll need to duplicate at least parts of it multiple times: for example, player A’s units will not see the area where player B’s units’ paths are marked as somewhat passable, etc. Still, for small enough areas, this might be a good trade-off, in order to gain some performance from doing less path recalculations (due to one unit stumbling over some other unit while both are moving).

The Code Example

The code for the example app used in this post get be obtained from here:

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

The actual code is located in the “WebContent/js” folder, and is separated into the following sections (subfolders):

– “astar”: this simply contains the A* algorithm implementation.
– “game”: this contains the game-related business logic: code for units behavior, area representation, animations, etc.
– “gameLoop”: here we have the code strictly related to the game loop implementation (including input handling, graphics resources loading, etc.)

The Basics of A* pathfinding – part 2

This post will discuss some finer A* points like how to get the path to the closest location to an unreachable destination and how to mark terrain as more or less preferable for walking (road vs. swamp).

Gracefully dealing with unreachable destinations

Part 1 of these series describes how the A* algorithms works. The example given there details its workings for a scenario where a path actually exists from the start to the end node (i.e. the destination node is reachable).

However, for a situation where the destination cannot be reached from our current start node, A* all by itself has 2 major issues:

– issue 1: it will investigate ALL reachable nodes (flood) before realizing that the destination node is unreachable
– issue 2: after doing all that, it won’t even come up with a path to the node closest to that unreachable destination. It will instead stop on some random node, which may or may not be closest to the destination node.

Now, in short, there’s no way to completely get rid of issue 1. There’s just some common sense things you can do to alleviate it to some extent. Issue 2 on the other hand has a great fix (which is already implemented in the examples, like the A* JavaScript Demo App ). Let’s discuss each of these.

To understand why A* investigates all reachable nodes when the destination is unreachable, we’ll need to take a look at how A* came to be and where its roots are. Here’s a brief, abridged and unofficial history of it: At some point, there was only Dijkstra’s algorithm. Not to get in to all the fine details: this algorithm’s main purpose was to find the shortest path from a given node TO ALL OTHER NODES (not to just ONE certain destination node). It could be used to just find the shortest path between 2 points (by simply starting it on the start node, and then stopping it when the desired destination node was reached) but that was not its main point. Due to its way of doing things, this algorithm is widely used in computer networks to find all the existing shortest paths between multiple, randomly “placed” network nodes. Basically a lot of network rooters have this algorithm or some variation on it implemented and are using it to find out how to reach this or that router/network segment, etc.

Now, the biggest difference between Dijkstra and A* (what A* brought as a major new optimization) is the heuristics: the “guesstimation” A* uses to only explore the most promising nodes (and not everything in any direction from the start node). Simply put, aside from calculating how much it costs to get from the start node to the currently investigated node (which Dijkstra and A* calculate roughly in the same way, it’s what’s called the g score in A*) A* also calculates the distance between the currently investigated node and the destination if no obstacles were between them (the shortest distance) and picks the next node to investigate based (also) on which node has the shortest such distance.

This is not really a shortcoming of Dijkstra. It’s just a particular optimization for a certain context, namely the one where we only care about the path between 2 certain nodes, and not one node and many other nodes thrown randomly around it. Dijkstra still works great in the 2nd case: there’s no need (sense) for heuristics when you don’t know where your destination is (aka, you’ll know it when you find it). Also Dijkstra calculates ALL paths to ALL possible nodes in ONE go. For situations where the “terrain” doesn’t change a lot, and there’s many destinations, Dijkstra is great. Usually in video games, this is not so much the case, as more often than not obstacles will change all the time (think real time strategy games, where a bridge can be choked and un-choked by moving units all the time) and, for a given cell/node/location we’re only interested in the shortest path to one certain node (not multiple nodes). It’s this context that A* is optimized for.

Basically, if we “turn off” A*’s heuristics, it will behave roughly like Dijkstra. Here’s how the A* Demo App would behave if we’d modify the A* code such that it always assigns 0 for the h score (the heuristics):

As a reminder: the black cells represent non-walkable obstacles. The white cells are walkable. The “S” and the “E” marked cells represent the start and the end nodes, respectively. The red cells represent the path and finally, the cells marked with a dot “.” represent the other cells investigated during the path calculation (but which were found to not make the shortest path). The “radius pattern” is pretty obvious: roughly all nodes in a radius equal to the straight distance between the start and the finish cells have been investigated in order to find the path. You can see in the console that it says that 285 nodes were explored.

Now, when using heuristics, “true” A* will explore a lot less nodes to obtain the same path:

This time around, only 54 nodes were explored in order to get the same path. And you can see that while it may sometimes stray a bit, most of the time A* heuristics guide the nodes exploration in the good direction, towards the destination node.

So here’s how things go bad when you tell A* to find the distance to an unreachable node: what this basically does is turn A* into Dijkstra (the heuristics are useless). Yes, at first its heuristics will guide it towards the destination node, but since it’s unreachable, at some point A* will hit obstacles, and desperately check every other reachable node:

In the above picture we have a “wall” of black cells, completely separating the upper part of our area from the rest. If we place our start node in the lower part of this wall, and our destination (end) node in the part above the wall, we can see that this makes A* check every single reachable cell before declaring the destination unreachable.

There’s no actual way to avoid this with pure A*. We can however, do common sense things to minimize the number of situations where A* will be forced to calculate a path to an unreachable destination, like marking certain isolated areas of our in-game maps as “un-selectable for path destination”, aka, if the player wants to send his units there no A* calculation is triggered, instead, they just won’t move. Of course, there’s also dynamic unreachable areas, created by units chocking a single bridge to a certain area etc, for this situation the previous solution won’t help. In this case, a possible improvement may be to set a maximum number of explored nodes that A* can have before stopping a certain path calculation. However this may lead to having the game unit stop before reaching its destination and/or not taking the shortest path to it. Another thing that may help is to implement A* such that for a given path calculation, it will only do a maximum number of iterations per game state update. This helps, especially in situations where the player selects a large group of units and sends them all to an unreachable destination: if we were to do the whole A* for each of them in one game state update they player would experience a visible “hiccup” in the game play, where nothing gets updated for a long while (few seconds) and then everything catches up all of a sudden. By spreading the A* iterations over multiple game state updates the over all game will be smoother (though, those specific units may seem like they’re not responsive enough to player input, if it takes too many game state updates to finish the A* calculations).

Now, in the previous picture, the one showing the path to the unreachable destination, we can see that in fact the path does end on a reachable node closest to our destination. That’s because the demo app uses an implementation of A* which has already been modified to do this.

On it’s own, pure A* will simply stop on some random (reachable) node when trying to get to an unreachable destination. That node may be the closest to the destination or it may not. The way A*’s heuristics operate, there’s a better chance of it NOT being the closest one.

Fixing this is pretty easy: when we say “closest node to the destination node” we’re actually meaning, “the node which has the shortest distance between it and the destination node”, and this simply means the “h” score. So all we have to do is to keep track, during A*’s path calculating iterations, of the node with the lowest “h” score. And them if the A* loop finishes without finding the destination node (gets to have an empty open list), then we simply get that lowest h node, and construct a path by backtracking from its parent and its parent’s parent and so on up until the start node.

All of the implementations (JavaScript, Java, C) given as example contain code similar to this in their “processSucessors” method/function:

neighbor.h = this.distanceCalculator.getDistance(neighbor, finish);

neighbor.setParent(currentNode);

if(this.closestNode == null || this.closestNode.h > neighbor.h) {
this.closestNode = neighbor;
}

and again, the main A* loop of each contains something like this:

if(arrivedAtDestination) {
endNode = currentNode;
} else if(this.closestNode != null) {
endNode = this.closestNode;
}
//(...)

Marking terrain as more/less preferable for walking

Lets start with an example. Imagine you have a shallow river that is crossed by a bridge at some point:

For the sake of argument, we’ll assume that the river is walkable, but that walking through the river is a lot slower (less desirable) than walking on the bridge. This means that if we’d like to cross the river, there’s a balance between taking a detour to use the bridge and simply crossing the river:

This can be controlled within A* by assigning different g-score values to different nodes. Namely, if we want a path calculation to lean towards certain nodes and avoid others, after calculating the actual g score for each of those nodes, we’ll artificially increase the g score of those nodes we want the path to avoid, by an amount proportional with how much we want them to be avoided. Note that doing this will never make the node completely “un-walkable”: if a node with a huge g score (but which is not specifically marked as un-walkable) is the only way to get to the destination, a path through it will be returned by A*.

Let’s use the JavaScript Demo App to try to approximate the terrain described in the images above, and see how A* behaves:

The grey cells represent the river and surrounding rocks which are deemed as “walkable, but not as preferable as flat ground and bridge terrain”. The white cells represent the bridge and the flat terrain, which is the most preferable for passing through, and the black cells represent the various un-walkable things like houses and trees and such.

We can see that if we place our start close enough to the bridge, and our destination on the other side of the bridge, A* will calculate a path going over the bridge:

However, if our start cell is sufficiently far from the bridge, A* will consider walking through the river as less costly rather than doing the detour to pass via the bridge:

Now, the A* implementation exemplified here deals with this in the simplest way possible: the API allows for a cell to be marked as “somewhat passable”. There’s also a “multiplicator” value that can be passed on when a path calculation is demanded. This way, after the regular g score for a “somewhat passable” cell is calculated, the fixed value of “one unit of walk multiplied by the multiplicator” will be added to it, making it less desirable for path-finding when the multiplicator is greater than 0:

//(...)

var newG = currentNode.g + this.distanceCalculator.getDistance(currentNode, neighbor);

if(area.getTerrainType(neighbor.x, neighbor.y) == TerrainType.SOMEWHAT_PASSABLE) {
}

//(...)

neighbor.g = newG;

Now, what this does is only allow to have one kind of “less preferable terrain”. For example if you’d like to have shallow river and swamp, with shallow river being less preferable than regular terrain but more preferable than swamp, the example A* implementation given here would have to be modified, such that when the terrain is created (the Area object) we can specify individual values to add to the g score for each cell.

As a final note on this: adding different degrees of “walkability” to terrain makes for more nodes to be explored when a path is calculated. For example: if the only way to get to a destination is through some nodes with really low desirability, A* will explore a lot of surrounding nodes with more desirable terrain (but which lead in the wrong direction from the destination node) before choosing to go through the low-desirability ones.

Posted in Examples, Game Dev | | 1 Comment

The Basics of A* Pathfinding – part 1

The A* algorithm allows you to find the shortest path between two points with (impassable) obstacles between them. The key word here is “shortest”. Let’s take a look at what that means:

How A* “sees” it

Imagine we have the following:

(Images created using Daniel Cook’s awesome tile sets as well as Wulax’s sweet character sheets)

More precisely, the character on the left needs to get to the chests on the right:

For the sake of argument, the trees and stone cliffs are impassable obstacles (the character cannot walk through them). Now, there are multiple paths the character can take in order to get to the chests:

A* gives the shortest of these paths (the one marked with blue in the above picture). It does so by first separating the area in discrete chunks, like little square cells, which are then interpreted as “passable” or “impassable”. We’ll see later on that we can also declare cells as more or less preferable for passage (like swamp vs. road), but we won’t get into that right now. So, the above image might “look” to the A* algorithm as something like this:

where black marks the areas through which the character cannot walk (impassable obstacles) while the white parts mark the areas the character can walk through (passable terrain).

As we said, A* separates everything into discrete cells (usually square), where some cells are passable terrain, other are impassable obstacles. Then, after doing its thing, A* will tell which of the cells containing passable terrain make up the shortest path between two points. Before detailing on all this, here’s a JavaScript live demo of this:

The A* demo app can be tried here.

Here’s a quick tutorial on how it works:

Select “impassable obstacle” from the left menu, then, with that selected, drag around the area with your mouse (holding down the left mouse button). This will mark cells as obstacles (impassable) and they’ll become black. You can also select “(completely) passable terrain” from the left menu and reset some black cells back to white (aka, terrain through which we can walk) by dragging with the left mouse button over them.

Once you’re satisfied with the placement of obstacles, select “path start” from the left and click somewhere on the area to place the start of the path. A red square with an “S” on it will be created at the clicked location (cell). Similarly, select “path end” and click where you want the path to end. Now that both a start cell and an end cell have been placed, you should see the shortest path between them marked with red. At this point, selecting either “path start” or “path end” and placing either of them somewhere else will show the new path. You can even drag around with your mouse while having either “path start” or “path end” selected to see how the path changes in real time, though this might now run too smoothly on some machines (mostly due to the fact that the code used here for drawing is not very optimized). You’ll also notice than when a path is shown in red, there’s also some cells with a dot (“.”) in them. Those are the cells that were considered (explored) during the calculation of the path, but were found to not belong to the shortest path.

A*’s constituents

It’s vital to note at this point, that what we’re presenting here is only a subset of the whole A* algorithm, more precisely, we’re only describing A* in a specific context (finding the shortest path between obstacles for a video game). One of the important characteristics of this context is the fact that we’re assuming that the nodes are rectangular cells of a certain size placed inside a grid. This simplifications allows us to use certain optimizations which normally wouldn’t be globally available to A*: for example, we can estimate the distance between two cells when we don’t know what obstacles are between them using the Pythagorean theorem, and we can be sure that this estimation will never be bigger than the length of the actual path (obstacles and all) that exists between those 2 cells. (the Pythagorean theorem gives us the shortest possible distance between 2 points when we know their xy coordinates) and because of this nice feature, once we process a cell, we can set it aside and be sure that we don’t need to re-evaluate it again.

Now, said cells allows for 8 directions of movement. From one cell, we can, at most (if there are no obstacles) go: up, down, left, right and on any of the four diagonals in between. We assign a distance (cost) for walking straight (not diagonally) from one cell to an orthogonally adjacent one, in this particular example that distance is 3. Using the Pythagorean theorem we can calculate the distance/cost of getting to any of the diagonally adjacent cells: it’s 3 multiplied by the square root of 2 ( 3*sqrt(2) ) which is about 4.24.

This same formula is used to calculate the distance between any two cells: if the coordinates of the first cell are x1, y1 and those of the 2nd cell are x2, y2, then the distance between those two cells (if the straight distance between to orthogonally neighboring cells is 3) will be:

distanceBetweenCells = sqrt( ( 3*(x1-x2) )^2 + ( 3*(y1-y2) )^2 )

So, one of the notions of A* is the distance between cells. The calculations shown above, using the Pythagorean theorem are but one way to calculate said distance. Other formulas can be used as well, as we’ll see later on.

Now, the next notions will all be described at the same time, because they are pretty tied up to each-others.

For a given cell, A* will analyze its neighbors to determine the best path between 2 points. It will start with the neighbors of the first cell (the one containing the start position). Each cell in this setup can have at most 8 neighbor cells. There can be less than 8 if the cell is placed at some extreme of the analyzed area (like a corner, of one of the side rows/columns) or if any of the neighbors contain impassable obstacles (in which case they are ignored for the path analysis).

So the A* algorithm advances by getting all the available neighbors of a cell, calculating certain metrics for each of them, and then using those metric to decide which amongst them is the next cell to be analyzed, at which point this cell’s neighbors are gathered, their metrics are calculated, and so on and so forth, until either one of the analyzed cells is the one containing the destination (at which point we’ve successfully obtained the shortest path) or we run out of cells to analyze (meaning that the destination cell is unreachable, i.e. : it may be completely surrounded by impassable terrain, etc.). So another two A* specific notions are those of neighbors of a given cell, and metrics calculated for each neighbor cell.

Lets detail a bit the metrics. This is where A* starts to become less intuitive. Not to worry, we’ll soon see how these metrics (and all the other notions here) are actually used by doing a step-by-step description of an actual path obtained using A* calculations. So once A* gathers the neighbors of a cell, what it does is: calculate the cost (distance walked) from the start cell to this neighbor cell, when going through the currently analyzed cell (aka, when going through the cell who’s neighbor’s metrics we’re calculating right now). This score is called “g” and, once calculated, it is attached to the current neighbor cell along with the cell through which we’ve passed to get to this neighbor cell. This score doesn’t have a meaning without the parent cell, because it may be possible to get a better such score if going through a different (parent) cell. Each time such a pair of “g” score and parent is obtained, we’re also checking a list of other possible cells to see if this neighbor cell doesn’t already have a better “g” score with a different parent, aka, if there’s not a shorter path from the start cell to it. This list is called the “open list” because it is open to adding/removing of cells during the execution of the A* algorithm.

Another metric that’s calculated is a “guesstimation” of the distance from the current (neighbor) cell to the destination cell. This score is obtained by simply applying whatever distance calculation we’ve decided to use to the current and destination cells (and ignoring any possible obstacles that may exist between them). This value is called the “h” score (for Heuristics). Once this has been calculated for all neighbors, it contributes to deciding which cell we’re gonna analyze next: the “g” and “h” scores are summed up, the value is assigned to what’s called the “f” score. Once all neighbors have their “f” scores calculated, the one with lowest such “f” score value will be the next analyzed cell.

We’ve mentioned the notion of “open list” above. This list contains cells for which the metrics (g,h,f scores and parent) have been calculated, but which have not yet been themselves used (analyzed). By this we mean that they haven’t yet went through the process of getting their neighbors, etc etc. Once the metrics for a cell are calculated, it’s the value of the “g” score that decides whether or not it will be added to the open list for future analysis: if the cell is not already present on the open list, we simply add it. If it is already present on the open list, we check the g score. If it’s lower than our current g score for that cell, we leave it there. If however our newly calculated g score is lower, we replace the cell in the open list. What this translates to is that the open list should only contain cells who’s parents make for the shortest distance between it and the start cell. That’s because, when (if) the destination cell is reached, the actual path to it is reconstituted by going backwards to its parent cell, and its parent’s parent cell and so on until we get to the start cell.

Once a cell has been analyzed (namely, its neighbors have been obtained, etc etc.) the cell is placed in what’s called the “closed list”. This is simply so that if we stumble upon this cell again, we know to skip it from analysis (as, once one analysis on it has been performed, doing another one will not yield new information).

To recap, the last lot of A* notions presented above are:

open list: used to hold cells which still need to be analyzed, aka cells who can potentially be part of the shortest path
closed list: cells who have already been analyzed (And that’s all! The closed list does NOT contain the path cells exclusively. The cell’s parent, and parent’s parent, etc. are used to actually obtain the shortest path).
g score: distance from start cell to current cell, when going through its parent. Used to determine if this cell, with its current parent deserves to be added to the open list for further analysis or if it should simply be disregarded (as a shorter path from start to it already exists).
h score: estimation of current’s cell distance (cost) to destination cell. Used in conjunction with the g score to decide what cell to analyze next, aka, what cell is most promising to be the next cell is the shortest path.
f score: see h score above. The sum of g and h scores.
parent cell. The g score refers to the cost of getting from start cell to current cell VIA A CERTAIN PATH, aka via a certain set of cells. This set of cells is denoted by the parent cell (which in turn has a parent cell as well and so on and so forth up to when the parent is the start cell).

A step-by-step example

The A* algorithms is not very complex. Some of the things it does are however (perhaps…) a little counter-intuitive. Rather than doing a whole theory analysis of it, we’ll just look at a step-by-step proceedings of how A* actually performs the iterations when calculating a simple path:

As we said, A* “splits” the area into discrete cells. For this example, the cells are square. This leads to inaccuracies into modeling the exact terrain (maybe there’s some round cornered walls there, etc.). The inaccuracies can be diminished by splitting the area into smaller and smaller cells, but this will also increase computation time for the path. The number of cells in which the area is split (and which are then used to approximate the shape of the terrain) must be chosen so as to have a balance between how closely it resembles what the player sees as obstacles, and the time it takes to calculate the path(s). For our example, the cells are perfect squares. Also, although the actual area is 20×20 cells, for the path in this particular example, the calculations will not go outside a 5×5 cells area.

Let’s take a closer look at that 5×5 cells area. We’re gonna assign numbers to the rows and columns of cells that constitute it, going from top to bottom and from left to right:

Now, let’s take a look at the core code of the A* JavaScript implementation. This is the “getPath” function of the “AStar” object, which is declared in the AStar.js file:

var openList = new NodeOpenList(area.getWidth(),area.getHeight());
var closedList = new NodeList(area.getWidth(),area.getHeight());

var g = distanceCalculator.getDistance(new Node(destinationX,destinationY),new Node(startX,startY));
var finish = new Node(destinationX,destinationY,g);

var startNode = new Node(startX,startY,0,distanceCalculator.getDistance(new Node(startX,startY),finish));

var currentNode = null;

var arrivedAtDestination = false;
while(openList.size!=0) {
currentNode = openList.getLowestFNode();

if(finish.equals(currentNode)) {
arrivedAtDestination = true;
break;
}

openList.remove(currentNode.x,currentNode.y);

this.processSucessors(currentNode, openList, closedList, finish, area, somewhatPassableGAddendum);
}

The above contains the high level operation of A*:

When the calculation of the shortest path between two points is demanded (by calling the “getPath” function with the necessary arguments, start position, destination position, terrain description, etc) what happens is

– the open and closed lists are created. They are initially empty.
– the Node object for the start and destination positions are created. The start node is added to the open list
– a while loop starts. This loop advances the path calculations, by getting the next nodes and analyzing them.
– the node with the lowest “f” score is extracted (removed) from the open list (on the very first step, this is the start node, since it’s the only one in the open list)
– if the node has the coordinates of the destination location, then we’re done looping and the shortest path has been obtained
– if not, we process it (via the “processSuccessor” function, which we’ll look at in a minute) and then add it to the closed list, so we know not to process it again. This processing may add new nodes to the open list (if any are available)
– this goes on until we’re out of nodes in the open list, at which point we can declare that the destination is unreachable.

Now let’s see what processing a node actually entails:

AStar.prototype.processSucessors = function(currentNode, openList, closedList, finish, area, somewhatPassableGAddendum) {
//Get all neighbours of analyzed node, that DO NOT contain impassable terrain:
var neighbours = this.distanceCalculator.getNeighbours(currentNode, area);

for(var i = 0; i < neighbours.length; i++) {
var neighbour = neighbours[i];

//if neighbour node is already IN THE CLOSED LIST, skip it:
var closedNode = closedList.searchByPosition(neighbour.x, neighbour.y);
if (closedNode != null) {
continue;
}

//(...)
//calculate the cost of getting to the neighbour THROUGH the currently analyzed node:
var newG = currentNode.g + this.distanceCalculator.getDistance(currentNode, neighbour);

//(...)

//if the neighbour is alerady IN THE OPEN LIST *AND* IT'S THERE WITH A LOWER G COST, skip it
//as this means that this neighbour is already present in some other path (has some other parent) which is better than
//what we're investigating rigth now:
var openNode = openList.searchByPosition(neighbour.x, neighbour.y);
if (openNode != null && openNode.g <= newG) {
continue;
}

//if we're here, that means that this neighbour represents a node worth investigating as a potential member of the best path

//if this neighbour is present in the open list, but with a worse (higher) g score, then remove it from the opened list
//this means that this neighbour has made it to the open list already, but with a parent which constitutes for a path which is
//longer (costlier) than if it were to go through the currently analysed node (have it as parent)
if (openNode != null /* implicit: && openNode.g <= newG */) {
openList.remove(neighbour.x,neighbour.y);
}

/*
* at this point we know that this neighbour is:
* - not on the closed list
* - is walkable (does not contain impassable terrain)
* - either
*    - not on the open list
*    - on the open list, but with a g cost higher than if it were to pass through the currently analysed node
*    (aka: if we replace it's current parent with the currently analyzed node, it will make for a less costly (shorter) path
*
* Set it's g and h scores, set the currently analyzed node as its parent, and add it to the opened list:		 *
*/
neighbour.g = newG;
neighbour.h = this.distanceCalculator.getDistance(neighbour, finish);
neighbour.setParent(currentNode);
//(...)
}
};

Let’s now go through the calculation of the path, using some visual aids:

– Initialisation

At the beginning of the “getPath” function, before getting into the loop, we initialize our two empty lists. We then create a node for the start coordinates, and add it to the open list. So our two lists look like this:

open list:
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
closed list:
-empty-

– Iteration 1

The first iteration of the “while” loop in the “getPath” function is pretty straight forward: there’s only one node in the open list (the start node), so it will be extracted as per the “get the node with the lowest f score from the open list” rule. It’s added to the closed list. We’ll create neighbor nodes from all of its surrounding cells. Metrics are calculated for each of these neighbors (g, h and f scores, they also get the current node as their parent):

At the end of this iteration, the two lists look like this:

OpenList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]

ClosedList:
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]

The open list contains all of the start node’s neighbors, and the start node itself is the only element in the closed list.

– Iteration 2

The node with the lowest f score currently in the open list is the one at x=1, y=2. We remove it from the open list and add it to the closed list.

We then proceed to get all of its neighbor cells and create nodes for each of them, then calculate their metrics. It’s important to note that:

– the neighbor cells on its right (those at (2, 1), (2, 2) and (2, 3)) are ignored because they contain impassable terrain. They can’t ever take part in the shortest path.
– other than that, all other surrounding cells are taken, nodes are created from them and the g score is calculated for each, ignoring whether any of these cells have already went through the process in any prior steps. For this particular case, all these cells HAVE in fact been analyzed in the prior iteration as well. However back then we looked as them from the perspective of the start node at (0, 2), while now we are re-analyzing them from the perspective of the current node at (1, 2) to see if going through this node doesn’t make us reach any of these cells faster.

Now, none of the neighbor nodes of the current node are good candidates for the shortest path (when getting to them through the current node) because either:

– they’re already on the closed list. This is the case of the neighbor node at (0, 2). It has already been analyzed in the previous iteration.
– they’re already on the open list with better g scores than those obtained when getting to them through the current node. This is the case for all the other remaining neighbor nodes. We’re gonna take a look at what this means for only on of them, the one at (1, 1).

The current node’s g score is 3. That means that that’s how costly it is to get to it from the start node. In order to obtain the g score for its neighbor at (1, 1) when going there through the current node, we calculate the distance from the current node to the (1, 1) node, and then add it to the current node’s g score, and this value is the g score for the (1, 1) node. It’s 3 + 3 = 6. We then check the open list to see if the (1, 1) node isn’t already there. We find it there (from the previous iteration). That (1, 1) node already present in the open list has a g score of 4.24, and if we check it’s parent, we can see that it’s the node at (0, 2) – the start node. This means that it’s easier (less costly) to reach the (1, 1) node via the (0, 2) node, not via the (1, 2) node and it’s this more optimal version of the node that we keep (leave as-is in the open list). The same reason is analogously applied to the other remaining neighbors, making it so none of them are (re) added to the open list.

At the end if this iteration the lists look like this:

OpenList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]

ClosedList:
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]

The only thing that’s changed from the previous iteration is that the (1, 2) node has been analyzed, removed from the open list and placed on the closed list.

– Iteration 3

This iteration is a mix of the 2 previous ones: we’ll stumble upon some never-before-explored nodes (and immediately add them to the open list) as well as re-investigate some that are already on the open list (and find none better then what was there already):

The lowest f nodes currently on the open list are (1, 1) and (1, 3) each with an f score of 13.73… . In this situation, we can chose any of them as the next node to investigate. The way the search for the first lowest f node is implemented, the (1, 1) node will be selected. We remove it from the open list and add it to the closed list.

We get all of its neighbors, save those 2 that have impassable terrain on them. Form the 7 remaining neighbors, the 3 ones at the top are all previously unexplored, so we calculate their metrics and add them to the open list. Out of the remaining neighbors, after calculating their current g score, we notice that they all have better counterparts (with lower g score) already present on the open list, so we ignore them (in their present incarnation) or they’re on the closed list and we ignore them from the start.

At the end of the iteration, the lists look like this:

OpenList:
[x:0 y:0 g:8.49 h:13.42 f:21.90 parent:(x:1 y:1)]
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]

ClosedList:
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]

– Iteration 4

This time there’s only one node for the lowest f score, the one at (1, 3) with an f score of 13.73… :

It’s removed from the open list and added to the closed list. After wards, the treatment of it’s neighbors is pretty similar to those of the node from the previous iteration so we won’t detail it.

At the end of the iteration, the lists look like this:

OpenList:
[x:0 y:0 g:8.49 h:13.42 f:21.90 parent:(x:1 y:1)]
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:4 g:8.49 h:13.42 f:21.90 parent:(x:1 y:3)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:4 g:7.24 h:10.82 f:18.06 parent:(x:1 y:3)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]
ClosedList:
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]

– Iteration 5

This iteration has as lowest f node the one at (0, 1). The node seems promising because getting to it from the start node is very cheap (the g cost is 3, it’s right under the start node). However all of its neighbors are proven undesirable after their metrics are calculated: either they’re on the closed list, or their g score are worse than previous incarnations of them. There’s is one unexplored node at (0, 0) which will be added to the open list. However, we’ll see from the next iterations that we’ll never get back to the (0, 0) node, as its large f score (mostly due to its large h score) makes it uninteresting. There are more promising nodes which don’t stray that far from the start node while at the same time keeping away from the destination node as well as this node does.

At the end of the iteration, the lists look like this:

OpenList:
[x:0 y:0 g:6.00 h:13.42 f:19.42 parent:(x:0 y:1)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:4 g:8.49 h:13.42 f:21.90 parent:(x:1 y:3)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:4 g:7.24 h:10.82 f:18.06 parent:(x:1 y:3)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]
ClosedList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]

– Iteration 6

The lowest f node for this iteration is (0, 3). It’s a mirrored version of the node treated in the previous iteration, with a similar outcome, so we won’t detail it any further:

At the end of the iteration, the lists look like this:

OpenList:
[x:0 y:0 g:6.00 h:13.42 f:19.42 parent:(x:0 y:1)]
[x:0 y:4 g:6.00 h:13.42 f:19.42 parent:(x:0 y:3)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:4 g:7.24 h:10.82 f:18.06 parent:(x:1 y:3)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]
ClosedList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]

– Iteration 7

This iteration selects the node at (2, 0) as it’s the one with the lowest f score on the open list right now: f=16.97 :

At the end of this iteration, the lists look like this:

OpenList:
[x:0 y:0 g:6.00 h:13.42 f:19.42 parent:(x:0 y:1)]
[x:0 y:4 g:6.00 h:13.42 f:19.42 parent:(x:0 y:3)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:4 g:7.24 h:10.82 f:18.06 parent:(x:1 y:3)]
[x:3 y:0 g:11.49 h:6.71 f:18.19 parent:(x:2 y:0)]
[x:3 y:1 g:12.73 h:4.24 f:16.97 parent:(x:2 y:0)]
ClosedList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]

– Iteration 8

At the end of this iteration, the lists are:

OpenList:
[x:0 y:0 g:6.00 h:13.42 f:19.42 parent:(x:0 y:1)]
[x:0 y:4 g:6.00 h:13.42 f:19.42 parent:(x:0 y:3)]
[x:1 y:0 g:7.24 h:10.82 f:18.06 parent:(x:1 y:1)]
[x:1 y:4 g:7.24 h:10.82 f:18.06 parent:(x:1 y:3)]
[x:3 y:0 g:11.49 h:6.71 f:18.19 parent:(x:2 y:0)]
[x:3 y:2 g:15.73 h:3.00 f:18.73 parent:(x:3 y:1)]
[x:4 y:0 g:16.97 h:6.00 f:22.97 parent:(x:3 y:1)]
[x:4 y:1 g:15.73 h:3.00 f:18.73 parent:(x:3 y:1)]
[x:4 y:2 g:16.97 h:0.00 f:16.97 parent:(x:3 y:1)]

ClosedList:
[x:0 y:1 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:0 y:2 g:0.00 h:12.00 f:12.00 parent:n/a]
[x:0 y:3 g:3.00 h:12.37 f:15.37 parent:(x:0 y:2)]
[x:1 y:1 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:1 y:2 g:3.00 h:9.00 f:12.00 parent:(x:0 y:2)]
[x:1 y:3 g:4.24 h:9.49 f:13.73 parent:(x:0 y:2)]
[x:2 y:0 g:8.49 h:8.49 f:16.97 parent:(x:1 y:1)]
[x:3 y:1 g:12.73 h:4.24 f:16.97 parent:(x:2 y:0)]

– Iteration 9

When the loop begins for this iteration, it will find the destination node (4, 2) in the open list. This signals the fact the the path-finding part of the run has ended and that the shortest path to the destination exists.

– Backtracking to get path

In order to actually construct the ordered sequence of nodes that represent the shortest path, going from start to end node, what we need to do is backtrack from the destination node, up to its parent and then THAT parent’s parent and so on. Doing this will eventually make us stumble on to the start node (which has a null parent) at which point we stop. The path is then the reverse order of the above described backtrack:

Note that the end node from where the backtracking begins is the destination node as it has been added to the open list during our iterations.

Considerations on the implementations (it rhymes!)

The 3 A* implementations presented here: using JavaScript, Java and C, have as main goal to clearly illustrate how to implement the A* algorithms in various languages. They are not made to be used in professional path-finding libraries/game engines. What this means is that, in order to keep the code clear and easy to follow, its performance (optimization) is less than great. While the implementations are perfectly usable for scenarios involving relatively small areas and/or units, they will quickly bog down for large enough simulations (They’d work fine for some turn based game where only one unit moves at a time, or some real time game with just a handful of units like a 6 members party in an RPG, but will not work fast for something like Starcraft).

Here are the main areas in the code that suffer from this:

– The fact that we’re using separate object instances (structs in C’s case) for each cell of the area (the Node objects). This can be somewhat optimized by replacing them with a 2-dimensional (or even pseudo-2-dimensional stored as 1-dimensional) array having a “column” for each of the fields “g”, “h”, “f”, “parent”, etc. and a “line” for each node instance. Arguably, addressing array elements is cheaper than calling methods/functions on object instances.

– The way in which the OpenNodeList retrieves the Node with the lowest “f” score. Here’s a snippet:

/**
* @private
*/
NodeOpenList.prototype.calculateLowestFNode = function() {
if(this.nodePositionHash.length == 0) {
return null;
}

var lowestFNode = null;
for(var x=0; x<this.nodePositionHash.length; x++) {
var column = this.nodePositionHash[x];
if(column!=null) {
for(var y=0; y<column.length; y++) {
var n = column[y];
if(n!=null) {
if(lowestFNode==null) {
lowestFNode=n;
} else {
if(n.getF()<lowestFNode.getF()) {
lowestFNode = n;
}
}
}
}
}
}
return lowestFNode;
};

Yep, sadly all that does is simply iterate through all the nodes, and then return the one with the lowest “f” score. It’s used in conjunction with a a bit of caching (once calculated, a lowest “f” score node will be kept in a global field until the list is modified, at which point it will be recalculated), but still, all in all, it’s not the best way to do this. A better way would be to use a binary heap as described here.

– Also, for calculating the g score for the neighbors of a given cell: normally there’s only two possible values for this: one for the neighbors immediately to the left, right, up or down of the current cell. For these, the distance is the number we’ve chosen as the distance between 2 non-diagonal cells, namely 3. For the other 4 diagonal neighbors, Pythagorean theorem tells us that the distance is 3*sqrt(2) which is roughly 4.24. In order to underline that this is how these distances are calculated, the code still does the actual math each time to calculate these (using the DistanceCalculator object). This can be optimized by using 2 constants for the two possible values.

– The code uses doubles (Double-precision floating-point format) for the decimal values. This can be replaced with floats for a boost in performance, keeping in mind that for some scenarios this may also lead to not finding the shortest path between 2 points, but only a path.

– Even for other (between non-adjacent cells) distance calculations, the Pythagorean theorem can be replaced with some other means of approximating distance, which are less resource demanding (the Pythagorean theorem uses power and square root to do its thing) like the Manhattan Distance. Again, for certain scenarios this may lead to not getting the shortest possible path (still, if it exists, a path will be found). The code for distance calculations is abstracted in the “DistanceCalculator” object/class, which is passed as argument when computing a path so as to easily allow for new implementations of the distance calculation formula.

Finally, something the A* algorithm doesn’t do well at all is calculating the path to the closest reachable point of an unreachable destination. In order to compensate for this, when a path is calculated, we keep track of the node which is closest to the destination node. If that destination node proves to be unreachable, we return the path to the closest node. This was done as per the answer to this question.

The Code Examples

The A* algorithm described here has been implemented in 3 different languages (platforms): JavaScript, Java and C. The implementations are equivalent (with small differences accounting for each platform’s various idiosyncrasies). Each implementation only uses the default libraries that come with each respective platform (no extra 3rd party libraries are added).

The JavaScript code can be git-cloned from here:

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

It uses prototype-based objects. The actual A* algorithm code can be found in the “WebContent/js/astar” folder. The other folders contain the code for the small web example.

The Java code can be git-cloned from here:

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

It uses class-based objects, and a few of the Java Lists for certain variables (which are declared as arrays in the JS and C implementations). Other than that, the structure of the code is similar to the other implementations.

The C code can be git-cloned from here:

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

For C, the code is organized as follows: for each of the previously declared classes/prototypes (Node, Area, etc.) a C-style struct has been declared. The corresponding functions are still present here as well, the only difference is that instead of having them declared on their respective objects, they accept a pointer to the corresponding struct as argument. Otherwise, the overall organization of the code is similar to the one in the other implementations.

t

Posted in Examples, Game Dev | | 12 Comments

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:

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:

– 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:

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.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.processInput();

for(var i=0; i<this.gameEntities.length; i++) {
var gameEntity = this.gameEntities[i];
}
//(...) 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.

The Basics of Game Loop Implementation – part 3

Intro

A good way to code a game loop in JavaScript is to use the new “Timing control for script-based animations” aka “requestAnimationFrame” feature. The specs for this are still in draft state, but most modern browsers support it one way or another. The browsers I’ve tried and found to support it are: Chrome v. 27, Firefox v. 24 and Internet Explorer v. 8. I’m sure other version of these borwsers, as well as other browsers support this.

Much like Open GL’s callbacks that we discussed in the 2nd part of these series, “requestAnimationFrame” gives your graphics drawing code a way to get notified when it can draw. This basically translates to taking advantage in the most optimal way possible of the graphics drawing resources of the browser.

Before we dive into detailing the implementation, you can take a look at the running demo by clicking here:

We’re back to the “1-second counters” from part 1. This time there’s also a bit of user input handling: if you left-click anywhere inside the rectangle containing the counters, you’ll see one of the counters slowly moving towards the clicked location. Don’t worry if everything becomes a bit jerky when the counters reach 7, it’s supposed to do that (it’s not a bug, it’s a feature!). It’s one of the things that will come into discussion later on.

The (mixed step) game loop

The game loop implemented in this example is the one most discussed throughout these series: the affectionately called “mixed step” game loop. The mixed part comes from the fact that the loop keeps to separate steps: one fixed, happening at a given rate per time interval (25 times per second in this example), and one variable, which is executed as fast as possible, but only when we’re sure that the fixed step’s frequency is respected. The fixed step is used for updating the game state, while the variable step is used to update the graphics.

Here’s a code snippet of the game loop implementation in JavaScript:

this.update = function() {
var self = this;

var actualLoopDurationMs = self.getCurrentTimeMs()-self.lastLoopCallTime;
self.lastLoopCallTime = self.getCurrentTimeMs();
self.accumulatedTimeMs += actualLoopDurationMs;
while(self.accumulatedTimeMs>=FIXED_STEP_IDEAL_DURATION_MS) {
self.accumulatedTimeMs -= FIXED_STEP_IDEAL_DURATION_MS;
}

self.updateGraphics();

/*
* request a new graphics rendering, specifying this function as the function to be called back when
* the browser schedules a frame update
*/
window.requestAnimationFrame(function() {self.update();});
};

So basically, each time we want to update our graphics, we inform the browser of our intention by calling the “requestAnimationFrame” function, passing as argument the function that we’d like to have called (back) when the browsers deems that it’s time to make a new graphics rendering pass.

This must be manually invoked each time we’d like our graphics to be updated. This is why the “update” function in the code snippet above, has on its last line a call to requestAnimationFrame passing itself as argument.

What that call guarantees is that our update function will be called at some point in the future, when the browser thinks it’s a good time to do a new graphics update. For example, the update function will NOT be called if the browser tab/window where the drawing is happening is minimized or not visible for some reason. You can easily test this with the above example: As you can see, in the upper left corner it displays the local values for fixed updates rate (UPS) and variable update rates (FPS). Normally they are at about 25 and somewhere around 60 respectively. They may fluctuate a bit when the counters get to 7, as described above, but for most of the time they stick to these values. Now switch over from the tab displaying the demo, to another browser tab. Wait 10 seconds than go back to the game loop demo tab. You’ll notice that UPS and FPS are 0, followed by a quick jolt where they go to values such as 100 or 200 before finally settling in to their “regular” values of 25 and 60-ish, respectively. That’s because while the tab was invisible, the “update” function was not called, effectively NOT advancing our game state or rendering any of the game graphics. Once you come back to it, due to the fact that there’s a lot of accumulated time, a lot of game state updates will happen very fast, in order to give the game a chance to catch up and be back at about 25 game state updates per second.

This behavior from the requestAnimationFrame mechanism is a good thing. Your game loop will automatically spare resource usage when there’s no one to see it run. The way this is actually handled in this example is not the best way possible: normally you’d want to pause your game advancement when the game is no longer visible, and resume it when it’s visible again, and avoid the game state updates spike. This simplified implementation is done to showcase this behavior of the “requestAnimationFrame”. In a later article we’ll also see how to automatically and manually pause/resume a game.

Now, the game loop implementation is not really that exotic. We have two global variables: one for storing the last time when the last loop step was executed: self.lastLoopCallTime as well as another global variable for storing the accumulated time that has passed since a game state update has ran:

var actualLoopDurationMs = self.getCurrentTimeMs()-self.lastLoopCallTime;
self.lastLoopCallTime = self.getCurrentTimeMs();
self.accumulatedTimeMs += actualLoopDurationMs;

At the beginning of each loop step we calculate how much the last step has taken, we add that to the accumulated time, and then, if the accumulated time dictates that one or more game state updates are due, we execute them, deducting for each the fixed amount of time it should represent:

while(self.accumulatedTimeMs>=FIXED_STEP_IDEAL_DURATION_MS) {
self.accumulatedTimeMs -= FIXED_STEP_IDEAL_DURATION_MS;
}

Finally, we do a graphics rendering update as well.

self.updateGraphics();

Coping with graphics rendering slowdowns

During the game loop steps, you may run into situations where one update to the graphics takes so long, there’s no more time left for the game state update to run at its fixed step.

The graphics update can have such slowdowns usually when the graphics on the screen suddenly become a lot more complex then they were a moment ago, and the hardware cannot draw them as fast as desired. Imagine explosions. You have a game where the player has to kill a boss enemy. The player is one sprite (or a 3d model consisting of X triangles). The boss is one main sprite with 10 extra small sprites for various effects such as lasers shooting in all direction, rockets firing, etc (or a big 3d model consisting of y triangles plus 10x smaller 3d models consisting of z triangles each). The hardware can handle all these ok: each graphics update is fast enough so that there’s time to call the game state update when necessary. However at some point the boss explodes and for a few seconds there are hundreds of explosion sprites (hundreds of 3d explosions of y triangles each). During this time, each graphics update might take 10 times longer than before. If each of those graphics updates were executed, the game stat updates would be delayed for 5 seconds. That would mean that for 5 seconds, the player couldn’t move and the game would seem to be advancing a lot slower than before.

But the game loop described here doesn’t handle things like this: with a target fixed step update of 25 per second this translates to ideally doing a fixed step every 40 milliseconds. This means that if a graphics update takes way more than 40 milliseconds, we’re falling behind on the fixed steps execution. To compensate for this, the game loop measures how much time it has passed since the last fixed update was called, let’s say:200 milliseconds, calculates how many fixed updates it has missed, 200/40 = 5 updates, and executes them before doing another graphics update. What this translates to is that, while the fluidity of the graphics has to suffer (animations and motions are more “jagged”, etc), the game remains responsive to input, and does not freeze for long periods (like those 5 seconds in our hypothetical example). You can see this in action with the demo, by doing the following: when the counters are at something like “3” or “4” click somewhere in the game area. One of the counters will start moving towards the destination. As it moves, watch what happens when the counters hit 7: the motion will no longer be smooth, but will become very jerky for a while (normally until the counters get to something like “8” or “9”), after which the motion becomes smooth again. You can also check that if you click somewhere else in the game area doing the “jerky” animation period, the input will in fact be taken into account, and the moving counter will start moving towards the new destination. Finally, you can see in the console below that the overall precision of the counters (how closely they are to counting actual seconds), remains very high (this is the counters’ precision from the very beginning of the loop, not a local measurement, like for the last 2 seconds or something).

The reason why everything gets “jerky/jagged” for a while after “7” is that at this point the code is “rigged” to simulate a slowdown in graphics rendering, the equivalent of the explosion described in the example above: basicaly, the GameEntity.js object contains the following:

this.updateGraphics = function(context) {

if(this.simulateUpdateGraphicsDelay && this.currentAnimationImageIdx==7) {
var st = new Date().getTime();
while(new Date().getTime()-st < 100) {}
}
context.drawImage(this.imgs[this.currentAnimationImageIdx], this.startX-this.width/2, this.startY-this.height/2, this.width, this.height);
};

While the counter is a 7, the updateGraphics function will busy-wait for 100 milliseconds.

The Code Example

The code for this example can be git-cloned from here:

https://gitlab.com/shivansite/jsGameLoopStudy.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.

Posted in Examples, Game Dev | | 2 Comments

The Basics of Game Loop Implementation – part 2

Intro

In part one, we discussed the basic notion of “game loop” as well as given some code examples. In this 2nd part of the article, we’ll improve on the first examples as follows:

– This time we’ll be using C as the coding language, and the Open GL graphics library. This will allow us to see how to hook-up into the existing loop Open GL exposes, in order to obtain the “mixed step game loop” that was presented in part one.

– We’ll also see how to make the game loop more “energy efficient” by having it use hardware resources in a more optimal fashion (while at the same time not skimp out on game play experience)

– The examples will also introduce some basic notions of how the user input should be handled in the game loop.

About Open GL & Auto-looping game loop

Open GL is a lot more closer to the metal than Java’s Swing library will ever be. One side effect of this is the fact that Open GL is a lot faster. The Java & Swing example discussed in part 1 would run at about 500 graphics updates per second (Frame Per Second aka FPS) on my laptop. A roughly identical version of that example written in C using Open GL, on the same laptop, will now run at about 6000+ FPS:

Granted, the Java example would draw actual images, while this example only draws colored squares. However the game state updates here happen twice as often than in the Java example (50 UPS here, 25 UPS in Java). Given all this we can safely say that Open GL draws stuff a few orders of magnitude faster than Swing. That’s the good side effect. The somewhat bad side effect of Open GL’s closeness to metal (coupled with C’s closeness to metal) is that drawing images needs more coding. And since that would have over-complicated this example without any added bonus to the game loop discussion, I’ve chosen to simply replace the 1-10 counter from the previous example with squares that blink red/green at fixed time intervals.

The actual calls to Open GL are made using the GLUT library. Here’s how the code hooks up to the provided loop. The below snippet is taken from the “autoLoopingGameLoop/ALGameLoop.c” file:

void ALGameLoop_initOpenGL() {
//...

glutDisplayFunc(ALGameLoop_onLoop);
glutIdleFunc(ALGameLoop_onLoop);
//..
glutMainLoop();
}

Basically, we need to inform the GLUT library of what function it should call when a graphics rendering update can (is scheduled to) happen – glutDisplayFunc and also what’s the function to call between graphics rendering updates – glutIdleFunc. After this, the call to glutMainLoop() will start the never ending GLUT loop, which will periodically call on a best effort basis the functions declared as callbacks. In this example, we’re passing the same function – ALGameLoop_onLoop for both callbacks. In doing so, we’re able to achieve the same behavior as with the “mixed step game loop” from part 1:

void ALGameLoop_onLoop() {
double now = glutGet(GLUT_ELAPSED_TIME);
double timeElapsedMs = ((now-alGameLoopState.lastLoopTime)*1000)/(CLOCKS_PER_SEC);
alGameLoopState.timeAccumulatedMs += timeElapsedMs;
ALGameLoop_updateGraphics();

while(alGameLoopState.timeAccumulatedMs >= DESIRED_STATE_UPDATE_DURATION_MS) {
alGameLoopState.timeAccumulatedMs -= DESIRED_STATE_UPDATE_DURATION_MS;
}

alGameLoopState.lastLoopTime = now;
ALGameLoop_updateMeasurements();
}

This function, which represents the entire recurring step of our game loop, tries to functionally achieve two things: have the game state advance at a fixed step (configured here at 50 game state updates per second aka 50 UPS) and have the graphics rendering updates execute as fast as possible as long as the game state updates frequency holds true.

The implementation in the code snippet above achieves all this by doing the following:

– the first 2 lines at the beginning of the step measure how much time last game loop step took. They add this time interval to a global variable.
– next they’ll call the ALGameLoop_updateGraphics() function, which contains all the OpenGL code for drawing the squares of the appropriate color
– finally, it will check the accumulated loop time that has added up until now, and if one or more game state updates are due, they’ll all be executed now, at which point the necessary (fixed) amount of time which would have normally been allocated to said game state updates is deducted from the accumulated time
– finally the variable containing the time when the current loop step has ended is updated – so that the next loop step can calculate how much this loop step had lasted…

Now, if we look at this game loop in action, we’ll notice the following (as displayed in the windows Title Bar):

– the game state updates (UPS) are fixed at 50 as intended
– the graphics updates (FPS) happen as fast as possible (on my laptop they’re between 6000 and 6500)

Now, because Open GL does all his graphics calculations using the GPU (on your video card), the above numbers translate to the following: The main processor (CPU) consumption is capped at a decent value. The code will only use that fraction of CPU necessary to update the game state 50 times a second and no more. However the GPU will be at almost 100% load, no matter what. Running this app on my laptop, I can see that it uses between 10-17% of the CPU, and about 92% of my GPU! And sure enough if I let it run for a few minutes the fans on my laptop will spin at maximum speed.

I call this the AutoLoopingGameLoop, because part of its looping (namely the graphics update part) is set on “auto”. The code never tries to pace this part of the loop, letting it run as fast as possible. This is not good from a resources consumption point of view. Furthermore it’s useless for the most part of the time: once one of those 50 game state updates per second has executed, you only need on graphics update (before the next game state update happens). Doing multiple graphics updates between two game state updates will simply redraw the same thing and from the human player’s point of view, this makes no difference.

On-demand-looping game loop

This type of game loop still does the game state updates at a fixed time step, but the graphics updates are done at the most once for each game state update. What this means is that after each game state update, we signal to GLUT that we’d like a refresh on the graphics, by calling the glutPostRedisplay(). The nice thing about this function is that is does not en-queue (doesn’t stack up) these calls: if multiple calls to this function have been made, once a re-display actually happens, all those calls are “cleared”. In practice this translates into “frame skipping”: if for some reason the graphic update steps take too long, they will be executed less often in order to ensure that the game update steps run at the desired fixed rate.

Before exploring the code for all this, here’s how you can see it in action with the app:

The “main” function is found in the CGameLoopStudy.c file. If ran with the “odl” command line parameter, it will execute the OnDemanGameLoop demo:

On my laptop, this runs with both a FPS and UPS of 50. Now, we can simulate delays in graphics rendering by tapping the “p” key:

Tapping “p” multiple times will increase the delay in graphics rendering steps execution. This in turn will translate into a decrease of the FPS value, while the UPS value will remain at 50. You can also tap “o” repeatedly to remove the simulated delay incrementally.

On my laptop, the CPU usage for both the AutoLoopingGameLoop and the OnDemandGameLoop is about the same: about 15%. However, here’s how the GPU usage differs between the two:

The above is a screen capture from the GPU-Z program. First the on-demand-looping game loop demo has run. Then, at the time marked by the vertical green line, we switched to the auto-looping game loop. Without detailing too much all of the metrics there, we can tell only by looking at the GPU Load that it changes from about 20-30% to 92%. And since from a functional stand point both versions of the game loop are identical, it’s clearly better to use the on-demand-looping type of game loop.

Now, here’s how this is implemented: first, we now have separate functions for the GLUT idle callback and for the rendering callback:

void ODLGameLoop_initOpenGL() {
//...
glutDisplayFunc(ODLGameLoop_updateGraphics);
glutIdleFunc(ODLGameLoop_onOpenGLIdle);
//...
glutMainLoop();
}

Furthermore, now, the ODLGameLoop_onOpenGLIdle function signals to GLUT when it wants to request a graphics update:

void ODLGameLoop_onOpenGLIdle() {
double now = glutGet(GLUT_ELAPSED_TIME);
double timeElapsedMs = ((now-odlGameLoopState.lastLoopTime)*1000)/(CLOCKS_PER_SEC);
odlGameLoopState.timeAccumulatedMs += timeElapsedMs;

while(odlGameLoopState.timeAccumulatedMs >= DESIRED_STATE_UPDATE_DURATION_MS) {
odlGameLoopState.timeAccumulatedMs -= DESIRED_STATE_UPDATE_DURATION_MS;

odlGameLoopState.upsCount++;
ODLGameLoop_updateMeasurements();

glutPostRedisplay();
}

odlGameLoopState.lastLoopTime = now;
}

Each time a game state update is performed (call to ODLGameLoop_updateState()), we also call glutPostRedisplay().

Finally, it should be mentioned that this example also supports some basic in-game user input handling: by tapping the “w”, “s”, “a”, or “d” keys the blinking squares will move a bit in the respective direction: up, down, left or right. This is achieved by using a queue where user input events are en-queued as they happen, and then popped and processed at the beginning of each game state update:

void ODLGameLoop_onKeyboard(unsigned char key, int x, int y) {
switch (key) {
//...
case 'a': {
InputManager_pushEvent('L');
break;
}
//...
}
}

ArrowKeyPressedEvent* inputEvent = InputManager_popEvent();
int i;
for(i=0; i < odlGameLoopState.gameEntitiesLength; i++) {
}
}

A more detailed discussion and a more involved example on the user input event handling using a queue will be done in a future post.

The 3rd (and final) part of this series will showcase game loop implementation in JavaScript using “requestAnimationFrame”.

The Code Example

The code example for this post can be git-cloned from here:

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

The libraries needed to build are “opengl32” and “glut32”. The code also includes Eclipse project configuration files, so it should work ok if you import it into Eclipse for c/c++.

The main function is found in “CGameLoopStudy.c”. By default it will start the demo for the auto-looping game loop. If the “odl” command line argument is passed, the on-demand-looping game loop demo will start instead.

The code is organised as follows: the “common” folder contains stuff equally shared by each demo: the game entity code (the colored blinking squares), the user input handling code and the various constants. Implementation for the two types of game loops are found in each of the “autoLoopingGameLoop” and “onDemandLoopingGameLoop” folders.

Posted in Game Dev | | 3 Comments

The Basics of Game Loop Implementation – part 1

Intro

Games at their core have what’s called a “game loop”‘: a looping construct which advances the game a little bit at a time. The main issue with the game loop is how to make it so that it “paces” itself: i.e. that it will advance the game at the same (average) rate no matter what the speed of the loop is on a given machine configuration.

Game loop pacing is an issue for multiple reasons:

– the most immediate one is that given a game (and its game loop) written in a certain language for a target platform, there can be many different hardware configurations on which that game can be ran. Because of the potential difference in target platform’s hardware configuration the code inside the game loop can vary in the frequency with which it is executed. If the game loop does not compensate for this, the user experience when playing the game can vary from one where the game seems to run too fast, to one where it’s moving in “slow motion” and is not responsive.

– also related to game loop “pacing” is the fact that such pacing can be implemented in different ways: either the game loop is left to run as fast as possible and an interpolation must be done between the game advancement and the time the game loop takes to make a full loop (variable step game loop), or the game loop paces itself to a target number of steps per given time period (fixed step game loop). There’s also the option of mixing those two approaches in the same game loop: have some of the game advancing code run in a fixed step game loop and other parts run in a variable step game loop.

– finally, depending on how the target platform implements graphical capabilities, there may already exist a looping mechanism, with an option to hook into it, thus not needing to actually write the game loop by hand. Furthermore, if such a loop is already present, it may or may not have an imposed limit on the maximum number of loops it will do in a given time period (i.e. max steps or frames per second), other than the one that comes from reaching the hardware’s limits. To illustrate this point, here’s some examples: Open GL (both the “full blown” desktop computer version as well as its ES reduced version) expose a callback function which it will call as fast as possible (i.e as fast as it can can render the graphics). An example of a game loop that integrates with Open GL’s callback will be presented in the 2nd part of this article (coded in C). Another example would be JavaScript’s “requestAnimationFrame” mechanism (which is implemented slightly differently on the various browsers). It operates similar to Open GL’s callback, with the added difference that most browsers impose a limit on the frequency with which requestAnimationFrame can be invoked, usually it’s capped at 60 calls per second (meaning that no matter how fast your game loop is executing, the graphics will not be updated more than 60 times each second). The 3rd part of this article contains an example on how to code a game loop in JavaScript using “requestAnimationFrame”.

In order to implement any of the above mentioned game loops, it is advised to follow certain guide lines when organizing the game loop related code:

– There should be a separation at least between the code that deals with graphics rendering and the code that deals with game state advancement. It is desirable to have at least this level of separation in the gaming code because, as it will be discussed later, for most scenarios the state updating code needs to be ran at a different pace than the graphics rendering code.

– There should also be a separation of concerns at the code level, such that different logically grouped parts of the game functionality are implemented in code following that separation: i.e.: the game loop code itself should only deal with high level game loop issues like pacing the game loop. Then, for each step of the loop, it should delegate to other code entities the various jobs of updating the game state and rendering the graphics. A simplistic way to achieve this is to have isolated code representing various “game entities” which are notified by the game loop when the next loop step is to be executed (and, depending on the type of the game loop, how much time since the last loop has passed).

Next, simple examples of the above mentioned types of game loops will be given, implemented using the following platforms (languages): JavaScript (in browser), C (using OpenGL), Java (using Swing). The reason why multiple development languages/platforms have been employed for these examples is that, while fixed and variable step game loop implementations are pretty much platform agnostic (can be done in any of those languages), multiple languages/platforms were needed to also showcase the various types of existing (platform level) loops we can hook in to.

Basic Variable Step Game Loop

One of the simplest to implement game loops is the variable step game loop. If we adhere to the principle that the game loop code should only deal with the game loop and its pacing, and other game aspects should have separate code entities for their implementation, then the variable step game loop simply needs to run as long as the game is still going (hasn’t reached a “game over” or “win/lose” situation) and simply measure how much time has passed between each of its steps, then delegate the per-step game actions to other parts of the code, also passing to them that time difference (delta time) between steps. Then, it’s up to the game entities code to use the delta time in order to make the necessary computations and see how much the game state should advance such that it will give a consistent game experience on various machines.

The code example for this is a very simple technical demo for the variable step game loop. It can be git-cloned from here:

https://gitlab.com/shivansite/JGameLoopStudy.git
(the Variable game loop code is in the “com.shivandragon.jGameLoopStudy.basicVariableStepGameLoop” package)

Here are some screen shots of the running app:

What this thing does is display 4 counters, each going from 1 to 10 (and then looping back to 1). The functional demand is that each counter must be incremented once per second.

The example is coded in Java, and uses Java’s Swing library in order to draw to the screen.

Here’s the game loop code (from the “BasicVariableGameLoop” class):

long deltaTimeMs = 0;
while(true) {
long st = System.currentTimeMillis();
mainWindow.update(deltaTimeMs);
long et = System.currentTimeMillis();
deltaTimeMs = et-st;
}

Each of the 4 counters represent one instance of the “BasicVariableGameEntity”. The game loop “update” loop delegates to each of the “update” methods found in this class. The implementation of the counter’s update logic is very simple and straight forward: with each call, add the time of the current game loop to a global variable. If this accumulated time passes 1 second, draw the next counter bitmap (and wrap around to “1” when you get past “10”):

public void update(long deltaTimeMs) {
accumulatedDeltaTimeMs+=deltaTimeMs;
int animImageIncremIdx = (int) (accumulatedDeltaTimeMs/(1000f));

if(animImageIncremIdx > 0) {
currentAnimationImageIdx = currentAnimationImageIdx + animImageIncremIdx;
currentAnimationImageIdx = currentAnimationImageIdx%10;//wrap animation around
accumulatedDeltaTimeMs = accumulatedDeltaTimeMs-animImageIncremIdx*1000;
}
debugger.debug(tag, currentAnimationImageIdx);
}

– It will run as fast as possible. On my laptop, it runs at about 400 updates per second:

This is not necessarily good. For this particular and very basic example, one update per second would suffice (as the game state only changes each second). For a regular game, with actual animations and user input, an update rate of about 60 per second would be enough for a good playing experience. Having a lot more updates than that only uses hardware resources unnecessarily, draining the battery of mobile devices, heating up hardware components etc.

– This game loop will pace itself. This means that, on average, the game will run with the same “speed” (the counters will actually count each second) on most hardware configurations: even if the graphics were to become more complex, and take more time each step, this will only translate in a decrease of the game update rate, the actual “speed” of the game will remain constant (counters will still change their value each second). You can see a simulation of this by letting the application run for a while, and noticing what happens when the counters get to “7”. The “BasicVariableGameEntity” class is implemented such that when it gets to display the sprite for “7” it will sleep for 50 milliseconds. What this translates to in player experience is that when the counters reach 7, a drop in update rate happens (on my machine it drops from 400+ updates to about 20) and maybe some of the subsequent counter values (such as “8”, “9”) will not be displayed, but it will instead “jump” over them.

– The way this implementation deals with variations in game loop step time is not however ideal. You can get into a situation where so many updates take too long to process that the graphics updates will happen at a very decreased rate (the display may update itself one every 10 seconds, for example). This game loop’s simplistic implementation, especially the fact that game state updates are not separated from graphics updates (which would allow them to run at different rates), translates into poor handling of such extreme scenarios. The next example will show how to deal with this issue.

Mixed Step Game Loop

Next, will showcase the “Mixed step” game loop. “Mixed step” refers to the fact that this kind of game loop keeps two kinds of steps : one that advances at a fixed rate (25 updates per second here) and one that runs as fast as possible (variable step). Moreover it’s the fixed steps that have priority, meaning that, on average, we first make sure that fixed steps get to actually be executed once every 25th part of a second before letting the variable step have a turn as well. We’ll detail how this works by having a look at the code, which is found in the “com.shivandragon.jGameLoopStudy.basicMixedStepGameLoop” package.

First, the game loop is implemented as follows:

long accumulatedTimeMs = 0;
while(true) {
long startTime = System.currentTimeMillis();

mainWindow.updateGraphics();
while(accumulatedTimeMs >= FIXED_STEP_IDEAL_DURATION_MS) {
accumulatedTimeMs -= FIXED_STEP_IDEAL_DURATION_MS;
}

long endTime = System.currentTimeMillis();
accumulatedTimeMs += endTime - startTime;
}

The idea is this: we want the game to advance at the same rate no matter what the hardware performance of the platform is. When we say “game advancement” we refer to the rate with which the game state is updated, not the graphics. For this particular example, where we want to have counters that increment each second, the game state refers to advancing the counter value exactly one time per second. The graphics update refers to actually drawing the sprite corresponding to the current game state (i.e. if current game state says the counter should be at “7” draw the sprite that shows a counter with the value “7”). Now, depending on what graphics are drawn at a particular moment, or the overall performance of the hardware, we may run into situations where the graphics drawing take too long. In order to compensate for this, once such a long time running drawing happens, on the next game loop we’ll update the game state faster (more times) until the overall game advancement rate “catches up” with the average value we want.

Let’s see how all this is implemented in the above code snippet:

– On each game loop, we first measure the current time. When the loop ends we measure the current time once more and then calculate the duration of this particular game loop step and keep it in a global variable
– Next the loop will do a graphics rendering (mainWindow.updateGraphics()). This is the “variable step” part. It will be called as fast as possible, with one limiting condition:
– when the rendering for this game loop step is done, we look at how much time has accumulated so far. From this we deduce how far behind the fixed step execution is. As an actual example of this, imagine that we want to have 25 fixed steps per second. That means that once 1/25 = 40 milliseconds have past since the last fixed step, we need to do another fixed step. Now, imagine that the variable step (the graphics rendering part) actually took 95 milliseconds on the previous game loop step. This means that our accumulatedTimeMs=95, and we need to do 2 fixed steps (2×40 ms) in order to catch up, leaving an accumulatedTimeMs reminder of 95 – (2 x 40) = 15 milliseconds to keep for the next step in the loop.

If you run the example, you’ll notice that this time the window displays two update rate values: UPS (updates per second, refering to the local game state update rate) and FPS (frames per second, refering to the rate with which the grapics are updated):

As before, the code is “rigged” so that when one of the counters is displaying “7”, it will simulate a delay of 50 ms for the graphics rendering. What will happen this time is that this will mostly influence the graphics update rate (FPS value), which will drop sharply for a while, while the game state update rate (UPS) will drop a lot less (or possibly not at all) and will catch up as soon as it can (namely, when the counters gets to “8” and the graphics updates are no longer “slow”, then more game state updates will be executed for a while, until the average game state update rate is back to 25/second, aka accumulatedTimeMs is less then 1/25 = 40 milliseconds).

This implementation of the game loop is better then the previous example:

– firstly, the game state update rate is independent of the graphics update rate. Thus it is less influenced by how fast the graphics can be drawn, making the game advancement rate stick more closely to the desired (average) value.
– also, now we can easily change the state update rate as desired, without influencing how fast the graphics will be drawn. For example: for this particular example, a game state update rate of 25 per second is too high. We can lower it to 5 per second (since the actual game state only needs to change once every second) thus saving some CPU usage for the calculation of the game state.
– the downside here is that even though the game update steps are capped to a given (constant) value, the graphics rendering steps will run as fast as they can, aka they will “fill all the time gaps” left by the fixed game state update steps. Again this is not ideal, as more resources than necessary are consumed because of it.

The next part of the article will showcase various game loop implementations using C and OpenGL. We’ll see how to tap into the existing loop OpenGL gives us, as well as how to better control the game loop’s advancement rate in order to have a more economical usage of hardware resources.

The Code Example

The code can be git-cloned from here:

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

In order to actually run the application, the content of both “src” and “res” folders need to be added to the class path (if using Eclipse, make sure both these folders are declared as “source folders”).

The “Basic Variable Step Game Loop” example should be run using the “com.shivandragon.jGameLoopStudy.basicVariableStepGameLoop.BasicVariableGameLoop” main class.

The “Basic Mixed Step Game Loop” example should be run using the “com.shivandragon.jGameLoopStudy.basicMixedStepGameLoop.BasicMixedGameLoop” main class.

It should be noted that, in order to simplify the code, and focus only on the game loop implementation part, the way in which the Java Swing library is used in these examples to make graphics renderings is not the recommended one.

Swing offers the “paintComponent” method which normally should be overridden with the desired draw calls, letting Swing call it whenever it deems necessary. These examples avoid this and simply call “getGraphics().drawXXX” each time the game loop deems it necessary to make a graphics update. While for the two above-mentioned examples there’s no visible problem, you can see how this can lead to bad graphics artifacts by running the “com.shivandragon.jGameLoopStudy.inputMixedStepGameLoop.InputMixedGameWindow” main class. This example also contains user input handling. If a left-button mouse click is performed anywhere inside the application window, the counter will be moved at that position. In order to handle the redrawing of this, the “repaint()” method in called on the JPanel. This leads to image “flickering”. This could be fixed by refactoring the code to properly use the Swing library, but it’s beyond the scope of this article. However, in the words of every math textbook I’ve had in primary school: “this is left as a potential exercise for the reader” :)

Posted in Examples, Game Dev | | 7 Comments