Blog de tfe, Perl, Web et Libre...?

Game creation: simple pathfind algorithm

PubliƩ le 03/11/2016 dans threejs

Here is the article 12 about my series of posts about the game creation.

If you missed it, check out the previous part.


Here is a screenshot of the current state of the game.

Game threejs

Path find algorithm

To be able to add ennemys patroling from one cell to another, i implement a simple findpath algorithm.

Now the ennemys can randomly patrol in circle in one cell, or go to another cell.

So there are the steps i used to do it.

First we need to generate a three with all the path the ennemy can use.

pathfind altorithm

Once the three done, we can start the pathfind with the start node. Here the gif above, i search for the path from node 1 to 7.

pathfind altorithm

Here is a sample of the code which generates the path finding:

 this.findPath = function(origin, destination)
        // cache the result to avoid recalculating the path
        if(findPath_cache[' to '])
            var res = findPath_cache[' to '].concat();
            return res;

        var parent_paths= {};

        var to_visit = [];
        var correct_path= null;

        // Get the doors near the origin, and add them to the to_visit array
        var doors = this.near_doors(origin.params.x, origin.params.z, true);
        var i=0;
            var next = to_visit.shift();
            var cell = next.cell;

            this.near_doors(cell.params.x, cell.params.z, true).forEach(function(door_data)
                var near_cell = self.generated_doors[door_data[0]][door_data[1]];
                    parent_paths[] = { i : (door_data[2]), cell: cell };
                        correct_path = true;
                    to_visit.push({ parent:, cell: near_cell});

        var path = [];
        // There is a path to this
            var current = destination;
            var loop_avoid=0;
            var next_i = this.get_opposide_door(parent_paths[].i);

            path.push(this.getFindPathCoord(destination, parent_paths[].i));
            while(parent_paths[] && parent_paths[].cell!==origin)
                var old_current = current;
                current = parent_paths[].cell;
                path.push(this.getFindPathCoord(parent_paths[].cell, next_i));

                next_i = this.get_opposide_door(parent_paths[].i);
                path.push(this.getFindPathCoord(parent_paths[].cell, parent_paths[].i));

            path.push(this.getFindPathCoord(origin, next_i));
        findPath_cache[' to '] = path.concat();
        return path;

Stamina bar

I also added a stamina bar, like the one in the diablo games.

You can get: the source code or View the demo directly.