Akihabara Tutorial, Part 5: Enemy AI

This is the fifth tutorial in a multi-part tutorial series where we will teach you how to make an 8-way shooter in HTML5 and JavaScript using the Akihabara framework. Akihabara is a set of Javascript libraries that take advantage of some of HTML5’s unique features to facilitate game creation. One of the best things about writing a game in HTML5 is that it will run in any browser that supports HTML5 on any platform. This includes Chrome, Firefox, Safari, and WebKit browsers on iPhone/iPad, WebOS devices, and other mobile platforms.

In this tutorial, we will add a simple type of enemy to our game that chases the player around the map. To do this we’re going to use something called A* pathfinding (pronounced “ey star”), and we’re going to add some code to make the pathfinding more efficient.

You may wish to start with our final code from Part 4.5 of the tutorial. And please be sure that you’re using Akihabara v1.2.1!

The final product

When we’re done we’re going to have a program that looks like this. As you move your player sprite around the map, the enemies follow you.

A tip to help you follow along

This tutorial is quite a bit more complicated than past ones, and involves a lot of code to include in your game as you follow along. Because of this, we wanted to point out a feature of this blog to help you along. When you hover over a mono-space-formatted code box in this and all other parts of the tutorial you’ll see small icons on the top-right corner of the box. The first one allows you to see all the code in a new window, without any formatting. The second is even more useful: it directly copies the code to your clipboard!

This makes it very easy to include the example code verbatim. Just remember to be sure you understand the code before you move along in order to get the most out of this tutorial.

Adding the enemy sprite

The first thing we need to do is add a sprite for the enemies. Download enemy_sprite.png and add it to same directory as your index.html. Now we modify the loadResources function to load our image and create tiles from it, just as we have with every other image in our game. The first thing we do is add a new gbox.addImage call, which loads our image file and assigns it an ID of ‘enemy_sprite’:

[js]
gbox.addImage(‘font’, ‘font.png’);
gbox.addImage(‘logo’, ‘logo.png’);
gbox.addImage(‘player_sprite’, ‘player_sprite.png’);
gbox.addImage(‘map_spritesheet’, ‘map_pieces.png’);
gbox.addImage(‘enemy_sprite’, ‘enemy_sprite.png’); // New for Part 5
[/js]

Next we create a new gbox.addTiles call, which in this case creates a single 16×16 tile out of the image and assigns it the ID ‘enemy_tiles’:

[js]
gbox.addTiles({ // New for Part 5, adding the enemy sprite
id: ‘enemy_tiles’,
image: ‘enemy_sprite’,
tileh: 16,
tilew: 16,
tilerow: 1,
gapx: 0,
gapy: 0
});
[/js]

And finally, let’s create a rendering group for our Enemy object. At the beginning of our main function, we need to add a new group called ‘enemy’ to the gbox.setGroups call:

