65. A* (유니티)

Cube를 하나 만들어 플레이어로 둔다.

Grid라는 Quad를 만들어 프리팹화 한다.

큐브, 장애물 그리드, 길 그리드, 플레이어의 색을 표시할 마테리얼을 둔다.

//Click.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
/*
 * 설명 : 임의로 장애물을 만들고 지우고 경로를 출력하는 임시 클래스
 * 최종 수정일 : 18.8.10
 */
public class Click : MonoBehaviour
{
    public GameObject player; // 플레이어의 오브젝트 저장
    public Player ThePlayer; // 플레이어 스크립트 저장
    public GridData thisGrid; // 그리드 데이터를 매번 꺼냈을 때 저장해 둘 아이
    GridData._type t; //그리드 타입을 둘 것임
    Vector3 v; // 얘는 마우스 포지션 저장할 벡터
    Ray r; // 얘는 그 포지션으로 실제 그리드 좌표 따기 위해 ray 저장할 곳
 
    private void Update()
    {
        if (Input.GetMouseButtonDown(0)) // 좌클릭 했으면 실행
        {
            v = Input.mousePosition;//알거니까 여기부터 몇 줄은 설명 생략
            r = Camera.main.ScreenPointToRay(v);
            RaycastHit[] hits = Physics.RaycastAll(r);
            foreach (RaycastHit hit in hits)
            {
                if (hit.collider.name.Equals("Grid(Clone)"))//니가 클릭한 그리드가 이 그리드냐
                {//정직하구나 상으로 그리드 데이터를 주마
                    thisGrid = hit.collider.gameObject.GetComponent<GridData>();
                    switch (thisGrid.type)
                    {//그리드의 타입을 바꿔줌.
                        case GridData._type.way:
                            t = GridData._type.obstacle;
                            break;
                        case GridData._type.obstacle:
                            t = GridData._type.way;
                            break;
                    }
                }
            }
        }
        if (Input.GetMouseButton(0))//클릭한 후 쭉 드래그하는 경우. 다른 건 딱히 없음.
        {
            v = Input.mousePosition;
            r = Camera.main.ScreenPointToRay(v);
            RaycastHit[] hits = Physics.RaycastAll(r);
            foreach (RaycastHit hit in hits)
            {
                if (hit.collider.name.Equals("Grid(Clone)"))
                {
                    thisGrid = hit.collider.gameObject.GetComponent<GridData>();
                    if (thisGrid.type != t)//타입이 내가 색칠하려는 타입과 다르네?
                    {//그럼 너도 그 타입이 되어라
                        switch (thisGrid.type)
                        {
                            case GridData._type.way:
                                thisGrid.ChoiceObstacle();
                                break;
                            case GridData._type.obstacle:
                                thisGrid.ChoiceWay();
                                break;
                        }
                    }
                }
            }
        }
 
        if (Input.GetMouseButtonDown(1)) // 우클릭했음
        {
            ThePlayer = player.GetComponent<Player>();
            v = Input.mousePosition;
            r = Camera.main.ScreenPointToRay(v);
            RaycastHit[] hits = Physics.RaycastAll(r);
            foreach (RaycastHit hit in hits)
            {
                if (hit.collider.name.Equals("Grid(Clone)")) //그리드를 우클릭했느냐
                {//A* 알고리즘을 시작하고 리턴받아라
                    thisGrid = hit.collider.gameObject.GetComponent<GridData>();
                    Stack<GridData> yourRoute = AStar.instance.Move(ThePlayer.gridX, ThePlayer.gridZ, thisGrid.gridNum % MakeGrid.instance.gridMaxX, thisGrid.gridNum / MakeGrid.instance.gridMaxZ);
                    for (int i = 0, c = yourRoute.Count; i < c; ++i)
                    {//리턴 받은 아이를 이용해 경로를 색칠하고 로그에 경로를 순서대로 출력해 줘
                        GridData g = yourRoute.Pop();
                        print(i.ToString() + ":" + g.x.ToString() + ", " + g.z.ToString());
                        g.ColorCollectWay();
                    }
                }
            }
        }
    }
 
}
 

//Player.cs
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
/*
 * 설명 : 에이스타를 위한 플레이어의 그리드 좌표를 저장하는 클래스
 * 최종 수정일 : 18.8.10
 */
public class Player : MonoBehaviour
{
    public int beforeGridX, beforeGridZ; // 이전 그리드 좌표. 그리드에 입힌 색을 없애는 데에 필요.
    public int gridX, gridZ; // 현재 플레이어의 그리드 x, z좌표 저장
    public bool first = true; // 게임 켜고 최초 실행인가.
    private void Update()
    {
        if (first) // 얘를 스타트에 넣으면 꼬일 경우가 있어서 업데이트 중 최초 실행으로 함
        {
            ValueInit(); // 값 초기화
            MakeGrid.instance.GridDataList[gridZ * MakeGrid.instance.gridMaxX + gridX].ColorPlayer(); // 플레이어 그리드 위치에 색 입힘
            first = false; // 이제 최초 아니라고 선언
        }
        CheckPlayerGrid();
    }
 
