# A* Pathfinding confusing.

## Recommended Posts

SOLVED!

Hello! I'm trying to implement A* pathfinding for my RTS game, and I've got it working, but I'm confused with some parts of the algorithm.

Essentially, I don't know how to implement diagonal paths.

I followed this guide, while writing this script and I'm confused as to what I should do on line 96.

Here's the script.

A few notes, the current.adjecentNodes() method returns the 8 adjecent nodes (north, northeast, east etc).

Also, the i variable used in the foreach loop is simply used to detect diagonal adjecent nodes. Every 2nd node is a diagonal move.

public Path findPath(Node start, Node goal) {
if (start == null || goal == null || start == goal) return null;
open.Clear ();
closed.Clear ();

start.g = 0;
while(open.Count > 0) {

//get the lowest F node
Node current = null;
float f = 0;
foreach(Node node in open) {
if (current == null) {
current = node;
}else if (node.f < current.f) {
current = node;
}
}

//did we get the goal?
if (current == goal) {
return traceBack(start, goal);
}

open.Remove(current);

int i = 1;
if (adjecent != null && adjecent.walkable && !closed.Contains (adjecent)) {

int g = 10;
if (i % 2 == 0) {
g += 4;
}

//set g,h and f scores
//and parent

//is it closed?
if (open.Contains(adjecent) == false) {
}else {
//it's already on the open list
//check to see if this path to that square is better,
// using G cost as the measure.
// A lower G cost means that this is a better path.
// If so, change the parent of the square to the current square,
// and recalculate the G and F scores of the square.

float currentToThis = current.g + adjecent.g;
float prevToThis = current.parent.g + adjecent.g;
if (prevToThis < currentToThis) {
adjecent.g = current.parent.g + g;
}
}
}

i++;
}
}

return null;
}


UPDATE:
Thanks for your reply guys, I was able to solve it though. There was apparently a problem with the heuristics calculation.

Edited by afflicto

##### Share on other sites

Not sure what about the code around line 96, but line 81 looks dubious. I think you're giving a greater cost to non-diagonal nodes than you are to the diagonal ones when it should be the other way around.

##### Share on other sites

Basically it means:

Did I know how to get this point already?

- If I didn't (it was not in the open list yet), I add the point to the open list and set the cost to get to the point from the neighbor point we are currently checking.

- If I did (I had already added it to the open list), I discovered a new way to get to the point, I need to check if the new way is shorter than the former, and if it is, I update the cost and how I get there (by changing its parent).

Edited by KnolanCross

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• ### Forum Statistics

• Total Topics
628388
• Total Posts
2982403

• 10
• 9
• 16
• 24
• 11