HTML5 Game Development Blog

  • Tiled Game Engine slide



I like to move it! Pathfinding and units movement

Category : JavaScript, Tiled Game Engine Apr 7th, 2015

Pages: 1 2

pathfinding_head

Well, what we got now – we can generate some Tiled map using Tiled Map Editor, add some units on it, select unit and? Now I want my units or enemies to move on the map. To do that units should be able to find path from point A to B. There are a lot of pathfinding algorithms, but the most suitable for games is Dijkstra algorithm or more smarty A* (A star). So, what to do at start? Find current unit position, get target cell position, find path, set unit behavior and make unit follow the path.

Preparing for pathfinding

To get path we need to get start and end coordinates. Also, we need to find which unit should be moved. To get start position and currently selected unit we use TiledMap::getEntityByXY method. We modify main game class method Game::onMouseClick, to get start and end positions:

Game.prototype.onMouseClick = function(key, value) {
    ...
    // convert screen coordinates to tile
    var iso = this.activeStage.scr2Tile(value.x, value.y);
    ...
    // get object from click position
    var obj = this.map.getEntityByXY(iso[0], iso[1]);
    if (!obj) {
        // no object was clicked - find path to the target position
        ...
    } else {
        // selectable object was clicked - change selection
        ...
    }
}

Looks pretty simple to understand. If we click on unit – we select it, if not – find a path to the selected cell.

Path finding algorithm will be discussed deeply in separate post, here we’ll concentrate on it usage.

It looks reasonable to extend TiledMap class with getPath method:

    /**
     *  Find a path from start position (x0, y0) on current map to finish position (x1, y1)
     *  @param  {number}    x0  Start X coordinate (in tiles)
     *  @param  {number}    y0  Start Y coordinate (in tiles)
     *  @param  {number}    x1  Finish X coordinate (in tiles)
     *  @param  {number}    y1  Finish Y coordinate (in tiles)
     *  @return {Array|undefined}   If path found it will be returned as Array, or undefined otherwise
     */
    TiledMap.prototype.getPath = function(x0, y0, x1, y1) {...};

But this is not all we need to get path finding works. A*, as all others algorithms used for path finding, require some initialization. Particular in case of A* we need to create weighted graph with links between node.

Creating graph from tiled map

To create graph we need get some source information from map. If you’ll take a look to the map file in the Map Editor you’ll see special layer, called “collision”. This layer is like a terrain map.

Map layers

Collision layer in the map can be treated as terrain map for path finding

In the simplest case we can treat any non zero value as obstacle while path finding. To create graph from collision layer we create new onParse trigger for that layer. Let’s call it initGraph.

Collision layer properties

onParse trigger to generate graph from layer

Note, that this layer is not going to be rendered (property render is set to false), but we still need its data for path finding. The code of that trigger handler is following:

    TiledMap.prototype.initGraph = function(layerID) {
        var json = this.assetsManager.get(this.asset),
            layer = json['layers'][layerID];

        this.graph = new Graph(layer.data, this.width, this.height, {diagonal: true});

        this.astar = new AStar();
    };

Graph class parse layer data and create rectangular matrix with some internal values and properties, that will be used later while A* processing. As a base for the A* and Graph classes I used very good implementation of it by Brian Grinstead. I do not like the Graph class implementation, actually, as far it uses huge amount of memory and is not optimized from garbage collection perspective and memory usage.  Details of pros and cons for that implementation will be in separate post.

Simple changes in Graph class initialization made to get our one dimension numeric array as source data. Also, implementation of GridNode::isWall changed. In the Brian’s implementation any zero value treated as obstacle, but in our case we treat any non-zero value as obstacle.

So, now we have initialized graph from the collision layer data and are ready to get path from A to B. Lets take a look how we’ve done it. Continue on the next page…

.
Click on unit, to select it. Click on grassland to move unit

Pages: 1 2

SHARE :

Leave a Reply

Your email address will not be published.


Like it? Share It!

We're making our best to provide good and valuable content. Please help us by clicking on one of the social icons, thanks for everything.