View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# A* Pathfinding confusing.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1afflicto  Members

Posted 20 August 2014 - 10:17 PM

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, 21 August 2014 - 06:02 PM.

### #2C0lumbo  Members

Posted 21 August 2014 - 12:20 AM

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.

### #3KnolanCross  Members

Posted 21 August 2014 - 11:11 AM

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, 21 August 2014 - 03:13 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.