• 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 EmanayStudios · May 19 at 12:39 PM · aipathfindingalgorithm

Using A* Algorithm for Pathfinding for a 2D platformer

I have problems properly setting up a Script for my AI Character in a 2D Platformer. It is supposed to be a little mobile game, which was the main reason I've decided not to use the A* Pathfinding project, which everyone refers to. To keep the project small and compact I decided to write the A* Algorithm myself, using Pathnode objects.

What I've done so far: I am setting the Start and End Nodes via Drag and drop in the Inspector and when I press a key, the path is beeing calculated and returned to the AIController. Now the AI follows the nodes and removes every reached Node from the path list and stops at the end of the path. alt text

Whats my problem: I want to update the target position every 5 seconds based on the AI and Player's position. The first time everything is okay. But on midway, when the path is recalculated Unity freezes for about 10 - 15 seconds and I get a OutOfMemoryException alt text Like you can see, from 14:23:41 to 14:23:54 nothing happens. Thats the point the editor freezes. when it unfreezes again, the AI does not work anymore. He just walks straight forward in one direction.

Here is my code for the Pathfinding:

 public void CreateAllPathNodes()
     {
         //This is called once only at Start
         NodeController[] nc = FindObjectsOfType<NodeController>();
         Debug.Log("NodeController anzahl " + nc.Length);
         foreach (NodeController node in nc)
         {
             PathNode pn = new PathNode(node.transform.position);
             pn.gCost = float.MaxValue;
             pn.parentNode = null;
             pn.CalculateFCost();
             pn.nodeIndex = node.nodeIndex;
 
             foreach (GameObject nn in node.NeighbourNodes)
             {
                 int index = nn.GetComponent<NodeController>().nodeIndex;
                 pn.neighbourNodeIndexes.Add(index);
             }
 
             allNodes.Add(pn);
 
             if(node.nodeIndex == GameStartNode.GetComponent<NodeController>().nodeIndex)
             {
                 startNode = pn;
                 startNode.nodeIndex = pn.nodeIndex;
             }
             if (node.nodeIndex == GameEndNode.GetComponent<NodeController>().nodeIndex)
             {
                 endNode = pn;
                 endNode.nodeIndex = pn.nodeIndex;
             }
         }
 
         foreach(PathNode pn in allNodes)
         {
             foreach(int indexes in pn.neighbourNodeIndexes)
             {
                 PathNode myPn = allNodes.Find(index => index.nodeIndex == indexes);
 
                 pn.neighbourNodes.Add(myPn);
 
             }
         }
     }
     public List<PathNode> FindPath()
     {
         
         Debug.Log("Startnode = " + startNode.ToString() + " and endnode = " + endNode.ToString());
         if (startNode == null || endNode == null)
         {
             //if start or endnode not setproperly just return null
             Debug.Log("startnode or endnode null. return null");
             return null;
         }
 
         //set openList and put startNode as first item. closedList is empty
         openList = new List<PathNode>() { startNode };
         closedList = new List<PathNode>();
 
         startNode.gCost = 0;
         startNode.hCost = CalculateHCost(startNode, endNode);
         startNode.CalculateFCost();
 
         while (openList.Count > 0)
         {
             PathNode currentNode = GetLowestFCostNode(openList);
 
             //when reached end
             if(currentNode == endNode)
             {
                 //setting null before returning for the next time using FindPath
                 openList = null;
                 closedList = null;
                 return CalculatePath(endNode);
             }
 
             openList.Remove(currentNode);
             closedList.Remove(currentNode);
             //select next node from neighbours
             foreach(PathNode neighbourNode in currentNode.neighbourNodes)
             {
                 if(closedList.Contains(neighbourNode)) { continue; }
 
                 float tentativeGCost = currentNode.gCost + CalculateHCost(currentNode, neighbourNode);
 
                 if(tentativeGCost < neighbourNode.gCost)
                 {
                     neighbourNode.parentNode = currentNode;
                     neighbourNode.gCost = tentativeGCost;
                     neighbourNode.hCost = CalculateHCost(neighbourNode, endNode);
                     neighbourNode.CalculateFCost();
 
                     if(!openList.Contains(neighbourNode))
                     {
                         openList.Add(neighbourNode);
                     }
                 }
             }
             
             
             
         }
 
         //if nothing found
         return null;
     }
 
     public List<PathNode> CalculatePath(PathNode endNode)
     {
         //creating local List for returning
         List<PathNode> pathList = new List<PathNode>();
         pathList.Add(endNode);
         PathNode currentNode = endNode;
         while(currentNode.parentNode != null)
         {
             pathList.Add(currentNode.parentNode);
             currentNode = currentNode.parentNode;
         }
         pathList.Reverse();
         /*foreach(PathNode pn in pathList)
         {
             Debug.Log(pn.ToString());
         }*/
         Debug.Log("CalculatePath done with " + pathList.Count + " items");
         return pathList;
     }

