# A* path finding algorithm in JavaScript problem

Page 1 of 1

## 1 Replies - 681 Views - Last Post: 07 August 2015 - 05:05 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=379811&amp;s=e42e2e44c3c1c5923afd426ee87ddb62&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 max67412

Reputation: 3
• 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
{
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

Reputation: 3
• 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