Search Unity

  1. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

[Request] AStar Pathfinding Chat Tutorial

Discussion in 'Community Learning & Teaching' started by raiden, Aug 4, 2009.

  1. raiden

    raiden

    Joined:
    Feb 8, 2009
    Posts:
    333
    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
     
  2. raiden

    raiden

    Joined:
    Feb 8, 2009
    Posts:
    333
    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. }
     
  3. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    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.
     
  4. raiden

    raiden

    Joined:
    Feb 8, 2009
    Posts:
    333
    Hi Andeeee, no I haven't, but I'm heading there right now, thanks so much. :)

    -Raiden
     
  5. Guybrush

    Guybrush

    Joined:
    Jul 8, 2009
    Posts:
    4
    Is unity developer magazine still active?
    It has shipped issue three for months now.
    How can we find the article about introduction in A*?
     
  6. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    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 ....
     
  7. raiden

    raiden

    Joined:
    Feb 8, 2009
    Posts:
    333
    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
     
  8. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    Raiden,

    no, not at the moment ....

    You are ready for C#?
    You can think object orientated?
     
  9. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    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).
     
  10. raiden

    raiden

    Joined:
    Feb 8, 2009
    Posts:
    333
    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
     
  11. HJP

    HJP

    Joined:
    Jul 8, 2009
    Posts:
    152
    no, not really… you can do it in each language. C# helps you to get the fastest solution.