Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 13 Next capture
2021 2022 2023
1 capture
13 Jun 22 - 13 Jun 22
sparklines
Close Help
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
0
Question by GutoThomas · May 14, 2012 at 10:46 PM · pathfindingloop

Help with pathfinding function!

Hey everyone. Can someone help me poiting some errors in this Pathfinding function?

This is just breaking Unity.

 void AStar (Node initialNode, Node finalNode) {
     
             openList = closedList = new List<Node>();
             
             initialNode.G = 0;
             initialNode.H = initialNode.GetH( finalNode );
             
             openList.Add(initialNode);
         
             Node current = null;
         
             while(openList.Count != 0) {
             
                 current = openList[0];
                 closedList.Add(current);
             
                 if(current == finalNode) {
                 
                     reconstructPath(openList);
                     return;
                 
                 }
             
                 foreach(Node neighbor in current.Neighbors) {
                 
                     if(closedList.Contains(neighbor)) {
                     
                     continue;
                     
                     } else {
                     
                     if(!openList.Contains(neighbor)) {
                     
                         neighbor.defineParentNode(current);
                         neighbor.GetF(current, finalNode);
                         openList.Add(neighbor);
                         
                         } else {
                         
                             int neighborG = neighbor.GetG(current);
                         
                             if(neighborG < neighbor.G) {
                             
                                 neighbor.defineParentNode(current);
                                 neighbor.G = neighborG;
                             
                             }
                         }
                     }
                 }
             
                     openList.Sort(delegate(Node x, Node y) {
                         
                         return x.F.CompareTo(y.F);
             
             });
         }
     }

And here's the Node class :

 public class Node {
 
     public Vector3 position;
     public List<Node> Neighbors; // these are defined with a function that I omitted, but I'm sure that it doesn't return a empty list
     public Node parentNode;
     
     public int F, G, H;
     
     public Node (Vector3 Position, bool DefineNeighbors) {
         
         position = Position;
         
     }
     
     
     public int GetF (Node currentNode, Node finalNode) {
         
         this.G = GetG(currentNode);
         this.H = GetH(finalNode);
         
         this.F = this.G + this.H;
         
         return this.F;
         
     }
     
     public int GetH (Node finalNode) {
         
         H = (int)(Mathf.Abs(this.position.x - finalNode.position.x) + Mathf.Abs(this.position.z + finalNode.position.z));
         return H;
         
     }
     
     public int GetG (Node currentNode) {
         
         int distanceToCurrent = (int)(Mathf.Abs(this.position.x - currentNode.position.x) + Mathf.Abs(this.position.z + currentNode.position.z));
         G = currentNode.G + distanceToCurrent;
         
         return G;
         
     }
     
     
     public void defineParentNode(Node parent) {
         
         this.parentNode = parent;
         
     }
 
     
 }

If someone have the time to read the code and point something that could be make me get stuck in the loop, I'll appreciate!

Thanks from now!

Comment
Add comment · Show 7
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image Justin Warner · May 14, 2012 at 10:53 PM 0
Share

I'd recommend putting in some Debug.Log's in the loops and just see which one is getting called over and over again and not leaving?

avatar image GutoThomas · May 14, 2012 at 11:02 PM 0
Share

The problem is that Unity's breaking and I can't take a look at the console.

avatar image Justin Warner · May 14, 2012 at 11:17 PM 0
Share

By breaking, do you mean it just crashes completely and won't let you stop? Could then put counters and if the counter goes about (Huge number here), then you auto-close it. Then you can find the infinite that way too?

avatar image GutoThomas · May 14, 2012 at 11:25 PM 0
Share

I can't stop. I need to close Unity from task manager.

avatar image GutoThomas · May 14, 2012 at 11:28 PM 0
Share

Ins$$anonymous$$d of while(...) I did a for(int i=0;i<1000;i++) {... and after some seconds Unity continue the execution normally.

Show more comments

2 Replies

· Add your reply
  • Sort: 
avatar image
1

Answer by hathol · May 14, 2012 at 10:59 PM

You're never removing nodes from your open list. I think it should be

 current = openList[0];
 openList.removeAt(0);
 closedList.Add(current);
Comment
Add comment · Show 7 · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users
avatar image GutoThomas · May 14, 2012 at 11:06 PM 0
Share

I think that's not necessary because of the :

 if(current == finalNode) {

           reconstructPath(openList);
           return;

       }

The open list is necessary to build the path after the current node is equal do the final one.

Correct me if I'm wrong.

avatar image hathol · May 14, 2012 at 11:08 PM 0
Share

In addition, for reconstructing the path you don't need either of the lists, just the last node. Then you can just walk backwards by recursively looking at the nodes respective parent until you reach your start.

avatar image GutoThomas · May 14, 2012 at 11:10 PM 0
Share

Nice point hathol! I studied a lot of the theory and forget about this.

avatar image hathol · May 14, 2012 at 11:16 PM 0
Share

You are wrong ;)

a) You might not have a valid path -> infinite loop

b) It could happen that your current node is still the one with the lowest F cost (there might be an obstacle for example) after the loop, so it will always end up on top of the list -> infinite loop

avatar image GutoThomas · May 14, 2012 at 11:22 PM 0
Share

I tried with the line you suggest me but I didn't get any results. Is there some other logical error in the function or any other idea?

Show more comments
avatar image
0

Answer by Justin Warner · May 14, 2012 at 11:39 PM

Going through your code, I'll agree with Alex. You're never removing a node from the list, because of this, your count in the list is never reaching 0, therefore, never ending. Unity will always freeze/crash if an infinite loop happens, and in this case, it never once will leave the while loop, also shown by the example code you gave me.

Upon looking at the code you're using, assuming [this][1], you can see that the method current == finalNode, may be true, and may run that reconstructPath, but this does nothing to openList, which is ultimately the problem.

Some work arounds, that I don't know if it'll work, but may strike an idea from you:

  1. Make multi-[thread][2], so this works along with the main [thread][3] (Don't know if Unity does this, I assume it's possible though).

  2. Have another list, something similiar to backedUpOpenList, and put all the openList in it, then remove the header and do the while it's not null, then return so said list when done with w/e you need to be done with.

  3. Write your own A* program ;). You'll have more control, but no seriously, I think option 2 will work.

Hope this helps a bit, but yes, ultimately I believe Alex was right. =). Good luck! [1]: http://unifycommunity.com/wiki/index.php?title=AStarHelper [2]: http://answers.unity3d.com/questions/47732/about-multiple-thread.html [3]: https://www.google.com/search?client=opera&rls=en&q=unity3d+threads&sourceid=opera&ie=utf-8&oe=utf-8&channel=suggest#sclient=psy-ab&hl=en&client=opera&hs=IgQ&rls=en&channel=suggest&q=unity3d++multiple+threads&oq=unity3d++multiple+threads&aq=f&aqi=&aql=&gs_l=serp.3...4436.6972.0.7129.17.15.0.2.2.0.187.1617.9j6.15.0...0.0.gYeLB1SESyw&pbx=1&bav=on.2,or.r_gc.r_pw.,cf.osb&fp=59aa6895a8e2ed70&biw=1718&bih=990

Comment
Add comment · Share
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

7 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image

Related Questions

Loop crashing unity (pathfinding) 2 Answers

Logic question, unique path finding system 2 Answers

Pathfinding function crashes Unity? 1 Answer

Unity crashes when doing A* pathfinding loop 1 Answer

How to Implementing Morten Nobel-Jorgensen's A* Pathfinding 3 Answers


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges