지금까지 BFS, Dijksta 와 같이 써먹어왔던 알고리즘은 '모든' 길을 탐색해야 한다는 사실이 있다.. 따라서, 모든 지점이 탐색된다는 불편함이 존재한다. 길찾기를 할 때는 목적지만 보는게 더 좋기 때문! 그래서 이를 개선한 알고리즘이 바로 A* 알고리즘이다. A* 알고리즘에서 새로운 개념이 등장하는데 그것은 휴리스틱이다. 휴리스틱은 길을 어림잡아 매긴 수치이다.파란색이 길이고, 빨간색이 벽이고 녹색이 도착지점이다. 여기서 휴리스틱은 3이다.. 내가 갈 수 있는 길인지 판단하지 않고 그냥 나와 목적지까지의 거리를 가중치로 부여하는것. 그래서 현재 거리와 (G) 휴리스틱(H)가 더해진 값 F로 계산을 진행한다. (F = G + H) 이렇게 아무 의미 없이 탐색을 하는 다익스트라와 달리 이 휴리스틱이 ..

BFS를 이용하여 길찾기 알고리즘을 시도해보았다. 하지만, 길을 가는 비용이 모두 동일하다 라는 조건이 성립해야만 이 BFS 알고리즘을 사용할 수 있다. 그렇다면, 이제 길에 각기 다른 비용이 들어간다고 해 보자. 어떤게 비용이 적게들까?? 바로 1, 2, 3, 4, 5 이렇게 가는 방법이다. 왜냐면 5의 비용을 적기 때문! 이렇게 가중치가 있을 경우 최단경로를 구할 수 있는 알고리즘이 다익스트라 알고리즘이다. 이제 다익스트라 알고리즘을 코드로 구현 해 보자. 우리가 눈으로 볼 때는 당연한 말이지만 알고리즘을 이해하려면 항상 컴퓨터적인 사고를 해야한다. 나머지 비용은 모른다. 오로지 내 앞에 연결된 Vertex까지의 비용을 알아내야 한다! 즉, 내가 연결된 Vertex의 모든 비용을 비교해서 최소 비용을..

지금까지 콘솔에서 BFS를 진행해서 별로 재미가 없었다. 동일한 구조를 가져와서 Unity에서 길찾기를 진행해보자! 먼저, Tile이라는 클래스를 하나 만든다. TileType로 벽과 길을 구분하는것은 동일하고 MeshRenderer에 접근해서 색을 변경함! Tile 2차원 배열을 생성하고, Instantiate로 실제 타일을 생성. 프리팹은 Tile 컴포넌트를 가지고 있다. 생성 후 위치를 조정해줘야 하는데, 오브젝트의 크기 + 위치로 해 줌! 그러면 딱 딱 맞춰서 들어감. 타일이 완성되었다! 이제 SideWinder 알고리즘을 이용하여 미로를 만들자. 미로가 정상적으로 생성되었다! 이제 플레이어를 만들어야 한다. Player Componet를 제작한다. 제일 먼저 할 것은 'Go' 함수를 만들었다. ..

BFS라는 개념에 대해서 알아보았다. 이제 길찾기를 진행해 본다면... 먼저, 길이 그래프여야 하는데 지금은 Tile 이다. 하지만 이런 타일의 규칙을 살펴보자면 TIle은 결국 Vertex라는 생각을 할 수 있고 결국 길은 상,하,좌,우 로 갈 수 있어서 하나의 타일당 자신의 상하좌우로 Edge를 형성함을 알 수 있다. 벽은 갈수 없으니 연결되어 있지 않다고 생각하면 된다. 따라서 이러한 개념으로 Tile에 BFS를 적용할 수 있다. Tile에 BFS를 적용 해 보자. 먼저, 타일은 X,Y로 되어있어서 상,하,좌,우에 맞는 각각의 X,Y 위치를 정의해줌을 알 수 있다. 그리고 찾은 Vertex또한 2차원 배열로 구성해서 기록한다. 그 외 진행은 역시 전에 만들어둔 BFS 형식과 동일하다. BFS가 끝날..

그래프를 순회하는 방법 BFS (Breadth First Search) 는 너비 우선 탐색이다. 이러한 그래프가 있으면 쭉 들어가는 DFS와 달리 인접한 Vertex에 모두 방문. 대충 이런식이다! BFS는 인접한 Vertex에 방문하는 형식이라서 길찾기 알고리즘에 쓰인다고 한다. DFS를 코드로 구현해본다면 이러하다. Queue 에 인접한 Vertex를 넣어서(예약해서) 다음 반복때 예약된 번호를 빼고 다시 인접한 Vertex를 예약하고.. Queue의 요소가 0이 될때까지 반복한다! Queue는 선입 선출의 자료구조라 먼저 예약된 Vertex가 먼저 나올것! parent와 distance라는 개념을 도입하면, 내가 어느 Vertex에서 왔는지, 내가 시작 위치보다 얼마만큼의 거리를 왔는지 볼 수 있다..

앞서 알아본 그래프에서 순회를 하려면 어떻게 해야 할까? 그래프는 배열처럼 인덱스를 증가시키면서 할 수 없는 구조이다. 따라서 순회를 하는 알고리즘이 존재하는데 그 중 하나가 DFS라는 놈이다. DFS는 Depth First Search로 깊이 우선 탐색이다. 깊이 우선 탐색은 연결된 길이 끝날때까지 쭉~ 가는것이다. 그리고 막다른 길이 나올 시 안갔던 길로 다시 쭉~ 가는 것 지금 그림에서는 0 - 1 - 2 를 가고 더이상 길이 없으니 가지 않았던 길 3 - 4 이렇게 가는것 한번 Graph와 DFS를 구현한다면 먼저 행렬로 구현한 그래프로 DFS를 진행하려면 내가 방문한 Vertex의 정보가 있어야한다. 방문 기록용 변수를 하나 생성 먼저 DFS 함수 시작으로 시작점(Vertex) 값을 받고 그 위..