3
\$\begingroup\$

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: Unity Image

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

Any help?

Thanks

Improve this question
\$\endgroup\$
  • \$\begingroup\$ I suspect the problem is in grid.GetNeighbours(). You might want to include the source to that function too. \$\endgroup\$ – Adam Nov 15 '15 at 15:21
  • \$\begingroup\$ @Adam I update my post with the code part that ask for it :) \$\endgroup\$ – Juan Carlos Leon Nov 15 '15 at 20:27
  • 1
    \$\begingroup\$ Do you actually have any variable that contains the locations of all the walls or have you just created game objects? Assuming the latter... You'll need some way of checking if going from cell A to cell B involves going through a wall. Most naively, that's a list of all wall start/end points. Then some basic trig will determine if there's an intersection. Of course, after you have that list, you can use it to generate the wall objects quickly... Note that if you used whole cells as walls, you could get away with just keeping a list of wall cells and not add a neighbour if it's in that list. \$\endgroup\$ – Basic Nov 16 '15 at 21:12
  • \$\begingroup\$ I would just add insanely high cost modifiers to coordinates that contain walls. \$\endgroup\$ – JDSweetBeat Feb 9 '17 at 19:12
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
  • \$\begingroup\$ Well the diagonal movement it's already fixed, but I still need to prevent the walls and I don't know how to add the restriction in the prefab or in the code \$\endgroup\$ – Juan Carlos Leon Nov 15 '15 at 19:54
  • \$\begingroup\$ In a similar manner to preventing diagonal movement. Eliminate undesirable or "illegal" tiles from the A* algorithm's choice. Walls are never a legal space and can be removed after map generation. Diagonal choices are state based and must be checked at every node A* considers. \$\endgroup\$ – user3730788 Nov 16 '15 at 1:39
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
  • \$\begingroup\$ how I put a restriction that inside the prefab walls, for A* can't cross them, I already tried put a tag to the walls and put the restriction if neighbour.GetComponentChildrens<Transform>().tag=="wall" don't add to neighbours list... any idea? \$\endgroup\$ – Juan Carlos Leon Nov 16 '15 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.