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 Obsdark · Dec 31, 2017 at 09:11 PM · c#tilemappathfindingastar

How can i take the right path in this pathfind algorithm?

I'm trying to make a pathfinding algorithm (A*) by myself to add it to my proyect, and i'm actualy making all the calculation sucessfully to meet the target tile BUT i can't find a way to actualy trim the route of the unused tiles to get the actual path to use.

The failing part seem to be the assignation of the parent node, the one who actualy make the route, i'm not exactly getting right the asignation of this and, as such, when you recalculate the cost so to obtain the optimal path doesn't actualy make a conected line back to the starting tile.

Let me show you an image of how is searching the tiles and then the code, so you can have a better idea of the problem, this is what i have so far:

Picture of the exploration algorithm after finish the search to find the ending tile: alt text

Picture of the backtracking problem:

alt text

 private void Start()
     {
         CreateGrid();
         
         foreach (Node item in PathFinding_GetClosedListReady()/*PathFinder_SetStream()*/)
         {
             WorldController.Instance.world.Tiles[item.x, item.y].ChangeSprite();
         }
         //TileChangeForUpdate();
 
         //PathFinding_GetClosedListReady();
     }
 
     public List<Node> PathFinder_SetStream()
     {
         List<Node> posiblePath = PathFinding_GetClosedListReady();
         Node currentNode = posiblePath.Where(i => i.prefab.name == this.NodeWhereStanding(Seeked).prefab.name).Select(i => i).FirstOrDefault();
         Node endingNode = posiblePath.Where(i => i.prefab.name == this.NodeWhereStanding(Seeker).prefab.name).Select(i => i).FirstOrDefault();
         Node SelectedNode = new Node (999999999,999999999);
         List<Node> newList = new List<Node>();
         List<Node> suplementaryList = new List<Node>();
         int LowestAmmount;
         do
         {
             LowestAmmount = 999999999;
             suplementaryList = Path_Controller.Instance.NodesOfArround(currentNode).Intersect(posiblePath).ToList(); //
             newList.Add(currentNode);
             foreach (Node node in suplementaryList)
             {
                 //node.UpdateValues(currentNode, endingNode);
                 if(node.FGcostHCost < LowestAmmount)
                 {
                     SelectedNode = node;
                     SelectedNode.parentNode = currentNode;
                 }
             }
             //newList.Add(currentNode);
             //currentNode = currentNode.parentNode;
             currentNode = SelectedNode;
             Debug.Log(SelectedNode.prefab.name);
         }
         while (currentNode.x != endingNode.x && currentNode.y != endingNode.y);
         return newList;
     }
     
     private List<Node> PathFinding_GetClosedListReady()
     {
         Tile firstTile = WorldController.Instance.world.Tiles[this.TileWhereStanding(Seeker).X, this.TileWhereStanding(Seeker).Y];
         Tile endingTile = WorldController.Instance.world.Tiles[this.TileWhereStanding(Seeked).X, this.TileWhereStanding(Seeked).Y];
         Node currentNode = NodesPositions[firstTile.X, firstTile.Y];
         currentNode.UpdateValues(firstTile, endingTile);
 
         List<Node> OpenList = new List<Node>();
         List<Node> ClosedList = new List<Node>();
 
         OpenList.Add(currentNode);
         float LowestF;
         Node selectedNode = currentNode;
         ClosedList.Add(currentNode);
         
         do
         {
             OpenList.AddRange(Path_Controller.Instance.NodesOfArround(currentNode));
             LowestF = 999999999;
             foreach (Node node in OpenList)
             {
                 if (node.x == endingTile.X && node.y == endingTile.Y)
                 {
                     node.parentNode = currentNode;
                     selectedNode = node;
 
                     OpenList.Remove(selectedNode);
                     ClosedList.Add(selectedNode);
                     return ClosedList; //Aquí returnaré la ClosedList listo para hacer el algoritmo final O un objeto que retorne y posea la closed y open list
                 }
 
                 node.UpdateValues(firstTile, endingTile);
 
                 if (node.FGcostHCost < LowestF && !ClosedList.Any(i => i.prefab.name == node.prefab.name))
                 {
                     LowestF = node.FGcostHCost;
                     node.parentNode = currentNode;
                     selectedNode = node;
                 }
             }
 
             OpenList.Remove(selectedNode);
             ClosedList.Add(selectedNode);
             currentNode = selectedNode;
             //Debug.Log(currentNode.prefab.name);
         }
         while (OpenList.Count > 0);
         return ClosedList;
     }



Here is the methods than i use to get the Heurisitcs of my nodes, is a node method, i suspect the problem can be there too:

 public void UpdateValues(Tile StartingTile, Tile EndingTile)
     {
         try
         {
             GstartingNode = (StartingTile.X - this.x) + (StartingTile.Y - this.y);//(StartingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (StartingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
             HendNode = (EndingTile.X - this.y) + (EndingTile.Y - this.y);//(EndingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (EndingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
 
             GstartingNode = GstartingNode < 0 ? GstartingNode * -1 : GstartingNode;
             HendNode = HendNode < 0 ? HendNode * -1 : HendNode;
 
             FGcostHCost = GstartingNode + HendNode;
         }
         catch (Exception ex)
         {
             Debug.Log("UpdateValues(Tile StartingTile, Tile EndingTile) Error: " + ex.ToString());
             Debug.Log("G: " + GstartingNode + "\nH: " + HendNode + "\nF: " + FGcostHCost);
             Debug.Log(Path_Controller.Instance.worldToPathfind.Tiles[this.x, this.y].ToString());
             Debug.Log(StartingTile.ToString());
             Debug.Log(EndingTile.ToString());
         }
     }
 
     public void UpdateValues(Node StartingNode, Node EndingNode)
     {
         try
         {
             GstartingNode = (StartingNode.x - this.x) + (StartingNode.y - this.y);//(StartingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (StartingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
             HendNode = (EndingNode.x - this.y) + (EndingNode.y - this.y);//(EndingTile.tile_GO.transform.position.x - this.tileNode.tile_GO.transform.position.x) + (EndingTile.tile_GO.transform.position.y - this.tileNode.tile_GO.transform.position.y);
 
             GstartingNode = GstartingNode < 0 ? GstartingNode * -1 : GstartingNode;
             HendNode = HendNode < 0 ? HendNode * -1 : HendNode;
 
             FGcostHCost = GstartingNode + HendNode;
         }
         catch (Exception ex)
         {
             Debug.Log("UpdateValues(Node StartingTile, Node EndingTile) Error: " + ex.ToString());
         }
     }



If you need more details, information or have suggestions to improve the question, please let me know.




Thanks a lot

backtracking.png (63.9 kB)
algorithmsofar.png (92.9 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

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

420 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 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

A* Pathfinding Turn Off Rotation 2 Answers

A* endless loop 0 Answers

A* pathfinding generating new path when created new obstacle 0 Answers

A* Pathfinding AB Path usage without Seeker 1 Answer

Multiple Cars not working 1 Answer


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