Sign in to follow this  
Followers 0
afflicto

A* Pathfinding confusing.

2 posts in this topic

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
0

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.

0

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
0

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  
Followers 0