[js]
function main() {
gbox.setGroups([‘background’, ‘player’, ‘enemy’, ‘game’]); // New ‘enemy’ group for part 5
[/js]

Now we’re ready to move into pathfinding!

A little bit about A*

You might not believe it, but one of the harder things to get an enemy to do in a video game is to navigate around walls to get to a target. The A* search algorithm is an extremely common solution for what’s referred to as “pathfinding” — finding the optimal route between two points while avoiding obstacles.

We’re not going to go into the technical specifics of how A* works, but generally speaking it keeps a list of what it thinks the best paths to the target are, ordered from best to worst. It traverses what it thinks the best path to the target is, but if at any point it looks like the cost for the current path is getting too high, it ditches its path and moves on to the next best one.

The important thing to remember is that each time we run an A* algorithm, it traverses the maze many times in order to figure out the best path. This means that A* is pretty computationally intensive!

Our particular A*

For our game we’re going to use some Javascript A* code provided by the blog 46 Dogs. The original post containing and explaining the code is available here. Download the A* Javascript file from our server (right click, save as) and place it in the root of your project directory.

The first thing we need to do is include the A* script in our game. We do this by going to the very top of our index.html file and inserting a new <script> tag right after the initial Akihabara includes:

[html]<script type="text/javascript" src="a_star.js"></script>[/html]

The way we call our new A* algorithm looks like this:

[js]nodes = a_star(start, destination, board, rows, columns);[/js]

Our function is called a_star, and it takes 5 arguments as inputs. The board argument is an array of 1’s and 0’s, where a 1 indicates a solid tile and a 0 indicates a tile that can be passed through. The start value is your starting tile for the path, formatted as a 2 by 1 array [x, y]. The destination argument is the target [x, y] for the path. Finally, rows and columns are the number of rows and columns in the board array.

What the A* function returns is an array of node objects. The set of nodes returned describe the optimum path from start to destination. Each node has a bunch of properties, but the most important ones are x and y, which are the coordinates on the board array of the node. So if we wanted to know the x coordinate of the 3rd node in the path, we’d read nodes[3].x, which would return that value as an integer.

Setting up for A*

If we’re going to use the a_star function, we’re going to need to create an array of 1’s and 0’s for its board argument. Let’s create a global variable called pathMap which will hold that array. At the top of your index.html, after the other global variable declarations, add a new one for pathMap:

[js]
var maingame;
var map;
var frameCount = 0;
var pathMap; // New for Part 5
[/js]

Next we need to populate pathMap. We do this near the end of the main function, right after we call help.finalizeTilemap:

[js]
map = help.finalizeTilemap(map);

// New for Part 5, we create a 40×30 array to match our 40×30 tiles in the map.
pathMap = new Array(40);
for (i = 0; i < pathMap.length; i++)
pathMap [i] = new Array(30);
// For each element in the array, check and see if the corresponding tile is solid using our map’s tileIsSolid function.
// The function will return 1 if the tile is solid, and 0 if it’s empty space. We copy map(i,j) to pathMap(j,i) since there’s something
// inverted in the A* pathfinding function and the present authors are too lazy to fix it. What we’re creating is an array
// of 0’s and 1’s where each array element represent one tile and whether it’s solid. This is what the pathfinding algorithm
// will use as its version of the level map.
for(i = 0; i < map.map.length; i++)
for(j = 0; j < map.map[0].length; j++)
pathMap[j][i] = map.tileIsSolid(map, map.map[i][j]);
[/js]

The first thing we do is create an empty 40×30 array. Our tilemap itself is 40 tiles wide by 30 tiles high, so this means that pathMap will be able to store one array element for each tile in the map. In Javascript, if we want to create a two-dimensional array with R rows and C columns, we declare a one-dimensional array of length R, then we go through each element in that array and create a one-dimensional array of length C. It’s an array of arrays.

The next thing we do is go through each element in the map array and figure out if its corresponding tile is solid. Fortunately we already have a map.tileIsSolid function that we’ve defined, which returns a 1 if a tile is solid and a 0 if a tile is not solid. So for each element of the map array and evaluate it using map.tileIsSolid, assigning the returned 0 or 1 to pathMap. Note that we had to copy map[i,j] to pathMap[j,i] — the map array is addressed (row, column) whereas a_star wants things in a (column, row) format.

Now that we’re all set up to use A*, we should define our enemy object.

Creating the enemy

We’re going to create an addEnemy function, which will be similar to our addPlayer function in that it encapsulates a single gbox.addObject call. However, unlike our Player object, we’re going to want to add multiple instances of the enemy object on the map. In order to make this easier on ourselves, we’ll provide three arguments to addEnemy: xx, yy, and enemy_id. The xx and yy arguments are the starting x and y position of the object. The enemy_id position is going to be concatenated to the Enemy object’s ID. This will prevent us from having the same ID for each object and will allow us to do things like search for a particular enemy and do something to it.

The first part of our addEnemy function looks like this:

[js]
function addEnemy(xx, yy, enemy_id) {
gbox.addObject({
id: ‘enemy_id’ + enemy_id, // id refers to the specific object, here we concatenate a unique id so enemy 2 would be ‘enemy_id2’
group: ‘enemy’, // The rendering group
tileset: ‘enemy_tiles’, // tileset is where the graphics come from
colh: gbox.getTiles(‘enemy_tiles’).tileh,
speed: 2, // needs to be a power of 2 (2, 4, 8, 16)
[/js]

We include the arguments in the function header, and then call gbox..addObject as usual. Our id value is set to ‘enemy_id’ concatenated with the enemy_id value we passed in. (Even though we’ll be passing in an integer as enemy_id, Javascript is smart enough to automatically convert enemy_id to a string before it concatenates.)

We set our rendering group and tileset, as well as our collision box height (for details on colh see Tutorial 3). Finally we define the speed of our enemy, which we’re setting to 2 for now.

The enemy initialize(), first(), and blit() functions

To briefly review, all objects in Akihabara have three core functions: initialize, first, and blit. The initialize function runs once, when an object is created, and is where all the initialization code typically goes. The first function runs every frame and is where all the calculations that don’t have to do with rendering happen. And finally the blit function is what puts the pixels on the screen, where the drawing code goes. Here are the core functions for our Enemy object:

[js]
initialize: function() {
// First we initialize this like any other topview object.
toys.topview.initialize(this, {});

// Set the starting position of the object to the x/y coordinates that we passed in.
this.x = xx;
this.y = yy;
},

first: function() {
this.obj = gbox.getObject(‘player’,’player_id’);
this.nodes = a_star([Math.floor(this.x/16), Math.floor(this.y/16)], [Math.floor(this.obj.x/16), Math.floor(this.obj.y/16)], pathMap, 40, 30);
this.waypoint = [16*this.nodes[1].x, 16*this.nodes[1].y]; // multiply by 16 to get the true pixel coord of each pair<br />
// Move toward our new waypoint
if (this.x < this.waypoint[0]) this.x += this.speed;
if (this.x > this.waypoint[0]) this.x -= this.speed;
if (this.y < this.waypoint[1]) this.y += this.speed;
if (this.y > this.waypoint[1]) this.y -= this.speed;
},

blit: function() {
gbox.blitTile(gbox.getBufferContext(), {
tileset: this.tileset,
tile: this.frame,
dx: this.x,
dy: this.y,
fliph: this.fliph,
flipv: this.flipv,
camera: this.camera,
alpha: 1.0
});
},
});
}
[/js]

The initialize function is simple enough. The first thing we do is run toys.topview.initialize, just like any other topview object. This gives the object a bunch of basic properties and functions. Then we set the starting position of the object to the xx and yy coordinates that we passed in.

Our first function is where the pathfinding magic happens. We call the gbox.getObject function, which will take a group and an id and return the particular instance of an object that matches the two. In this case we’re telling it to look for an object in the ‘player‘ group with an id of ‘player_id’, which is our game’s instance of our Player object. We set the Player object to a temporary variable called obj. This temporary variable now has all the properties of the player, so obj.x would give us the player’s x coordinate, etc. This will be our target for the pathfinding.

Next we run a_star and set its output to a variable called nodes. The first argument we pass to a_star needs to be the x and y coordinates of the start of the path, in the form [x, y]. We pass it the x and y coordinates of the enemy object, this.x and this.y. But we divide by 16 and round down using Javascript’s Math.floor function, because it’s expecting to know which tile it’s on, not the exact pixel. Dividing by 16 and rounding down transforms a pixel to its tile number (if we’re on pixel (17,17) that means we’re on tile (1,1), and so on). The second argument is the destination of the path, which is the same, except that we use obj (our player target) instead of this. For the third argument, we send it the pathMap that we defined back in our main function. And finally we send it the number of x and y tiles to expect, 40 and 30, respectively.

As explained above, the output of the function is an array of node objects, which we set to a variable called nodes.

With this done, we can now set a waypoint for the enemy to move to. We set our waypoint like so:

[js]this.waypoint = [16*this.nodes[1].x, 16*this.nodes[1].y];[/js]

First of all, we’re looking at nodes[1], not nodes[0]. This is because nodes[0] is the Enemy object’s current position, so we actually want to use nodes[1], which is the next nearest position in the path. We also multiply the x and y values by 16 — this is to translate the pathMap coordinates back to absolute pixels on the screen.

And to wrap up the first function we have some simple code that moves us toward our waypoint. If our Enemy object is to the left of the waypoint, we move the the right, and vice versa. Same goes for the up and down directions.

And finally the blit function is the same standard drawing code we use for our Player object, making a basic blitTile call (see Tutorial 2 for more details on blitTile).

Adding the enemies to the map

Last but not least we need to add the enemies to the map itself. In our main function, inside our maingame.initializeGame definition, we need to call our new addEnemy function, right after we place down the Player and the Map objects.

[js] maingame.initializeGame = function() {
// Create the ‘player’ (see tutorial Part 2 for a detailed explanation)
addPlayer();

// Create the ‘map’ (see tutorial Part 3 for a detailed explanation)
addMap();

// Create the enemies for Part 5. We’re passing in x coord, y coord, and a unique ID for the enemy.
// The reason we write 16*8 instead of 128 is it helps us remember it’s 8 tiles in length.
addEnemy(16*8,16*8,0);
addEnemy(16*18,16*24,1);
addEnemy(16*28,16*28,2);
};[/js]

In this case we’re creating three enemy objects and putting them in three different locations on the map.

Testing performance

Let’s see how well this thing runs. Open your index.html in a compatible web browser. You’ll notice that the enemies do track you down, but the performance is terrible. It depends on your particular computer, but on our (very fast) laptop, the game sometimes dips to about 1 frame per second. Also, when an enemy reaches you, the game crashes, but we’ll fix that later! For now we just want you to notice how poorly the program runs.

You can see the performance for yourself here. Pretty bad, huh?

Fixing our performance problem

There are a number of ways that we can go about solving the realtime A* performance issue, but one of the most common ways is to set up a waypoint system. We’ve already begun treating the 1st nontrivial node returned by the A* function as a simple waypoint, so why not continue down this path (pun not intended)?

What we’re going to do is change our enemy code so it finds the path to its target when it’s created. It’s going to travel to the first 4 waypoints in its list, at which point it will recalculate the A*. This means that the A* is only going to be recalculated once every few seconds, as opposed to 30 times a second in the above example.

The first step is to modify our initialize function so we create our waypoint counter, set a maximum number of waypoints to travel to before we recalculate, and then grab our initial A* path.

[js] initialize: function() {
// First we initialize this like any other topview object.
toys.topview.initialize(this, {});

// Set the starting position of the object to the x/y coordinates that we passed in.
this.x = xx;
this.y = yy;

// Set the initial waypoint count to 0, our max to 5
this.waypointCount = 0;
this.waypointMax = 5;

// Calculate our initial A* path to the player. We grab the player object and then run the A* function to
// populate this.nodes with a set of nodes comprising the path, setting our waypoint to the 2nd x/y pair in the path.
// The first x/y pair, at this.nodes[0], is our current node, which isn’t a valid waypoint for us.
this.obj = gbox.getObject(‘player’,’player_id’);
this.nodes = a_star([Math.floor(this.x/16), Math.floor(this.y/16)], [Math.floor(this.obj.x/16), Math.floor(this.obj.y/16)], pathMap, 40, 30);
this.waypoint = [16*this.nodes[1].x, 16*this.nodes[1].y];
},[/js]

The first three lines of the function are the same, but then we add the waypoint variables and calculate our initial A*. The code for the initial A* is the same code we were running in our previous first function; that part hasn’t changed.

Our new first function is going to be somewhat difficult to understand, so please read through the following code and comments first, then follow along with the rest of the tutorial:

[js]
first: function() {
// If we’ve reached the next waypoint…
if (this.x == this.waypoint[0] && this.y == this.waypoint[1]) {
// …and if we haven’t gone through enough waypoints to recalculate the path yet…
if (this.waypointCount < this.waypointMax) {
// …then increase the waypoint count and set this.waypoint to the next waypoint.
this.waypointCount++;

// If the number of nodes in our path is less than or equal to our current waypoint count (i.e., we’re
// going to try and move 3 more nodes when there’s only 2 left)
if (this.nodes.length <= this.waypointCount) {
// then re-run our A*
this.nodes = a_star([Math.floor(this.x/16), Math.floor(this.y/16)], [Math.floor(this.obj.x/16), Math.floor(this.obj.y/16)], pathMap, 40, 30);
// if it turns out we’re AT our destination, just stay in our current location
if (this.nodes.length == 1)
this.waypointCount = 0;
else // otherwise, start moving to the next location
this.waypointCount = 1;
}

// Set this.waypoint to the next waypoint that we determined above
this.waypoint = [16 * this.nodes[this.waypointCount].x, 16 * this.nodes[this.waypointCount].y];

} else { // if we’ve reached the next waypoint and we’ve gone through enough waypoints that we need to recalculate…
// reset our waypoint counter
// If it turns out we’re AT our destination, just stay in our current location…
if (this.nodes.length == 1)
this.waypointCount = 0;
else // …otherwise, start moving to the next location.
this.waypointCount = 1;

// grab the player object and calculate our A* path to the player, and set the next waypoint
this.obj = gbox.getObject(‘player’,’player_id’);
this.nodes = a_star([Math.floor(this.x/16), Math.floor(this.y/16)], [Math.floor(this.obj.x/16), Math.floor(this.obj.y/16)], pathMap, 40, 30);
this.waypoint = [16*this.nodes[this.waypointCount].x, 16*this.nodes[this.waypointCount].y];
}
}

// Move toward our new waypoint
if (this.x < this.waypoint[0]) this.x += this.speed;
if (this.x > this.waypoint[0]) this.x -= this.speed;
if (this.y < this.waypoint[1]) this.y += this.speed;
if (this.y > this.waypoint[1]) this.y -= this.speed;
},
[/js]

Essentially we’re testing to see if we’ve reached the next waypoint in our nodes list. If we haven’t, then we just move toward our next waypoint using the same waypoint moving code we used previously.

If we have reached the next waypoint, and it’s not the 4th waypoint in our list, then we increment our waypoint counter and update this.waypoint, the variable that holds our current waypoint we’re heading towards. If it is the 4th waypoint in our list, then reset the waypoint counter and re-run our A*.

There’s also some code in there that takes care of edge cases: when we have less than 4 nodes in our list, then we recalculate A* (otherwise we’ll attempt to access a 4th node that isn’t there). When we are at our target, we stay in place.

When you wish upon A*…

What you end up with should look something like this. The enemies will chase you around, but if you run circles around them it takes them a moment to reorient themselves to your position. The program also runs at a much smoother framerate now!

[aki_tut_toc full_url=”“]