    //이전 그리드 값과 현 그리드 값 저장.
    private void ValueInit()
    {
        beforeGridX = gridX;
        beforeGridZ = gridZ;
        gridX = Mathf.RoundToInt(transform.position.x - MakeGrid.instance.XStart);//반올림
        gridZ = Mathf.RoundToInt(transform.position.z - MakeGrid.instance.ZStart);
    }
 
    //현재 플레이어의 그리드를 체크해 그리드 색을 교체해 줌
    private void CheckPlayerGrid()
    {
        ValueInit();
        if (beforeGridX != gridX || beforeGridZ != gridZ)
        {
            MakeGrid.instance.GridDataList[beforeGridZ * MakeGrid.instance.gridMaxX + beforeGridX].ColorWay();
            MakeGrid.instance.GridDataList[gridZ * MakeGrid.instance.gridMaxX + gridX].ColorPlayer();
        }
    }
}

//AStar.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
/*
 * 설명 : A* 알고리즘을 진행해 경로 스택을 리턴하는 클래스
 * 최종 수정일 : 18.8.10
 */
public class AStar : MonoBehaviour
{
    static public AStar instance; // A*는 하나만 둘 거라서 
    MakeGrid TheMakeGrid;
    Priority_Queue<GridData> openList; // 우선순위 큐. 탐색 예정인 애들 저장.
    public Stack<GridData> yourRoute; // 확정된 경로 저장
    int nowCheck = 0, maxCheck = 0; // 모든 노드를 탐사할 수 없으니 최대 횟수를 둠. 탐사하는 그리드 기준으로 주변 장애물 수에 따라 갈림
 
    private void Start()
    {
        instance = this;
        TheMakeGrid = MakeGrid.instance;
        openList = new Priority_Queue<GridData>();
        yourRoute = new Stack<GridData>();
    }
 
    /// <summary>
    /// AStar Function
    /// sx : firstX, sy : firstY, fx : finishX, fy : finishY
    /// </summary>
    //A* 알고리즘 호출할 함수
    public Stack<GridData> Move(int sx, int sy, int fx, int fy)
    {
        Stack<GridData> returnStack = TheAStar(sx, sy, fx, fy, true);
        return returnStack;
    }
 
    //A* 관련 값 초기화
    public void AStarInit()
    {
        TheMakeGrid.ResetGridData();
        openList.Clear();
        nowCheck = 0;
        maxCheck = 0;
        yourRoute.Clear();
    }
 
 
    //A*를 재귀로 돌림. A*는 해봤을 테니 자세한 설명은 생략. 다 돌고나면 경로를 스택에 담아 리턴.
    private Stack<GridData> TheAStar(int sx, int sy, int fx, int fy, bool first = false)
    {
        GridData now = TheMakeGrid.GridDataList[sx + sy * TheMakeGrid.gridMaxX], around;
        if (first)
        {
            AStarInit();
            now.g = 0;
            int rx = Mathf.Abs(sx - fx);
            int ry = Mathf.Abs(sy - fy);
            if (rx > ry)
                now.h = ry * 14 + (rx - ry) * 10;
            else
                now.h = rx * 14 + (ry - rx) * 10;
            now.f = now.g + now.h;
            now.start = true;
            now.check = true;
            GridData fin = TheMakeGrid.GridDataList[fx + fy * TheMakeGrid.gridMaxX];
            fin.finish = true;
            for (int i = fy - 1; i < fy + 2; ++i)
                for (int j = fx - 1; j < fx + 2; ++j)
                {
                    if (i < 0 || i >= TheMakeGrid.gridMaxZ || j < 0 || j >= TheMakeGrid.gridMaxX)
                        continue;
                    if (TheMakeGrid.GridDataList[j + i * TheMakeGrid.gridMaxX].type.Equals(GridData._type.way))
                        ++maxCheck;
                }
        }
        for (int i = sy - 1; i < sy + 2; ++i)
        {
            for (int j = sx - 1; j < sx + 2; ++j)
            {
                if (i < 0 || i >= TheMakeGrid.gridMaxZ || j < 0 || j >= TheMakeGrid.gridMaxX)
                    continue;
                around = TheMakeGrid.GridDataList[j + i * TheMakeGrid.gridMaxX];
                if (!around.check && around.type.Equals(GridData._type.way))
                {//아예 안 본 녀석이다
                    around.check = true;
                    if (i.Equals(sy) || j.Equals(sx))
                        around.g = now.g + 10;
                    else
                        around.g = now.g + 14;
                    int rx = Mathf.Abs(j - fx);
                    int ry = Mathf.Abs(i - fy);
                    if (rx > ry)
                        around.h = ry * 14 + (rx - ry) * 10;
                    else
                        around.h = rx * 14 + (ry - rx) * 10;
                    around.f = around.h + around.g;
                    around.prevGridNum = now.gridNum;
                    openList.push(around);
                }
                else if (around.check && (i != sy || j != sx))
                {
                    int g = now.g + 10;
                    if (i != sy && j != sx)
                        g += 4;
                    int rx = Mathf.Abs(j - fx);
                    int ry = Mathf.Abs(i - fy);
                    int h;
                    if (rx > ry)
                        h = ry * 14 + (rx - ry) * 10;
                    else
                        h = rx * 14 + (ry - rx) * 10;
                    int f = h + g;
                    if (around.f > f)
                    {
                        around.prevGridNum = now.gridNum;
                        around.f = f;
                        around.g = g;
                        around.h = h;
                    }
                }
                if (around.finish)
                    ++nowCheck;
            }
        }
 
        if (openList.count > 0 && nowCheck < maxCheck)
        {
            now = openList.pop();
            TheAStar(now.gridNum % TheMakeGrid.gridMaxX, now.gridNum / TheMakeGrid.gridMaxZ, fx, fy);
        }
        else
        {
            int next = fx + fy * TheMakeGrid.gridMaxX;
            while (true)
            {
                yourRoute.Push(TheMakeGrid.GridDataList[next]);
                if (TheMakeGrid.GridDataList[next].start)
                {
                    break;
                }
                else
                {
                    next = TheMakeGrid.GridDataList[next].prevGridNum;
                }
            }
        }
        return yourRoute;
    }
}
 
/// <summary>
/// Priority_Queue Function(Compare GridData's F, low value pop)
/// </summary>
// C#은 우선순위 큐가 없나보길래 임시로 만듦. 발퀄 ㅈㅅ
public class Priority_Queue<T>
{
    List<GridData> nowList;
 
    public int count
    {
        get
        {
            return nowList.Count;
        }
    }
 
    public Priority_Queue()
    {
        nowList = new List<GridData>();
    }
 
    public void push(GridData data)
    {
        int count = nowList.Count;
        int index = -1;
        if (count < 1)
        {
            nowList.Add(data);
            return;
        }
        for (int i = count; --i > -1;)
            if (nowList[i] < data)
            {
                index = i + 1;
                break;
            }
        if (index.Equals(-1))
            index = 0;
        nowList.Insert(index, data);
    }
 
    public GridData pop()
    {
        GridData g = nowList[0];
        nowList.RemoveAt(0);
        return g;
    }
 
    public void Clear()
    {
        nowList.Clear();
    }
}

//GridData.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
/*
 * 설명 : 각 그리드가 데이터를 저장해두는 클래스
 * 최종 수정일 : 18.8.10
 */
public class GridData : MonoBehaviour
{
    public int gridNum; // 현 그리드의 넘버를 저장. 변경 X
    public int f; // A* f값
    public int g; // A* g값
    public int h; // A* h값
    public bool start; // 시작 플레이어 위치인 애면 트루
    public bool finish; // 도착지면 트루
    public bool check; // 이미 체크한 애면 트루
    public int prevGridNum; // 탐색이 끝나면 경로를 잇기 위해 이어진 곳의 그리드 넘버를 저장
 
    public Material wayMat, obstacleMat, playerMat; // 그냥 볼라고 넣은거
    public float x, z; // x값, z값
    public enum _type { obstacle, way }; // obstacle = 장애물, way = 길. 검사할 때는 타입을 추가해서 장애물이 아닌 적플레이어 등도 넣기를 추천
    public _type type = _type.way; // 기본적으로는 다 way로.
    private MeshRenderer TheMeshRenderer; // 메쉬렌더러
    private Material back; // 경로 탐색한 녀석이 보인 뒤 몇 초 뒤에 다시 원 상태로 돌려주는 데, 그 마테리얼 임시 저장
 
    private void Start()
    {
        TheMeshRenderer = GetComponent<MeshRenderer>();
    }
 
    //그리드 값 초기화
    public void Init()
    {
        f = -1;
        g = 0;
        h = 0;
        prevGridNum = -1;
        start = false;
        finish = false;
        check = false;
    }
 
    //현 그리드를 길인 그리드로 바꿀 때 way 타입을 넣음 
    public void ChoiceWay()
    {
        if (type.Equals(_type.obstacle))
        {
            ColorWay();
            type = _type.way;
        }
    }
 
    //현 그리드를 장애물인 그리드로 바꿀 때 obstacle 타입을 넣음
    public void ChoiceObstacle()
    {
        if (type.Equals(_type.way))
        {
            ColorObstacle();
            type = _type.obstacle;
        }
    }
 
    //그리드의 색을 길 색으로 바꿈
    public void ColorWay()
    {
        TheMeshRenderer.material = wayMat;
    }
 
    //그리드의 색을 장애물 색으로 바꿈
    public void ColorObstacle()
    {
        TheMeshRenderer.material = obstacleMat;
    }
 
    //그리드의 색을 플레이어 색으로 바꿈 (경로 색도 이거임)
    public void ColorPlayer()
    {
        TheMeshRenderer.material = playerMat;
    }
 
    //경로를 표시. 3초 뒤 Color 함수를 호출해 색을 원래대로 돌림
    public void ColorCollectWay()
    {
        back = TheMeshRenderer.material;
        ColorPlayer();
        Invoke("ColorBack", 3);
    }
 
    //색을 원래대로 돌림
    public void ColorBack()
    {
        if (back != null)
            TheMeshRenderer.material = back;
    }
 
    #region region : 연산자 오버로딩 부분
    public static bool operator <(GridData g1, GridData g2)
    {
        return (g1.f < g2.f);
    }
 
    public static bool operator >(GridData g1, GridData g2)
    {
        return (g1.f > g2.f);
    }
 
    public static bool operator <=(GridData g1, GridData g2)
    {
        return (g1.f <= g2.f);
    }
 
    public static bool operator >=(GridData g1, GridData g2)
    {
        return (g1.f >= g2.f);
    }
 
    public static bool operator ==(GridData g1, GridData g2)
    {
        return (g1.f == g2.f);
    }
 
    public static bool operator !=(GridData g1, GridData g2)
    {
        return (g1.f != g2.f);
    }
    #endregion
}

//MakeGrid.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
/*
 * 설명 : 그리드를 만드는 클래스
 * 최종 수정일 : 18.8.10
 */
public class MakeGrid : MonoBehaviour
{
    static public MakeGrid instance; // 유일한 애라 싱글톤으로 뽑음
    public GameObject GridPrefab; // 그리드로 쓸 프리팹 저장
    public int gridMaxX, gridMaxZ; // 그리드가 X, Z방향으로 몇 개인지 설정
    public float XStart, ZStart; // 그리드에 있어 X의 시작 좌표, Z의 시작 좌표. 시작 좌표로부터 X도 Z도 커지는 방향으로 맵이 생김
    public int gridGap = 1; // 그리드 사이즈. 우선은 1로 고정을 추천. 숫자를 바꾸면 그리드 프리팹의 스케일 등도 바뀌어야 할 것.
    [HideInInspector]
    public List<GameObject> GridList = new List<GameObject>(); //각 그리드 오브젝트를 저장할 리스트
    [HideInInspector]
    public List<GridData> GridDataList = new List<GridData>(); //각 그리드가 가진 GridData 클래스를 저장할 리스트
 
    private void Start()
    {
        instance = this;
        Vector3 turn = new Vector3(90, 0, 0); // 그리드 세워진 애라 그냥 눕혀줄거임 신경 ㄴㄴ ㄱㅊ
        for(int i = 0; i < gridMaxZ; ++i)
        {
            for(int j = 0; j < gridMaxX; ++j)
            {
                GameObject test = Instantiate(GridPrefab, new Vector3(XStart + j * gridGap, 0.5f, ZStart + i * gridGap), Quaternion.identity, transform); // 그리드 만듦
                test.transform.Rotate(turn); // 그리드 세워진 애라 이쁘게 눕힘
                GridData g = test.GetComponent<GridData>();
                g.x = test.transform.position.x; // GridData에 현 x값 저장
                g.z = test.transform.position.z; // GridData에 현 z값 저장
                g.gridNum = j + (i * gridMaxZ); // GridData에 현 그리드 번호 저장
                g.Init(); // 그리드 내 값 초기화
                GridList.Add(test); // 그리드 리스트에 현 그리드 저장
                GridDataList.Add(g); // 그리드 데이터 리스트에 현 그리드의 데이터 저장
            }
        }
    }
 
    //모든 그리드를 예쁘게 초기화 함.
    public void ResetGridData()
    {
        for(int i = 0; i < GridDataList.Count; ++i)
        {
            GridDataList[i].Init();
        }
    }
}
 

GridManager라는 오브젝트를 하나 만들고 MakeGrid.cs, Click.cs, AStar.cs를 넣는다.

플레이어 용 큐브에 Player.cs를 넣는다.

그리고 돌린다

임의로 만든 장애물.

왼쪽 맨 아래가 플레이어 위치.

중심부를 눌렀을 때 이렇게 경로를 출력한다.