Help! Pathfinding
Hey guys, i'm trying to create a game tile based 2D, top view, with random map generating. Well everithing was going fine until i decide create a function for pathfinding, the idea was to use it in many ways on the game, first to be sure that the exit is acessible and then for the future IA. The problem is when i press play unity stop working, i think it enters in an infinite loop i just don't know why, this function receive 2 (vector3), it use the vector3 list (that have the position of all tiles and walls created on the map) to find the path from one point to another, after that it return a list with all the positions of that path. I believe its a simple code and i hope someone can help me, anyway here it is:
List<Vector3> PathFinding(Vector3 begin, Vector3 end){
List<Vector3> open, closed, caminho;
open = new List<Vector3> ();
closed = new List<Vector3> ();
caminho = new List<Vector3> ();
Vector3 current, proximo;
current = begin;
while (current != end) {
caminho.Add (current);
proximo = new Vector3 (current.x + mapgen.tileSize, current.y, current.z); // Check Right
if (!mapgen.createdWall.Contains (proximo) && !closed.Contains (proximo) ){
open.Add (proximo);
}
proximo = new Vector3 (current.x - mapgen.tileSize, current.y, current.z); // Check Left
if (!mapgen.createdWall.Contains (proximo) && !closed.Contains (proximo) ){
open.Add (proximo);
}
proximo = new Vector3 (current.x, current.y - mapgen.tileSize, current.z); // Check Down
if (!mapgen.createdWall.Contains (proximo) && !closed.Contains (proximo) ){
open.Add (proximo);
}
proximo = new Vector3 (current.x, current.y + mapgen.tileSize, current.z); // Check Up
if (!mapgen.createdWall.Contains (proximo) && !closed.Contains (proximo) ){
open.Add (proximo);
}
proximo = current;
//For all the possible positions to move, find the one with short distance to target point
for(int i = 0; i < open.Count; i++){
if (!caminho.Contains(open[i]) && (Distancia (open[i], end) < Distancia (proximo, end))) {
proximo = open[i];
}
//If there is only one possible movement, that means end up in a dead end.
//Remove the current position from caminho and block that position to no longer be a possible movement
if ((open.Count == 1) && caminho.Contains(open[i])) {
closed.Add (current);
caminho.Remove (current);
}
}
open.Clear();
current = proximo;
}
return caminho;
}
//-------------------------- RETURN THE DISTANCE BETWEEN 2 POINTS --------------------------------------------------
float Distancia(Vector3 end, Vector3 start){
float distance;
distance = Mathf.Sqrt(Mathf.Pow((end.x - start.x),2) + Mathf.Pow((end.y - start.y),2));
return distance;
}
PS: I didn't use nodes for this map, its only list of vector3 and each element is a object with a sprite. PS²: Sorry if i made mistakes in english.
Tip: Don't use Vector3, every Equals()-operation causes a new memory allocation. I noticed this behaviour when I was new to pathfinding. You can use a custom class Node(){public int X; public int Y}. For increased performance you should use a Hashset for the closedList (since you will only insert and lookup things in it).
Overall you have the wrong approach. The open list should include a queue (and in itself be the data structure of a priority queue) of all unexplored neighbours, e.g. the border or the area of explored nodes (the closed list). Look at the visualisations here. You're not supposed to clear the open list, and ALL neighbours should be added to it (except if the neighbour is already in the closed list) and then SORTED according to priority (we assume that the node with the shortest distance to the goal is the right path). What you're doing is sorting and then throwing away all other neighbours :) I believe your code currently get stuck on a node when it doesnt find any neighbours and the open list is empty (because you clear it). So it will just set "proximo = current;" and then continue the next iteration on the same node.
For a good guide to A* look here.