A* (Astar) , JPS

 

아래와 같은 길이 있을때

녹색 : 시작점

빨간색 : 도착점

노란색 화살표가 가르키는 곳 : 또 다른 길

 

시작점에서 끝점까지 이동 할때 노란색 화살표가 가리키는 곳으로 가게 되면 더 먼 경로로 가게 된다는 것을 알 수 있는데

Astar 에선 거리 측정을 두가지로 한다

1 현재 플레이어 위치와 목표 지점

2 현재 플레이어 위치 기준 이동 누적 거리가 얼마나 되는가

 

1,2 이것을 합산하여 거리 비교 판단을 하게 되어 더 가까운 쪽을 우선적으로 거리를 선택하여 도착점 까지 가게 되어 최단 경로를 구하게 됩니다
(최단 경로는 종점에서 역으로 시작점으로 가면서 현재 점의 부모 위치인 역으로 올라가는 방식입니다)

즉 여기선 아래쪽의 최단 경로를 찾게 된다는 애기가 됩니다

 

 

알고리즘 처리는 우선순위 큐를 활용해 현재 후보 노드들 중에서 합산 거리 가장 가까운 노드 기준으로 계속 탐색을 하는 방식입니다

 

 

 

 

 

코드는 4방향과 8방향이 있는데

4방향은 거리 10, 14를 모두 1로 처리해놓으면 됩니다

