public class AstarNode
{
public Tile tile;
public AstarNode parent;
public int gCost; // 시작부터 현재까지의 누적 비용
public int hCost; // 휴리스틱 (목표까지 예상 거리)
public int fCost => gCost + hCost;
public int astarCost => tile != null ? tile.AstarCost : int.MaxValue; // 현재 타일의 이동 비용 (Tile의 AstarCost를 복사)
public AstarNode(Tile tile)
{
this.tile = tile;
}
/// <summary>
/// 길찾을땐 true 복도 생성용 false
/// </summary>
/// <param name="forPathfinding"></param>
/// <returns></returns>
public bool IsWalkable(bool forPathfinding = true)//통로생성용으로 사용시 empty는 이동 가능 길찾기용은 불가능 isDoorPoint일경우 wall도 이동가능으로 취급
{
if (tile == null) return false;
return forPathfinding ? tile.IsWalkable : tile.isDoorPoint || tile.tileType == TileType.empty || tile.IsWalkable;
}
}
public static class AStarPathfinder
{
public static List<Tile> FindPath(Tile startTile, Tile goalTile, Level level, bool forPathfinding = true)//최대 탐색 거리 추가예정
{
if (startTile == null || goalTile == null || level == null) return null;
var openList = new Dictionary<Vector2Int, AstarNode>();//리스트 중복시 성능 저하로 오픈리스트 딕셔너리처리 내부 필드를 통한 검색필요 변수명만 list
var closedList = new HashSet<Vector2Int>();//방문 여부만 체크하므로 해쉬셋 gridPosition
AstarNode startNode = new AstarNode(startTile)
{
gCost = 0,
hCost = Heuristic(startTile, goalTile)
};
openList[startTile.gridPosition] = startNode;
while (openList.Count > 0)
{
AstarNode current = GetLowestFCostNode(openList);//모든 오픈리스트를 돌며 fcost가 낮은 오픈리스트 반환
if (current.tile == goalTile) return ReconstructPath(current);
openList.Remove(current.tile.gridPosition);
closedList.Add(current.tile.gridPosition);
foreach (Tile neighbor in GetNeighbors(current.tile, level, forPathfinding))//길찾기용은 8dir 통로생성용은 4dir neighbor반환
{
if (closedList.Contains(neighbor.gridPosition)) continue;
int tempGCost = current.gCost + neighbor.AstarCost;
if (!openList.TryGetValue(neighbor.gridPosition, out AstarNode neighborNode))
{
neighborNode = new AstarNode(neighbor)
{
gCost = tempGCost,
hCost = Heuristic(neighbor, goalTile),
parent = current
};
if (neighborNode.IsWalkable(forPathfinding))
{
openList[neighbor.gridPosition] = neighborNode;
}
}
else if (tempGCost < neighborNode.gCost)
{
neighborNode.gCost = tempGCost;
neighborNode.parent = current;
}
}
}
return null; //오픈리스트를 다돌았음에도 경로 없음 추가로 gCost가 일정량 이상 넘어가면 null처리 후 별도의 길찾기 로직실행
}
private static int Heuristic(Tile a, Tile b)//맨허튼 거리 필요할경우 수정
{
return Mathf.Abs(a.gridPosition.x - b.gridPosition.x) + Mathf.Abs(a.gridPosition.y - b.gridPosition.y);
}
private static AstarNode GetLowestFCostNode(Dictionary<Vector2Int, AstarNode> dict)
{
AstarNode best = null;
foreach (var node in dict.Values)
{
if (best == null || node.fCost < best.fCost || (node.fCost == best.fCost && node.hCost < best.hCost))
best = node;
}
return best;
}
private static List<Tile> ReconstructPath(AstarNode node)
{
List<Tile> path = new List<Tile>();
while (node != null)//목적지의 노드부터 부모 노드들을 추적하며 리스트에 추가
{
path.Add(node.tile);
node = node.parent;
}
path.Reverse();//길찾기용 반전
return path;
}
private static List<Tile> GetNeighbors(Tile tile, Level level, bool allowDiagonal)
{
List<Tile> neighbors = new List<Tile>();
Vector2Int[] directions = allowDiagonal
? new Vector2Int[]
{
Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right,
new Vector2Int(1, 1), new Vector2Int(-1, 1),
new Vector2Int(1, -1), new Vector2Int(-1, -1)
}
: new Vector2Int[]
{
Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right
};
foreach (var dir in directions)
{
Vector2Int pos = tile.gridPosition + dir;
if (level.tiles.TryGetValue(pos, out Tile neighbor))
{
neighbors.Add(neighbor);
}
}
return neighbors;
}
}
A*알고리즘
타일 맵이 있다고 했을때 각 노드는 인접한 노드들과 모두 연결되어있고 수직 수평으로는 이동비용을 10 대각선으로는 14라고 가정한다.
이때 f(n) = g(n) + h(n) 이다
이때 g는 지금까지 이동에 사용된 cost 이며 h는 휴리스틱 즉 목적지까지의 장애물이 없을 경우의 예상 비용을 계산한것이다 이때 휴리스틱은 맨허튼 방식을 활용하겠다 맨허튼 방식은 맨허튼의 거리처럼 수직으로만 이동하는것을 가정한 계산 방식이다
시작시 시작노드를 openlist에 넣어준다 그뒤 이동가능한 노드들을 openlist에 넣어준다 이제 시작노드를 closedlist에 넣어준다 closedlist는 다시 볼필요가 없다는 뜻이다 openlist의 노드중에서 f값이 제일 낮은곳으로 이동한다
이제 이동한 노드의 부모노드를 이전노드로 지정해준다. 또한 openlist에서 빼준뒤 closedlist에 넣어준다 이제 이동한 노드의 인접 노드들 중에서 이미 closedlist에 있는 노드 이동이 불가능한 노드들을 제외한 노드들을 openlist에 넣어준다. 이때 열린 목록에 있는 노드들의 f g h 를 계산해준다. 이때 이미 기존의 열린 목록에 있다면 hashset true or false 인접한 사각현까지 이동할때 g 비용이 낮아지는지 확인한다 비용이 낮아질경우 해당노드의 부모노드을 현재노드로 바꿔준다
즉 현재노드로 이동한뒤 해당노드로 이동하는것이 비용이 절감된다는뜻이다. 비용이 절감되지않는경우는 오히려 돌아서 간다는 의미이므로 그대로 냅둔다
이제 다시 openlist의 f 비용이 제일 낮은 노드를 찾고 closedlist에 넣고 인접 노드들을 openlist에 넣고 부모노드로 설정해준뒤 f g h를 계산하는것을 반복한다 이것은 openlist가 비거나 목표노드가 openlist에 추가될때까지 반복한다.
이를 활용하여 타일맵의 복도를 연결하고 길을 찾는데 활용한다