저번 글에 이어 이번엔 알고리즘을 이용하여 출발지부터 목적지까지의 길을 표시해주는 것까지 구현해보도록 하겠습니다.
유니티(Unity) Grid지도 만들어 길찾기 구현하기(1)
유니티를 이용한 길찾기 를 구현해보기 위해 글을 작성하게 되었습니다. 길찾기 알고리즘은 상당히 다양하기에 각각의 알고리즘을 사용해볼 계획입니다. 그러기 위해서 Grid 지도를 생성해보고
ljhyunstory.tistory.com
먼저 길찾기 알고리즘/ 최단거리 / 최단경로 알고리즘에는 다양한 알고리즘이 있습니다.
그중에서 A*알고리즘과 다익스트라 알고리즘이 길찾기 알고리즘에 많이 사용된다는것을 알게되었고
이를 구현해 보기로 하였습니다.
하지만.... A*알고리즘의 경우 휴리스틱 함수값을 직접 설정하여 길을 찾는다는 점에서
일정한 거리상에 있는 그리드 좌표계에서의 길찾기에서는 필요가 없을것으로 생각되어져
일단 다익스트라 알고리즘으로 구성하게 되었습니다!
그럼 이제 시작!
간단하게 다익스트라 알고리즘의 실행방법에 대해서 정리해보자면
1. 시작점에서 이어진 정점에 대한 거리를 측정하여 Temp저장합니다.
2. 그중 가장 거리가 가까운 지점을 먼저 탐색합니다.
3. 가까운 지점에 도착했다면 다시 그 지점과 연결되어있는 지점의 거리를 Temp에 저장해줍니다
4. 그리고 Temp에 저장된 값중 거리값이 가장 가까운 지점을 탐색합니다.
이런식으로 계속 반복하게 됩니다.
한줄로 표현하자면
거리를 계속 저장하면서 제일 짧은 거리의 지점으로 이동하여 탐색을 진행한다는것!
여기서 저희는 경로를 저장할 것이기에 거리를 최신화 시켜주며 부모노드/이전 지점을 기록만 해주면 끝!
이제 구현부분입니다 .
선언부분은 아래처럼 구성됩니다.
public int StartTarget=0; // 시작점
public int EndTarget=99; // 목적지
private LineRenderer lineRenderer; // 길을 그려줄 라인렌더러
public GridSetting GridSetting; // 그리드 지점을 들고올 스크립
private List<List<int>> WayList=new List<List<int>>(); // 각 지점에 대한 연결노드
public List<GameObject> GridObj = new List<GameObject>(); // 각 지점에 대한 큐브 오브젝트
private void Start()
{
lineRenderer=GetComponent<LineRenderer>(); // 조절
lineRenderer.startWidth = .8f;
lineRenderer.endWidth = .8f;
}
그리고 길을 그려주는 함수를 따로 만들어 줍시다.( 이부분은 전 글에서 잘 소개 되어있습니다! [LineRenderer] )
public void WayPaint()
{
WayList = GridSetting.WayList;// 각 노드의 연결노드
GridObj = GridSetting.GridObj; // 각 노드의 오브젝트들
List<int> dijkstraList = dijkstra(StartTarget, EndTarget); // 다익스트라 알고리즘
List<Vector3> positionList=new List<Vector3>();//경로 지점
for (int i = 0; i < dijkstraList.Count; i++) //경로 만큼
{
positionList.Add(GridObj[dijkstraList[i]].transform.position);//다음점!
}
lineRenderer.positionCount = positionList.Count;
lineRenderer.SetPositions(positionList.ToArray()); // 그려주기
}
마지막으로 가장 중요한 다익스트라 알고리즘 구현 부분입니다 .
알고리즘을 구현하기 위해서는 3가지의 배열이 필요합니다.
1. 현위치에서 각노드까지의 거리
2. 각 노드의 방문 유무
3. 각 노드의 부모 노드 >> 경로를 위해선 필수!
public List<int> dijkstra(int start , int end) // 다익스트라 // 출발, 목적
{
List<int> dijkstraList = new List<int>(); //경로 저장 출력!
bool[] visited = new bool[WayList.Count]; // 방문
float[] distance = new float[WayList.Count]; // 현 위치에서의 거리 가중치
Array.Fill(distance, 987654321); // 처음엔 무한으로 채움
int[] parent = new int[WayList.Count]; // 각 노드의 최단 거리 노드 >> 경로!위처럼 선언해줍시다.
거리의 경우 처음값을 987654321같은 큰수로 채워 넣어줍시다. >> 최솟값으로 최신화 예정
그리고 가장 먼저 시작위치에 대한 탐색부터 마쳐봅시다.
distance[start] = 0;
visited[start] = true;
parent[start] = start;
for (int i = 0; i < WayList[start].Count; i++) // 시작위치에서 정점까지의 거리
{
distance[WayList[start][i]] = distanceCal(start, WayList[start][i]);
parent[WayList[start][i]] = start;
}지금 현재 wayList에는
wayList[Start]={1,2,3,4} >> 이런식으로 연결되어 있는 노드의 인덱스 번호가 저장되어있습니다!
그렇기에 WayList[start][i] = 연결된 노드의 인덱스 번호 라 생각하여 각각의 거리와 부모를 지정해줍시다.
이제 나머지 노드들을 탐색해 줍시다.
while(true)
{
int NearNodeInd = SortestNode(visited, distance); // 현재 연결된 노드들중 가장 가까운 노드
if(NearNodeInd < 0) // 갈때가 없다?
{
break;
}
...
}while문을 통한 무한반복에서 NearNodeInd(현재 탐색한 지점들과 인접노드들 중에서 가장 인접한 노드)를 찾아
그 노드의 인접한 노드를 찾아 다시 저장해줍시다. 그리고 더이상 탐색할 노드가 없을때까지 반복하게끔 구성했습니다.
가장 인접한 노드는 아래처럼 방문 유무와 거리의 단순 크기 비교로 구현해 보았습니다.
이 경우를 위해 우선순위 큐를 통해 구성하는 방법이 있었으나 노드의 수가 그렇게 많지 않기에 단순 크기비교로 구현하였습니다. (추후에 다익스트라 알고리즘을 구현하면서 우선순위큐도 사용해보겠습니다.)
private int SortestNode(bool[] visited, float[] distance)
{
int resultNode = -1;
float minDis = 987654321;
for(int i=0;i< WayList.Count; i++)
{
if (!visited[i]) // 아직 방문 x
{
if (distance[i]< minDis)
{
minDis = distance[i];
resultNode = i;
}
}
}
return resultNode;
}
다익스트라 내부에서 NearNodeInd 을 찾게되면 바로 방문 체크를 해주고 그에대한 간접노드를 아래처럼 탐색합니다.
visited[NearNodeInd] = true; // 출발
for (int j=0;j< WayList[NearNodeInd].Count;j++)
{
int TempInd = WayList[NearNodeInd][j];// 간접노드
if (visited[TempInd])//이미 왔다감
{
continue;
}
else if(distance[TempInd] > 5+ distance[NearNodeInd])//distanceCal(NearNodeInd, TempInd)
{
distance[TempInd] =5 + distance[NearNodeInd]; // distanceCal(NearNodeInd, TempInd)
parent[TempInd] = NearNodeInd;
}
}거리비교를 통해 최신화할지를 결정해줄텐데
현재 거리는 그리드를 통해 5로 일정하여 정수를 대입
>> 일정하지 않을시 distanceCal(NearNodeInd, TempInd) 사용하였습니다.
단순 오브젝트 거리 비교입니다.
private float distanceCal(int a, int b)// a와 b의 거리
{
float result = 0;
result = Vector3.Distance(GridObj[a].transform.position,GridObj[b].transform.position);
return result;
}
그리고 해당 목적지를 통과 못했을 경우와
경로를 위한 값들을 반환받기 위해 아래같이 구현해 보았습니다.
if (visited[end] == false) //목적지에 못갔다..
{
return dijkstraList;
}
int temp = end;
while (true)
{
dijkstraList.Add(temp);
if (temp == start)
{
break;
}
temp = parent[temp];
}
for (int i = dijkstraList.Count - 1; i >= 0; i--) // 출력부분
{
print(dijkstraList[i]);
}목적지 부분부터 부모를 타고 올라가 출발지에 도착하면 멈추게끔
이렇게 dijkstra 리스트를 받아와 아까 WayPaint함수로 그 지점간 연결을 하게되면 끝!
여기까지하면 끝!
여기서 좀더 추가해서 랜덤한 목적지를 가지게 되면 아래처럼 가능합니다.
끝!
두 글에 이어 유니티에서 길찾기를 구현해보았습니다.
전체코드
Navigation.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public class Navigation : MonoBehaviour
{
public int StartTarget=0; // 시작점
public int EndTarget=99; // 목적지
private LineRenderer lineRenderer; // 길을 그려줄 라인렌더러
public GridSetting GridSetting; // 그리드 지점을 들고올 스크립
private List<List<int>> WayList=new List<List<int>>(); // 각 지점에 대한 연결노드
public List<GameObject> GridObj = new List<GameObject>(); // 각 지점에 대한 큐브 오브젝트
private void Start()
{
lineRenderer=GetComponent<LineRenderer>(); // 조절
lineRenderer.startWidth = .8f;
lineRenderer.endWidth = .8f;
}
private void Update()
{
}
private int randTaget = 0;
IEnumerator time()
{
while (true)
{
yield return new WaitForSeconds(0.5f);
if (randTaget == 100)
{
randTaget = 0;
}
while (GridSetting.Check[randTaget]) // 못가는곳
{
randTaget++;
}
WayPaint();
randTaget += 1;
}
}
public void TestWayFun()
{
StartCoroutine(time());
}
public void WayPaint()
{
WayList = GridSetting.WayList;
GridObj = GridSetting.GridObj;
List<int> dijkstraList = dijkstra(31, randTaget);
List<Vector3> positionList=new List<Vector3>();//경로 지점
for (int i = 0; i < dijkstraList.Count; i++) //경로 만큼
{
positionList.Add(GridObj[dijkstraList[i]].transform.position);//다음점!
}
lineRenderer.positionCount = positionList.Count;
lineRenderer.SetPositions(positionList.ToArray());
}
private float distanceCal(int a, int b)// a와 b의 거리
{
float result = 0;
result = Vector3.Distance(GridObj[a].transform.position,GridObj[b].transform.position);
return result;
}
public List<int> dijkstra(int start , int end) // 다익스트라 // 출발, 목적
{
List<int> dijkstraList = new List<int>(); //경로 저장 출력!
bool[] visited = new bool[WayList.Count]; // 방문
float[] distance = new float[WayList.Count]; // 현 위치에서의 거리 가중치
Array.Fill(distance, 987654321); // 처음엔 무한으로 채움
int[] parent = new int[WayList.Count]; // 각 노드의 최단 거리 노드 >> 경로!
distance[start] = 0;
visited[start] = true;
parent[start] = start;
for (int i = 0; i < WayList[start].Count; i++) // 시작위치에서 정점까지의 거리
{
distance[WayList[start][i]] = distanceCal(start, WayList[start][i]);
parent[WayList[start][i]] = start;
}
while(true)
{
int NearNodeInd = SortestNode(visited, distance); // 현재 연결된 노드들중 가장 가까운 노드
if(NearNodeInd < 0) // 갈때가 없다?
{
break;
}
visited[NearNodeInd] = true; // 출발
for (int j=0;j< WayList[NearNodeInd].Count;j++)
{
int TempInd = WayList[NearNodeInd][j];// 간접노드
if (visited[TempInd])//이미 왔다감
{
continue;
}
else if(distance[TempInd] > 5+ distance[NearNodeInd])//distanceCal(NearNodeInd, TempInd)
{
distance[TempInd] =5 + distance[NearNodeInd]; // distanceCal(NearNodeInd, TempInd)
parent[TempInd] = NearNodeInd;
}
}
}
if (visited[end] == false) //목적지에 못갔다..
{
return dijkstraList;
}
int temp = end;
while (true)
{
dijkstraList.Add(temp);
if (temp == start)
{
break;
}
temp = parent[temp];
}
for (int i = dijkstraList.Count - 1; i >= 0; i--)
{
print(dijkstraList[i]);
}
return dijkstraList;
}
private int SortestNode(bool[] visited, float[] distance)
{
int resultNode = -1;
float minDis = 987654321;
for(int i=0;i< WayList.Count; i++)
{
if (!visited[i]) // 아직 방문 x
{
if (distance[i]< minDis)
{
minDis = distance[i];
resultNode = i;
}
}
}
return resultNode;
}
}
끝!
'유니티 최고 > 유니티 구현' 카테고리의 다른 글
| 유니티(Unity) 터치, 마우스 클릭시 이펙트 생성하기 (0) | 2024.04.04 |
|---|---|
| 유니티(Unity) URP환경에서 Shader Graphs를 이용해서 OutLine 생성하기 (0) | 2024.03.07 |
| 유니티(Unity) Grid지도 만들어 길찾기 구현하기(1) (2) | 2023.05.17 |
| 유니티(Unity) LineRenderer를 이용한 여러 객체 연결하기 (1) | 2023.05.16 |
| 유니티(Unity) 유니티에서 ChatGpt 봇 만들어보기 (0) | 2023.05.04 |
댓글