Forums » Help » Could use some help with my pathfinding scripts

I felt like a full A* algorithm was overkill so I was writing one for my specific application. The code is for an npc wanting to chase a target.
So I tried to comment my code so its followable let me know if I need to explain something...
I'll add collision detecting later I was having problems with it not returning collisions when I checked a collision with a perfect corner from 45 degrees

This while statement actually gives an infinite loop I dont know why...
...
moved code to next post

I added collision detection and updated the code the script runs but it doesn't find a path yet. not sure why.

// start initializing varriables
tile_size = 55;
node = new Array(49);
bestnode=null;
/*  VISUAL MAP OF THE 49 NODES
 *  entity is always in node 24
 *  
 *  00, 01, 02, 03, 04, 05, 06,   
 *  07, 08, 09, 10, 11, 12, 13,
 *  14, 15, 16, 17, 18, 19, 20,
 *  21, 22, 23, 24, 25, 26, 27,
 *  28, 29, 30, 31, 32, 33, 34,
 *  35, 36, 37, 38, 39, 40, 41,
 *  42, 43, 44, 45, 46, 47, 48,
 *  
 */
// set the center square to the first parent because all moves are from this square
// g is essentially how far the entity has traveled to get to the node
// h is how far is left straight line to the target
parent = 24;
thisnode = parent;
for (j=0;j<49;j++){
	node[j]={"open":null}
}
node[parent]={
	"parent":null,
   "pos":{"x":this.pos.x,"y":this.pos.y},
   "open":true,
   "g":0,
   "h":Math.max(Math.abs(this.pos.x-targets[i].pos.x), Math.abs(this.pos.y-targets[i].pos.y)),
   "f":null
}
node[thisnode].f = node[thisnode].g+node[thisnode].h
// end of initializing varriables
//check if parent node is target
//while there are open nodes
repeat=true;
while (repeat==true){
   for (y=-1;y<=1;y++){
      for (x=-1;x<=1;x++){
			thisnode = parent+(7*y)+x;
			if (thisnode>=0&&thisnode<49){
				console.log(parent);
				res = ig.game.collisionMap.trace( node[parent].pos.x , node[parent].pos.y, x*tile_size, y*tile_size, 1,1);
				if (res.collision.x == true || res.collision.y == true){
					node[thisnode].open=false;            
				}
				skip=false;
				if (node[thisnode].open==true&&node[thisnode].g < node[parent].g+tile_size){
					skip=true;
				}
				if (node[thisnode].open!=false&&skip==false){
					node[thisnode] ={
						"parent":parent,
						"pos":{"x":node[parent].pos.x+(x*tile_size),"y":node[parent].pos.y+(y*tile_size)},
						"open":true,
						"g":node[parent].g+tile_size,
						"h":null,
						"f":null
					};
					node[thisnode].h =Math.max(Math.abs(node[thisnode].pos.x-targets[i].pos.x), Math.abs(node[thisnode].pos.y-targets[i].pos.y)),
					node[thisnode].f = node[thisnode].g+node[thisnode].h
					if (bestnode==null){
						bestnode = thisnode;
					}
					if (node[thisnode].f < node[bestnode].f){
						bestnode=thisnode
					}
				}
			}
		}
   }
	node[parent].open = false;
	parent=bestnode //set best node as next parent
	bestnode=null;
	repeat=false;
   for (j=0;j<49;j++){
		if (node[j].open==true){
			repeat=true;
			parent=j;
		}
	}
}
debugger

To be honest I haven't read through all your code as I am in transit right now on a work break. But I wanted to share my initial thoughts so I don't forget them.

If it thinks the first path is best.... could you set some variable on NPC, like: bestNodeScore = -9999.

Then add a scoring system to your nodeTracing, and force it to find all possible paths not just quit when it finds the first.

// pseudo code

while ( thereArePathsToTrace) {
    if ( currentPathScore > this.bestNodeScore ) {
    	this.bestNodeScore = currentPathScore;
    	this.bestFollowPath = theCurrentPathIteratedOver;
    }
}

Maybe this helps? Or I could be completely off base.

