Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 12 Next capture
2021 2022 2023
1 capture
12 Jun 22 - 12 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 ambitiousmustard · Mar 13, 2017 at 08:56 AM · pathfindingscript erroralgorithm

A* Implementation broken?

I tried implementing [Wikipedia's version][1] of the A* pathfinding algorithm, but when I run it in Unity the object which the script is applied to does nothing and Unity ends up taking 15% of my CPU. I feel like this is a stack overflow error, but I can't tell where it breaks down. Here's the entirety of the script:

 public class Walker : MonoBehaviour {
 
     public int x { get; set; }
     public int y { get; set; }
     public MapView core { get; set; }
     public Node goal { get; set; }

     public float DistanceBetween(Node a, Node b) {
         return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
     }
 
     public List<Vector3> FindPath(Node goal) {
         Node start = new Node(x, y);
 
         List<Node> open = new List<Node>();
         open.Add(start);
         List<Node> closed = new List<Node>();
 
         Dictionary<Node, Node> cameFrom = new Dictionary<Node, Node>();
 
         Dictionary<Node, float> gScore = new Dictionary<Node, float>();
         gScore[start] = 0;
 
         Dictionary<Node, float> fScore = new Dictionary<Node, float>();
         fScore[start] = DistanceBetween(start, goal);
 
         while (open.Count != 0) {
             
             Node current = open[0];
 
 
             foreach (Node n in fScore.Keys)
                 if (fScore[n] < fScore[current])
                     current = n;
 
             if (current == goal)
                 return ReconstructPath(cameFrom, current);
 
             open.Remove(current);
             closed.Add(current);
 
             foreach (Node neighbor in Neighbors(current)) {
 
                 if (closed.Contains(neighbor))
                     continue;
                 float tempGScore = gScore[current] + DistanceBetween(current, neighbor);
 
                 if (!open.Contains(neighbor))
 
                     open.Add(neighbor);
 
                 else if (tempGScore >= gScore[neighbor])
                     continue;
 
                 cameFrom[neighbor] = current;
                 gScore[neighbor] = tempGScore;
                 fScore[neighbor] = gScore[neighbor] + DistanceBetween(neighbor, goal);
             }
         }
 
         return new List<Vector3>();
     }
 
     public List<Vector3> ReconstructPath(Dictionary<Node, Node> cameFrom, Node current) {
         List<Vector3> path = new List<Vector3>();
         path.Add(current.GetVector());
         while (cameFrom.ContainsKey(current)) {
             current = cameFrom[current];
             path.Add(current.GetVector());
         }
         return path;
     }
 
     public List<Node> Neighbors(Node current) {
         int currx = current.x;
         int curry = current.y;
 
         List<Node> neighbors = new List<Node>();
         neighbors.Add(new Node(currx, curry - 1));
         neighbors.Add(new Node(currx, curry + 1));
         neighbors.Add(new Node(currx - 1, curry));
         neighbors.Add(new Node(currx + 1, curry));
         return neighbors;
     }
 
     public virtual void SetStartCoords() {
         x = (int)transform.position.x;
         y = (int)transform.position.z;
     }
 }
 
 public class Node {
 
     public int x;
     public int y;
 
     public Node(int x, int y) {
         this.x = x;
         this.y = y;
     }
 
     public Vector3 GetVector() {
         return new Vector3(x, 0, y);
     }
 }

Could I be misusing the DistanceBetween() function incorrectly, since I'm using it to calculate both the gScore and fScore of each node? [1]: https://en.wikipedia.org/wiki/A*_search_algorithm

Comment
Add comment · Show 1
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 Salmjak · Mar 13, 2017 at 03:30 PM 0
Share

I suspect you need to override Equals() (so that instances of node that share the same coordinates are equal to eachother) since you create new nodes when adding neighbours they will never previously exist in the closed-list (for every neighbour open/closed.Contains() will always return false). (EDIT: Clarification. The default Equals()-implementation will compare references, this is not the behaviour you're after.)

In addition you should consider using other datastructures. Like a HashSet for the closed-list (O(1) Contains() ins$$anonymous$$d of O(n) Contains()), a PriorityQueue for the open-list (so looking up the node with best score isn't a O(n) operation).

0 Replies

· Add your reply
  • Sort: 

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

4 People are following this question.

avatar image avatar image avatar image avatar image

Related Questions

Unity 3.5: What is the definition of PLE algorithm? 1 Answer

A* optimization and path help 0 Answers

Preventing lines from overlapping 1 Answer

Help with A* algorithm 0 Answers

Making a list of list of nodes for Kruskal 2 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