Forums » Code » A* Path Finder

Hi Hurik

I would prefer that my game's Entity class not be modified (by injection) by one pathfinding method. I may for example--have been considering in fact--want to use different pathfinders for different entities. Injection interferes with that.

Also--though I haven't dwelled a lot on that yet--I think that local navigation behaviour should not be so tightly coupled to (embedded in same file as) that of the pathfinder. Again, I may want different local navigation behaviours for different entities, independently of pathfinders.

Would you be willing to refactor your class a bit, perhaps by making astar a standalone object (or singleton) and by moving local nav (followPath) to a different class&file (PathFollower?) ?

hi alexandre,

i'm making this plugin for my use and that it is easy to use for newbies.

to take it and put it in standalone class should by done in one second. for example i'm using it in a parent class and extending my entities which need path finding from it.

this form i use is more to help beginners ....

to all: i update the plugin a bit and added an example to show how to use it ...
here the code: https://github.com/hurik/impact-astar-for-entities

hurik

Hi there

Got it and makes sense. A plug and play no-questions-asked component. I'll branch at some point for my own (off-the-path:) needs.

cheers
alex

Hello,
I got the pathfinder to work nicely but it does not get around ig.Entity.COLLIDES.FIXED entities. Is there any way around this?
Cheers, Emass

this entities aren't moving?

i would add same where after

map = ig.game.collisionMap.data; // line 30

something like this (haven't testet it, but it should work ...), put it in line 47

for (var i = 0; i < ig.game.entities.lenght, i++) { // Go throuth the entites list
 	if (ig.game.entites[i].collides == ig.Entity.COLLIDES.FIXED) { // Check if the entity is fixed
 		var x = ig.game.entites[i].pos.x / mapTilesize).floor(); // Get his x position on the collision map
		var y = ig.game.entites[i].pos.y / mapTilesize).floor(); // And y

		map[y][x] = 1; // Now the pathfinder think this tile is a wall!
	}
}

I think we're close! but they are still not moving. I logged x and y positions and they indeed show the fixed entity positions, but after map[y][x] = 1; they are not recognized as walls yet.

for (var i = 0; i < ig.game.entities.length; i++) { // Go throuth the entites list
     if (ig.game.entities[i].collides == ig.Entity.COLLIDES.FIXED) { // Check if the entity is fixed
        var x = (ig.game.entities[i].pos.x / mapTilesize).floor(); // Get his x position on the collision map
        var y = (ig.game.entities[i].pos.y / mapTilesize).floor(); // And y
        console.log(x);
        console.log(y);
        map[y][x] = 1; // Now the pathfinder think this tile is a wall!
    }
}

I have an other question I'm breaking my head over. It seems the entity size needs to be the same as the collision tilesize for this to work. My collision tilesize is set to 8 while my entity is 40x40. The entity travels over the calculated line but when the entity tries to pass a collision then it stops. Any ideas?

can you show me the code? or a demo?

for you second problem, not tested and not very fast:

for (var i = 0; i < ig.game.entities.lenght, i++) { // Go throuth the entites list
 	if (ig.game.entites[i].collides == ig.Entity.COLLIDES.FIXED) { // Check if the entity is fixed
 		// Now we check all the coordinates which the entity occupies an add them to the collision map
 		for (var x = ig.game.entites[i].pos.x; x < ig.game.entites[i].pos.x + ig.game.entites[i].size.x; x++) {
	 		for (var y = ig.game.entites[i].pos.y; x < ig.game.entites[i].pos.y + ig.game.entites[i].size.y; y++) {
	 			map[y  / mapTilesize).floor()][x  / mapTilesize).floor()] = 1;
	 		}
 		}
	}
}

Quote from hurik
https://github.com/hurik/impact-astar-for-entities

I was wondering how difficult would it be to modify things to only allow horizontal and vertical paths (no diagonal)?

[edit]

Not that anybody wants to know, but I what found works to accomplish the above is to add the very last line into Hurik's code, as such:

// Now create all 8 neighbors of the node
            for (var dx = -1; dx <= 1; dx++) {
                for (var dy = -1; dy <= 1; dy++) {
                    if (Math.abs(dx) == Math.abs(dy)) continue; // skips checking of diagonals

Quote from Joncom
I was wondering how difficult would it be to modify things to only allow horizontal and vertical paths (no diagonal)?
....

added your code in the new version. thanks. when you want credits please give me you realname. :)

We will continue this conversation over email. Thanks for the help.

@Emass, plz bake your code!

Hey Hurik,

First of all nice work with the A* plugin. It worked like a charm for me.

I'm still a newbie on the impactjs, and i'm starting it learning with the pacman game, something that I always wanted to build, so I would appreciate if you could help me :)

I downloaded your code, and plugged and play nicely. So the following code works fine to follow the pacman.

update: function() {
	this.parent();

	// get pacman entities (inmported on the top)
	var pacman = ig.game.getEntitiesByType( EntityPacman )[0];

	this.getPath(pacman.pos.x + pacman.size.x/2, pacman.pos.y + pacman.size.y/2);
	
	this.followPath(this.speed);
}

But I still have 2 questions.

1 - what would i have to do to have on the pacman game, to have the phantoms randomly follow pacman? I mean, they dont actually get to a point that will be overlaping each other in the same position and same place.

2 - When pacman get his power pill and the phantoms become eatable, what do i need to do with your code to them actually go in a different direction?

I mean, assuming this has to do with the pathfinder. I'm no genius and I would really appreciate you guys to help me out with this one. I have a lot to learn and I would love to learn some from you guys! :)



Ta,
Raf

Quote from Rafael

update: function() {
	this.parent();

	// get pacman entities (inmported on the top)
	var pacman = ig.game.getEntitiesByType( EntityPacman )[0];

	this.getPath(pacman.pos.x + pacman.size.x/2, pacman.pos.y + pacman.size.y/2);
	
	this.followPath(this.speed);
}

this.getPath(pacman.pos.x, pacman.pos.y);

this should be enought ...

Quote from Rafael
1 - what would i have to do to have on the pacman game, to have the phantoms randomly follow pacman? I mean, they dont actually get to a point that will be overlaping each other in the same position and same place.

i doesn't understand what the question is ...

Quote from Rafael
2 - When pacman get his power pill and the phantoms become eatable, what do i need to do with your code to them actually go in a different direction?

i would check in your phantom entity if pacman has eaten a pill and when that is the case i would change the pathfinder plugin. or make a new one for the phantoms. in which the pacman is threaten like a wall (read the thread for an example how it can be done) and the the new destination would be the edge which is most far away from pacman. and i woukd check every second or two a new possible path.

thats only one possible approach for that problem.

sorry for my very bad english, not much time at the moment ...

Hi Hurik,

Thanks for your reply!

Let me try to explain the first item.

I've applied the Path Finder to the phantom. But at one point they all meet at the same place and starting following the pacman together, at the same position.

Does that make sense?

I just found a great article about the pacman and how everything works.

This might help a lot of people out.
http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

Now i just need to apply it to my code! :) anyone wants to help lol! :)

Raf

Really excellent work hurik. I'm using your plugin for enemies. This has saved me a lot of work, I hope you keep working on and refining this plugin.

One thing I changed, when using this on enemies the first run seems to update the pos.x and pos.y of the enemy to the location of the player. In the followPath() I've used the following to stop it running one time.

if (this.path && !this.firstRun)

Then toggle it off in else...

this.firstRun = false;

You can check out my enemies on the second level of my project. It's not much of a game yet but I'm really pleased with the life your plugin has given my project.

http://project.dnsalias.com/

Hi Hurik,
Wonderful plugin thanks !!
I have 2 comments/questions :

1) I have a map with a tile size of 25 px and an entity with the size of : 60 * 30 px
The path is calculated withe the tiles size, and it happens a lot that my entity can't reach the destination point.

