C#에서는 클래스를 찾는 스타 경로에 대각선을 어떻게 추가합니까?

Question

A *를 사용하는 간단한 경로 찾기 클래스가 있지만 타일 맵의 4 가지 기본 경로 만 다루고 있습니다. 벽에 복종하고 피하는 것이지만 열린 공간에서는 지그재그 패턴을 만들어 목적지까지 도달합니다.

지도의 열린 영역에 대각선을 포함하도록 패턴을 단순화하고 싶지만 대각선을 사용하는 경우 벽 전체를 무시하는 것처럼 보입니다.

어떻게 이것을 해결하고 대각선을 올바르게 추가 할 수 있습니까?

using UnityEngine; 
using System.Collections.Generic; 

public class AStar { 

    private List<Node> openList; 
    private List<Node> closeList; 
    private List<Node> neighbors; 
    private List<Node> finalPath; 

    private Node start; 
    private Node end; 

    public AStar() 
    { 
     openList = new List<Node>(); 
     closeList = new List<Node>(); 
     neighbors = new List<Node>(); 
     finalPath = new List<Node>(); 

    } 

    public void FindPath(MazeCell startCell, MazeCell goalCell) 
    { 
     start = new Node(0, 0, 0, null, startCell); 
     end = new Node(0, 0, 0, null, goalCell); 

     openList.Add(start); 

     bool keepSearching = true; 
     bool pathExists = true; 

     while(keepSearching && pathExists) 
     { 
      Node currentNode = ExtractBestNodeFromOpenList(); 

      if (currentNode == null) 
      { 
       pathExists = false; 
       break; 
      } 

      closeList.Add(currentNode); 

      if (NodeIsGoal(currentNode)) 
      { 
       keepSearching = false; 
      } else 
      { 
       FindValidFourNeighbors(currentNode); 
      } 

      foreach(Node neighbor in neighbors) 
      { 
       if (FindInList(neighbor, closeList) != null) 
        continue; 

       Node inOpenList = FindInList(neighbor, openList); 
       if (inOpenList == null) 
       { 
        openList.Add(neighbor); 
       } else 
       { 
        if (neighbor.G < inOpenList.G) 
        { 
         inOpenList.G = neighbor.G; 
         inOpenList.F = inOpenList.G + inOpenList.H; 
         inOpenList.parent = currentNode; 
        } 
       } 

      } 
     } 

     if (pathExists) 
     { 
      Node n = FindInList(end, closeList); 
      while (n != null) 
      { 
       finalPath.Add(n); 
       n = n.parent; 
      } 
     } 

    } 

    public bool ContainsCoordinates(IntVector2 coordinate) 
    { 
     return coordinate.x >= 0 && coordinate.x < GameConfig.mazeSize && coordinate.z >= 0 && coordinate.z < GameConfig.mazeSize; 
    } 

    private void FindValidFourNeighbors(Node node) 
    { 
     neighbors.Clear(); 

     // Check South of this Cell // 

     int south = node.cell.mazeCellCoordinates.z - 1; 
     IntVector2 SouthNeighbor = new IntVector2(node.cell.mazeCellCoordinates.x , south); 

     int north = node.cell.mazeCellCoordinates.z + 1; 
     IntVector2 NorthNeighbor = new IntVector2(node.cell.mazeCellCoordinates.x, north); 

     int east = node.cell.mazeCellCoordinates.x + 1; 
     IntVector2 EastNeighbor = new IntVector2(east, node.cell.mazeCellCoordinates.z); 

     int west = node.cell.mazeCellCoordinates.x - 1; 
     IntVector2 WestNeighbor = new IntVector2(west, node.cell.mazeCellCoordinates.z); 

     IntVector2 SouthEastNeighbor = new IntVector2(south, east); 

     IntVector2 SouthWestNeighbor = new IntVector2(south, west); 

     IntVector2 NorthEastNeighbor = new IntVector2(north, east); 

     IntVector2 NorthWestNeighbor = new IntVector2(north, west); 

     if (ContainsCoordinates(SouthNeighbor)) 
     { 
      if (Maze.Instance.cellStorage[SouthNeighbor.x, SouthNeighbor.z].IsWalkable) 
      { 
       MazeCell c = Maze.Instance.cellStorage[SouthNeighbor.x, SouthNeighbor.z]; 

       if (!(c.cellEdges[(int)MazeDirection.North] is MazeCellWall)) 
       { 
        Node vn = PrepareNewNode(node, 0, -1); 
        neighbors.Add(vn); 
       } 
      } 
     } 


     if (ContainsCoordinates(NorthNeighbor)) 
     { 
      if (Maze.Instance.cellStorage[NorthNeighbor.x, NorthNeighbor.z].IsWalkable) 
      { 
       MazeCell c = Maze.Instance.cellStorage[NorthNeighbor.x, NorthNeighbor.z]; 

       if (!(c.cellEdges[(int)MazeDirection.South] is MazeCellWall)) 
       { 
        Node vn = PrepareNewNode(node, 0, 1); 
        neighbors.Add(vn); 
       } 
      } 
     } 

     if (ContainsCoordinates(WestNeighbor)) 
     { 
      if (Maze.Instance.cellStorage[WestNeighbor.x, WestNeighbor.z].IsWalkable) 
      { 
       MazeCell c = Maze.Instance.cellStorage[WestNeighbor.x, WestNeighbor.z]; 

       if (!(c.cellEdges[(int)MazeDirection.East] is MazeCellWall)) 
       { 
        Node vn = PrepareNewNode(node, -1, 0); 
        neighbors.Add(vn); 
       } 
      } 
     } 

     if (ContainsCoordinates(EastNeighbor)) 
     { 
      if (Maze.Instance.cellStorage[EastNeighbor.x, EastNeighbor.z].IsWalkable) 
      { 
       MazeCell c = Maze.Instance.cellStorage[EastNeighbor.x, EastNeighbor.z]; 

       if (!(c.cellEdges[(int)MazeDirection.West] is MazeCellWall)) 
       { 
        Node vn = PrepareNewNode(node, 1, 0); 
        neighbors.Add(vn); 
       } 
      } 
     } 

    } 

