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 ();
open.Add (start);
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);
}
closed.Add (current);
open.Remove(current);
int i = 1;
foreach(Node adjecent in current.adjecentNodes()) {
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
adjecent.g += current.g;
adjecent.h = getHeuristic(adjecent, goal);
adjecent.f = adjecent.g + adjecent.h;
//is it closed?
if (open.Contains(adjecent) == false) {
open.Add(adjecent);
adjecent.parent = current;
}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.parent = current.parent;
adjecent.g = current.parent.g + g;
adjecent.f = adjecent.g + adjecent.h;
}
}
}
i++;
}
}
return null;
}
Thanks in advance.
UPDATE:
Thanks for your reply guys, I was able to solve it though. There was apparently a problem with the heuristics calculation.