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:





The 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):

null

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();		
	};
	
	this.onUnitUpdateState = function() {
		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;
		return this.getEvaluatePathAdvancementState(path);
	};
}

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


	this.onUnitUpdateState = function() {
		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.)

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

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s