2) Is there a way to know the orientation of the path :
I mean, i want to change my entity's animation to simulate a walk.
If the path goes up, I will choose the anim : "walk_up", ...

thanks
Fabien

I am back ;
I have updated your followPath function to add a vraible : this.pathDirection

followPath: function(speed) {
        // Only do something if there is a path ...
        if (this.path) {
            // Did we reached a waypoint?
            if (((this.pos.x >= this.path[0].x && this.last.x < this.path[0].x) || (this.pos.x <= this.path[0].x && this.last.x > this.path[0].x) || this.pos.x == this.path[0].x) && ((this.pos.y >= this.path[0].y && this.last.y < this.path[0].y) || (this.pos.y <= this.path[0].y && this.last.y > this.path[0].y) || this.pos.y == this.path[0].y)) 
			{
				// hack fabien				
				this.pathDirection=null;
				
                // Was it the last waypoint?
                if (this.path.length == 1) {
                    // Stopp the movement and set the position
                    this.vel.x = 0;
                    this.pos.x = this.path[0].x;
                    this.vel.y = 0;
                    this.pos.y = this.path[0].y;										
                }
											
                // Erase the last waypoint
                this.path.splice(0, 1);

                // if it was the last nothing to do ...
                if (!this.path.length) {
                    this.path = null;
                    return;
                }
            }

			// Hack Fabien 
				
				
				
				// calculate orientation
				if(this.pos.x<this.path[0].x)
				{
					if(this.pos.y<this.path[0].y)
						this.pathDirection=8;
					else if(this.pos.y==this.path[0].y)
						this.pathDirection=7;
					else
						this.pathDirection=6;
				}
				else if(this.pos.x==this.path[0].x)
				{
					if(this.pos.y<this.path[0].y)
						this.pathDirection=5;
					else if(this.pos.y==this.path[0].y)
						this.pathDirection=0;
					else
						this.pathDirection=4;
				}
				else
				{
					if(this.pos.y<this.path[0].y)
						this.pathDirection=3;
					else if(this.pos.y==this.path[0].y)
						this.pathDirection=2;
					else
						this.pathDirection=1;
				}
							
			
			// fin hack
				
            // Calculate the speed if we move diagonal
            if (this.pos.x != this.path[0].x && this.pos.y != this.path[0].y) {
                speed = Math.sqrt(Math.pow(speed, 2) / 2);
            }

            // Move it in the right direction ...
            if ((this.pos.x >= this.path[0].x && this.last.x < this.path[0].x) || (this.pos.x <= this.path[0].x && this.last.x > this.path[0].x)) {
                this.vel.x = 0;
                this.pos.x = this.path[0].x;
            } else if (this.pos.x < this.path[0].x) {
                this.vel.x = speed;
            } else if (this.pos.x > this.path[0].x) {
                this.vel.x = -speed;
            }

            if ((this.pos.y >= this.path[0].y && this.last.y < this.path[0].y) || (this.pos.y <= this.path[0].y && this.last.y > this.path[0].y)) {
                this.vel.y = 0;
                this.pos.y = this.path[0].y;
            } else if (this.pos.y < this.path[0].y) {
                this.vel.y = speed;
            } else if (this.pos.y > this.path[0].y) {
                this.vel.y = -speed;
            }
        } else {
            // When there is no path, don't move ...
            this.vel.x = 0;
            this.vel.y = 0;
			
			// hack fabien			
			this.pathDirection=null;
        }
    },

I just have to check the pathDirection variable in my update function to choose my animation

Fabien

Just wanna chime in and give props to Hurik. Using his plugin I've managed to combine line of sight enemy fire and path finding within a top down level. My only minor knitpick is that enemies sometimes get stuck on corners of collision tiles when moving diagonally towards the player. Is there a modification I could use to resolve it?

had a lot to do and so very few time for the plugin ... but now i'm working on it again ...

@fabienM:
1. at the moment the plugin is only really usable for entities with the size of a tile. there would be an easy way to make it work with entities which have the double, triple, .. size of a tile. but your example would not be so easy ...

