next »

[Vampade]

Hello all, I'm making an A* pathfinding algorithm for my 2d top down game. To make it I followed a lot of tutorials, the ones I used the most are this and this. in the part where you must iterate through the adjacent nodes,

If T is already in the open list: Check if the F score is lower when we use the current generated path to get there. If it is, update its score and update its parent as well.

(this quote is from the 1st link, where is explained the pseudocode)

 I didn't understand the parent part where you must update the parent,to set it you simply do for example node.transform.parent=this_other_node.transform? I tried this but it didn't work, in fact in this part I set the nodes' parent to be the node with the lowest F cost in the open list but it didn't contain in its children only the nodes of the closed list,and also how would you know that a node is "right" and that it can be included in the path? When A* works in a map with a lot of obstacles it expands a lot its search area and consequently its closed list, but not all the nodes of the closed list once found the target will be in the path.

Here's an image:
The red nodes are the ones in the closed list,the green nodes are in the open list,the red square is the enemy and the blue is the player. Obviously not all the red nodes will be in the final path but only a part of them,so how could I set the parents so that they don't include the "useless" nodes in their children?



Here my code:

Code:

    // Update is called once per frame
    void Update()
    {
        //DEBUG colors the nodes
        if (open_list.Count > 0)
            foreach (GameObject go in open_list)
            {
                go.GetComponent<SpriteRenderer>().color = a;
            }

        if (closed_list.Count > 0)
            foreach (GameObject go in closed_list)
            {
                go.GetComponent<SpriteRenderer>().color = b;
            }
        //starts the AI
        if (Input.GetKeyDown(KeyCode.R))
        {
            start_ai = true;
        }
        //adds the start node to the open list
        my_node = actual_node.my_node;
        if (!open_list.Contains(my_node))
        {
            open_list.Add(my_node);
        }

        if (open_list.Count > 0 && start_ai)
        {
            //sorts by movement cost(here movement cost is F)
            open_list = open_list.OrderBy(x => x.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject)).ToList();
            my_node = open_list.First();
            //puts my node in the closed list
            if (!closed_list.Contains(my_node))
            {
                open_list.Remove(my_node);
                closed_list.Add(my_node);
            }

            //if we found a path
            if (closed_list.Contains(targ_node.my_node))
            {
                start_ai = false;
            }

            //finds the adjacent nodes
            FindAdjacentNodes(my_node);
            foreach (GameObject node in adjacent_nodes)
            {
                if (closed_list.Contains(node))
                {
                    continue;
                }
                if (!open_list.Contains(node))
                {
                    open_list.Add(node);
                    //here would you set the parent?
                    if (closed_list.Contains(node))
                    {
                        node.transform.parent = my_node.transform;
                    }
                }
                else
                {
                    //here where it says to update the F,how?
                    int tentative_g_score = open_list.IndexOf(node);
                    if (tentative_g_score+Dist(node,targ_node.my_node) < node.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject))
                    {
                        //node.transform.parent = my_node.transform;
                    }
                }
            }
        }
    }

That's all. So how would you set a parent here to find the final path? What should I change?
Thanks in advance guys!

[oahda]

Don't really have the time to give you a specific answer, but here's my working C# implementation from a while ago, feel free to try to find your answer in there or just steal the entire class, whichever you prefer. c:

http://pastebin.com/MKkTYSYT

[Vampade]

Thank you very much. I gave it a shot and I didn't understand that part

Code:

        private Node _parent = null;
        public Node parent
         {
            get { return _parent; }
            set
             {
                _parent = value;
                G = value.G + calculateCostGBetween(value.x, value.y, x, y);
             }
         }

value if I'm not wrong is a something that has to be assigned to be used after but I didn't understand how you used it in the rest of the code, for example in the while, but same for all the other parts where you use n.parent

Code:

        if (walk(nodeCurr) && nodeGoal != null)
         {
            // Trace backwards from final node.
            Node n = nodeGoal;
            while (n.parent != null)
             {
                path.Add(new Point<uint>(n.x, n.y));
                n = n.parent;
             }

how it works? Thank you very much for your help

[oahda]

value if I'm not wrong is a something that has to be assigned to be used after but I didn't understand how you used it in the rest of the code, for example in the while, but same for all the other parts where you use n.parent

Are you at all familiar with properties in C#? Otherwise I can understand the confusion. Do read up on it on my link there. The variable value is local to each set block and is not the same variable between different ones.

how it works? Thank you very much for your help

Each node has a reference to its parent node. This is a loop that starts at the final node and adds the position of each node to a list until it reaches the first node, which has no parent, and so that node's parent reference is null, which is the loop's condition, and so the loop would end at that point. At the end of each iteration, the variable n is set to the parent node of the current node. Is that clear enough?

I feel like it's a bit difficult to explain despite being simple once you know it. I don't know how advanced you are at C# or programming in general yet, since you seemed not to know about properties either, so do tell me if I'm using too much terminology and making too many assumptions.

[Vampade]

Ok,but how did you assign to the parent a node instead of another,how did your code choses it?

[Vampade]

I'm happy to say that I solved the problem and got the algorithm make a path :D.
I made a Pastebin if anyone is trying to make it and needs help. I didn't add a function to make the gameobject follow the path because I don't know how to make it ^_^' I tried to make a simple method in a for where if the gameobject position != the position of the node i it moves towards it. But it didn't work. So if you have any suggestions on how to make it don't hesitate to write, that so if it works I'll add it to the pastebin if anyone needs it