유니티 - 다익스트라를 이용하여 최단 경로 이동하기 (Move the Shortest Path using Dijkstra)

Unity 전체 링크

 

다익스트라(데이크스트라)를 이용하면 최소 경로를 찾을 수 있다.

그리고 최소 경로를 찾을 때 해당 경로를 저장해두면 경로도 구할 수 있다.

 

관련 알고리즘은 아래 링크를 참고하자.

- BOJ 11779 : 최소비용 구하기 2 (최단 경로 기억)

- BOJ 1261 : 알고스팟 (2차원 배열 다익스트라)

 

그리드 기반으로 맵을 탐색한 후,

빨간 큐브 (0, 1, 0)가 보라색 큐브 (-7, 1, 4)로 가기 위한 최단 경로를 찾아보고 직접 이동도 해보자.

그리드 보다 높게 보이기 위해 y = 1로 설정하였다.

 

최단 경로를 찾으면 아래와 같다.

 

Invoke는 필요 없으므로 원래대로 돌린다.

아래의 코드에서 다익스트라를 시작한다.

다익스트라 관련 코드는 #region Dijkstra Algorithm ~ #endregion 사이에 추가한다.

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];

    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);

        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);
                }
            }
        }
    }

    void Start()
    {
        gridParent = new GameObject("GridParent");

        BFS(0, 0);
    }
    
    #region Dijkstra Algorithm

    // ...

    #endregion
}

---

- BOJ 11779 : 최소비용 구하기 2 (최단 경로 기억)

- BOJ 1261 : 알고스팟 (2차원 배열 다익스트라)

 

최단 경로도 기억해야 하고 2차원 배열에서 다익스트라를 사용해야 한다.

따라서 위의 링크에 있는 알고리즘을 잘 조합해야 한다.

 

각 맵에 대한 거리를 저장할 distance, 방문 여부를 체크할 visitDijk, 경로를 기억하기 위한 from이 필요하다.

    int[,] distance = new int[MAP_SIZE, MAP_SIZE];
    bool[,] visitDijk = new bool[MAP_SIZE, MAP_SIZE];
    Vector3[,] from = new Vector3[MAP_SIZE, MAP_SIZE];

 

그리고 우선순위 큐를 위한 HEAP을 선언한다.

pop, push는 전체 코드를 참고한다.

    struct HEAP
    {
        public int r;
        public int c;
        public int value;
    }

    HEAP[] heap = new HEAP[MAP_SIZE * MAP_SIZE];
    int hn;

 

다익스트라가 완성된 후 from을 이용해 경로를 찾기 위한 함수는 아래와 같다.

Instantiate를 이용해 하얀 큐브(public으로 path를 선언)를 생성해서 경로를 확인하자.

경로가 잘 보이도록 chPos의 y 값을 0.1f로 하였다.

    void DFS(Vector3 pos)
    {
        Vector3 chPos;

        /* 빨간 큐브 좌표를 만나면 종료 */
        if (pos.x == 0 && pos.z == 0) return;

        DFS(from[(int)pos.x, (int)pos.z]);

        chPos = new Vector3(pos.x - OFFSET, 0.1f, pos.z - OFFSET);
        Instantiate(path, chPos, Quaternion.identity);

        chPos.y = 1.0f;
        moveList.Add(chPos);
    }

 

다익스트라 함수는 다음과 같다.

distance를 처리할 때, isPlaneAllDirection을 이용하여 장애물인 경우 100000에 해당하는 penalty를 준다.

그리고 한 칸 이동에 대한 비용이 있어야 하므로 매번 1을 더한다.

    void startDijkstra()
    {
        HEAP tmp, output;

        for (int i = 0; i < MAP_SIZE; i++)
            for (int k = 0; k < MAP_SIZE; k++)
                distance[i, k] = 0x7fff0000;

        //빨간 큐브 좌표 초기화.
        distance[0 + OFFSET, 0 + OFFSET] = 0;

        tmp.r = 0 + OFFSET; tmp.c = 0 + OFFSET;
        tmp.value = 0;

        push(tmp);

        while (hn != 0)
        {
            output = pop();

            if (visitDijk[output.r, output.c]) continue;

            visitDijk[output.r, output.c] = true;

            for (int i = 0; i < 4; i++)
            {
                int nr = output.r + dr[i];
                int nc = output.c + dc[i];

                if (nr < 0 || nc < 0 || nr >= MAP_SIZE || nc >= MAP_SIZE) continue;

                int obstacle 
                    = isPlaneAllDirection(nr - OFFSET, nc - OFFSET) ? 0 : 100000 /* penalty */;
                if (distance[nr, nc] > distance[output.r, output.c] + obstacle + 1)
                {
                    from[nr, nc] = new Vector3(output.r, 1, output.c);
                   
                    distance[nr, nc] 
                        = distance[output.r, output.c] + obstacle + 1 /* 한 칸 움직이는 비용 */;

                    tmp.r = nr; tmp.c = nc;
                    tmp.value = distance[nr, nc];

                    push(tmp);
                }
            }
        }

        DFS(new Vector3(-7 + OFFSET, 1, 4 + OFFSET) /* 보라색 큐브 좌표 */);
    }

