A* Pathfinding confusing.

Started by
1 comment, last by KnolanCross 9 years, 8 months ago

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.

Advertisement

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.

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).

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

This topic is closed to new replies.

Advertisement