Problems with 2D A* Pathfinding

Questions & Answers
1

Hello all, I’m making an A* pathfinding system for a 2d top down game using a grid of nodes. I have a 2d array that stores the coordinates of each node (NodeGrid wich is in NodeManager). The problem is that it doesn’t find the adjacent nodes of the node the enemy is on because the function that has to find them (FindAdjacentNodes) throws an IndexOutOfRangeException and also it doesn’t remove the node from the open list when it is adding it to the closed list even if I wrote to remove it lol. Here’s the code

    public class AIEn : MonoBehaviour {
        
        public List<GameObject> open_list = new List<GameObject>(); //list of the nodes that have to be taken  into account
        public List<GameObject> closed_list = new List<GameObject>(); //list of the already considered nodes
    
        public GameObject target;
        public GameObject my_node;
        GetClosestNode targ_node;//the target's closest node
        GetClosestNode actual_node;//the enemy's closest node at the start
        NodeManager node_manager;//it is the spawner of the nodes and contains the NodeGrid 2d array with all the nodes' coordinates
    
    void Start () {
    
            targ_node = target.GetComponent<GetClosestNode>();
            actual_node = gameObject.GetComponent<GetClosestNode>();
            node_manager = GameObject.FindGameObjectWithTag("nodes manager").GetComponent<NodeManager>();
        }
    	
    	// Update is called once per frame
    	void Update () {
    
            if(node_manager.FinishedNodeGrid)
            {
               //at the start it is the closest node
                my_node = actual_node.my_node;
    
                if(!open_list.Contains(my_node))
                {
                    open_list.Add(my_node);
                }
    
                if(open_list.Count>0)
                {
                    //with this the node with the least movement cost is the first in the open list
                    open_list.Sort(delegate (GameObject x, GameObject y)
                    {
                       return (x.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject).CompareTo(y.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject)));
                    });
                    my_node = open_list.First();
                    if(!closed_list.Contains(my_node) && open_list.Contains(my_node))
                    {
                        closed_list.Add(my_node);
                        open_list.Remove(my_node);
                    }
                    FindAdjacentNodes(my_node);
                }
    
            }
        }
    
        void FindAdjacentNodes(GameObject node)
        {
            int my_node_coord_x = node.GetComponent<GetNodeCoord>().NodeCoordX;
            int my_node_coord_y = node.GetComponent<GetNodeCoord>().NodeCoordY;
    
            GameObject left_node;
            GameObject right_node;
            GameObject upper_node;
            GameObject down_node;
    
            for (int i = 0;i<node_manager.n_nodes_x;i++)
            {
                for (int j = 0; j < node_manager.n_nodes_y; j++)
                { 
                   //if NodeGrid[i,j] == the coordinates of the enemy's node gets the adjacent ones
                    if (node_manager.NodeGrid[i, j] == node_manager.NodeGrid[my_node_coord_x, my_node_coord_y])
                    {
                        //the error is here 
                        left_node = node_manager.NodeGrid[i - 1, j];
                        right_node = node_manager.NodeGrid[i + 1, j];
                        upper_node = node_manager.NodeGrid[i, j + 1];
                        down_node = node_manager.NodeGrid[i, j - 1];
    
                        AddAdjacentNodes(left_node);
                        AddAdjacentNodes(right_node);
                        AddAdjacentNodes(upper_node);
                        AddAdjacentNodes(down_node);
                    }
                }
            }
        }
    
        void AddAdjacentNodes(GameObject adjacent_node)
        {
            if(!open_list.Contains(adjacent_node))
            {
                open_list.Add(adjacent_node);
            }
        }
    }

What’s wrong? How can I fix it? If you have any suggestions or better methods to make it don’t hesitate to tell me! :wink: Thank you in advance for your help.

2

left_node = node_manager.NodeGrid[i - 1, j];

What node is left of the left edge? There isn’t one correct? But you’re asking for one out of your array when i is zero.

What if i is 0? i - 1 will be -1, which is where your index out of range exception comes from. You need to check the value of i - 1, i + 1, and so on so you don’t look for an adjacent node when it would be out of range of the grid.

For example:

if (i - 1 >= 0)
{
   left_node = node_manager.NodeGrid[i - 1, j];
}

And of course you’ll not want to add left_node to your adjacent list if it doesn’t exist.

3

I’m happy to say that I found a solution. Instead of finding the adjacent nodes using the way above, we can cast from our node 4 raycasts in 4 different directions for a distance equal to the distance between the nodes,then we collect the nodes we got and BOOM! It works Here’s the complete code:
using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class AIEn : MonoBehaviour {
    
    public List<GameObject> open_list = new List<GameObject>(); //lista dei nodes che devono essere considerati per trovare il percorso
    public List<GameObject> closed_list = new List<GameObject>(); //lista dei nodes già considerati
    public GameObject target;
    public GameObject my_node;
    GetClosestNode targ_node;
    GetClosestNode actual_node;
    NodeManager node_manager;

    RaycastHit2D ray_dx;
    RaycastHit2D ray_sx;
    RaycastHit2D ray_up;
    RaycastHit2D ray_down;

    public Color a;
    public Color b;

    // Use this for initialization
    void Start () {

        targ_node = target.GetComponent<GetClosestNode>();
        actual_node = gameObject.GetComponent<GetClosestNode>();
        node_manager = GameObject.FindGameObjectWithTag("nodes manager").GetComponent<NodeManager>();
    }
	
	// Update is called once per frame
	void Update () {

        if(node_manager.FinishedNodeGrid)
        {
            //colors the nodes,just for debug
            foreach(GameObject go in open_list)
            {
               go.GetComponent<SpriteRenderer>().color = a;
            }
            foreach (GameObject go in closed_list)
            {
                go.GetComponent<SpriteRenderer>().color = b;
            }
            my_node = actual_node.my_node;

            if(!open_list.Contains(my_node))
            {
                open_list.Add(my_node);
            }

            //finchè l'open list non è vuota
            if(open_list.Count>0)
            {
                if (!open_list.Contains(null))
                {
                    //ordina i nodes in base al loro movement cost, in ordine decrescente
                    open_list.Sort(delegate (GameObject x, GameObject y)
                    {
                        return (x.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject).CompareTo(y.GetComponent<GetNodeMovementCost>().GetMovementCost(gameObject)));
                    });
                    my_node = open_list.First();
                }
                if(!closed_list.Contains(my_node) && open_list.Contains(my_node))
                {
                    closed_list.Add(my_node);
                    open_list.Remove(my_node);
                }
                FindAdjacentNodes(my_node);
            }
        }
    }

    void FindAdjacentNodes(GameObject node)
    {
        RaycastHit2D ray_dx = Physics2D.Raycast(node.transform.position, Vector2.right, node_manager.NodesDistance);
        RaycastHit2D ray_sx = Physics2D.Raycast(node.transform.position, -Vector2.right, node_manager.NodesDistance);
        RaycastHit2D ray_up = Physics2D.Raycast(node.transform.position, Vector2.up, node_manager.NodesDistance);
        RaycastHit2D ray_down = Physics2D.Raycast(node.transform.position, -Vector2.up, node_manager.NodesDistance);

        AddAdjacentNodes(ray_dx);
        AddAdjacentNodes(ray_sx);
        AddAdjacentNodes(ray_up);
        AddAdjacentNodes(ray_down);
    }

    void AddAdjacentNodes(RaycastHit2D ray)
    {
        if (ray.collider != null && ray.collider.gameObject.tag == "node" && !open_list.Contains(ray.collider.gameObject))
        {
            open_list.Add(ray.collider.gameObject);
        }
    }
}

Hope it helped someone