A* pathfinding help

am using inScope Studio's Tower Defense tutorial as a scaffold for a game I'm making, and have set up a working A* pathfinder to get from start to finish, but am having trouble setting up dynamic pathfinding for attacking units.

When triggered, the unit should generate a path from its location to the target's location, but for some reason the pathfinding script fails to return a path. While debugging I noticed that the the algorithm isn't able to detect deduce the best path, and it just ends up putting all the nodes in the closed list.

Here is my A* script and pertinent code:

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using UnityEngine;
5.  
6. public static class AStar
7. {
8. /// <summary>
9. /// A dictionary for all nodes in the game
10. /// </summary>
11. private static Dictionary<Point, Node> nodes;
12.  
13. /// <summary>
14. /// Creates a node for each tile in the game
15. /// </summary>
16. private static void CreateNodes()
17. {
18.     //Instantiates the dicationary
19.     nodes = new Dictionary<Point, Node>();
20.  
21.     //Run throughm all the tiles in the game
22.     foreach (TileScript tile in LevelManager.Instance.Tiles.Values)
23.     {
24.         //Adds the node to the node dictionary
25.         nodes.Add(tile.GridPosition, new Node(tile));
26.     }
27. }
28.  
29. /// <summary>
30. /// Generates a path with the A* algothithm
31. /// </summary>
32. /// <param name="start">The start of the path</param>
33. public static Stack<Node> GetPath(Point start, Point goal)
34. {
35.     if (nodes == null) //If we don't have nodes then we need to create them
36.     {
37.         CreateNodes();
38.     }
39.  
40.     //Creates an open list to be used with the A* algorithm
41.     HashSet<Node> openList = new HashSet<Node>();
42.  
43.     //Creates an closed list to be used with the A* algorithm
44.     HashSet<Node> closedList = new HashSet<Node>();
45.  
46.     // 1,2,3
47.  
48.     Stack<Node> finalPath = new Stack<Node>();
49.  
50.     //Finds the start node and creates a reference to it called current node
51.     Node currentNode = nodes[start];
52.  
53.     //1. Adds the start node to the OpenList
54.     openList.Add(currentNode);
55.  
56.     while (openList.Count > 0)//Step 10
57.     {
58.         //2. Runs through all neighbors
59.         for (int x = -1; x <= 1; x++)
60.         {
61.             for (int y = -1; y <= 1; y++)
62.             {
63.                 Point neighbourPos = new Point(currentNode.GridPosition.X - x, currentNode.GridPosition.Y - y);
64.  
65.                 if (LevelManager.Instance.InBounds(neighbourPos) && LevelManager.Instance.Tiles[neighbourPos].Walkable && neighbourPos != currentNode.GridPosition)
66.                 {
67.                     //Sets the initial value of g to 0
68.                     int gCost = 0;
69.  
70.                     if (Math.Abs(x - y) == 1)//Check is we need to score 10
71.                     {
72.                         gCost = 10;
73.                     }
74.                     else //Scores 14 if we are diagonal
75.                     {
76.                         if(!ConnectedDiagonally(currentNode, nodes[neighbourPos]))
77.                         {
78.                             continue;
79.                         }
80.                         gCost = 14;
81.                     }
82.  
83.                     //3. Adds the neighbor to the open list
84.                     Node neighbour = nodes[neighbourPos];
85.  
86.                     Debug.Log (gCost);
87.  
88.                     if (openList.Contains(neighbour))
89.                     {
90.                         if (currentNode.G + gCost < neighbour.G)//Step 9.4
91.                         {
92.                             neighbour.CalcValues(currentNode, nodes[goal], gCost);
93.                         }
94.                     }
95.                     else if (!closedList.Contains(neighbour))//9.1
96.                     {
97.                         openList.Add(neighbour); //9.2
98.                         neighbour.CalcValues(currentNode, nodes[goal], gCost);//9.3
99.  
100.                     }
101.  
102.                 }
103.             }
104.         }
105.  
106.         //5. & 8. Moves the current node from the open list to the closed list
107.         openList.Remove(currentNode);
108.         closedList.Add(currentNode);
109.  
110.         if (openList.Count > 0)//STEP 7.
111.         {
112.             //Sorts the list by F value, and selects the first on the list
113.             currentNode = openList.OrderBy(n => n.F).First();
114.         }
115.  
116.         Debug.Log ("currentNode: " + currentNode.GridPosition.X + ", " + currentNode.GridPosition.Y + "\ngoal: " + nodes[goal].GridPosition.X + ", " + nodes[goal].GridPosition.Y);
117.  
118.         if (currentNode == nodes[goal])
119.         {
120.             while (currentNode.GridPosition != start)
121.             {
122.                 finalPath.Push(currentNode);
123.                 currentNode = currentNode.Parent;
124.             }
125.  
126.             break;
127.         }
128.     }
129.  
130.  
131.     return finalPath;
132. }
133.  
134. private static bool ConnectedDiagonally(Node currentNode, Node neighbor)
135. {
136.     Point direction = neighbor.GridPosition - currentNode.GridPosition;
137.  
138.     Point first = new Point (currentNode.GridPosition.X + direction.X, currentNode.GridPosition.Y + direction.Y);
139.  
140.     Point second = new Point (currentNode.GridPosition.X, currentNode.GridPosition.Y + direction.Y);
141.  
142.     if (LevelManager.Instance.InBounds (first) && !LevelManager.Instance.Tiles [first].Walkable)
143.     {
144.         return false;
145.     }
146.  
147.     if (LevelManager.Instance.InBounds (second) && !LevelManager.Instance.Tiles [second].Walkable) {
148.         return false;
149.     }
150.  
151.     return true;
152. }
153. }
154.  
155. private void GeneratePathToTarget()
156. {
157.     Point targetLocation = new Point (target.transform.parent.GetComponent<TileScript> ().GridPosition.X, target.transform.parent.GetComponent<TileScript> ().GridPosition.Y);
158.  
159.     path = AStar.GetPath (this.GridPosition, targetLocation);
160. }
161.  
162. private void OnTriggerEnter2D(Collider2D other)
163. {
164.     if (other.tag == "Tower" && Attacker)
165.     {
166.         target = other.gameObject;
167.  
168.         GeneratePathToTarget ();
169.     }
170. }

