Chapter 6. A* 길찾기 알고리즘 구현
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 6. A* 길찾기 알고리즘
🚖 A* 길찾기 알고리즘 개념
다익스트라와 비교
- 다익스트라
- 해당 지점에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾는다. 👉 비효율적
- 따라서 시작 지점만 알면 된다. 목적지를 주진 않는다.
- 다익스트라를 목적지 찾으면 종료하게끔 개선할 수도 있지만 그래도 아쉽다. 매번 모든 지점마다 갈 수 있는 모든 경로에 대한 최단 거리를 찾아 비교하기 때문에.
- 예약된 정점들 중 최고의 정점을 선택할 땐
- 최단 거리 경로를 유지할 수 있는 정점을 선택한다.
- 해당 지점에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾는다. 👉 비효율적
- A*
- 모든 경로를 다 찾지 않는다.
- 시작 지점, 끝 지점 목적지. 이렇게 두 개가 주어진다. 목적지를 알고 있다.
- 예약된 정점들 중 최고의 정점을 선택할 땐
- 1️⃣ 최단 거리 경로를 유지할 수 있는 정점도 고려하고 👉
G- 어떤 경로를 따라왔냐에 따라 해당 정점의 비용은 그때 그때 다르므로 가변적이다.
- 2️⃣ 이에 더하여 목적지에 얼마나 가까운 정점인지 또한 고려한다. 👉
H(휴리스틱)- 목적지에 얼마나 가까운 정점인지를 고려하는건 피타고라스로 실제 남은 거리를 쓸 수도 있고 그냥 목적지까지 벽을 무시하고 그냥 가로 세로 총 몇 개의 타일이 남았는지 세는 등등 다양하게 정의할 수 있다.
- 이런 정의 방법을 휴리스틱 함수라고 하며 어떤 휴리스틱 함수를 사용하느냐에 따라 A* 알고리즘의 효율성이 좌지우지 된다.
- 어떤 경로를 따라왔냐와는 상관 없이 해당 정점이 목적지와 얼마나 가까운 정점인지는 고정적인 값이다.
- 목적지에 얼마나 가까운 정점인지를 고려하는건 피타고라스로 실제 남은 거리를 쓸 수도 있고 그냥 목적지까지 벽을 무시하고 그냥 가로 세로 총 몇 개의 타일이 남았는지 세는 등등 다양하게 정의할 수 있다.
- 최종 점수 👉
F=G+H
- 1️⃣ 최단 거리 경로를 유지할 수 있는 정점도 고려하고 👉
- 다익스트라 버전에서 2️⃣ 를 고려한 알고리즘이라고 할 수 있겠다.
- 다익스트라 👉
f = g기준으로 다음 방문 정점 선택 - A * 👉
f = g + h기준으로 다음 방문 정점 선택
- 다익스트라 👉
- 모든 경로를 다 찾지 않는다.
이 예제에서는
H를 [목적지까지 남은 X 방향의 타일 + Y 방향의 타일]로 할 것이다.
🚖 A* 길찾기 알고리즘 구현 : 📜Player.cs
BFS, 다익스트라랑 거의 똑같은 구조로 흘러간다.
h를 고려한다는 것을 제외하고는 비슷
🚔 상하좌우 이동만 가능할 때
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>();
public void Initialize(int posY, int posX, Board board)
{
PosX = posX;
PosY = posY;
_board = board;
AStar(); // ⭐A * 알고리즘⭐
}
struct PQNode : IComparable<PQNode>
{
public int F;
public int G;
// F랑 G만 알아도 H 는 구할 수 있으니 생략
public int Y;
public int X;
public int CompareTo(PQNode other)
{
if (F == other.F) // F 값을 기준으로 크기를 비교
return 0;
return F < other.F ? 1 : -1;
}
}
void AStar()
{
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
int[] cost = new int[] { 1, 1, 1, 1 };
// 점수 매기기
// F = G _ H
// F = 최종 점수 (작을 수록 좋음. 경로에 따라 달라짐)
// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음. 경로에 따라 달라짐)
// H = 목적지로부터 얼마나 가까운 곳인지를 따지는 보너스 점수 (작을 수록 좋음. 고정인 값)
// (y, x) 이미 방문 했는지 여부 (방문 = closed 상태)
bool[,] closed = new bool[_board.Size, _board.Size];
// 출발지에서 (y, x) 가는데에 현재까지 업뎃된 최단거리
// (y, x) 가는 길을 한번이라도 발견 했었는지 여부가 될 수도 있다. (한번이라도 예약 되있는지 여부)
// 발견(예약)이 안됐다면 Int32.MaxValue 로 저장이 되어 있을 것.
// F = G + H 값이 저장된다. (이 F 값이 가장 작은 정점이 방문 정점으로 선택될 것)
int [,] open = new int[_board.Size, _board.Size];
for (int y = 0; y < _board.Size; y++)
for (int x = 0; x < _board.Size; x++)
open[y, x] = Int32.MaxValue;
Pos [,] parent = new Pos[_board.Size, _board.Size];
// 우선순위 큐 : 예약된 것들 중 가장 좋은 후보를 빠르게 뽑아오기 위한 도구.
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
// 시작점 발견 (시작점 예약 진행)
open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX); // 시작점이니까 G는 0이고, H 값임.
pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);
while(pq.Count > 0)
{
// 제일 좋은 후보를 찾는다.
PQNode node = pq.Pop();
// 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
if (closed[node.Y, node.X])
continue;
// 방문 한다.
closed[node.Y, node.X] = true;
// 목적지에 도착했으면 바로 종료
if (node.Y == _board.DestY && node.X == _board.DestX)
break;
// 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
for (int i = 0; i < deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
// 유효 범위를 벗어났으면 스킵
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
// 벽으로 막혀서 갈 수 없으면 스킵
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
// 이미 방문한 곳이면 스킵
if (closed[nextY, nextX])
continue;
// 비용 계산
int g = node.G + cost[i];
int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);
// 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵 (업뎃 할 필요가 없으니까)
if (open[nextY, nextX] < g + h)
continue;
// 예약 진행
open[nextY, nextX] = g + h;
pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
parent[nextY, nextX] = new Pos(node.Y, node.X);
}
}
CalcPathFromParent(parent);
}
void CalcPathFromParent(Pos[,] parent)
{
int y = _board.DestY;
int x = _board.DestX;
while (parent[y, x].Y != y || parent[y, x].X != x)
{
_points.Add(new Pos(y, x));
Pos pos = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
const int MOVE_TICK = 10; // 10밀리세컨즈 = 0.01 초 마다 움직이게
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
return;
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK) // 이부분은 0.1초마다 실행
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
}
우선순위 큐에 넣을 데이터
예약한 데이터를 우선순위큐에 넣으며, POP 하면 가장 작은 값이 나오게 할 것이다.
struct PQNode : IComparable<PQNode>
{
public int F;
public int G;
// F랑 G만 알아도 H 는 구할 수 있으니 생략
public int Y;
public int X;
public int CompareTo(PQNode other)
{
if (F == other.F) // F 값을 기준으로 크기를 비교
return 0;
return F < other.F ? 1 : -1;
}
}
PQNode라는 타입의 데이터로F,G,Y,X정보를 묶어서, 예약하기로 결정한 좌표를 우선순위 큐에 넣을 것이다.F👉 해당 좌표의 최종 점수 F = G + HG👉 시작점에서 해당 좌표까지 이동하는데 드는 비용- H 는 F - G 로 알 수 있으므로 넣지 않음
Y👉 예약한 Y 좌표X👉 예약한 X 좌표
- 비교 함수
- int, float 같은 기본 데이터 타입이 아니기 때문에
PQNode타입의 비교 기준을 만들어 주어야 함F값이 작을 수록 루트에 위치하게 한다. 즉, 오름 차순. 예약 목록, 즉 우선순위 큐에서F값이 가장 작은 것을 POP 하게 할 것이다.- 최종점수
F값이 작을 수록 최단 경로를 만들기에 적합한 좌표
- 최종점수
F < other.F ? 1 : -1- 나의
F가 다른 PQNode 객체의F보다 작으면 1 리턴. 크면 -1 리턴.- ✨우선 순위 큐에
PQNode객체를 넣으면 이 비교 기준을 통해 힙 트리를 만들게 된다.✨
- ✨우선 순위 큐에
- 나의
- int, float 같은 기본 데이터 타입이 아니기 때문에
필요한 변수들
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
int[] cost = new int[] { 1, 1, 1, 1 };
bool[,] closed = new bool[_board.Size, _board.Size];
int [,] open = new int[_board.Size, _board.Size];
for (int y = 0; y < _board.Size; y++)
for (int x = 0; x < _board.Size; x++)
open[y, x] = Int32.MaxValue;
Pos [,] parent = new Pos[_board.Size, _board.Size];
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
- 현재 좌표의 앞 뒤 좌 우 좌표를 알기 위해선 이만큼 더해주기
deltaY[0],deltaX[0]👉 UpdeltaY[1],deltaX[1]👉 DowndeltaY[2],deltaX[2]👉 LeftdeltaY[3],deltaX[3]👉 Down
- 현재 좌표 기준 앞 뒤 좌 우로 각각 가기 위한 비용
cost전부 1 이지만 나중에 대각선도 갈 수 있게 된다면 대각선 비용은 상하좌우 비용과 다르게 적용될 것이다.
closed👉 방문한 좌표 표시- 사실 없어도 무방하다. 그 이유는 아래 후술.
open👉 단 한번이라도 예약된 적이 있는지- Int32.MaxValue 로 초기화 해둔다.
- 한번이라도 예약된적이 있다면 Int32.MaxValue 값이 아닐 것이다.
parent👉 방문한 좌표의 부모 좌표 표시 (이전 방문 좌표)- 미로 길 찾기를 위하여 저장
- 우선순위 큐
pg- 현재의 예약 좌표들을 이 우선순위 큐에
PQNode타입으로 저장한다. - 이 우선순위큐를 POP 하면 현재의 예약 좌표들 중 가장
F값이 작은 좌표가 빠져나오게 되고 이를 방문할 것이다.
- 현재의 예약 좌표들을 이 우선순위 큐에
방문 체크 안해줘도 된다.
방문 체크 안해줘도 답이 도출되는데 지장이 없다.
더 좋은, 더 최소의 가중치합(최단경로)를 가지는 경로를 발견했다면 최단경로를 새롭게 업데이트 해야 한다. 근데 이미 우선순위큐 안에 들어가있는 정점을 수정할 수는 없다. 큐는 배열처럼 이미 안에 들어있는 원소에 접근할 수 없기 때문이다. 따라서 어차피 가중치합만 다른 동일한 정점이 큐 안에 두개 있더라도 우선순위 큐 특성상 최소의 가중치합을 가진 정점이 먼저 빠져나오기에 동일한 정점 중 나중에 빠져나오는 정점은 업뎃 “당한”, 더 크고 안좋은 경로를 가진 정점일게 분명하다. 그러므로 어차피 이미 방문된 정점은 예약과정의 *if (open[nextY, nextX] < g + h) continue;* 코드에서 걸러지게 되어 있다. 다익스트라 알고리즘(어쨋든 A* 길찾기도 h를 고려하는 것만 다르지 베이스는 다익스트라니까)
0 👉 2(1) 1(10)
1 👉 0(10) 3(10)
2 👉 0(1) 3(1000)
3 👉 1(10) 2(1000)
예시) closed를 두지 않고, 방문체크를 하지 않는다고 가정했을 때
- 0 방문, 우선순위큐에 2 (1), 1 (10) 를 넣어 예약, 우선순위 큐 상태는 [ 2 (1), 1 (10) ]
- 2 방문, 우선순위큐에 3 (1000) 을 넣어 예약. 0 (1) 은 if (open[0] < 1 + 1 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[0] 은 출발지라 이미 0 인 상태이기 때문. 우선순위 큐 상태는 [ 1 (10), 3 (1000) ]
- 1 방문, 우선순위큐에 0 (10) 을 예약할 수 있는지 확인해보려는데 if (open[0] < 10 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함.(즉, 0이 방문된 정점인지 아닌지 굳이 검사하지 않더라도 이 과정 하나만으로 알아서 걸러집니다.) 3 (10) 은 if (open[3] < 10 + 10 ) continue; 에 해당되지 않기때문에 예약 가능. open[3] 은 현재 1001 이기 때문. open[3]은 20 으로 업데이트 되고 우선순위 큐 상태는 [ 3 (1000), 3(20) ] 이 됨. (큐에 해가 다른 동일한 두 정점 3 이 들어가있는 상태)
- 3 방문 (3(20)) , 우선순위큐에 2 (1000)을 예약할 수 있는지 확인해보려는데 if (open[2] < 20 + 1000 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[2]는 1이기 때문. 우선순위큐에 1 (10)을 예약할 수 있는지 확인해보려는데 if (open[1] < 20 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[1]는 10이기 때문. 3 과 연결되어있는 1 과 2 둘 다 예약되지 못함. 우선순위 큐 상태는 [ 3 (1000) ]
- 3 방문 (3(1000)), 어차피 앞서 3(20) 방문을 통해 2 와 1 은 3(1000) 에서 가는 것 보다는 더 짧은 경로로 업데이트가 되어 있는 상태이므로 어차피 3(1000)을 통한 2 와 1은 if (open[2] < 1000 + 1000 ) continue; if (open[2] < 1000 + 10 ) continue; 에 걸려 예약되지 못함. 우선순위큐는 비게 되어 종료.
이처럼 방문체크를 굳이 해주지 않아도 if (open[nextY, nextX] < g) continue; 로 재방문된 정점은 어차피 더 크고 안좋은 해를 가진 것이기 떄문에 어차피 여기서 걸러지게 되어 있는 것을 확인할 수 있다.
그럼에도 불구하고 방문 체크를 따로 해주는 이유
- 1️⃣ 가독성, 논리성, 역할분담
open은 좌표마다 현재까지의 최단 경로를 저장해두는 역할이다. if (open[nextY, nextX] < g + h) 로 이미 방문한 정점을 거를 수도 있지만! 그래도 역할을 분담하는게 코드를 이해하는 면에서도 좋을 것이다.
- 2️⃣ 비용 계산이 복잡하다면 이 복잡한 비용 계산을 피할 수 있게 된다.
- 방문 체크를 하고 미리 예약 전에 if (closed[nextY, nextX]) 재방문 정점을 걸러준다면,
g + h계산을 피할 수 있다. 경로 계산은 단순히 길이 계산 뿐만아니라 다른 여러 비용까지 합쳐진다면 더 복잡해질 수도 있다. 이 계산 자체를 피할 수가 있으므로 성능상 더 나을 수도 있다.
- 방문 체크를 하고 미리 예약 전에 if (closed[nextY, nextX]) 재방문 정점을 걸러준다면,
시작 좌표는 미리 예약
open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX); // 시작점이니까 G는 0이고, H 값임.
pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);
- 시작 좌표. 현재
PosY,PosX값은 각각 1, 1 open[1, 1]- G 는 0
- 시작 좌표에서 시작 좌표까지의 거리는 0
- H 는
- 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
- Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)
- G 는 0
pq우선순위 큐에 넣어 예약
과정 1️⃣ : 예약된 것들 중에서 방문할(제일 좋은) 정점 고르기
과정 1️⃣2️⃣3️⃣ 무한 반복. 우선순위큐가 빌 때까지 (더 이상 예약 된게 하나도 없을 때까지)
// 제일 좋은 후보를 찾는다.
PQNode node = pq.Pop();
// 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
if (closed[node.Y, node.X])
continue;
우선순위큐 POP 👉 예약된 좌표들 중에 가장 좋은 좌표(
F값이 가장 작은)를 꺼내고 이를 방문한다.
- 우선순위 큐를 쓰기 전엔, 예약된 것들 중에서 일일이 점수 값이 가장 작은 것을 비교해가며 찾았어야 했는데 편해졌다.
- 3️⃣ 에서 방문하기로 결정되고 1️⃣ 로 넘어온 경우라면 if (closed[node.Y, node.X]) 에 걸린다.
- 방문된 좌표라면 다시 1️⃣ 실행. 우선순위 큐에서 다른거 다시 꺼냄
- 위에서도 설명했지만 사실 이미 방문된 정점은 if (open[nextY, nextX] < g + h) 에서도 걸러질 수 있다. 그러나 1️⃣역할분담, 2️⃣비용계산 피하기 차원에서
closed를 따로 두어 방문 체크를 하고 예약 전에 미리 걸러주는 것이다.
과정 2️⃣ 방문한다.
// 방문 한다.
closed[node.Y, node.X] = true;
// 목적지에 도착했으면 바로 종료
if (node.Y == _board.DestY && node.X == _board.DestX)
break;
- 방문한다. 해당 좌표로
closed업데이트 - 목적지에 도착했다면 모든 과정을 종료한다.
과정 3️⃣ 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정
// 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
for (int i = 0; i < deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
// 유효 범위를 벗어났으면 스킵
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
// 벽으로 막혀서 갈 수 없으면 스킵
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
// 이미 방문한 곳이면 스킵
if (closed[nextY, nextX])
continue;
// 비용 계산
int g = node.G + cost[i];
int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);
// 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵
if (open[nextY, nextX] < g + h)
continue;
// 예약 진행
open[nextY, nextX] = g + h;
pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
parent[nextY, nextX] = new Pos(node.Y, node.X);
}
우선순위 큐 PUSH 👉 해당 좌표 예약하기
- 예약하기 적합한 좌표 찾기
- 현재 방문 좌표의 상 하 좌 우 좌표들 검사
- 이를
nextY,nextX에 담아 검사한다. - 예약 하면 안되는 좌표 스킵
- 유효 범위를 벗어났다면 스킵
- 벽이라면 갈 수 없으므로 스킵
- 연결되지 않은 정점이라고 생각할 수 잇겠다.
- 이미 방문 했었던 정점이라면 스킵
- 비용(
g + h)이 해당 좌표에서 이미 다른 경로에서 더 적은 비용을 찾았었다면 방금 구한 이 비용으로 새롭게 예약할 필요가 없으니 스킵g👉 현재 방문중인 노드까지의G값에 현재 검사중인 이nextY,nextX까지 오기 위한 비용 더하기h👉 현재 검사중인 이nextY,nextX기준 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
- 위 과정에서 스킵되지 않았다면 최종적으로 예약할 좌표로 선정
- 해당 좌표의
open에g + h비용 저장 - 해당 좌표를
PQNode로 묶어 우선순위 큐에 PUSH - 해당 좌표의
parent를 현재 방문 좌표인node.Y,node.X로 업뎃
- 해당 좌표의
- 이를
- 현재 방문 좌표의 상 하 좌 우 좌표들 검사
리스트에 방문한 정점들 차례로 추가 (최종 완성된 길)
CalcPathFromParent(parent); // 실행
void CalcPathFromParent(Pos[,] parent)
{
int y = _board.DestY;
int x = _board.DestX;
while (parent[y, x].Y != y || parent[y, x].X != x)
{
_points.Add(new Pos(y, x));
Pos pos = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
목적지부터 부모의 부모로 쭉쭉 타고 올라가면서 방문할 타일들을 전부 _points 리스트에 저장. 그리고 이 과정이 다 끝나면 리스트 거꾸로!
🚔 대각선 이동도 허용할 때
int[] deltaY = new int[] { -1, 0, 1, 0, -1, 1, 1, -1 };
int[] deltaX = new int[] { 0, -1, 0, 1, 1, -1, -1, 1 };
int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14 };
// 출발지 예약
open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)); // 시작점이니까 G는 0이고, H 값임.
pq.Push(new PQNode() { F = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);
// 예약시 비용 계산
int g = node.G + cost[i];
int h = 10 * (Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX));
- 대각선 방향 추가!
- UpLeft, DownLeft, DownRight, UpRight
deltaY[4],deltaX[4]👉 UpLeftdeltaY[5],deltaX[5]👉 DownLeftdeltaY[6],deltaX[6]👉 DownRightdeltaY[7],deltaX[7]👉 UpRight
cost- 대각선 이동 비용은
14(\(\sqrt{2} = 1.4\) X 10), 상하좌우 이동 비용은 10 으로 정해보았다. - 이에 대한 형평성을 위해
H값에 10 을 곱해주었다.- 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
- 즉 상하좌우 수평적인 방향이므로 하나 이동 당 10 쳐주기로.
- 대각선 이동 비용은
cf) 미로 찾기 무한 반복
const int MOVE_TICK = 100; // 100밀리세컨즈 = 0.1 초 마다 움직이게
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
{
_lastIndex = 0;
_points.Clear();
_board.Initialize(25, this); // 플레이어보다 먼저 이니셜라이징이 이루어져야 함
Initialize(1, 1, _board);
}
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK) // 이부분은 0.1초마다 실행
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
- if (_lastIndex >= _points.Count)
- 리스트를 다 다돌면
- 다시 다 초기화 하고 미로 다시 새롭게 초기화 하고 플레이어도 새로 초기화
- 리스트를 다 다돌면
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기