koobas.hobune.stream
Problems with 2D A* Pathfinding
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! ;) Thank you in advance for your help.
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.
Thank you very much. I changed that piece of code and now is:
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 (node_manager.NodeGrid[i, j] == node_manager.NodeGrid[my_node_coord_x, my_node_coord_y])
{
if (i-1 >= 0)
{
left_node = node_manager.NodeGrid[i - 1, j];
AddAdjacentNodes(left_node);
Debug.Log("1");
}
if (i+1 < node_manager.n_nodes_x)
{
right_node = node_manager.NodeGrid[i + 1, j];
AddAdjacentNodes(right_node);
Debug.Log("2");
}
if (j+1 < node_manager.n_nodes_y)
{
upper_node = node_manager.NodeGrid[i, j + 1];
AddAdjacentNodes(upper_node);
Debug.Log("3");
}
if (j-1 >= 0)
{
down_node = node_manager.NodeGrid[i, j - 1];
AddAdjacentNodes(down_node);
Debug.Log("4");
}
}
}
}
}
It fixed the IndexOutOfRangeException but it executes only the 2nd and 3rd if even if I chose a node that is in the middle of the grid so it isn't out of range and it also gives me a NullReferenceException error at line 37,where it sorts the list based on the movement costs. I had tried to solve this NullReferenceExcetion by adding if(!open_list.Contains(null)) before it starts sorting the nodes but unity crashed and in the list there's still a null element, so I don't think it's right ahahah.
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
