[Request] AStar Pathfinding Chat Tutorial

I've gone to web sites, studied code examples, re-written my code 3-5 times, and like many others, cannot grasp the concepts of what should happen in a pathfinding code such as AStar.

I am aware that AngryAnt has a system already, and I believe it is a great system, but I am really after learning AStar, not re-using someone else's code.

I am asking if anyone would be willing to host a chat class and give everyone who would like to participate the fundamentals of learning AStar.

I would also like for anyone who would be interested in this "chat class" to respond to this post.


I think it's a great idea, the class can be hosted through the IRC channel, a time and date can be given by the instructor, the project to use can be d/l here: http://www.geartechgames.com/GearTech_Games/Beginning_a_Project/Beginning_a_Project.html.

I am aware that there are many versions of pathfinding, and many different ways to go about AI. I'm not looking to learn anything else but the fundamentals of AStar, once we (me and anyone else who wants to learn) have this understanding, it allows us to use this to expand our AI programming ideas.

Thanks for your help.

-Raiden

 

Well, with great disappointment, in response to this request I am giving up on learning this algorithm for now, due to the simple fact that after at least 2 months of trial and error, I still cannot successfully write this code to work as it should in a 3d environment.

I am posting my last attempt of scripting code for this, honestly it's a very crude attempt at coding this, it has limited comments, and still does not work correctly, not to mention it takes some time to build the path due to the number of traces required to find clear directions.

If you like, comment on the code, correct it, or feel free print it off and run it through a shredder just because that's (imo) about how crappy I think it is.

Really bummed out with the fact I just can't grasp this, even after all the references I have gone through. Would be nice if the AStar guru's out there would post a step by step video, then possibly I would get it.

Thanks to all who listened to me go on and on about this (those on the IRC channel). If perhaps I ever decide to come back to this someday and "DO" figure it out, you can bet your next dollar I'll make a tutorial that will resolve anyone's attempt's at writing this for themselves.

Thanks

-Raiden

Code (csharp):

