아래와 같이 평면을 그리드로 분할해보자.
BFS(Breadth First Search)는 너비 우선 탐색으로 길 찾기에 주로 쓰이는 알고리즘이다.
이번 경우에는 Plane에서 갈 수 있는 경로를 탐색하여 Grid로 표시하기 위해 BFS를 사용한다.
자세한 알고리즘 설명은 아래 링크를 참고하자.
아래의 영상은 BFS를 이용하여 (0, 0, 0) 좌표에서 Plane을 탐색한 결과다.
먼저 구현하기 쉽게 (0, 0, 0)에는 반드시 Plane이 있다고 가정하자.
여기서 Plane은 Tag = "Plane"인 경우를 말한다.
(0, 0, 0)에 반드시 Plane이 있다고 가정하고 이 점을 중심으로 그리드를 만든다.
원하는 대로 평면을 조합하여 탐색할 땅을 만들자.
빈 오브젝트를 만든 후 SearchPlane.cs를 추가한다.
탐색 방법은 BFS를 이용한 것이므로 미로 탐색 또는 단지번호붙이기와 완전히 동일하다.
따라서 C#의 Queue를 사용하지 않고 배열을 이용하여 Queue처럼 사용하였다.
using System; /* Array.Clear */
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class SearchPlane : MonoBehaviour
{
GameObject gridParent;
public GameObject grid1, grid2;
struct QUEUE
{
public int r;
public int c;
}
const int MAP_SIZE = 100;
const int OFFSET = MAP_SIZE / 2;
QUEUE[] queue = new QUEUE[MAP_SIZE * MAP_SIZE];
bool[,] visit = new bool[MAP_SIZE, MAP_SIZE];
bool isPlane(int r, int c)
{
RaycastHit hit;
if(Physics.Raycast(new Vector3(r, 5.0f, c), Vector3.down, out hit, 10.0f))
{
if (hit.collider.tag == "Plane")
return true;
}
return false;
}
int[] dr = { 0, -1, 0, 1 };
int[] dc = { -1, 0, 1, 0 };
void BFS(int sr, int sc)
{
int wp, rp;
wp = rp = 0;
Array.Clear(visit, 0, MAP_SIZE * MAP_SIZE);
queue[wp].r = sr;
queue[wp++].c = sc;
visit[sr + OFFSET, sc + OFFSET] = true;
GameObject go = Instantiate(grid1, new Vector3(sr, 0, sc), Quaternion.identity);
go.transform.SetParent(gridParent.transform);
while(wp > rp)
{
QUEUE output = queue[rp++];
for(int i = 0; i < 4; i++)
{
int nr = output.r + dr[i];
int nc = output.c + dc[i];
if(visit[nr + OFFSET, nc + OFFSET] == false && isPlane(nr, nc) == true)
{
queue[wp].r = nr;
queue[wp++].c = nc;
visit[nr + OFFSET, nc + OFFSET] = true;
if(((nr + nc) % 2) == 0)
go = Instantiate(grid1, new Vector3(nr, 0, nc), Quaternion.identity);
else
go = Instantiate(grid2, new Vector3(nr, 0, nc), Quaternion.identity);
go.transform.SetParent(gridParent.transform);
}
}
}
}
void Start()
{
gridParent = new GameObject("GridParent");
BFS(0, 0);
}
}
코드의 추가 설명은 다음과 같다.
gridParent는 만들어진 그리드를 관리하기 위한 부모다.
go.transform.SetParent(gridParent.transform)에 의해 생성된 그리드의 부모로 설정된다.
GameObject gridParent;
void Start()
{
gridParent = new GameObject("GridParent");
BFS(0, 0);
}
Vector3 (r, 0, c)에 Plane이 있는지 판단한다.
y = 5.0f 에서 아래로 10.0f인 레이캐스트로 확인한다.
현재 tag = "Plane"이라면 Plane으로 판단하기로 하였다.
bool isPlane(int r, int c)
{
RaycastHit hit;
if(Physics.Raycast(new Vector3(r, 5.0f, c), Vector3.down, out hit, 10.0f))
{
if (hit.collider.tag == "Plane")
return true;
}
return false;
}
알고리즘에서 좌표는 보통 (0, 0)에서 시작한다.
하지만 유니티에서는 음수 좌표가 포함될 수 있으므로 (0, 0)의 좌표는 (OFFSET, OFFSET)에 저장한다.
따라서 MAP_SIZE의 절반을 OFFSET으로 지정하였다.
MAP_SIZE도 자신이 만든 Plane을 보고 적절히 정해야 한다.
const int MAP_SIZE = 100;
const int OFFSET = MAP_SIZE / 2;
-> visit[sr + OFFSET, sc + OFFSET] = true;
그리드의 모습을 편하게 보기 위해 좌표의 합이 홀수냐 짝수냐에 따라 다른 색으로 표시하기 위한 로직이다.
if(((nr + nc) % 2) == 0)
go = Instantiate(grid1, new Vector3(nr, 0, nc), Quaternion.identity);
else
go = Instantiate(grid2, new Vector3(nr, 0, nc), Quaternion.identity);
그리드는 프리팹으로 만들어 스크립트에 추가한다.
여기서 그리드는 1 x 1 x 1 크기의 큐브다.
코드를 실행하면 아래와 같은 결과가 나온다.
왼쪽 위의 평면은 (0, 0, 0)과 연결되어 있지 않기 때문에 그리드가 생성되지 않는다.
이제 처음 본 영상에서 처럼 BFS가 어떻게 동작하는지 확인해보자.
그리드를 바로 생성하지 않고 List에 담아둔 후에 마지막에 한꺼번에 천천히 생성한다.
List<Vector3> rcList = new List<Vector3>();
따라서 Instantiate를 하는 코드에서 아래와 같이 코드를 수정한다.
//GameObject go = Instantiate(grid1, new Vector3(sr, 0, sc), Quaternion.identity);
//go.transform.SetParent(gridParent.transform);
rcList.Add(new Vector3(sr, 0, sc));
...
//if(((nr + nc) % 2) == 0)
// go = Instantiate(grid1, new Vector3(nr, 0, nc), Quaternion.identity);
//else
// go = Instantiate(grid2, new Vector3(nr, 0, nc), Quaternion.identity);
//go.transform.SetParent(gridParent.transform);
rcList.Add(new Vector3(nr, 0, nc));
BFS가 종료된 후, Invoke를 이용하여 함수를 일정시간 동안 반복하도록 하자.
int index = 0;
void invokeInstantiate()
{
if(index >= rcList.Count)
{
CancelInvoke();
return;
}
GameObject go;
int r = (int)rcList[index].x;
int c = (int)rcList[index++].z;
if (((r + c) % 2) == 0)
go = Instantiate(grid1, new Vector3(r, 0, c), Quaternion.identity);
else
go = Instantiate(grid2, new Vector3(r, 0, c), Quaternion.identity);
go.transform.SetParent(gridParent.transform);
}
void Start()
{
gridParent = new GameObject("GridParent");
BFS(0, 0);
InvokeRepeating("invokeInstantiate", 1.0f, 0.03f);
}
Invoke에 의해 BFS 종료 후, 1초 뒤에 0.03초 간격으로 너비 우선 탐색이 어떻게 진행되는지 볼 수 있다.
이제 장애물을 배치해보자.
(0, 0, 0)에는 배치되지 않도록 큐브를 적절히 배치하였다.
새로 추가한 Obstacle 큐브는 Tag가 Untagged이기 때문에 Raycast가 Plane을 검출하지 못한다.
따라서 아래와 장애물을 제외하고 그리드가 만들어진다.
하지만 Scene에서 자세히 보면, Obstacle을 침범하는 것을 알 수 있다.
(r, c)에 Raycast로 검출하기 때문에 그리드 영역을 침범하는지는 판단할 수가 없다.
따라서 isPlane을 주변 네 방향 탐색까지 추가하여 조건을 강화한다.
int[] dr = { 0, -1, 0, 1 };
int[] dc = { -1, 0, 1, 0 };
bool isPlane(int r, int c)
{
RaycastHit hit;
if(Physics.Raycast(new Vector3(r, 5.0f, c), Vector3.down, out hit, 10.0f))
{
if (hit.collider.tag == "Plane")
return true;
}
return false;
}
bool isPlaneAllDirection(int r, int c)
{
if (isPlane(r, c) == false) return false;
for(int i = 0; i < 4; i++)
{
int nr = r + dr[i];
int nc = c + dc[i];
if (isPlane(nr, nc) == false) return false;
}
return true;
}
void BFS(int sr, int sc)
{
...
while (wp > rp)
{
QUEUE output = queue[rp++];
for(int i = 0; i < 4; i++)
{
int nr = output.r + dr[i];
int nc = output.c + dc[i];
if(visit[nr + OFFSET, nc + OFFSET] == false && isPlaneAllDirection(nr, nc) == true)
{
...
}
}
}
}
네 방향 모두 Plane이라고 판단되는 경우만 그리드가 생성되었다.
좀 더 간편한 방법은 BoxCast(박스캐스트)를 사용하는 방법이다.
박스캐스트를 이용하면 그리드 한 칸을 통째로 검출할 수 있다.
bool isPlane(int r, int c)
{
RaycastHit hit;
Vector3 boxSize = new Vector3(1, 1, 1);
if (Physics.BoxCast(new Vector3(r, 5.0f, c), boxSize / 2, Vector3.down, out hit, Quaternion.identity, 10.0f))
{
if (hit.collider.tag == "Plane")
return true;
}
return false;
}
하지만 여기서는 네 방향 레이캐스트를 계속 사용한다.
혹시나 invoke로 그리드를 만들지 않았다면, 이미 만들어진 Grid로 인해 Plane을 못 찾을 수 있다.
이 경우에 Grid의 Collider를 제거하면 Raycast가 Grid를 검출하지 않는다.
장애물이 있는 경우 장애물을 피하며 Grid를 생성하게 된다.
최종 코드는 아래와 같다.
using System; /* Array.Clear */
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class SearchPlane : MonoBehaviour
{
GameObject gridParent;
public GameObject grid1, grid2;
struct QUEUE
{
public int r;
public int c;
}
const int MAP_SIZE = 100;
const int OFFSET = MAP_SIZE / 2;
QUEUE[] queue = new QUEUE[MAP_SIZE * MAP_SIZE];
bool[,] visit = new bool[MAP_SIZE, MAP_SIZE];
List<Vector3> rcList = new List<Vector3>();
int[] dr = { 0, -1, 0, 1 };
int[] dc = { -1, 0, 1, 0 };
bool isPlane(int r, int c)
{
RaycastHit hit;
if(Physics.Raycast(new Vector3(r, 5.0f, c), Vector3.down, out hit, 10.0f))
{
if (hit.collider.tag == "Plane")
return true;
}
return false;
}
bool isPlaneAllDirection(int r, int c)
{
if (isPlane(r, c) == false) return false;
for(int i = 0; i < 4; i++)
{
int nr = r + dr[i];
int nc = c + dc[i];
if (isPlane(nr, nc) == false) return false;
}
return true;
}
void BFS(int sr, int sc)
{
int wp, rp;
wp = rp = 0;
Array.Clear(visit, 0, MAP_SIZE * MAP_SIZE);
queue[wp].r = sr;
queue[wp++].c = sc;
visit[sr + OFFSET, sc + OFFSET] = true;
//GameObject go = Instantiate(grid1, new Vector3(sr, 0, sc), Quaternion.identity);
//go.transform.SetParent(gridParent.transform);
rcList.Add(new Vector3(sr, 0, sc));
while (wp > rp)
{
QUEUE output = queue[rp++];
for(int i = 0; i < 4; i++)
{
int nr = output.r + dr[i];
int nc = output.c + dc[i];
if(visit[nr + OFFSET, nc + OFFSET] == false && isPlaneAllDirection(nr, nc) == true)
{
queue[wp].r = nr;
queue[wp++].c = nc;
visit[nr + OFFSET, nc + OFFSET] = true;
//if(((nr + nc) % 2) == 0)
// go = Instantiate(grid1, new Vector3(nr, 0, nc), Quaternion.identity);
//else
// go = Instantiate(grid2, new Vector3(nr, 0, nc), Quaternion.identity);
//go.transform.SetParent(gridParent.transform);
rcList.Add(new Vector3(nr, 0, nc));
}
}
}
}
int index = 0;
void invokeInstantiate()
{
if(index >= rcList.Count)
{
CancelInvoke();
return;
}
GameObject go;
int r = (int)rcList[index].x;
int c = (int)rcList[index++].z;
if (((r + c) % 2) == 0)
go = Instantiate(grid1, new Vector3(r, 0, c), Quaternion.identity);
else
go = Instantiate(grid2, new Vector3(r, 0, c), Quaternion.identity);
go.transform.SetParent(gridParent.transform);
}
void Start()
{
gridParent = new GameObject("GridParent");
BFS(0, 0);
InvokeRepeating("invokeInstantiate", 1.0f, 0.03f);
}
}
+ 완성된 맵에서 다익스트라(Dijkstra)로 최단 경로를 찾아보자.
Unity Plus:
Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store
Have a 2D, 3D, VR, or AR project that needs cross-platform functionality? We can help. Take a look at the easy-to-use Unity Plus real-time dev platform!
store.unity.com
Unity Pro:
Unity Pro
The complete solutions for professionals to create and operate.
unity.com
Unity 프리미엄 학습:
Unity Learn
Advance your Unity skills with live sessions and over 750 hours of on-demand learning content designed for creators at every skill level.
unity.com
'개발 > Unity' 카테고리의 다른 글
| 유니티 - 자식 오브젝트 접근, 순회하기 (Iterating Child GameObjects) (0) | 2022.07.19 |
|---|---|
| 유니티 - 다익스트라를 이용하여 최단 경로 이동하기 (Move the Shortest Path using Dijkstra) (7) | 2022.07.17 |
| 유니티 - 인보크로 일정 시간 이후 함수 실행하기, 반복하기 (Invoke) (0) | 2022.07.16 |
| 유니티 Attribute - ExecuteInEditMode / ExecuteAlways로 편집 모드에서 스크립트 실행하기 (0) | 2022.07.10 |
| 유니티 Attribute - MenuItem 속성으로 원하는 함수 실행하는 메뉴 만들기 (Calling Function with MenuItem) (0) | 2022.07.09 |
댓글