Возникла проблема с реализацией поиска пути A*. ⇐ C#

[Anonymous]

Я пытаюсь добавить поиск пути в игру, которую создаю, и пытался использовать алгоритм поиска пути A*. Это вроде как работает, так как в конечном итоге находит маршрут, однако это может занять очень много времени, когда узлы находятся далеко друг от друга, и когда я смотрю на него во время поиска, кажется, что он снова и снова проходит по одним и тем же узлам, и я не совсем понимаю, почему?
Я сделал это именно так, и не уверен, что где-то напутал.
internal class PathFinding
{
const int NO_PARENT = -1; //Constant to show that starting node and end node have no parent nodes

private List _obstacles = new List();
private List _open = new List();
private List _closed = new List();

private struct Node
{
//Position
int x;
int y;

//Parent node position
int parentX;
int parentY;

int gCost; //Distance from node to starting node
int hCost; //Distance from node to target node
int fCost; //Which node should be explored next gCost + hCost

public Node(int nodeXPosition, int nodeYPosition, int parentXPosition, int parentYPosition)
{
x = nodeXPosition;
y = nodeYPosition;
parentX = parentXPosition;
parentY = parentYPosition;
gCost = 0;
hCost = 0;
fCost = 0;
}

public void CalculateCosts(Node startingNode, Node targetNode)
{
gCost = Math.Abs(x - startingNode.x) + Math.Abs(y - startingNode.y);
hCost = Math.Abs(x - targetNode.x) + Math.Abs (y - targetNode.y);
fCost = gCost + hCost;
}

public int GetFCost()
{
return fCost;
}

public int GetXPosition()
{
return x;
}

public int GetYPosition()
{
return y;
}

public Node[] ExploreNeighbours()
{
//0 = up
//1 = right
//2 = down
//3 = left

Node[] neighbours = new Node[4];
neighbours[0].x = x;
neighbours[0].y = y - 1;
neighbours[1].x = x + 1;
neighbours[1].y = y;
neighbours[2].x = x;
neighbours[2].y = y + 1;
neighbours[3].x = x - 1;
neighbours[3].y = y;
//Set parent node for explored nodes
for (int i = 0; i < neighbours.Count(); i++)
{
neighbours.parentX = x;
neighbours.parentY = y;
}
return neighbours;
}

}

public PathFinding(List obstacles)
{
_obstacles = obstacles;
}

public void FindRoute(int startPositionX, int startPositionY, int endPositionX, int endPositionY)
{
bool routeFound = false;
Node startingNode = new Node(startPositionX,startPositionY,NO_PARENT,NO_PARENT);
Node endNode = new Node(endPositionX,endPositionY,NO_PARENT,NO_PARENT);
Node[] exploredNodes;

startingNode.CalculateCosts(startingNode,endNode);
_open.Add(startingNode);

while(routeFound == false)
{
//Sort list by lowest F cost
_open = _open.OrderBy(x => x.GetFCost()).ToList();
//Explore the node in open list with lowest F cost (First in list due to sorting)
exploredNodes = _open[0].ExploreNeighbours();
//Check to see if explored nodes already exist as well as calculate their costs
//If explored node already then remove it from the open list.
//Once it has checked to makes sure that duplicates are gone add all explored nodes to the open list
for (int i = 0; i < exploredNodes.Length; i++)
{
exploredNodes.CalculateCosts(startingNode,endNode);
for (int j = 0; j < _open.Count; j++)
{
if (exploredNodes.GetXPosition() == _open[j].GetXPosition() && exploredNodes.GetYPosition() == _open[j].GetYPosition())
{
_open.RemoveAt(j);
}
}
}

_open.AddRange(exploredNodes);
_closed.Add(_open[0]);
_open.RemoveAt(0);

}

}

}


Подробнее здесь: https://stackoverflow.com/questions/789 ... athfinding