A* scanning extra nodes?

Mustafa Al-Sibai · 2015-05-03T15:45:24

Hello everyone, A while ago I implemented my own A* pathfinding algorithm, and it works great. But I feel like my implementation of the A* is wrong. I feel like my algorithm is scanning extra nodes that should not be scanned. Here is a picture of my program. The yellow square is the starting node, the green square is the target node, the black squares are solid non-walkable nodes, the blue squares are the final path, the white squares are the squares that were not scanned and the red squares are the nodes that were in the closed list. And here is another website that has A* implemented. As you can see this website algorithm is scanning less nodes than my program. I don't know how and I don't know why. This is the website. Can you guys please help. I don't know how to fix this. And here is my code:- namespace Pathfinding { public class Node { internal Node Parent; public Vector2 Position; internal bool Diagonal; internal bool Passable = true; internal int H_Value; internal int G_Vaule; internal int F_Vaule { get { return H_Value + G_Vaule; } private set { } } public Node(Vector2 Position) { this.Position = Position; } } } namespace Pathfinding { public class Astar { public List<Node> OpenList; public List<Node> ClosedList; List<Node> NonePassable; Vector2 GridSize; Node CurrentNode, StartingNode, TargetNode; bool ReachedTarget; const int G_Score = 10; const int Diagonal_G_Score = 14; Map map; public Astar() { OpenList = new List<Node>(); ClosedList = new List<Node>(); NonePassable = new List<Node>(); ReachedTarget = false; GridSize = new Vector2(15, 15); } void FindAllNeighborNodes() { Node RightNeighbor = new Node(new Vector2(CurrentNode.Position.X + 1, CurrentNode.Position.Y)); GetNeighbor(RightNeighbor); Node LeftNeighbor = new Node(new Vector2(CurrentNode.Position.X - 1, CurrentNode.Position.Y)); GetNeighbor(LeftNeighbor); Node TopNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y - 1)); GetNeighbor(TopNeighbor); Node BottomNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y + 1)); GetNeighbor(BottomNeighbor); } void GetNeighbor(Node Neighbor) { if (Neighbor.Position.X < GridSize.X && Neighbor.Position.X >= 0 && Neighbor.Position.Y >= 0 && Neighbor.Position.Y < GridSize.Y) { IsNodePassable(Neighbor); if (Neighbor.Passable) { if (!ClosedList.Any(node => node.Position == Neighbor.Position)) { if (!OpenList.Any(node => node.Position == Neighbor.Position)) { Neighbor.Parent = CurrentNode; Neighbor.G_Vaule = CurrentNode.G_Vaule + G_Score; Neighbor.H_Value = GetHeuristicCost(Neighbor); OpenList.Add(Neighbor); } else if (OpenList.Any(node => node.Position == Neighbor.Position)) { if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score < CurrentNode.G_Vaule) { int NodeIndex = OpenList.FindIndex(node => node.Position == Neighbor.Position); OpenList[NodeIndex].Parent = CurrentNode; OpenList[NodeIndex].G_Vaule = CurrentNode.G_Vaule + G_Score; } } } } } } void IsNodePassable(Node node) { if (NonePassable.Any(nonePassableNodes => nonePassableNodes.Position == node.Position)) node.Passable = false; else node.Passable = true; } int GetHeuristicCost(Node node) { Vector2 Distance = new Vector2(Math.Abs(TargetNode.Position.X - node.Position.X), Math.Abs(TargetNode.Position.Y - node.Position.Y)); return (int)(Distance.X + Distance.Y) * 10; } Node GetMinF_Value() { int Lowest_F_Value = OpenList.Min(node => node.F_Vaule); int Index = OpenList.FindIndex(node => node.F_Vaule == Lowest_F_Value); return OpenList[Index]; } public List<Vector2> GetFinalPath() { List<Vector2> FinalPath = new List<Vector2>(); while(true) { if (CurrentNode.Parent != null) { FinalPath.Add(CurrentNode.Position); CurrentNode = CurrentNode.Parent; } else break; } FinalPath.Reverse(); return FinalPath; } public void FindPath(Map map, Node StartingNode, Node TargetNode) { this.map = map; this.StartingNode = StartingNode; this.TargetNode = TargetNode; for (int i = 0; i < map.CollisionObjects.Count; i++) NonePassable.Add(new Node(map.CollisionObjects[i].Position)); OpenList.Add(StartingNode); while(OpenList.Count > 0) { CurrentNode = GetMinF_Value(); OpenList.Remove(CurrentNode); ClosedList.Add(CurrentNode); FindAllNeighborNodes(); if(CurrentNode.Position == TargetNode.Position) { ReachedTarget = true; break; } } } } }

Artificial Intelligence Programming

Started by FantasyVII March 26, 2015 03:04 PM

22 comments, last by polyfrag 8 years, 11 months ago

polyfrag

2,504

March 28, 2015 07:07 PM

Try logging every node that's checked. Especially the node that's not supposed to be checked according to the website you mentioned.

Yours definitely looks like Manhattan heuristic, but the one from the website looks more like Euclidean distance, because not every node within a rectangle formed by the goal and start has an equal chance of being checked. So it might be a matter of the order in which you expand your search or use of diagonal moves. Try using something other than Manhattan distance.

[edit] Seems like you don't allow diagonal moves, which would explain why yours makes the square shape. It would approach the goal quicker if you allowed diagonals.

ferrous

6,164

March 30, 2015 05:21 PM

I give up. I have been working on this for almost a week and I'm no where close to solving this..... I don't know what to do.....

Also, sometimes it's best to just toss it on the backlog. Your current implementation works, it has a bug, but it's not gamebreaking. Log it, give it a priority, and return to it after a while. I've come back to a problem at a later time with a fresh perspective and sometimes that can help if I've been blocked and pulling my hair out.

WozNZ

2,010

April 30, 2015 09:03 PM

This if statement is never true....


if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score < CurrentNode.G_Vaule)

Off top of my head I think the check should be

if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score > CurrentNode.G_Vaule)

I need to check my a* code when I get home tonight but don't you want to subst the value in the open list if the old path for the location is more costly than the one you have. Given that the nodes hold the route back your test is saying replace the cheaper one with the more costly?

EDIT: Just done some digging and am sure you always want the cheapest version of a node for a given location while your condition will swap out a cheaper for a more expensive node. Not run your code but thing you should start there

polyfrag

2,504

May 03, 2015 03:45 PM

It's only counting the distance to the goal, and not the distance traversed. What is G_score and H_score measured in?


                            Neighbor.Parent = CurrentNode;
                            Neighbor.G_Vaule = CurrentNode.G_Vaule + G_Score;
                            Neighbor.H_Value = GetHeuristicCost(Neighbor);
                            OpenList.Add(Neighbor);



        const int G_Score = 10;
        const int Diagonal_G_Score = 14;

The heuristic H_score might be 100 times bigger.

[edit] Nevermind.

The F_score is basically = distance to goal + distance from start, and since it's Manhattan, any cell within the square formed by the start and goal might be picked. Any path taken to get 3 squares right and 2 squares up is equally valid.

There are several equally-low F_score squares in the open list, so it's just a matter of whether you choose the ones farthest to the back, or the front. Yours chooses the ones closest to the back (i.e., the ones that are the oldest). Which makes it closer to breadth first search, then depth first search.

This is actually pretty important. If you use a min binary heap, nodes pushed to the top that are equal or less will stay and the top and thus be the first popped.

A* scanning extra nodes?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* scanning extra nodes?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines