- Home /
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.
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 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?
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.
Your answer
Follow this Question
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