This forum is read only and just serves as an archive. If you have any questions, please post them on github.com/phoboslab/impact

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:
This is really good. And the timing too. I was just about to start scouting for an A* impact solution tomorrow. I just tried yours and it works very nicely. I'll have to tweak it to prevent diagonal paths (90 degree turns only) by extending and adding an allowedDirections function supplied by the client and that the a* navigator will use to determine eligible (for consideration) neighbouring positions. Other than that, it's great. Thanks.

EDIT
and nice one on the debug panel too
Quote from alexandre
... I'll have to tweak it to prevent diagonal paths (90 degree turns only) by extending and adding an allowedDirections function supplied by the client and that the a* navigator will use to determine eligible (for consideration) neighbouring positions. ...

fastes way is to change this (line 123):
```                    // 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;
}
```

into this:
```                    // 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;
}
```

but when you have very big maps, i would change the two for() loops in line 103 and 104. maybe i will add this feature in the next update.
How about:

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

astar-for-entities:
```getPath: function (destX, destY, skipFunction)
{
...

if (skipFunction(dx,dy))
continue;
...
```
I am using a custom collisionMap (not done in WM) because entity paths must avoid other, possibly moving entities. To do this, within the goto(dest) function, I force a collisionMap refresh that adds an imprint of all entity positions to the map.

Last, because other entities are on the move, the path needs to be recalculated every time an entity arrives at path waypoint... which gets tricky because positions are never exact.

Working on this now but your path planner gave me a big headstart. :)
here i used this tutorial:
http://www.policyalmanac.org/games/aStarTutorial.htm
there a lots of links to more complex articles about pathfinding, an i think you will find something about coordinated movement ...

by the way, when you have made a good function which let the entity follow the path it would be nice if you post it here. :)
by the way, when you have made a good function which let the entity follow the path it would be nice if you post it here. :)

I will. On my todo list for tomorrow. :|
Thanks for the link on coordinated movements. That helps.
hi,

i added a followPath() function to my plugin. but it is far from a real good implementation. anyone made something in that way?

here you can find it: https://github.com/hurik/impact-astar-for-entities

hurik
Page 1 of 3
« first « previous next › last »