    private float Heuristic(Node n) 
    { 
     return Mathf.Sqrt((n.cell.mazeCellCoordinates.x - end.cell.mazeCellCoordinates.x) * (n.cell.mazeCellCoordinates.x - end.cell.mazeCellCoordinates.x) + (n.cell.mazeCellCoordinates.z - end.cell.mazeCellCoordinates.z) * (n.cell.mazeCellCoordinates.z - end.cell.mazeCellCoordinates.z)); 
    } 

    private float MovementCost(Node a, Node b) 
    { 
     return Maze.Instance.cellStorage[b.cell.mazeCellCoordinates.x, b.cell.mazeCellCoordinates.z].movementCost(); 
    } 

    private Node PrepareNewNode(Node n, int x, int z) 
    { 
     IntVector2 iv = new IntVector2(n.cell.mazeCellCoordinates.x + x, n.cell.mazeCellCoordinates.z + z); 
     Node node = new Node(0, 0, 0, n, Maze.Instance.cellStorage[iv.x, iv.z]); 
     node.G = n.G + MovementCost(n, node); 
     node.H = Heuristic(node); 
     node.F = node.G + node.H; 
     node.parent = n; 
     return node; 
    } 

    public List<MazeCell> CellsFromPath() 
    { 
     List<MazeCell> path = new List<MazeCell>(); 
     foreach (Node n in finalPath) 
     { 
      path.Add(n.cell); 
     } 

     if (path.Count != 0) 
     { 
      path.Reverse(); 
      path.RemoveAt(0); 
     } 
     return path; 
    } 

    public List<int> PointsFromPath() 
    { 
     List<int> points = new List<int>(); 
     foreach (Node n in finalPath) 
     { 
      points.Add(n.cell.mazeCellCoordinates.x); 
      points.Add(n.cell.mazeCellCoordinates.z); 
     } 
     return points; 
    } 

    bool NodeIsGoal(Node node) 
    { 
     return ((node.cell.mazeCellCoordinates.x == end.cell.mazeCellCoordinates.x) && (node.cell.mazeCellCoordinates.z == end.cell.mazeCellCoordinates.z)); 
    } 

    Node FindInList(Node n, List<Node> xl) 
    { 
     foreach (Node nn in xl) 
     { 
      if ((nn.cell.mazeCellCoordinates.x == n.cell.mazeCellCoordinates.x) && (nn.cell.mazeCellCoordinates.z == n.cell.mazeCellCoordinates.z)) 
       return nn; 
     } 
     return null; 
    } 

    private Node ExtractBestNodeFromOpenList() 
    { 
     float minF = float.MaxValue; 
     Node bestNode = null; 

     foreach(Node n in openList) 
     { 
      if (n.F < minF) 
      { 
       minF = n.F; 
       bestNode = n; 
      } 
     } 

     if (bestNode != null) 
     openList.Remove(bestNode); 
     return bestNode; 
    } 

} 

Answer 1

나는 대각선을 사용하여 A *를 구현 했으므로 가능한 이웃 목록에 포함시켜야합니다.

기술적으로 당신은 오히려 당신의 휴리스틱 기능에 원가 계산/배제를해야하지만, 당신의 코드를보고 확실히 당신은 private void FindValidFourNeighbors(Node node) 4 개 더 검사를 추가 할 수 있습니다

if (ContainsCoordinates(SouthEastNeighbor)) 
    { 
     if (Maze.Instance.cellStorage[SouthEastNeighbor.x, SouthEastNeighbor.z].IsWalkable) 
     { 
      MazeCell c = Maze.Instance.cellStorage[SouthEastNeighbor.x, SouthEastNeighbor.z]; 

      if (!(c.cellEdges[(int)MazeDirection.South] is MazeCellWall) && !(c.cellEdges[(int)MazeDirection.East] is MazeCellWall)) 
      { 
       Node vn = PrepareNewNode(node, 0, -1); 
       neighbors.Add(vn); 
      } 
     } 
    } 

(너무 명확하지 무엇을 'cellEdges을 '수표는 정확히하고 있지만 대각선을 위해 양측을 점검해야한다고 가정합니다. 이것은 아마도 여러분이 실패한 곳일 것입니다.)