Hello everyone, I read the threads on the algorithm A * (a star), I have a problem about it. While running, I put the open nodes in a list. My problem is when I go to retrieve them because I take even those that do not interest me. Using LINQ takes me the knot with variable “F” less but first on the list. In some cases I have to retrieve the last inserted. Someone can give me a hand?
1)Find node with min “F” value
private Node findMin(List<Node> openList)
{
Node current = new Node();
float Fmin = float.MaxValue;
for (int i = 0; i < openList.Count; i++)
{
if(openList[i].F < Fmin)
{
current = openList[i];
Fmin = openList[i].F;
}
}
return current;
}
- A* algorithm
private void pathFind (Node start, Node end)
{
openList.Add(start);
while(openList.Count > 0)
{
Node currentNode = openList.OrderBy(minValue => minValue.F).First(); // findMin(openList);
openList.Remove(currentNode);
findNeighboards(currentNode); //I find adjacent nodes in the current node and insert them in a list
closedList.Add(currentNode);
if (closedList.Contains(end))
break;
foreach (Node item in adjacentNodes)
{
if (closedList.Contains(item))
continue;
if (!openList.Contains(item))
{
item.G = setG(start, item);
item.H = setH(item, end);
float result = item.F;
openList.Add(item);
}
}
adjacentNodes.Clear(); I clean the list of adjacent nodes
}
}
- Find Neighboards
void findNeighboards(Node currentNode)
{
for (int i = 0; i < nodes.Count; i++)
{
if (Vector3.Distance(currentNode.position, nodes[i].position) == range)
{
if (nodes[i].isWalkable && (!closedList.Contains(nodes[i])))
{
adjacentNodes.Add(nodes[i]);
}
}
}
}
- Heuristic algorithm
float heuristic(Node firstNode, Node secondNode)
{
float manhattanDistance = Mathf.Abs(secondNode.position.x - firstNode.position.x) + Mathf.Abs(secondNode.position.z - firstNode.position.z);
return manhattanDistance;
}
float setG(Node starPosition, Node currentNode)
{
float valueG = heuristic(starPosition, currentNode);
return valueG;
}
float setH(Node currentNode, Node endNode)
{
float valueH = heuristic(currentNode, endNode);
return valueH;
}