Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
2 replies to this topic

#1 afflicto   Members   -  Reputation: 127

Like
0Likes
Like

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

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


Sponsor:

#2 C0lumbo   Crossbones+   -  Reputation: 2498

Like
0Likes
Like

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.



#3 KnolanCross   Members   -  Reputation: 1362

Like
0Likes
Like

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.



PARTNERS