Hello everyone,
A while ago I implemented my own A* pathfinding algorithm, and it works great. But I feel like my implementation of the A* is wrong. I feel like my algorithm is scanning extra nodes that should not be scanned.
Here is a picture of my program.
The yellow square is the starting node, the green square is the target node, the black squares are solid non-walkable nodes, the blue squares are the final path, the white squares are the squares that were not scanned and the red squares are the nodes that were in the closed list.
And here is another website that has A* implemented.
As you can see this website algorithm is scanning less nodes than my program. I don't know how and I don't know why.
Can you guys please help. I don't know how to fix this.
And here is my code:-
namespace Pathfinding
{
public class Node
{
internal Node Parent;
public Vector2 Position;
internal bool Diagonal;
internal bool Passable = true;
internal int H_Value;
internal int G_Vaule;
internal int F_Vaule
{
get { return H_Value + G_Vaule; }
private set { }
}
public Node(Vector2 Position)
{
this.Position = Position;
}
}
}
namespace Pathfinding
{
public class Astar
{
public List<Node> OpenList;
public List<Node> ClosedList;
List<Node> NonePassable;
Vector2 GridSize;
Node CurrentNode, StartingNode, TargetNode;
bool ReachedTarget;
const int G_Score = 10;
const int Diagonal_G_Score = 14;
Map map;
public Astar()
{
OpenList = new List<Node>();
ClosedList = new List<Node>();
NonePassable = new List<Node>();
ReachedTarget = false;
GridSize = new Vector2(15, 15);
}
void FindAllNeighborNodes()
{
Node RightNeighbor = new Node(new Vector2(CurrentNode.Position.X + 1, CurrentNode.Position.Y));
GetNeighbor(RightNeighbor);
Node LeftNeighbor = new Node(new Vector2(CurrentNode.Position.X - 1, CurrentNode.Position.Y));
GetNeighbor(LeftNeighbor);
Node TopNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y - 1));
GetNeighbor(TopNeighbor);
Node BottomNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y + 1));
GetNeighbor(BottomNeighbor);
}
void GetNeighbor(Node Neighbor)
{
if (Neighbor.Position.X < GridSize.X && Neighbor.Position.X >= 0 && Neighbor.Position.Y >= 0 && Neighbor.Position.Y < GridSize.Y)
{
IsNodePassable(Neighbor);
if (Neighbor.Passable)
{
if (!ClosedList.Any(node => node.Position == Neighbor.Position))
{
if (!OpenList.Any(node => node.Position == Neighbor.Position))
{
Neighbor.Parent = CurrentNode;
Neighbor.G_Vaule = CurrentNode.G_Vaule + G_Score;
Neighbor.H_Value = GetHeuristicCost(Neighbor);
OpenList.Add(Neighbor);
}
else if (OpenList.Any(node => node.Position == Neighbor.Position))
{
if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score < CurrentNode.G_Vaule)
{
int NodeIndex = OpenList.FindIndex(node => node.Position == Neighbor.Position);
OpenList[NodeIndex].Parent = CurrentNode;
OpenList[NodeIndex].G_Vaule = CurrentNode.G_Vaule + G_Score;
}
}
}
}
}
}
void IsNodePassable(Node node)
{
if (NonePassable.Any(nonePassableNodes => nonePassableNodes.Position == node.Position))
node.Passable = false;
else
node.Passable = true;
}
int GetHeuristicCost(Node node)
{
Vector2 Distance = new Vector2(Math.Abs(TargetNode.Position.X - node.Position.X), Math.Abs(TargetNode.Position.Y - node.Position.Y));
return (int)(Distance.X + Distance.Y) * 10;
}
Node GetMinF_Value()
{
int Lowest_F_Value = OpenList.Min(node => node.F_Vaule);
int Index = OpenList.FindIndex(node => node.F_Vaule == Lowest_F_Value);
return OpenList[Index];
}
public List<Vector2> GetFinalPath()
{
List<Vector2> FinalPath = new List<Vector2>();
while(true)
{
if (CurrentNode.Parent != null)
{
FinalPath.Add(CurrentNode.Position);
CurrentNode = CurrentNode.Parent;
}
else
break;
}
FinalPath.Reverse();
return FinalPath;
}
public void FindPath(Map map, Node StartingNode, Node TargetNode)
{
this.map = map;
this.StartingNode = StartingNode;
this.TargetNode = TargetNode;
for (int i = 0; i < map.CollisionObjects.Count; i++)
NonePassable.Add(new Node(map.CollisionObjects[i].Position));
OpenList.Add(StartingNode);
while(OpenList.Count > 0)
{
CurrentNode = GetMinF_Value();
OpenList.Remove(CurrentNode);
ClosedList.Add(CurrentNode);
FindAllNeighborNodes();
if(CurrentNode.Position == TargetNode.Position)
{
ReachedTarget = true;
break;
}
}
}
}
}
You should write a loop instead of four blocks of nearly identical code. For instance, you can write a function that returns a list of neighbors and then loop over them. I implemented A* as part of an engine to play Quoridor, and the implementation is 30 lines of code.