Weirdly enough, I managed to get it working last week, but due to a massive github fail I'm having to rewrite everything.

 

Pretty sure the only way you're going to get any traction is to do some small data set debugging.

Make a small 2x2 or 3x3 map so you can "know" all the cells and what they should be in a trivial way, and then debug it to see what conditions its finding that leads it to put everything in the closed list. It sounds like a data problem, like the cost is coming out wrong and it gives up.

 

Thanks, I'll try that. Also weird, I tried switching the start and goal points when I call GeneratePathToTarget () and it spat out the correct path, but of course the locations were swapped so it doesn't really help. bleh

 

Well that's a clue... see if you have a bug in how the cost is determined. Each way should be the same.

 

Random thoughts:

That's how A* is supposed to work. The only way you can prove there is no path is to check every single node.

Your gCost function is a little weird. Its technically possible for a node to get through with a cost of 0.

Comments on line 83 don't match the code on line 84. Is this a potential bug? Otherwise just kill the comments. Comments you don't maintain are worse then no comments.

This isn't A*. A* is a directed graph search that uses a heuristic to guide the path. Unless you have hidden your heuristic inside the node class?

 

SOLVED the goal node was being excluded because it was marked as unwalkable

And yeah the heuristic is part of the Node class, my code def needs some cleaning up though (next on the to do )

 

Actual debugging thoughts.

The only way this will not return a path at all is if line 118 fails to return true. Which would align with this quote I just read.

 

Exactly, the conditional on line 65 was excluding the goal node so line 118 was never true.

Thanks for the help all!