실제 좌표와 2차원 배열에 저장하기 위한 좌표(OFFSET) 사용에 유의하자.

 

Start에서 BFS가 완료된 후, 다익스트라를 실행하자.

    void Start()
    {
        gridParent = new GameObject("GridParent");

        BFS(0, 0);

        startDijkstra();
    }

 

DFS에 의해 경로가 생성되었다.

---

이제 경로에 따라 블럭을 움직여보자.

여기서는 Invoke 대신 코루틴(Coroutine)을 이용하여 매번 다음 좌표를 넘겨 이동하자.

 

moveList는 from을 보고 만든 startBlock이 움직여야할 경로다. (스크립트에 startBlock을 public으로 선언)

mcnt는 moveList를 한 칸씩 처리할 index 변수다.

moving은 코루틴 중에 다시 코루틴이 실행되지 않도록 처리하는 bool 변수다.

다익스트라가 완료된 후, dijkstraCheck가 true가 되면 경로를 이동한다.

한 칸 움직일 때 이동하는 시간 blockMoveTime은 0.3초다.

    #region 경로 이동 변수 
    List<Vector3> moveList = new List<Vector3>();
    int mcnt;
    bool moving, dijkstraCheck;
    float blockMoveTime = 0.3f;
    #endregion

 

DFS 안에서 moveList에 좌표를 담아주면 된다.

이때, chPos의 y를 1.0f로 변경해야 움직일 블럭의 높이가 일치하게 된다.

    void DFS(Vector3 pos)
    {
        Vector3 chPos;

        /* 빨간 큐브 좌표를 만나면 종료 */
        if (pos.x == 0 && pos.z == 0) return;

        DFS(from[(int)pos.x, (int)pos.z]);

        chPos = new Vector3(pos.x - OFFSET, 0.1f, pos.z - OFFSET);
        Instantiate(path, chPos, Quaternion.identity);

        chPos.y = 1.0f;
        moveList.Add(chPos);
    }

 

블럭 한 칸 이동하기 (그리드 기반 이동, 코루틴)를 참고하여 아래와 같이 moveBlock 코루틴을 만든다.

그리고 Update에서 다익스트라 완료 후(dijkstraCheck = true) 이동한다.

    void Start()
    {
        gridParent = new GameObject("GridParent");

        BFS(0, 0);

        startDijkstra();

        dijkstraCheck = true;
    }
    
    ...
    
    private IEnumerator moveBlock(Vector3 target)
    {
        moving = true;

        float elapsedTime = 0.0f;

        Vector3 currentPosition = startBlock.transform.position;

        while (elapsedTime < blockMoveTime)
        {
            startBlock.transform.position 
                = Vector3.Lerp(currentPosition, target, elapsedTime / blockMoveTime);
            
            elapsedTime += Time.deltaTime;
            yield return null;
        }

        transform.position = target;

        moving = false;
    }

    void Update()
    {
        if (dijkstraCheck) /* dijkstra 완료 후 시작 */
        {
            if (moving == false && mcnt < moveList.Count)
                StartCoroutine(moveBlock(moveList[mcnt++]));
        }
    }

 

SearchPlane의 설정 상태는 아래와 같다.

 

게임을 실행하면 아래와 같이 경로를 따라 움직인다.

 

아래는 path 생성 코드를 지운 후에 위에서 바라본 모습이다.

 

최종 코드는 다음과 같다.

using System; /* Array.Clear */
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SearchPlane : MonoBehaviour
{
    GameObject gridParent;
    public GameObject grid1, grid2, path, startBlock;

    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];

    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);

        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);
                }
            }
        }
    }

    void Start()
    {
        gridParent = new GameObject("GridParent");

        BFS(0, 0);

        startDijkstra();

        dijkstraCheck = true;
    }

    #region Dijkstra Algorithm

    int[,] distance = new int[MAP_SIZE, MAP_SIZE];
    bool[,] visitDijk = new bool[MAP_SIZE, MAP_SIZE];
    Vector3[,] from = new Vector3[MAP_SIZE, MAP_SIZE];

    struct HEAP
    {
        public int r;
        public int c;
        public int value;
    }

    HEAP[] heap = new HEAP[MAP_SIZE * MAP_SIZE];
    int hn;

    #region 경로 이동 변수 
    List<Vector3> moveList = new List<Vector3>();
    int mcnt;
    bool moving, dijkstraCheck;
    float blockMoveTime = 0.3f;
    #endregion

    HEAP pop()
    {
        HEAP ret, tmp;

        ret = heap[1];
        heap[1] = heap[hn];
        heap[hn--].value = 0x7fff0000;

        for (int i = 1; i * 2 <= hn;)
        {
            if (heap[i].value < heap[i * 2].value && heap[i].value < heap[i * 2 + 1].value) break;
            else if (heap[i * 2].value < heap[i * 2 + 1].value)
            {
                tmp = heap[i * 2];
                heap[i * 2] = heap[i];
                heap[i] = tmp;

                i = i * 2;
            }
            else
            {
                tmp = heap[i * 2 + 1];
                heap[i * 2 + 1] = heap[i];
                heap[i] = tmp;

                i = i * 2 + 1;
            }
        }

        return ret;
    }

    void push(HEAP x)
    {
        HEAP tmp;
        heap[++hn] = x;

        for (int i = hn; i > 1; i /= 2)
        {
            if (heap[i / 2].value < heap[i].value) break;

            tmp = heap[i];
            heap[i] = heap[i / 2];
            heap[i / 2] = tmp;
        }
    }

    void DFS(Vector3 pos)
    {
        Vector3 chPos;

        /* 빨간 큐브 좌표를 만나면 종료 */
        if (pos.x == 0 && pos.z == 0) return;

        DFS(from[(int)pos.x, (int)pos.z]);

        chPos = new Vector3(pos.x - OFFSET, 0.1f, pos.z - OFFSET);
        Instantiate(path, chPos, Quaternion.identity);

        chPos.y = 1.0f;
        moveList.Add(chPos);
    }

    void startDijkstra()
    {
        HEAP tmp, output;

        for (int i = 0; i < MAP_SIZE; i++)
            for (int k = 0; k < MAP_SIZE; k++)
                distance[i, k] = 0x7fff0000;

        //빨간 큐브 좌표 초기화.
        distance[0 + OFFSET, 0 + OFFSET] = 0;

        tmp.r = 0 + OFFSET; tmp.c = 0 + OFFSET;
        tmp.value = 0;

        push(tmp);

        while (hn != 0)
        {
            output = pop();

            if (visitDijk[output.r, output.c]) continue;

            visitDijk[output.r, output.c] = true;

            for (int i = 0; i < 4; i++)
            {
                int nr = output.r + dr[i];
                int nc = output.c + dc[i];

                if (nr < 0 || nc < 0 || nr >= MAP_SIZE || nc >= MAP_SIZE) continue;

                int obstacle 
                    = isPlaneAllDirection(nr - OFFSET, nc - OFFSET) ? 0 : 100000 /* penalty */;
                if (distance[nr, nc] > distance[output.r, output.c] + obstacle + 1)
                {
                    from[nr, nc] = new Vector3(output.r, 1, output.c);
                   
                    distance[nr, nc] 
                        = distance[output.r, output.c] + obstacle + 1 /* 한 칸 움직이는 비용 */;

                    tmp.r = nr; tmp.c = nc;
                    tmp.value = distance[nr, nc];

                    push(tmp);
                }
            }
        }

        DFS(new Vector3(-7 + OFFSET, 1, 4 + OFFSET) /* 보라색 큐브 좌표 */);
    }

    private IEnumerator moveBlock(Vector3 target)
    {
        moving = true;

        float elapsedTime = 0.0f;

        Vector3 currentPosition = startBlock.transform.position;

        while (elapsedTime < blockMoveTime)
        {
            startBlock.transform.position 
                = Vector3.Lerp(currentPosition, target, elapsedTime / blockMoveTime);
            
            elapsedTime += Time.deltaTime;
            yield return null;
        }

        transform.position = target;

        moving = false;
    }

    void Update()
    {
        if (dijkstraCheck) /* dijkstra 완료 후 시작 */
        {
            if (moving == false && mcnt < moveList.Count)
                StartCoroutine(moveBlock(moveList[mcnt++]));
        }
    }

    #endregion
}

 

Unity Plus:

Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store

 

Unity Pro:

Unity Pro

 

Unity 프리미엄 학습:

Unity Learn