using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm
{
	class Pos
	{
		public Pos(int y, int x) { Y = y; X = x; }
		public int Y;
		public int X;
	}

	class Player
	{
		public int PosY { get; private set; }
		public int PosX { get; private set; }
		Random _random = new Random();
		Board _board;

		enum Dir
		{
			Up = 0,
			Left = 1,
			Down = 2,
			Right = 3 
		}

		int _dir = (int)Dir.Up;
		List<Pos> _points = new List<Pos>();

		struct Node : IComparable<Node>
        {
			public int F;
			public int G;
			public int X;
			public int Y;

            int IComparable<Node>.CompareTo(Node other)
            {
				return F == other.F ?  0 : (F < other.F ? 1 : -1);
            }
        }

		public void Initialize(int posY, int posX, Board board)
		{
			PosY = posY;
			PosX = posX;
			_board = board;

			AStar();

		}

		void AStar()
        {
            //점수 매기기
            //F = G + H
            //F = 최종 점수 (작을 수록 좋음, 경로에 따라 달라짐)

            //G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 ( 작을 수록 좋음, 경로에 따라 달라짐 ), 현재 노드에서 열린 다음 노드까지
            //H = 목적지에서 얼마나 가까운지 (작을 수록 좋음, 고정)

            //open (거리 계산용) 배열과
            //closed 이미 방문한 노드인지 파악하기 위한배열
            //이 둘의 배열이 각각 존재한다

            // open 한 x,y 위치에 목적지까지 거리가 얼마나 되는지 거리 계산 후 저장한다 그렇지 않은것들은 max distance,  H 와 유사
            //오픈 리스트에 있는 정보들 중에서, 가장 좋은 후보를 뽑기 위해 => 우선순위 큐를 쓴다 => 저장 되는 기준은 거리가 짭을 수록 순위가 높은 것

            //방문 하게 되면 closed 가 된다, 방문한 곳은 더이상 조사하지 않는다

            //이동할수 있는 노드라면 예약을 해 놓는다, 상 하 좌우 좌표 확인해서 예약 한다(open)

            //F = G(현재 노드에서 다음 노드까지 거리) + H(현재 노드에서 목적지 까지의 거리H)

            //open 된 것들 중에서  계산한 F 가 open 되어진 즉 이전에 계산했던 open 거리보다 보다 작다면 더이상 계산 안함
            //=> open 된것과 현재 노드 기준 사방향을 보면서 가장 적은 비용의 F 를 구해서 다시 open[nextX, nextY] = F 에 넣어 준다
            //그리고 이것을 우선순위 Q 에 넣어 준다


			//4방향일때 
            // 			int[] deltaX = new int[] { 0, -1, 0, 1 };
            // 			int[] deltaY = new int[] { -1, 0, 1, 0 };
            // 			int[] cost = new int[] { 1, 1, 1, 1 };

			//8방향 일때
            int[] deltaX = new int[] { -1, 0,  1, 0,		-1,  1,  1, -1 };
            int[] deltaY = new int[] {  0, -1, 0, 1,		-1, -1 , 1,  1 };
            int[] cost =   new int[] { 10, 10, 10, 10,	14, 14, 14, 14 };

            bool[,] closed = new bool[_board.Size, _board.Size];
			int[,] open = new int[_board.Size, _board.Size];

			Pos[,] parent = new Pos[_board.Size, _board.Size];

			for(int i=0;i<_board.Size;++i )
            {
                for (int j = 0; j < _board.Size; ++j)
                {
					open[i, j] = int.MaxValue;
                }
            }


			PriorityQueue<Node> pq = new PriorityQueue<Node>();

			//초기 H 
			open[PosY, PosX] =  10 *  Math.Abs(_board.DestX - PosX) + Math.Abs(_board.DestY - PosY);
			pq.Push(new Node() { F=  open[PosY, PosX], G=0, X = PosX, Y = PosY });
			parent[PosY, PosX] = new Pos(PosY, PosX);

			while(pq.Count > 0)
            {
				//현재 후보군들 중에서 목표와 가장 근접한(계산식상) 후보를 하나 뽑는다
				Node node = pq.Pop();

				//방문했던 노드는 건너띔
				if(closed[node.Y, node.X])
                {
					continue;
                }
				closed[node.Y, node.X] = true;
				if (node.X == _board.DestX && node.Y == _board.DestY)
                {
					break;
                }

				//4방향으로 이동 할수 있는 노드인지 확인해서 가능하다면 예약(open) 에 거리 계산 한다
				for (int i = 0; i < deltaY.Length; ++i)
				{
					int nextX = node.X + deltaX[i];
					int nextY = node.Y + deltaY[i];

					//테두리를 벗어나지 않은 경우 and  벽이 아니며 and 방문을 안했었다면 새로운 open 노드를 찾는다
					if ((nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _board.Size) ||	
						(_board.Tile[nextY, nextX] == Board.TileType.Wall) ||
						closed[nextY, nextX])
					{
						continue;
					}


					int g = node.G + cost[i];
					//예약 가능 다음 노드 후보들에 대한 거리 계산을 하고
					//목적지와 다음 노드 같의 거리 임으로 이 차이가 더 작은 곳으로 
					int h =  10 *  Math.Abs(_board.DestX - nextX) + Math.Abs(_board.DestY - nextY);		
					//이전에 했었던 거리 계산이 더 작다면 skip
					if(open[nextY, nextX] < g + h)
                    {
						continue;
                    }
					 
					//거리를 갱신한다 더 짧은 거리로
					open[nextY, nextX] = g + h;
					pq.Push(new Node() { F = g + h, G = g, X = nextX, Y = nextY });

					parent[nextY, nextX] = new Pos(node.Y, node.X);

				}



			}

			calculatePath(parent);
		}

		void calculatePath(Pos[,] parent)
        {
			int x = _board.DestX;
			int y = _board.DestY;
			while(parent[y,x].X != x || parent[y, x].Y != y)
            {
				_points.Add(new Pos(y, x));
				Pos pos = parent[y, x];
				x = pos.X;
				y = pos.Y;
			}
			_points.Add(new Pos(y, x));
			_points.Reverse();
		}
			

		

		const int MOVE_TICK = 10;
		int _sumTick = 0;
		int _lastIndex = 0;
		public void Update(int deltaTick)
		{
			if (_lastIndex >= _points.Count)
				return;

			_sumTick += deltaTick;
			if (_sumTick >= MOVE_TICK)
			{
				_sumTick = 0;

				PosY = _points[_lastIndex].Y;
				PosX = _points[_lastIndex].X;
				_lastIndex++;
			}
		}
	}
}

 

 

 

 

노란 블럭 : 이동 경로

녹색 : 플레이어

붉은색 : 종점

왼쪽 상단 : 시작점

 

 

 

단점 : 목표하는대상과 거리가 멀 수록 성능이 떨어진다 => 조사 해야 하는 주변 블락 들이 많아지게 됨으로

장점 : BFS 보다 주변 환경이 반영된 좀 더 빠른 길 찾기가 가능하다, BFS 는 조사하는 범위가 계속 커진다

astar 는 BFS 보다는 조사 범위가  타일 하나의  누적 이동 거리+  플레이어의 위치에서 목표지점까지의 거리

를 고려하게 됨으로 좀 덜 커질 수 있다

 

 

거리 찾는데 Astar 도 느린건 마찬가지다 그렇다면?

JPS : 대상지점까지 거리를 찾는건 Astar 와 유사한데 길을 찾을때 대상 목표지점과 플레이어 사이에 벽같은게 있다면 벽면의 외각 부분에 우선순위가 높아 그쪽을 먼저 향해 가는 방식으로 주변 모든 타일을 게속 탐색하면서 가는 방식보다 성능이 빠르다