TfeServer

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.

Screenshot

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[origin.name+' to '+destination.name])
        {
            var res = findPath_cache[origin.name+' to '+destination.name].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;
        while(i0)
        {
            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]];
                if(!parent_paths[near_cell.name])
                {
                    parent_paths[near_cell.name] = { i : (door_data[2]), cell: cell };
                    if(near_cell===destination)
                    {
                        correct_path = true;
                    }
                    to_visit.push({ parent: cell.name, cell: near_cell});
                }
            });
        }

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

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

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

                loop_avoid++;
            }
            path.push(this.getFindPathCoord(origin, next_i));
        }
        findPath_cache[origin.name+' to '+destination.name] = 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.