1 Replies - 654 Views - Last Post: 07 August 2015 - 05:05 PM Rate Topic: -----

#1 max67412  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 32
  • Joined: 05-August 15

A* path finding algorithm in JavaScript problem

Posted 05 August 2015 - 08:27 PM

Hi,

I've been racking my brain trying to solve this for the last 24 hours.

I am trying to implement A* path-finding into my browser game and I have re-searched several examples but I have still been getting successful, yet sketchy results. The paths are being found and the enemy moves to my character however, sometimes the path is very strange and only works well when the enemy is only 1 or 2 sum's away.

I am not asking anyone to re-write this for me, I just want someone to tell me where I have gone wrong and a kick in the right direction.

Example: enemy co-ords are Y:56, X:43, player co-ords are Y:56, x:46, enemy should move to Y:56, X:44 however sometimes it moves to Y:56, X:42.

function findPath(id, toPos, fromPos)
{
	fpID = id;

	tposY = toPos["y"];
	tposX = toPos["x"];
	fposY = fromPos["y"];
	fposX = fromPos["x"];
	
	current[fpID] = {};
	openset[fpID] = {};
	openset[fpID]["y"+fposY+",x"+fposX] = {"y":fposY,"x":fposX,"parent":-1,"f":9999,"g":0,"h":0,};
	closedset[fpID] = {};
	pathFound[fpID] = false;
	
	while(Object.keys(openset[fpID]).length > 0)
	{
		//get lowest f cost
		lf = getLowestF();
		current[fpID] = jQuery.extend(true, {}, openset[fpID][lf]);
		
		//add to closedset and delete from openset
		closedset[fpID][lf] = jQuery.extend(true, {}, openset[fpID][lf]);
		delete(openset[fpID][lf]);
		
		//get neighbours
		neighbours = getNeighbours({"y":current[fpID]["y"],"x":current[fpID]["x"]});
		for(var n in neighbours)
		{
			n_obj = neighbours[n];
			n_y = n_obj["y"];
			n_x = n_obj["x"];
			
			//check if tile is walkable
			if(mapCommand("isTileWalkable",{"pos_y":n_y,"pos_x":n_x}) == true)
			{
				//check if neighbour is not in openset and closedset
				if((!openset[fpID][n]) && (!closedset[fpID][n]))
				{
					parentName = "y"+current[fpID]["y"]+",x"+current[fpID]["x"];
					
					//calculate f,g and h
					n_g = current[fpID]["g"] + 10;
					n_h = getH(n_y,n_x,tposY,tposX);
					n_f = n_g + n_h;
					
					//if neighbour is the target tile, path is found
					if((n_y == tposY) && (n_x == tposX))
					{
						pathFound[fpID] = true;
						closedset[fpID][n] = {"y":n_y,"x":n_x,"parent":parentName,"f":n_f,"g":n_g,"h":n_h,};
						openset[fpID] = {};
					}
					else
					{
						//add neighbour to openset
						openset[fpID][n] = {"y":n_y,"x":n_x,"parent":parentName,"f":n_f,"g":n_g,"h":n_h,};
					}
				}
				else
				{
					//if neighbour is in closedset or openset
					if(closedset[fpID][n])
					{
						if(current[fpID]["g"] < closedset[fpID][n]["g"])
						{
							parentName = "y"+current[fpID]["y"]+",x"+current[fpID]["x"];
							closedset[fpID][n]["parent"] = parentName;
						}
					}
					else if(openset[fpID][n])
					{
						if(current[fpID]["g"] < openset[fpID][n]["g"])
						{
							parentName = "y"+current[fpID]["y"]+",x"+current[fpID]["x"];
							openset[fpID][n]["parent"] = parentName;
						}	
					}
				}
			}
		}
		//end search is path is found
		if(pathFound[fpID] == true)
		{
			break;	
		}
	}
	
	if(pathFound[fpID] == true)
	{
		pathFound[fpID] = false;
		path[fpID] = [];
		p_current = "y"+tposY+",x"+tposX;
		
		//reverse and sort path tiles
		while(Object.keys(closedset[fpID]).length > 0)
		{
			parent = closedset[fpID][p_current]["parent"];
			py = closedset[fpID][parent]["y"];
			px = closedset[fpID][parent]["x"];
			
			if((closedset[fpID][parent]["y"] == fposY) && (closedset[fpID][parent]["x"] == fposX))
			{
				//closedset[fpID] = {};
				return path[fpID];
			}
			else
			{
				path[fpID].unshift({"y":py,"x":px});
				p_current = parent;
			}
		}
		
	}
	else
	{
		console.log("failed");
	}
	
}

function getLowestF()
{
	lowestF = 10000;
	lowestID = -1;
	for(var i in openset[fpID])
	{
		t = openset[fpID][i];
		if(t["f"] < lowestF)
		{
			lowestID = i;
		}
	}
	
	return lowestID;
}

function getH(posY,posX,toPosY,toPosX)
{
	//heuristic
	diffY = Math.abs(toPosY - posY) * 10;
	diffX = Math.abs(toPosX - posX) * 10;
	diff = diffY + diffX;
	return diff;
}

function getNeighbours(c)
{
	c_y = c["y"];
	c_x = c["x"];
	c_neighbours = {};
	c_dirs = {
		0:{"y":-1,"x":0},
		1:{"y":1,"x":0},
		2:{"y":0,"x":-1},
		3:{"y":0,"x":1},
	};
	
	for(a=0;a<4;a++)
	{
		n_y = c_y + c_dirs[a]["y"];
		n_x = c_x + c_dirs[a]["x"];
		
		//check neighbours aren't outside screen window
		if((playerPos["y"] >= (n_y-7)) && (playerPos["y"] <= (n_y+7)) && (playerPos["x"] >= (n_x-7)) && (playerPos["x"] <= (n_x+7)))
		{
			c_propname = "y"+n_y+",x"+n_x;
			c_neighbours[c_propname] = {"y":n_y,"x":n_x};
		}
	}

	return c_neighbours;
}



Many thanks,
Max

Is This A Good Question/Topic? 1
  • +

Replies To: A* path finding algorithm in JavaScript problem

#2 max67412  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 32
  • Joined: 05-August 15

Re: A* path finding algorithm in JavaScript problem

Posted 07 August 2015 - 05:05 PM

Solved.

For anyone that is interested in how i solved this, I simply forgot to change the F score in the getlowestF() function which resulted in fetching the last node in the open list rather than the node with the lowest f score.

a very embarrassing mistake but...we all make them now and again.

Max
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1