2. very nice idea ... can i add your code to the new version?

@bitmapshades:
have you an example? i have tested it a lot with diagonal movement and it was working for me ... but the followPath function isn't very good ... the real problem is that i have not found a way for a better approach of the problem ....

hi,

i updated the plugin:

1. improved the heuristic!
when diagonal movement is activated it uses the diagonal distance heuristic, when it is deactivated it uses the manhattan distance heuristic.
more information: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#heuristics-for-grid-maps

2. made the paths nicer!
added malus for 90 degress direction changes.
my opinion is that 45 degree is nicer than the 90 degree changes. but you can change the maluses in the astar-for.entities.js. for example if you make them the same value, it doesn't prefers one ...
Still testing for good malus values ...

3. added heading direction
Thanks FabienM for the idea! but i calculate it from the velocity and my variable has the name headingDirection.

// Heading direction values
// 1 4 6
// 2 0 7
// 3 5 8

edit: shit forget to mention FabienM in the credits ...

the plugin: https://github.com/hurik/impact-astar-for-entities
download: https://github.com/hurik/impact-astar-for-entities/zipball/master
demo: http://www.hurik.de/impact-astar-for-entities/

Very nice :)

Cool Hurik, I will test your new version and see if it resolves my issue. If not Ill try and post a screen grab if that's possible to do on this forum?

@bitmapshades:
send me a demo or the link to: andreas@giemza.net

just released version 1.0.0:
- the biggest new feature is that it now can take entities into account. i made this feature for my line of sight plugin (http://impactjs.com/forums/code/line-of-sight-plugin-with-entities-support) , so it was easy to add it for this plugin.
BUT this feature is more for fixed entities, that means entities that are not moving ...

- i improved the example! now it uses every feature. check the readme on github ...
to test the alignOnNearestTile feature click on a wall while moving (between to tiles!) and the entity will center on the nearest tile ...

the plugin: https://github.com/hurik/impact-astar-for-entities
download: https://github.com/hurik/impact-astar-for-entities/zipball/master
demo: http://www.hurik.de/impact-astar-for-entities/

Hey gang,

I can get a path to print, but as soon as I do followPath in my "monster" entity, the sprite disappears?!

http://prntscr.com/1eydqf

What could I be doing wrong?

        update: function() {
            // Update it every 2 seconds
            if(this.pathTimer.delta() > 0) {
                // Get the path to the player
                this.getPath(416, 302, true, ['EntityMonster'], []);

                this.pathTimer.reset();
            }

            // Walk the path
            this.followPath(this.speed);

            this.parent();
        },

Quote from ckcollab
I can get a path to print, but as soon as I do followPath in my "monster" entity, the sprite disappears?!

Log the troublesome monster's position and find out where he went. This should give you some clue as to what's going wrong...

PS - What is the size of your monster entity, a power of 2 perhaps?

Here's the size:

    EntityMonster = ig.Entity.extend({
        animSheet: new ig.AnimationSheet('media/effect_pow.png', 8, 8),
        size: {x: 8, y:8},
        offset: {x: 0, y: 0},
        flip: false,

Let's see what this outputs:

        update: function() {
            // ...
            console.log(this.pos);
            // ...
        },

Object {x: 64, y: 0}
Object {x: 64, y: 0}
Object {x: 64, y: 0}
Object {x: 64, y: 0}
Object {x: 64, y: 0}
... // for a while
Object {x: 64, y: -8}
Object {x: 64, y: -8}
Object {x: 64, y: -8} 
.... // for a while

No real movement, seems like it tries going backwards? I wonder what I'm missing!

Quote from ckcollab
No real movement, seems like it tries going backwards? I wonder what I'm missing!

Something seems off. When an entity "disappears" usually this means the position changed drastically or became NaN. First thing I'd do is find out where your entity is. Should {x: 64, y: 0} be visible?

Should {x: 64, y: 0} be visible?

I'm not sure, but it's definitely not visible at {x: 64, y: -8}