How to avoid Walls in A*

Question

Well I had a problem with the implementation of my A* algorithm in C# for unity, and I don't realize how to prevent the diagonal movement and the cross walls, I had the next code, the print line's are for debug purposes:

public void FindPath(Vector3 startPos, Vector3 targetPos)
{
   List<Transform> openSet = new List<Transform>();
   HashSet<Transform> closedSet = new HashSet<Transform>();
   openSet.Add(begin.GetComponent<Transform>());

   while (openSet.Count > 0)
   {
      Transform currentNode = openSet[0];

      for (int i = 0; i < openSet.Count; i++)
      {
          if (openSet[i].GetComponent<Cell>().fCost < currentNode.GetComponent<Cell>().fCost || openSet[i].GetComponent<Cell>().fCost == currentNode.GetComponent<Cell>().fCost && openSet[i].GetComponent<Cell>().hCost < currentNode.GetComponent<Cell>().hCost)
              currentNode = openSet[i];
          print("Todo bien despues de agregar el actual al set");
      }

      openSet.Remove(currentNode);
      closedSet.Add(currentNode);

      if (currentNode == end) {
          print("LLEGUE AL NODO FINAL");
          RetracePath(begin,end);
          return;
      }

      foreach (Transform neighbour in grid.GetNeighbours(currentNode.GetComponent<Cell>()))
      {
          if (closedSet.Contains(neighbour.GetComponent<Transform>()) || !neighbour.GetComponent<Cell>().IsOpened)
              continue;

          int newMovementCostToNeighbour = currentNode.GetComponent<Cell>().gCost + GetDistance(currentNode, neighbour.GetComponent<Transform>());
          if (newMovementCostToNeighbour < neighbour.GetComponent<Cell>().gCost || !openSet.Contains(neighbour.GetComponent<Transform>()))
          {
              neighbour.GetComponent<Cell>().gCost = newMovementCostToNeighbour;
              neighbour.GetComponent<Cell>().hCost = GetDistance(neighbour.GetComponent<Transform>(), end.GetComponent<Transform>());
              neighbour.parent = currentNode;
              print("Pase hasta definir los costos");

              if (!openSet.Contains(neighbour.GetComponent<Transform>()))
              {
                  openSet.Add(neighbour.GetComponent<Transform>());
                  neighbour.GetComponent<Renderer>().material.color = Color.blue;
              }
          }
      }
   }
}

The Getneighbours list is in here:

public List<Transform> GetNeighbours(Cell node)
{
    List<Transform> neighbours = new List<Transform>();
    for (int x = -1; x <= 1; x++) {
        for (int y = -1; y <= 1; y++) {
            if (x == -1 && y == -1)
                continue;

            if (x == 0 && y == 0)
                continue;

            if (x == 1 && y == 1)
                continue;

            int checkX =(int)node.Position.x + x;
            int checkY =(int)node.Position.z + y;

            if (checkX >= 0 && checkX < GridSize.x && checkY >= 0 && checkY < GridSize.z)
                neighbours.Add(GridArr[checkX, checkY]);
        }
    }
    return neighbours;
}

I use a Prefab and I really don't know to put the restiction of walls to prevent the algorithm pass over them, to destroy the other prefab walls I use a RayCastHit function.

this return the next image:

The problem with this is it cross my walls and I don't know how to avoid that

Any help?

Thanks

Answer 1

Add a restriction to the tiles your A* algorithm is able to consider and this will eliminate the undesired diagonals.

You wish to remove prevent two things from occurring, the first is you do not wish your algorithm to travel through walls and the second is that you do not wish the algorithm to travel along diagonals.

Let us suppose your maze is represented a graph where nodes represent rooms and edges represent a hallway between the rooms. So create a maze with only valid pathways and then allow A* to process the edges until it reaches the destination node. This works because if a wall exists you do not create a path and if a path would be diagonal you do not create a path.

Answer 2

In your GetNeighbours() function, check if there is a wall between the current node and the neigbouring node. If there is, do not add it to the 'neighbours' list.

I'm not sure what your 'Cell' data structure looks like, or how you connect between the two, but a wall is a barrier between a pair of cells - a cell doesn't have a wall, two cells have a potential wall between them. If you have a 'Cell' reference, how do you figure out the walls that surround it? You have to solve that in order to decide whether to return the neighbour or not. Unfortunately you have not given me enough information to deduce that.