# A*Pathfinding generating wrong path

I'm building a maze game where there's an enemy ready to pursuit the player if the player gets in his range, I'm using A*Pathfinding algorithm to do so, and I build the maze in a procedural way, where each block in the maze has a MapLocation with x and z position, so the start position is the enemy pos and goal is the player position, but when the RetracePath is called it generates an incomplete path causing the issue illustrated in the image below, I'm uploading a video to illustrate the problem:

IEnumerator Search(Vector3 start, Vector3 goal)
{
pathSuccess = false;
waypoints = new Vector3;
Heap<Path> open = new Heap<Path>(maze.MaxSize);
HashSet<Path> closed = new HashSet<Path>();

Path startNode = new Path(maze.GetMapLocation(start), 0, 0, 0, null);
Path goalNode = new Path(maze.GetMapLocation(goal), 0, 0, 0, null);

lastPos = startNode;

while (open.Count > 0)
{
if (lastPos.Equals(goalNode))
{
pathSuccess = true;
break;
}
foreach (MapLocation dir in maze.directions)
{
MapLocation neighbour = dir + lastPos.location;
if (maze.map[neighbour.x, neighbour.z] == 1) continue;
if (neighbour.x < 1 || neighbour.x >= maze.width || neighbour.z < 1 || neighbour.z >= maze.depth) continue;
if (IsClosed(neighbour, closed)) continue;

float G = Vector2.Distance(lastPos.location.ToVector(), neighbour.ToVector()) + lastPos.G;
float H = Vector2.Distance(neighbour.ToVector(), goalNode.location.ToVector());
float F = G + H;

if (!UpdateMarker(neighbour, G, H, F, lastPos, open))
open.Add(new Path(neighbour, G, H, F, lastPos));
}
Path pm = open.RemoveFirst();

lastPos = pm;
}
yield return null;
if (pathSuccess)
{
waypoints = RetracePath(startNode);
}
PathRequestManager.Instance.FinishedProcessingPath(waypoints, pathSuccess);
}

bool UpdateMarker(MapLocation pos, float g, float h, float f, Path prt, Heap<Path> open)
{
foreach (Path p in open)
{
if (p.location.Equals(pos))
{
p.G = g;
p.H = h;
p.F = f;
p.parent = prt;
return true;
}
}
return false;
}

bool IsClosed(MapLocation marker, HashSet<Path> closed)
{
foreach (Path p in closed)
{
if (p.location.Equals(marker)) return true;
}
return false;
}

Vector3[] RetracePath(Path startNode)
{
Path begin = lastPos;
List<Vector3> path = new List<Vector3>();
while (!startNode.Equals(begin) && begin != null)
{
begin = begin.parent;
}
path.Reverse();
return path.ToArray();
}

public MapLocation GetMapLocation(Vector3 position)
{
MapLocation mapLocation = new MapLocation((int)position.x / scale, (int)position.z / scale);
return mapLocation;
}
public List<MapLocation> directions = new List<MapLocation>() {
new MapLocation(1,0),
new MapLocation(0,1),
new MapLocation(-1,0),
new MapLocation(0,-1) };


The maze is generated like this:

public class Recursive : Maze
{
public override void Generate()
{
Generate(5, 5);
}

void Generate(int x, int z)
{
if (CountSquareNeighbours(x, z) >= 2) return;
map[x, z] = 0;

directions.Shuffle();

Generate(x + directions.x, z + directions.z);
Generate(x + directions.x, z + directions.z);
Generate(x + directions.x, z + directions.z);
Generate(x + directions.x, z + directions.z);
}

}

public byte[,] map;
public virtual void Generate()
{
for (int z = 0; z < depth; z++)
for (int x = 0; x < width; x++)
{
if(Random.Range(0,100) < 50)
map[x, z] = 0;     //1 = wall  0 = corridor
}
}


I already tried using Manhattan's Distance and it didn't make any difference:

float H = Mathf.Abs(neighbour.x - goalNode.location.x) + Mathf.Abs(neighbour.z - goalNode.location.z);


MapLocation:

public class MapLocation
{
public int x;
public int z;

public MapLocation(int _x, int _z)
{
x = _x;
z = _z;
}

public Vector2 ToVector()
{
return new Vector2(x, z);
}

public Vector3 ToVector3(Maze maze)
{
return new Vector3(x * maze.scale, 0, z * maze.scale);
}

public static MapLocation operator +(MapLocation a, MapLocation b)
=> new MapLocation(a.x + b.x, a.z + b.z);

public override bool Equals(object obj)
{
if ((obj == null) || !this.GetType().Equals(obj.GetType()))
{
return false;
}
else
{
return x == ((MapLocation)obj).x && z == ((MapLocation)obj).z;
}
}

public override int GetHashCode()
{
return 0;
}
}


The GetMapLocation was rounding the results down instead of up, misleading the path, so now I added some verification to see not only if the block is valid but round it up like this:

public MapLocation GetMapLocation(Vector3 position)
{
int x = (int)Math.Round(position.x / scale, MidpointRounding.AwayFromZero);
int z = (int)Math.Round(position.z / scale, MidpointRounding.AwayFromZero);

// Check if the position is out of bounds
if (x < 0 || x >= width || z < 0 || z >= depth)
{
return null;
}

// Check if the position is already a valid map location
if (map[x, z] == 0)
{
return new MapLocation(x, z);
}

// Search for the closest valid map location
int minDistance = int.MaxValue;
MapLocation closestLocation = null;
for (int i = 0; i < width; i++)
{
for (int j = 0; j < depth; j++)
{
if (map[i, j] == 0)
{
int distance = (i - x) * (i - x) + (j - z) * (j - z);
if (distance < minDistance)
{
minDistance = distance;
closestLocation = new MapLocation(i, j);
}
}
}
}
Debug.Log(closestLocation.x + " " + closestLocation.z);
return closestLocation;
}