Pathfinding in Isometric View

A few weeks ago, I blogged about creating an isometric world in EaselJS.  This is a continuation of that post and will be focusing on pathfinding.  Pathfinding deals with finding the shortest route between tile A and tile B, which we will need if we want to move our player around in the world.

1. Tile Model

In my isometric world post, we left off with rows and columns of tiles that became our grid or our tile map.  Ideally, we will need to store information about each tile.  Information such as, what is its x?  Its y?  Its row?  Its column?  This will become important when we use pathfinding and figuring out the tiles that the player must visit until reaching the destination tile.  All of this information about a tile can be stored in a Tile Model.  Since we’re using Backbone, we can create a model easily:

var TileModel = Backbone.Model.extend({
  defaults: {
    column : 0,
    row : 0,
    x : 0,
    y : 0
  }
});

Then, let’s modify our “for loops” where we set up the rows and columns of our tiles.  We need to somehow associate a given tile with a Tile Model:

createTileMap : function(context, img, x, y, regX, regY, data) {
   var tile,
       bmp,
       i,
       j;
   context.tileMap = [];
   for (i = 0; i < 4; i++) {
     context.tileMap[i] = [];
     for (j = 0; j < 4; j++) {
       bmp = new createjs.BitmapAnimation(img);
       bmp.x = (j-i) * x;
       bmp.y = (i+j) * y;
       bmp.regX = regX;
       bmp.regY = regY;
       bmp.row = i; // add row property
       bmp.column = j; // add column property
       bmp.currentFrame = data[i][j];
       context.stage.addChild(bmp);
       tile = new TileModel({column:i, row:j, x:bmp.x, y:bmp.y, img:bmp});
       context.tileMap[i][j] = tile;
     }
  }
}

2. The Player

Next, we’ll need a player in our isometric world.  Add this to the bottom of your createTileMap() function, so that once the tile map is ready, you can load the player:

context.loadPlayer(context);

Then create a loadPlayer() function like this (replace “image”, “width”, “height”, “regX”, and “regY” below with your player’s image and dimensions):

loadPlayer : function(context) {
  var img = new Image(),
  originTile = context.tileMap[0][0];
  img.src = '[image]';
  $(img).load(function() {
    // create spritesheet and assign the associated data.
    var spriteSheet = new createjs.SpriteSheet({
      // image to use
      images: [img],
      // width, height & registration point of each sprite
     frames: { width: [width], height: [height], regX: 0, regY: 0 }
  });
  context.player = new createjs.BitmapAnimation(spriteSheet);
  context.player.x = originTile.get('x');
  context.player.y = originTile.get('y');
  context.playerModel = new PlayerModel({x:context.player.x, y:context.player.y, row: originTile.get('row'), column: originTile.get('column') });
  context.player.regX = [regX];
  context.player.regY = [regY];
  context.player.currentFrame = 0;
  context.stage.addChild(context.player);
  context.stage.update();
  });
 }

3. Pathfinding Algorithm

Then, we’ll need a pathfinding algorithm.  I used A* and used a library called Pathfinding.js, which has other pathfinding algorithm choices as well.  First, for Pathfinding.js, we will need to set up a few things:

  • The grid (4×4):
this.grid = new PF.Grid(4,4);
  • Set the unwalkable tile (all tiles are walkable by default).  In our example, the unwalkable tile was in (2,2):
this.grid.setWalkableAt(2,2,false);
  • Create a new instance of the A* finder:
this.finder = new PF.AStarFinder();

All of the above 3 lines can be part of your “initialize()” method, which comes as part of your View.

In this example, we can have the user’s mouse click determine the “destination tile.”

bmp.onClick = function(event) {
   context.path = context.createPath(context, context.playerModel.get('row'), context.playerModel.get('column'), event.target.row, event.target.column, context.grid);
}

Then define a “createPath()” method that uses the A* finder method:

createPath : function(context, playerRow, playerColumn, destinationRow, destinationColumn, grid) {
  context.path = context.finder.findPath(playerRow, playerColumn, destinationRow, destinationColumn, grid);
  context.movePlayerToTile(context, context.path[0]);
  return context.path;
}