and this is the code for the AI Controller:

     void Update()
     {
         if (activeTarget != null && pathUpdateTimer >= 5f)
         {
             if(PathList != null) PathList.Clear();
             pathfinder.startNode = GetNearestNode(transform.position);
             pathfinder.endNode = GetNearestNode(activeTarget.transform.position);
             Debug.Log("EndNode was set: " + pathfinder.endNode.ToString());
             PathList = pathfinder.FindPath();
 
             pathUpdateTimer = 0;
 
         }
         else
         {
             if(!ic.isOnLadder)
             pathUpdateTimer += Time.deltaTime;
         }
 
         
         if (Input.GetKeyDown(KeyCode.X))
         {
             if (PathList != null) PathList = null;
             PathList = pathfinder.FindPath();
             /*for (int i = 0; i < PathList.Count; i++)
             {
                 Debug.Log(i + ". Position is index" + PathList[i].nodeIndex);
             }*/
         }
         if ( PathList != null && PathList.Count > 0)
         {
             
             //Debug.Log("pathlist nicht null" + PathList.Count);
             targetPosition = PathList[0].nodePosition;
             //Debug.Log(Vector2.Distance(transform.position, targetPosition));
             if (Mathf.Abs(transform.position.x - targetPosition.x) < 0.1f && Mathf.Abs(transform.position.y - targetPosition.y) < 1f)
             {
                 PathList.RemoveAt(0);
                 if(PathList.Count > 0)
                 {
                     targetPosition = PathList[0].nodePosition;
                 }
                 
                 
                 
             }
 
             if (Mathf.Abs(targetPosition.x - transform.position.x) < 1f && Mathf.Abs(targetPosition.y - transform.position.y) > 2f)
             {
                 if (ic.isInRangeOfLadder)
                 {
                     interactWithLadder();
                 }
             }
             float posdiff = 0f;
             if(!ic.isOnLadder && PathList.Count > 0)
             {
                 posdiff = Mathf.Sign(targetPosition.x - transform.position.x);
             }
             movementX = posdiff;
             ac.SetFloat("Speed", Mathf.Abs(movementX));
         }

the freeze happens only on the second findPath method call. Every other time, I get OutOfMemoryException, but the editor does not freeze, and the AI has no Pathlist anymore. can anyone maybe tell me where I am missing something?

screenshot-2022-05-19-141912.png (84.1 kB)
screenshot-2022-05-19-142724.png (97.6 kB)
Comment
Add comment
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

1 Reply

· Add your reply
  • Sort: 
avatar image
1
Best Answer

Answer by EmanayStudios · May 20 at 10:51 AM

In case someone faces the problem at any time, I finally managed to find the problem. I simply needed to reset the Node's g-, h-, and f-cost and the parent to it's default values. Else it gets stuck in a loop.

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

222 People are following this question.

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

Related Questions

Generate tiles along a path a certain distance before reaching end position 1 Answer

How can I get my pathfinding algorithm to know that it cant go through certain sides of tiles 1 Answer

how do I add abilities(Scripts/GameObjects) to my path finding agent 1 Answer

Start/End zigzag coverage region algorithm 1 Answer

How to connect generated points on a sphere? 0 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