1.  
2. // simple a* search and output routine
3. var pathNode : GameObject; // this is our parent node to all points to search from
4. var searchNode : GameObject; // our default open list node
5. var startNode : GameObject; // this is home
6. var targetNode : GameObject; // this is the destination
7. var moveCost : int = 2;
8.  
9. // visual aids booleans
10. var clearSearchNodes : boolean = true;
11. var clearPathNodes : boolean = false;
12. var clearStartNode : boolean = false;
13. var clearTargetNode : boolean = false;
14.  
15. // visual debug text
16. var debugTexts : GUIText[];
17.  
18. private var maxPathNodes : int = 100;
19. private var parentToPointTraceDistance : float = 2.0; // our distance to trace to our points around the parent
20. private var nodeObjects : Array = new Array();
21. private var initParentToPointDistance : Array = new Array(8); // our parent to trace point
22. private var closedListIndexPos : int = 0;
23. private var pathDoneIndex : int = 0;
24. private var pathFound : boolean = false;
25. private var closedListNodeLength : int = 0;
26. private var pathBuilt : boolean = false;
27.  
28. // our node data class
29. class nodeData {
30.     var fCost : int = 0; // our surrounding total costs
31.     var gCost : int = 0; // our move costs
32.     var hCost : float = 0.0; // our hueristic costs
33.     var node : GameObject;
34. }
35.  
36. private var openList : nodeData[];
37. private var jsOpenList = new Array();
38. private var closedList = new Array();
39. private var openListCtr : int = 0;
40.  
41. function Start() {
42.     if (startNode.transform.position.y != targetNode.transform.position.y) {
43.         Debug.Log("Path cannot be obtained! Your Start and Target heights are different!");
44.         return;
45.     }
46.    
47.     if (clearStartNode == true)
48.         startNode.GetComponent(MeshRenderer).enabled = false;
49.     if (clearTargetNode == true)
50.         targetNode.GetComponent(MeshRenderer).enabled = false;
51.        
52.     // initialize our search direction array, this is the distance and directions to search around our parent node
53.     initParentToPointDistance[0] = Vector3(0, 0.1, 1) * parentToPointTraceDistance;
54.     initParentToPointDistance[1] = Vector3(1, 0.1, 1) * parentToPointTraceDistance;
55.     initParentToPointDistance[2] = Vector3(1, 0.1, 0) * parentToPointTraceDistance;
56.     initParentToPointDistance[3] = Vector3(1, 0.1,-1) * parentToPointTraceDistance;
57.     initParentToPointDistance[4] = Vector3(0, 0.1,-1) * parentToPointTraceDistance;
58.     initParentToPointDistance[5] = Vector3(-1,0.1,-1) * parentToPointTraceDistance;
59.     initParentToPointDistance[6] = Vector3(-1,0.1, 0) * parentToPointTraceDistance;
60.     initParentToPointDistance[7] = Vector3(-1,0.1, 1) * parentToPointTraceDistance;
61.        
62.     var dis : float = Vector3.Distance(targetNode.transform.position, startNode.transform.position);
63.     openList = new nodeData[8];
64.     for (i = 0; i < 8; i++) {
65.         openList[i] = new nodeData();
66.     }
67.        
68.     openList[0].gCost = 0;
69.     openList[0].hCost = Mathf.RoundToInt(dis);
70.     openList[0].fCost = Mathf.RoundToInt(openList[0].hCost);
71.     openList[0].node = Instantiate(pathNode, startNode.transform.position, startNode.transform.rotation);
72.        
73.     // since we know this is our first addition to openList, we go ahead an add it to closedList
74.     closedList.Add(new nodeData());
75.     closedList[0].gCost = openList[0].gCost;
76.     closedList[0].hCost = Mathf.RoundToInt(openList[0].hCost);
77.     closedList[0].fCost = Mathf.RoundToInt(openList[0].fCost);
78.     closedList[0].node = openList[0].node;
79.        
80.     while(pathDoneIndex == 0) {
81.        
82.         pathBuilt = false;
83.        
84.         for (openListCtr = 0; openListCtr < 8; openListCtr++) {
85.             Debug.Break();
86.             AddToOpenList(openListCtr);
87.             if (pathFound == true) {
88.                 break;
89.             }
90.             yield;
91.         }
92.        
93.         if (pathDoneIndex == 0  pathFound == false) {
94.             var index = ReturnLowestfCostInIndex(openList);
95.             closedListIndexPos++;
96.             // assign that as our next index on the closedList
97.             AddToClosedList(closedListIndexPos, index);
98.         }
99.    
100.         yield;
101.     }
102.  
103. }
104.  
105. function DestroyOpenListNodes() {
106.     for (i = 0; i < openList.length; i++) {
107.         GameObject.Destroy(openList[i].node);
108.     }
109. }  
110.  
111. function AddToClosedList(clIndex : int, olIndex : int) {
112.     closedList.Add(new nodeData());
113.     closedList[clIndex].gCost = openList[olIndex].gCost;
114.     closedList[clIndex].hCost = Mathf.RoundToInt(openList[olIndex].hCost);
115.     closedList[clIndex].fCost = Mathf.RoundToInt(openList[olIndex].fCost);
116.     closedList[clIndex].node = Instantiate(pathNode, openList[olIndex].node.transform.position, Quaternion.identity);
117.    
118.     //GameObject.Destroy(openList[olIndex].node);
119.        
120.     DestroyOpenListNodes();
121. }
122.  
123. function ReturnLowestgCostInIndex(searchArray : Array) {
124.     // find the lowest fCost in the array index
125.     var lowest = 99999;  
126.     var index = -1;  
127.     for (n = 0; n < searchArray.length; n++) {     
128.         if (searchArray[n].gCost < lowest) {
129.             lowest = searchArray[n].fCost;
130.             index = n;
131.         }
132.     }  
133.    
134.     return index;
135. }
136.  
137. function ReturnLowestfCostInIndex(searchArray : Array) {
138.     // find the lowest fCost in the array index
139.     var lowest = 99999;  
140.     var index = -1;  
141.     for (n = 0; n < searchArray.length; n++) {     
142.         if (searchArray[n].fCost < lowest) {
143.             lowest = searchArray[n].fCost;
144.             index = n;
145.         }
146.     }  
147.    
148.     return index;
149. }
150.  
151. function AddToOpenList(index : int) {
152.     // so now we search it's neighbors
153.     var endPos : Vector3 = new Vector3(Mathf.RoundToInt(closedList[closedListIndexPos].node.transform.position.x),0.1,
154.                                            Mathf.RoundToInt(closedList[closedListIndexPos].node.transform.position.z)) + initParentToPointDistance[index];
155.         var dis = Vector3.Distance(targetNode.transform.position, Vector3(Mathf.RoundToInt(endPos.x),endPos.y,Mathf.RoundToInt(endPos.z)));
156.         Debug.DrawLine(closedList[closedListIndexPos].node.transform.position, endPos, Color.red);
157.         //print(endPos);       
158.         if (Vector3.Distance(targetNode.transform.position, endPos) < parentToPointTraceDistance) {
159.             print("We've found our goal");
160.             closedList[closedListIndexPos].node = targetNode;
161.             for (j = 0; j < closedList.length; j++) {
162.                 if (closedList[j].node != null) {
163.                     closedListNodeLength = j;
164.                 }
165.             }
166.             DestroyOpenListNodes();
167.             pathDoneIndex = closedListIndexPos;
168.             pathFound = true;
169.             return;
170.         }
171.        
172.         if ((index % 2) == 0)
173.             moveCost = 10;
174.         else
175.             moveCost = 14;
176.        
177.         print(jsOpenList.length);          
178.         jsOpenList.Add(new nodeData());
179.         print(jsOpenList.length);
180.        
181.         if (!Physics.Linecast(Vector3(closedList[closedListIndexPos].node.transform.position.x,0.1,closedList[closedListIndexPos].node.transform.position.z),endPos)) {
182.             if (closedListIndexPos > 0) { // this just means we have added the first round of position to the open list
183.                
184.                 if ((Mathf.RoundToInt(endPos.x) != Mathf.RoundToInt(closedList[closedListIndexPos-1].node.transform.position.x))
185.                 ||  (Mathf.RoundToInt(endPos.z) != Mathf.RoundToInt(closedList[closedListIndexPos-1].node.transform.position.z))) { // if our x or y is not our previous closed list node
186.                     print("We are not on the closed list");
187.                     var tempIndex : int = 0;
188.                     //print(jsOpenList.length);
189.                     for (i = 0; i < jsOpenList.length; i++) { // now we have to search our total open list
190.                         //print(i);
191.                         //print(endPos.x + " " + endPos.z + " " + jsOpenList[i].node.transform.position.x + " " + jsOpenList[i].node.transform.position.z);
192.                         if (jsOpenList[i].node != null) {
193.                             if ((Mathf.RoundToInt(endPos.x) == Mathf.RoundToInt(jsOpenList[i].node.transform.position.x))
194.                               (Mathf.RoundToInt(endPos.z) == Mathf.RoundToInt(jsOpenList[i].node.transform.position.z))) { // if we have found a node already on our open list
195.                                 print("You are on the openList");
196.                                 //print(endPos.x + " " + endPos.z + " " + jsOpenList[i].node.transform.position.x + " " + jsOpenList[i].node.transform.position.z);
197.                                 tempIndex = i; // record the index                         
198.                                 break;
199.                             }
200.                         }
201.                         else {
202.                             print(i);
203.                         }
204.                     }
205.                    
206.                     if (tempIndex == 0) { // if none are on the open list, we add it to the open list
207.                         print("We are not on the open list");
208.                         //print(openList.length);
209.                         print(index);
210.                         //print(jsOpenList.length);
211.                         openList[index].hCost = Mathf.RoundToInt(dis);
212.                         openList[index].gCost = moveCost; // temporary until we have found better ways to build our path
213.                         openList[index].fCost = Mathf.RoundToInt(openList[index].gCost + openList[index].hCost);
214.                         openList[index].node = Instantiate(searchNode,endPos,Quaternion.identity);   
215.                        
216.                         jsOpenList[index].hCost = openList[index].hCost;
217.                         jsOpenList[index].gCost = openList[index].gCost;
218.                         jsOpenList[index].fCost = openList[index].fCost;
219.                         jsOpenList[index].node = openList[index].node;                 
220.                     }
221.                     else {// if a searched position is on the open list
222.                         if (jsOpenList[tempIndex].gCost < (moveCost + closedList[closedListIndexPos].gCost)) { // see if the move cost is better than what it takes to move from our last closed list pos
223.                             //print("It is better to go to jsOpenList[tempIndex] than it is to go to closedList[closedListIndexPos]");
224.                             //print(moveCost + closedList[closedListIndexPos].gCost + " " + openList[index].gCost);
225.                            
226.                             // add the parent node with the bigger move costs to our total open list (so we do not go back to it)
227.                             var tempPos = jsOpenList[tempIndex].node.transform.position; // get our current parent position we are searching form
228.                                                        
229.                             // add to our index our previous parents data (we do this because we make sure we make this a prent node again)
230.                             jsOpenList[index].node = Instantiate(searchNode,closedList[closedListIndexPos].node.transform.position,Quaternion.identity);
231.                             print(jsOpenList[index].node.transform.position);
232.                             jsOpenList[index].hCost = closedList[closedListIndexPos].hCost;
233.                             var updatedgCost = closedList[closedListIndexPos].gCost + moveCost; // this should equal 20
234.                             jsOpenList[index].gCost = updatedgCost;
235.                             jsOpenList[index].fCost = closedList[closedListIndexPos].fCost + updatedgCost;
236.                            
237.                             GameObject.Destroy(closedList[closedListIndexPos].node); // now destroy the parent node (we are updating with a better to move to parent)
238.                            
239.                             //  now we replace our better node data to our current closedList position we are searching from                           
240.                             closedList[closedListIndexPos].node  = Instantiate(pathNode,tempPos,Quaternion.identity);
241.                             closedList[closedListIndexPos].hCost = Vector3.Distance(targetNode.transform.position, Vector3(Mathf.RoundToInt(tempPos.x), 0.1, Mathf.RoundToInt(tempPos.z)));
242.                             closedList[closedListIndexPos].gCost = jsOpenList[tempIndex].gCost;
243.                             closedList[closedListIndexPos].fCost = Mathf.RoundToInt(jsOpenList[tempIndex].gCost + jsOpenList[tempIndex].hCost);
244.                            
245.                             //jsOpenList.length = jsOpenList.length - 1;
246.                            
247.                             print("back to main loop");
248.                             openListCtr = -1;
249.                             return;
250.                         }
251.                         else {
252.                             print("Our cost is greater");
253.                         }                          
254.                     }                          
255.                 }
256.                 else {
257.                     print("We did find a cost on the closed list");
258.                     foundOnClosed = true;
259.                     openList[index].node = null;
260.                     openList[index].fCost = 99999;
261.                     openList[index].hCost = 99999;
262.                     openList[index].gCost = 99999;
263.                    
264.                     jsOpenList[index].hCost = openList[index].hCost;
265.                     jsOpenList[index].gCost = openList[index].gCost;
266.                     jsOpenList[index].fCost = openList[index].fCost;
267.                     jsOpenList[index].node = openList[index].node;
268.                 }  
269.             }
270.             else {
271.                 openList[index].hCost = Mathf.RoundToInt(dis);
272.                 openList[index].gCost = moveCost; // temporary until we have found better ways to build our path
273.                 openList[index].fCost = Mathf.RoundToInt(openList[index].gCost + openList[index].hCost);
274.                 openList[index].node = Instantiate(searchNode,endPos,Quaternion.identity);
275.                
276.                 jsOpenList[index].hCost = openList[index].hCost;
277.                 jsOpenList[index].gCost = openList[index].gCost;
278.                 jsOpenList[index].fCost = openList[index].fCost;
279.                 jsOpenList[index].node = openList[index].node;
280.             }                                              
281.         }  
282.         else {
283.             print("We hit a wall");
284.             openList[index].node = null;
285.             openList[index].fCost = 99999;
286.             openList[index].hCost = 99999;
287.             openList[index].gCost = 99999;
288.            
289.             jsOpenList[index].hCost = openList[index].hCost;
290.             jsOpenList[index].gCost = openList[index].gCost;
291.             jsOpenList[index].fCost = openList[index].fCost;
292.             jsOpenList[index].node = openList[index].node;         
293.         }
294.        
295.         debugTexts[index].text = "Cost: " + jsOpenList[index].fCost + " Move: " + jsOpenList[index].gCost + " Dist: " + jsOpenList[index].hCost;
296. }

 

Have you seen my A* tutorial in the first two issues of Unity Developer magazine? It's a very gentle introduction, but it should give you what you need to know for games work.

 

Hi Andeeee, no I haven't, but I'm heading there right now, thanks so much.

-Raiden

 

Is unity developer magazine still active?
It has shipped issue three for months now.
How can we find the article about introduction in A*?

 

I take your code, changed, optimized and supplemented that for my testproject with 320 waypoints. I get > 1000 fps in my testlevel with 1440 connections ... without a dll ....

 

HJP, would you be willing to share or possibly write a tutorial up on your modifications you made to andeeee's pathfinding system?

I've got the first 2 issues on the way now, but anything else you can add would make learning even better.

Thanks

-Raiden

 

Raiden,

no, not at the moment ....

You are ready for C#?
You can think object orientated?

 

As mentioned in the article, the main candidate for optimisation is the priority queue. The example code uses a very simple queue for ease of explanation, but it is highly inefficient. A very easy way to improve the speed considerably is to reverse the order of the queue so that the head of the queue is at the last element of the array (and you also add new items by searching backwards from the end).

 

HJP, I've only dabbled with C# some, but I don't think I would have a problem transitioning to it from JS.

Is t really necessary to know C# to write an AStar pathfinding system?

-Raiden

 

no, not really… you can do it in each language. C# helps you to get the fastest solution.