Forums » Code » A* Path Finder

Here's a simple A* path finder for impact. It is pretty fast, but you still shouldn't run it every frame. I made the heuristic and neighbors computations into functions so you can override them as needed.

https://gist.github.com/827899

That seems very cool jminor. Might be nice to see an example in action should you get a chance. Found an article for beginners about A* Pathfinding.

This is awesome, thanks!

Hmmm I had a look at it it does calculate something and does return the tile coordinates but I guess some extra info would be appreciated regarding what is actually returned by the path finder.

I ran through the script by jminor about a month ago and made it quite a bit easier to use.

https://gist.github.com/994534

Now, if you want to find a path of points from one entity to another, just do the following:

var path = new PathFinder(myEntity, otherEntity);
var points = path.getPath();
// [{ x : 0, y: 0 }, { x: 1, y: 1 }/* ... etc */]

Nice, i'm going to optimise my code soon so that it will be able to ignore...
[{x: 0, y: 0}, {x: 1, y: 0}, {x: 2, y: 0}, {x: 3, y: 0}, {x: 4, y: 0}]

and turn make it:

[{x: 0, y: 0}, {x: 4, y: 0}]

basically, removing any intermittent steps betweeen point on an axis.
I found that when moving a sprite from tile to tile, any intermittent tiles would cause the sprite to pause for a frame, when it was stopped it would go back to the idle animation. I had coded it so that it would display the correct animation for the direction the sprite was moving. if the velocity was 0 on both axis then it would revert to idle. This resulted in flaky looking animation as the sprite would freak out between tiles. I think removing the steps inbetween two points should resolve this.

I'll check out your code paularmstrong and see if i can incorporate that too. I'll probably roll it into a plugin at some point as well.

empika: the one I posted actually already does that... it steps between whatever your background tilesize is. The points that it spits out are the x,y coordinates of each tile on the path between your first entity and second that you pass to it.

aaah, nice! I didn't actually have time to check out your code last night, will have a look later

This is a really interesting piece of code you developed here. I found some really complicated javascript code online which was also designed to be a pathfinder. I was just breaking my head over how to implement it when I read this thread.

Does any of you have an actual code example of how to move entities with the PathFinder? It would be really usefull to have a real life example from someone who already used it.

thanks in advance,

Sleenee

I took a look at calling this function and I don't really get it I'm afraid.

Wouldn't the following be enough to at least assign the function to a variable?:

	    this.player = this.getEntitiesByType( EntityPlayer )[0];
		this.otherEntity = this.getEntitiesByType( EntityCivilian )[0];
		if (this.otherEntity){
			var path = new PathFinder(this.player, this.otherEntity);
		}

Or am I missing something fundamental (except adding the code and putting it in the requires off course)

thanks in advance,

Sleenee

I did not look properly into it (no need atm) but I think this returns the next step (tile coords) on the path to the tracked entity...

Ok so I think I got the function to work.

however I think the function might be a bit too intense for actual usage in a browser.
when I do this:

		if( ig.input.pressed('context') ) {
			if (this.otherEntity && this.player){
			  this.path = new PathFinder(this.player,this.otherEntity);
			  var points = this.path.getPath(); 
			  //alert(points);
			}   
		}

The game hangs for an entire second before going on. I guess that is calculation time? (the alert was to check if it really calculated something and it did return an array of objects so I presume it did what it was supposed to).

Is 1 second the normal runtime for this function or could I be doing something wrong?
Maybe there is a way to make it calculate less intermediate points and thus reduce runtime?

Thanks in advance,

Sleenee

A* pathfinding is not a small task. It's going to be hard on your browser no matter what.

The version that I posted above only calculates 1 point per tile, so it's really not calculating too much. You should make sure that the points that you're trying to get from and to are not too far apart.

Also, search for paths only as often as you actually need to. Updating the path on every update() call is not a viable solution.

I made a pacman clone and the plugin didnt work for me until I commented out this section of code

getBoard: function (radius) {
            var map = ig.game.collisionMap.data,
                board = [],
                tboard = map,
                c = this.columns,
                r = this.rows,
                s = Math.ceil(radius / this.tilesize),
                j = r, k = c,
                node, neighbors, n, l, m;
           /* 
            while (s--) {
                j = r;
                board = [];
                while (j--) {
                    k = c;
                    board.unshift([]);
                    while (k--) {
                        v = tboard[j][k];
                        node = new PathMapNode(k, j);
                        neighbors = this.getNodeNeighbors(node);
                        l = neighbors.length;
                        board[0][k] = v;
                        while (l--) {
                            n = neighbors[l];
                            if (tboard[n.y][n.x]) {
                                board[0][k] = 1;
                                continue;
                            }
                        }
                    }
                }
                tboard = board;
            }*/

            return map;
        },

and I written this function for the entity to follow a path

moveTowardsDestination:function(){
	var node = this.points[0];
	
	if(node.x < Math.floor(this.pos.x)){
	    this.vel.x = -20*this.multiplier;
	    this.currentAnim = this.anims.left;
	}
	
	if(node.x > Math.floor(this.pos.x)){
	    this.vel.x = 20*this.multiplier;
	    this.currentAnim = this.anims.right;
	}
	
	if(node.y > Math.floor(this.pos.y)){
	    this.vel.y = 20*this.multiplier;
	    this.currentAnim = this.anims.down;
	}
	
	if(node.y < Math.floor(this.pos.y)){
	    this.vel.y = -20*this.multiplier;
	    this.currentAnim = this.anims.up;
	}
		
	if(node.x == Math.floor(this.pos.x) && node.y == Math.floor(this.pos.y)){
	    if(this.points.length >1){
		this.points.splice(0,1);
	    }else{
		this.points = null;
	    }
	   
	}
	
    }