When you do a console.log on the context.path result, you will notice that you get an array of [row,column]’s that list out the tiles that the player must visit until reaching the destination tile.  So if your player starts at [0,0], and you clicked on tile [1,2] for example, then the context.path result would look something like: [ [0,0], [0,1], [1,1], [1,2] ].  That means we will need some sort of method that will make the player move to the tile at context.path[0], then remove that element at 0, and if the context.path still has a length greater than 0, have your player go to the tile that is now at context.path[0].  We will go over this more in the next section.

4. Moving the Player to the Destination

In the last section, we made a call to “movePlayerToTile().”  Let’s define what that is:

movePlayerToTile : function(context, array) {
  var row = array[0],
  column = array[1];
  context.playerModel.set('destRow', row);
  context.playerModel.set('destColumn', column);
  context.playerModel.set('destX', context.tileMap[row][column].get('x'));
  context.playerModel.set('destY', context.tileMap[row][column].get('y'));
  context.model.set('movePlayer', true);
 }

Remember how our main.js looked like?  It had the ticker and checked if the “movePlayer” property was set to true.  If so, then it would call “movePlayer().”

var tick = function(dt, paused) {
  mapView.stage.update();
  if (mapModel.get('movePlayer') === true) {
    mapView.movePlayer(mapView);
  }
}

And since the “movePlayer” property is now set to true, it will cause this “movePlayer()” method to run in the ticker:

movePlayer : function(context) {
  var playerX = context.player.x,
      playerY = context.player.y,
      destX = context.playerModel.get('destX'),
      destY = context.playerModel.get('destY'),
      removedElement;
  if (playerX < destX) {
    context.player.x += 0.5;
  } else if (playerX > destX) {
    context.player.x -= 0.5;
  } else {
    context.player.x = destX;
  }
  if (playerY < destY) {
    context.player.y += 0.5;
  } else if (playerY > destY) {
    context.player.y -= 0.5;
  } else {
    context.player.y = destY;
  }
  if ( (playerX === destX) && (playerY === destY) ) {
    context.model.set('movePlayer', false);
    context.playerModel.set('x', destX);
    context.playerModel.set('y', destY);
 
    if (context.path.length > 0) {
      context.path.splice(0,1);
      if (context.path.length > 0) {
        context.movePlayerToTile(context, context.path[0]);
      } else {
        context.model.set('movePlayer', false);
      }
    } else {
      context.model.set('movePlayer', false);
    }
 
  }
  context.stage.update();
}

And watch your player go from tile to tile by the click of your mouse!

For further reading and more information about pathfinding, check out this awesome link: http://theory.stanford.edu/~amitp/GameProgramming/

 

Grunt Basics

In a past post, I mentioned a build tool called Grunt.  IT IS AWESOME!

“Grunt is a task-based command line build tool for Javascript projects.”

Here are some basic steps on how to set up Grunt for your project:

1. Install Node.js:  http://nodejs.org/

2. Install Phantom.js:  http://phantomjs.org/

3. Install Grunt by using:  npm install -g grunt

4. Set up a project with grunt init, or you can do specific configurations.  Here is one for JQuery:  grunt init:jquery.

And ta-da!  It sets up your directory and project files.

5. Use grunt watch and it’ll run a batch of predefined tasks whenever you make changes to your files such as:

  • lint – Validate files with JSHint.
  • min – Minify files with UglifyJS.
  • qunit – Run QUnit unit tests in a headless PhantomJS instance.

You can even configure your grunt.js file a bit to cater to your project’s needs.  If you prefer Jasmine or Mocha over QUnit, for example, you can specify your grunt.js file to use that instead.  When I developed in AS3, I had to literally type a command (i.e., ant or mvn) in the command prompt or double-click an Ant icon in Flash Builder to have the build process going.  But Node.js brings along this ability to “watch” your files — it’ll build whenever you hit ctrl+s — and it’ll execute all of those commands that you tell it to in your configuration.  All of this sounds like a great boost to your development workflow… don’t you think?

Crazily enough, Grunt is not the only build tool out there for Javascript.  There’s Yeoman, Mimosa, Gear, Jake… some people even still use Ant.  I have yet to try them all out.  Which build process and configurations do you prefer?