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:





https://lazersoft.neocities.org/jsFastAstar/benchmark/BenchmarkOnPredefinedMap.html





https://lazersoft.neocities.org/jsFastAstar/benchmark/BenchmarkOnPredefinedMap.html





https://lazersoft.neocities.org/jsFastAstar/benchmark/InteractiveFloodBenchmark.html

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:

The “add” functionality:

add: function(n) {
    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);
	
openList.add(startNode);
	
var currentNode = null;	
	
while(!openList.isEmpty()) {
	currentNode = openList.removeLowestFNode();       
	if(currentNode.g <= maxDistance) {
		closedList.add(currentNode.x, currentNode.y, currentNode);
		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.

Advertisements
This entry was posted in Game Dev. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s