Sign in to follow this  
afflicto

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 ();

	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.

Edited by afflicto

Share this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

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

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this