For some reason the get map returned 1 in the places of 0 and therefore the getPath always returned empty array once i commented this out all works like a charm.

        if( ig.input.pressed('context') ) {
            if (this.otherEntity && this.player){
              this.path = new PathFinder(this.player,this.otherEntity);
              var points = this.path.getPath(); 
              //alert(points);
            }   
        }

So, the above would find a path between the otherEntity and player.

Is it possible to replace the otherEntity with coordinates? Like from a mouse click?

main.js init function:

        ig.input.initMouse();
        ig.input.bind( ig.KEY.MOUSE1, 'lbtn' );

player.js entity's update function:

        if( ig.input.pressed('lbtn') ) {

            if (this.player && this.pos){
              this.pos = ig.input.mouse.x, ig.input,mouse.y;
              this.path = new PathFinder(this.pos,this.player);
              var points = this.path.getPath(); 
              //alert(points);
            }   
        }

Would something like that work?

Yeah it wlll (well at least the idea is right) all you need to do is to assign these to an object so for example

var mymouseposition = {pos:{x:ig.input.mouse.x,y:ig.input.mouse.y} };

And then pass it to pathfinder

this.path = new PathFinder(this.player,mymouseposition);

I did that some time ago and it worked.

Thanks Jerczu!

I've been working on this and I think I've run into another issue.

when I hit the below line of code, I get errors up the wazoo in Chrome's Javascript consolde

              this.path = new PathFinder(this.player,this.mymouseposition);

The error just keeps on growing to a point where the console stops responding (I have to close the tab). The error says:

Uncaught TypeError: Cannot read property 'x' of undefined

@ a-star.js line 53

I can't expand the logs because the console is unresponsive. Any ideas?

This is the code I have in my player entity js:

// a*
        if( ig.input.pressed('lbtn')) {
		this.player = ig.game.getEntitiesByType(EntityPlayer)[0];
		this.mymouseposition = {pos:{x:ig.input.mouse.x,y:ig.input.mouse.y} };
		if (this.player && this.mymouseposition){
                    console.log(this.player);
                    console.log(this.mymouseposition);
                    this.path = new PathFinder(this.player,this.mymouseposition);
                    //console.log(this.path);

 //             var points = this.path.getPath(); 
	//	document.write(points);
  //            alert(points);
		}   


        }
 

Anyone have any ideas?

You will need to investigate the a* plugin on line 53 and check how it iterates through the pos.x and pos.y I think you may need to wrap your mouse position in one more set of curly brackets so you set

this.mymouseposition = {mouse:{pos:{x:ig.input.mouse.x,y:ig.input.mouse.y}}};

You need to adapt your mouse position info to the way that entity object is built I can't remember how exactly it is wrapped

How hard would this be to implement for a platform game?

As adding any plugin to impact

hi,

i changed the plugin in a little bit and added a debug view. here you can find the code: https://gist.github.com/1949089

when you load a level it automatically creates a PathFinder object in the game class, with the name astar.

when you collision maps changes you can update the map with:

// this.astar.updateBoard();
ig.game.astar.updateBoard();

to get a path you need to call:

// this.astar.getPath(start, end);
ig.game.astar.getPath(start, end);

when you have debug activated and also loading the a-star-debug.js you can display the last calculated path which is in ig.game.astar.path.

its more for testing to see how this plugin works ...

hurik

hi again,

i changed the plugin a lot and now:
- it inject the getPath(x, y) function to the entity class.
- it doesn't cut walls anymore.
- some other things ...

include the plugin (astar-for-entities.js) and then you can call the getPath(x, y) function in you entity, for example (here with mouse clicks ...):

this.getPath(ig.input.mouse.x + ig.game.screen.x, ig.input.mouse.y + ig.game.screen.y);

the path will be saved in this.path. when this.path is empty there was no path ...

you can also include astar-for-entities-debug.js and then you can activate the show paths option to see the calculated path ...

here the plugin: https://github.com/hurik/impact-astar-for-entities

and a example picture:

1 decade ago by alexandre

                    // Only use the upper left node, when both neighbor are not a wall
                    if (dx == -1 && dy == -1 && (map[currentNode.y - 1][currentNode.x] == 1 || map[currentNode.y][currentNode.x - 1] == 1)) {
                        continue;
                    }

                    // Only use the upper right node, when both neighbor are not a wall
                    if (dx == 1 && dy == -1 && (map[currentNode.y - 1][currentNode.x] == 1 || map[currentNode.y][currentNode.x + 1] == 1)) {
                        continue;
                    }

                    // Only use the lower left node, when both neighbor are not a wall
                    if (dx == -1 && dy == 1 && (map[currentNode.y][currentNode.x - 1] == 1 || map[currentNode.y + 1][currentNode.x] == 1)) {
                        continue;
                    }

                    // Only use the lower right node, when both neighbor are not a wall
                    if (dx == 1 && dy == 1 && (map[currentNode.y][currentNode.x + 1] == 1 || map[currentNode.y + 1][currentNode.x] == 1)) {
                        continue;
                    }

                    // Ignore diagonal
                    if (dx == -1 && dy == -1) {
                        continue;
                    }

                    // Ignore diagonal
                    if (dx == 1 && dy == -1) {
                        continue;
                    }

                    // Ignore diagonal
                    if (dx == -1 && dy == 1) {
                        continue;
                    }

                    // Ignore diagonal
                    if (dx == 1 && dy == 1) {
                        continue;
                    }

goto: function (destPos)
{
	ig.game.refreshCollisionMap();
	this.getPath (destPos.x, destPos.y, function (dx, dy){return (Math.abs(dx) == Math.abs(dy));});
},

getPath: function (destX, destY, skipFunction)
{
	...

	if (skipFunction(dx,dy))
		continue;
	...