koobas.hobune.stream
Pathfinding function crashes Unity?
Hey, I've been trying to add this pathfinding function to my program, but when I run it, it just crashes. I've read other threads and this might be an infinite loop, but I don't see where it would be other than the recursion area (and it shouldn't break there because of the if-statement checking if it's out of bounds).
public void SetPath(Vector3 pos, Vector3 goal, Queue<Vector3> p, List<Vector3> visited, int cost) {
Debug.Log("checking " + pos);
//method which checks if the target tile is outside of the map
if (core.OutOfBounds((int)goal.x, (int)goal.z))
Debug.LogError("target tile " + goal + " is out of bounds!");
//if the current position isn't out of bounds and hasn't been visited
else if (!core.OutOfBounds((int)pos.x, (int)pos.z) && !visited.Contains(pos)) {
Debug.Log("pos is within the limits of the map");
//add tile to the visited list and path queue
visited.Add(pos);
p.Enqueue(pos);
//add tile movement cost to total path cost
cost += core.TileCost((int)pos.x, (int)pos.z);
//if the current position is the target tile and the path is shorter than the current one
if (pos == goal && cost < shortestPath) {
Debug.Log("pos is the target tile");
shortestPath = cost;
path = p;
}
//else, check tiles around
else {
SetPath(new Vector3(pos.x + 1, 0, pos.z), goal, p, visited, cost);
SetPath(new Vector3(pos.x, 0, pos.z + 1), goal, p, visited, cost);
SetPath(new Vector3(pos.x - 1, 0, pos.z), goal, p, visited, cost);
SetPath(new Vector3(pos.x, 0, pos.z - 1), goal, p, visited, cost);
}
}
}
Yes it is It's called recursion. Beautiful yet VERY confusing
Oh, I see. I see. When I wrote my own path finder I just used a while loop. $$anonymous$$uch less beautifu,l I suppose, but it did work as intended.
One question about this method... if the first SetPath() called by itself finds the goal, won't the other three SetPath() directions still be called unnecessarily?
Can you please show how this method is called as well as what shortestPath is initialized with?
Edit: Also how large is your map? If it's too large then Unity may not be able to search it all and can crash.
The map is 30x30 right now! I'm hoping to support bigger sizes, though.
Can you try it on a smaller map? $$anonymous$$aybe 5x5 to see if it still crashes? If it does then it's not a sizing issue.
it seems to me that the method of recursion used here to find a path is going to take a long time to find paths that are not located "north" of its position. You benefit from looking into A* (A Star) or another suitable method to find paths. I know that's what I did and it helped me fix the design problems I ran into when I tried this sort of thing. On a personal aside I found pathfinding to be a really fun program$$anonymous$$g challenge. Good luck with ur project!
Actually you're right. This algorithm will always return the first path to the goal even if it's the longest due to the visited list containing the goal node.
Your problem is that every time you SetPath in the new directions, and from there branch it again, and again, and again, each direction doesn't know about the "visited" list that you've filled in the other directions, which means that your program never knows that you've actually visited all positions.
You need to try each direction one at a time, and when you're done with that direction, pass the visited list down to the next direction.
The visited list is passed as a reference around throughout the recursion so all iterations will use the same list.
This also means that the same Queue p is being used all throughout the recursion.
SetPath(new Vector3(pos.x + 1, 0, pos.z), goal, p, visited, cost);
p should be replaced with new Queue(p) in order for it to create a new path for each direction the recursion takes. Otherwise it will return the first path that gets to the goal node.
I'm going to try this as soon as I can :) Thanks!