@jswart thanks for the idea I tweaked things a lot not sure exactly what fixed that but this code works to get from A to B but its pathing is terrible sometimes taking twice as long as the best path.

Edit: The problem seems to be related to collision detection espectially when moving diagonally.
this.movelimit is a new varriable I added so I can have some entities that cannot move as far as they can path in one turn wether that reason is terrain just part of the entity's stats.

node = new Array(49);
bestnode=null;
parent = 24;
thisnode = parent;
for (j=0;j<49;j++){
	node[j]={"open":null}
}
node[parent]={
	"parent":null,
   "pos":{"x":this.pos.x,"y":this.pos.y},
   "open":true,
   "g":0,
   "h":Math.max(Math.abs(this.pos.x-targets[i].pos.x), Math.abs(this.pos.y-targets[i].pos.y)),
   "f":null
}
node[thisnode].f = node[thisnode].g+node[thisnode].h
repeat=true;
while (repeat==true){
   for (y=-1;y<=1;y++){
      for (x=-1;x<=1;x++){
			thisnode = parent+(7*y)+x;
			if (thisnode>=0&&thisnode<49){
				if (Math.abs(x)==Math.abs(y)){
					res = ig.game.collisionMap.trace( (node[parent].pos.x+HEX_SIZE), node[parent].pos.y, 0, y*HEX_SIZE, 1, 1);
				}else{
					res = ig.game.collisionMap.trace( node[parent].pos.x , node[parent].pos.y, x*HEX_SIZE, y*HEX_SIZE, 1,1);
				}
				if (res.collision.x == true || res.collision.y == true){
					node[thisnode].open=false;            
				}
				skip=false;
				if (node[thisnode].open==true&&node[thisnode].g < node[parent].g+HEX_SIZE){
					skip=true;
				}
				if (node[thisnode].open!=false&&skip==false){
					node[thisnode] ={
						"parent":parent,
						"pos":{"x":node[parent].pos.x+(x*HEX_SIZE),"y":node[parent].pos.y+(y*HEX_SIZE)},
						"open":true,
						"g":node[parent].g+HEX_SIZE,
						"h":null,
						"f":null
					};
					node[thisnode].h =Math.max(Math.abs(node[thisnode].pos.x-targets[i].pos.x), Math.abs(node[thisnode].pos.y-targets[i].pos.y)),
					node[thisnode].f = node[thisnode].g+node[thisnode].h
					if (bestnode==null){
						bestnode = thisnode;
					}
					if (node[thisnode].f < node[bestnode].f){
						bestnode=thisnode;
					}
				}
			}
		}
   }
	node[parent].open = false;
	parent=bestnode //set best node as next parent
	bestnode=null;
	repeat=false;
   for (j=0;j<49;j++){
		if (node[j].open==true){
			repeat=true;
			parent=j;
		}
		if (node[j].h==0){
			mobpathx = new Array();
			mobpathy = new Array();
			trace = j;
			while (node[trace].parent!=null){
				mobpathx.push(node[trace].pos.x);
				mobpathy.push(node[trace].pos.y);
				trace = node[trace].parent
			}
			mobpathx.reverse();
			mobpathy.reverse();
			while (mobpathx.length > this.movelimit){
				mobpathx.pop();
			   mobpathy.pop();
			}
			
			//go until move limit
			console.log('mobmove',mobpathx, mobpathy)
		}
	}
}

Hey Shawn,

I would love to help, but I have to be honest I can't really understand your code. Not because there is anything wrong with it,.. but because I didn't write it and don't have any sense of reference.

Can you explain what the code is doing, sort of walk me through the logic so I can get a better idea of what it is supposed to be doing and how I could offer advice on possible ideas.

I'll also make a new game and work on some AI pathing myself to better develop my own personal solution.

Would also be interested in some of this code being elaborated on.

@fulvio the varaible names are based on A* algorithm common terminology

http://www.policyalmanac.org/games/aStarTutorial.htm

g = how far this node has traveled
h=how far is left (estimated)
parent = the node that was traveled from
open = if false this node has been fully checked and there is no need to revisit it