일단 던전의 맵을 제작할때 Unity 엔진의 Isometric Tilemap 을 이용하여 제작 하였습니다.
따라서 맵이 일반적인 정사각형 모양의 타일이 아닌 마름모 모양의 타일로 구성되어 있습니다.
이로 인해 최간경로를 탐색할때 좌 우로 이동하는지, 위 아래로 이동하는지, 대각선으로 이동하는지에 따라 각각 이동 거리가 달라집니다.
public class Node
{
public Node(bool _isWall, int _x, int _y)
{
isWall = _isWall;
x = _x;
y = _y;
}
public bool isWall;
public Node ParentNode;
// G : 시작으로부터 이동했던 거리, H : |가로|+|세로| 장애물 무시하여 목표까지의 거리, F : G + H
public int x, y, G, H;
public int F
{
get
{
return G + H;
}
}
}
하나의 노드(타일) 클래스의 정의입니다.
A* 알고리즘은 F,G,H 이 세 값을 사용하는데
F는 출발 지점에서 목적지까지 예상되는 총 이동값,
G는 출발 지점에서 현재 지점까지의 이동값,
H는 현재 노드에서 목적지 까지 예상되는 값이 됩니다.
따라서 F = G + H 로 구할 수 있고, 항상 최고로 작은 F값을 가진 노드를 따라가고 F가 같으면 더욱 작은 H 를 가진 노드를 따라가는 길이 최단 경로가 됩니다.
//한 화면에 최대로 담기는 타일의 갯수가 가로,세로 10~11개 이기 때문에 이정도 크기로 고정하였다.
public Node[,] NodeArray = new Node[30, 30];
//시작노드, 목표 노드, 현재 탐색중인 노드
public Node StartNode, TargetNode, CurNode;
//현재 노드와 인접해있고 벽이 아닌, 이동 가능한 노드들의 리스트
public List<Node> OpenList;
//현재까지 지나온 노드들의 리스트
public List<Node> ClosedList;
//최종 경로
public List<Node> FinalNodeList;
탐색에 사용될 리스트들과 노드 변수들은 이렇게 됩니다.
일단 유저가 마우스 클릭을 하면 클릭된 지점의 타일맵은 TargetNode, 현재 캐릭터가 위치한 타일맵은 StartNode가 되고
현재 화면에 나와있는 모든 타일맵들의 정보를 NodeArray에 만들어 넣어 화면 안에 있는 타일들의 정보만 가지고 길찾기를 수행합니다.
//시작점부터 끝점까지 벽정보인지 아닌지 받아와서 노드를 만들어 준다.
for (int i = 0; i < sizeX; i++)
{
for(int j=0;j<sizeY;j++)
{
bool iswall = false;
//시작점부터 끝점까지 타일맵의 셀들을 조사하면서 해당 셀이 벽인지 확인해서 노드에 넣어준다
if (MapManager.GetI.IsWall(new Vector3Int(i + bottomLeft.x, j + bottomLeft.y, 0)))
{
iswall = true;
}
NodeArray[i, j] = new Node(iswall, i + bottomLeft.x, j + bottomLeft.y);
test.Add(NodeArray[i, j]);
}
}
// 시작과 끝 노드, 열린리스트와 닫힌리스트, 마지막리스트 초기화
StartNode = NodeArray[startPos.x - bottomLeft.x, startPos.y - bottomLeft.y];
TargetNode = NodeArray[targetPos.x - bottomLeft.x, targetPos.y - bottomLeft.y];
//처음 시작 노드를 OpenList에 넣고 알고리즘을 시작한다.
OpenList = new List<Node>() { StartNode };
ClosedList = new List<Node>();
FinalNodeList = new List<Node>();
길찾기는 OpenList에 더이상 남은 노드가 없거나 CurNode가 TargetNode와 같아졌을때 종료됩니다.
OpenList에 더이상 남은 노드가 없으면 TargetNode까지 가는 길이 존재하지 않는다는 뜻이고
CurNode가 TargetNode와 같아졌을때는 목적지에 도착 했다는 뜻 입니다.
전체적인 로직은 이렇게 진행됩니다.
1. OpenList에 들어있는 모든 노드들(CurNode에 인접하고, CloseList에 없고 범위를 벋어나지 않는 이동가능한 노드들) 중에서 가장 F값이 작거 나 F값이 같으면 H가 작은 노드를 CurNode로 바꿔주고 해당 노드는 OpenList에서 지워주고 CloseList에 넣어준다.
2. CurNode의 인접한 대각선 4방향, 상하좌우 4방향, 각각의 노드들을 검사하는데 각각의 노드들은 최대 탐색 범위(여기서는 화면에 보이는 범위)를 벗어나지 않고, 벽이 아니면서, CloseList에 존재하지 않아야 한다.
그러면서 또한 현재 노드의 G + 해당 노드로 가는데 드는 비용이 해당 노드의 G값(출발 지점에서 해당 노드까지의 이동값)보다 작거나 열린 리스트에 포함되어 있지 않아야 한다.
위의 조건들을 모두 충족하면 그때 각각의 노드들을 OpenList에 넣어준다.
3. 1번과 2번을 반복하다 CurNode가 TargetNode와 같아지면 탐색을 종료하고 각각의 노드가 가지고 있는 ParentNode를 이용해서 최종적인 투르 FinalNodeList를 만들어서 리턴해준다.
public List<Node> PathFinding(Vector3 start, Vector3 target)
{
//초기 세팅 (시작점, 끝점, TopRight, BottomLeft 지정 리스트들 초기화 등등을 수행한다.)
InitSetting(start, target);
while (OpenList.Count > 0)
{
// 열린리스트 중 가장 F가 작고 F가 같다면 H가 작은 걸 현재노드로 하고 열린리스트에서 닫힌리스트로 옮기기
CurNode = OpenList[0];
for (int i = 1; i < OpenList.Count; i++)
if (OpenList[i].F <= CurNode.F && OpenList[i].H < CurNode.H)
CurNode = OpenList[i];
OpenList.Remove(CurNode);
ClosedList.Add(CurNode);
// 마지막
if (CurNode == TargetNode)
{
Node TargetCurNode = TargetNode;
while (TargetCurNode != StartNode)
{
FinalNodeList.Add(TargetCurNode);
TargetCurNode = TargetCurNode.ParentNode;
}
FinalNodeList.Add(StartNode);
FinalNodeList.Reverse();
return FinalNodeList;
}
// ↗↖↙↘
if (allowDiagonal)
{
OpenListAdd(CurNode.x + 1, CurNode.y + 1);
OpenListAdd(CurNode.x - 1, CurNode.y + 1);
OpenListAdd(CurNode.x - 1, CurNode.y - 1);
OpenListAdd(CurNode.x + 1, CurNode.y - 1);
}
// ↑ → ↓ ←
OpenListAdd(CurNode.x, CurNode.y + 1);
OpenListAdd(CurNode.x + 1, CurNode.y);
OpenListAdd(CurNode.x, CurNode.y - 1);
OpenListAdd(CurNode.x - 1, CurNode.y);
}
return null;
}
void OpenListAdd(int checkX, int checkY)
{
// 상하좌우 범위를 벗어나지 않고, 벽이 아니면서, 닫힌리스트에 없다면
if (checkX >= bottomLeft.x && checkX < topRight.x + 1 && checkY >= bottomLeft.y && checkY < topRight.y + 1 && !NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y].isWall && !ClosedList.Contains(NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y]))
{
// 대각선 허용시, 벽 사이로 통과 안됨
if (allowDiagonal) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall && NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 코너를 가로질러 가지 않을시, 이동 중에 수직수평 장애물이 있으면 안됨
if (dontCrossCorner) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall || NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 이웃노드에 넣고, 수평으로 가는 직선은 16, 대각선은 14비용, 수직으로 가는 직선은 10
Node NeighborNode = NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y];
int MoveCost = 0;
if (CurNode.x - checkX == 0)//세로로 이동
{
MoveCost = CurNode.G + 10;
}
else if (CurNode.y - checkY == 0)//가로로 이동
{
MoveCost = CurNode.G + 16;
}
else //나머지 대각선으로 이동
{
MoveCost = CurNode.G + 14;
}
// 이동비용이 이웃노드G보다 작거나 또는 열린리스트에 이웃노드가 없다면 G, H, ParentNode를 설정 후 열린리스트에 추가
if (MoveCost < NeighborNode.G || !OpenList.Contains(NeighborNode))
{
NeighborNode.G = MoveCost;
NeighborNode.H = (Mathf.Abs(NeighborNode.x - TargetNode.x) + Mathf.Abs(NeighborNode.y - TargetNode.y)) * 10;
NeighborNode.ParentNode = CurNode;
OpenList.Add(NeighborNode);
}
}
}
몬스터 기본 클래스와, FSM을 이용한 AI 클래스의 대략적인 구조는 이렇게 구성 되어 있습니다.
몬스터의 특성상 얼마든지 다양한 종류의 몬스터 클래스와 FSM들을 만들어 낼 수 있도록 상속 구조를 적극적으로 활용 했습니다.
그리고 FSM의 전체적인 동작 방식은 MonsterLoveFSM을 참고하여서 간단하게 변경시켜 적용시켰습니다.
public class StateMachine : MonoBehaviour
{
bool isInTransition = false;
public string curStateName;
public BaseState curState;
public BaseState nextState;
public BaseState queuedState;
public BaseState destState;
public BaseState lastState;
IEnumerator transitionRoutine = null;
public IEnumerator enterRoutine;
public IEnumerator exitRoutine;
private IEnumerator currentTransition;
private IEnumerator queuedChange;
public virtual void Update()
{
if(curState!=null)
{
if(curState.UpdateCall!=null)
curState.UpdateCall();
}
}
public string GetCurstate
{
get
{
return curStateName;
}
}
public void ChangeState(BaseState newState)
{
//초기화 시점에 해당 함수가 호출 되었을때
if(curState==null)
{
//상태를 변경 해주고 변경된 상태의 Enter 함수만 실행시켜주고 종료한다.
curState = newState;
if (curState.EnterCall != null)
curState.EnterCall();
return;
}
//같은 상태로 변경 하려고 할때는 변경하지 않는다.
if (curState == newState)
return;
//현재 상태의 Exit또는 바뀔 상태의 Enter 함수가 코루틴 함수일때는
if(curState.hasExitRoutine||newState.hasEnterRoutine)
{
//코루틴이 완전히 종료될때까지 기다렸다가 상태를 변경해준다.
isInTransition = true;
transitionRoutine = ChangeStateRoutine(newState);
StartCoroutine(transitionRoutine);
}
else
{
//코루틴 함수가 아닐때는 상태를 바꿔주고 Exit 함수와 Enter 함수를 차례로
//실행시켜 준다.
destState = newState;
if (curState != null)
{
if (curState.ExitCall != null)
curState.ExitCall();
//라스트 이벤트
}
lastState = curState;
curState = destState;
curStateName = curState.ToString();
if (curState != null)
{
if (curState.EnterCall != null)
curState.EnterCall();
//체인지 이벤트
}
isInTransition = false;
}
}
//상태가 변경될때 현재 상태의 Exit 함수 또는 다음 상태의 Enter 함수가
//코루틴 일때 해당 함수가 호출된다.
public IEnumerator ChangeStateRoutine(BaseState newState)
{
destState = newState;
//exit가 코루틴일때
if (curState.hasExitRoutine)
{
exitRoutine = curState.ExitRoutine();
yield return StartCoroutine(exitRoutine);
exitRoutine = null;
}
//일반 함수일때
else
{
if (curState.ExitCall != null)
curState.ExitCall();
}
lastState = curState;
curState = destState;
curStateName = curState.ToString();
//enter가 코루틴 일때
if (curState.hasEnterRoutine)
{
enterRoutine = curState.EnterRoutine();
yield return StartCoroutine(enterRoutine);
enterRoutine = null;
}
//일반 함수일때
else
{
if (curState.EnterCall != null)
curState.EnterCall();
}
isInTransition = false;
}
IEnumerator WaitForPreviousState(BaseState waitState)
{
//queuedState = nextState; //Cache this so fsm.NextState is accurate;
while (isInTransition)
{
yield return null;
}
//queuedState = null;
ChangeState(nextState);
}
}
public class ZombieFSM : StateMachine
{
public baseMonster basemonster;
public Idle idleStste;
public Move moveState;
public Attack attackState;
public Die dieState;
public MonsterAttack zombieAttack;
public MonsterMove zombieMove;
private void Awake()
{
basemonster = GetComponent<baseMonster>();
idleStste = new Idle(this);
moveState = new Move(this);
attackState = new Attack(this);
dieState = new Die(this);
zombieAttack = GetComponent<MonsterAttack>();
zombieMove = GetComponent<MonsterMove>();
}
public override void Update()
{
base.Update();
}
}
각 상태들의 상위 클래스인 BaseState에서는 각 상태들의 Enter, Exit, Update 함수들이 코루틴인지, 일반 함수인지 리플렉션 기능을 이용해서 구분하고 분류해서 관리합니다. 리플렉션은 성능부하가 크기 때문에 해당 기능은 초기화 때에만 동작 합니다.
public class BaseState
{
//public bool isInTransition = false;
public StateMachine stateMachine;
//Enter
public bool hasEnterRoutine = false;
public Action EnterCall = null;
public Func<IEnumerator> EnterRoutine = null;
//Exit
public bool hasExitRoutine = false;
public Action ExitCall = null;
public Func<IEnumerator> ExitRoutine = null;
//Update
public Action UpdateCall = null;
public BaseState(StateMachine _stateMachine)
{
InitSetting(_stateMachine);
}
//각각의 메소드들을 구분해서 미리 매핑해서 가지고 있는다.
public virtual void InitSetting(StateMachine _stateMachine)
{
stateMachine = _stateMachine;
MethodInfo[] methods = this.GetType().GetMethods();
foreach (MethodInfo method in methods)
{
if( method.Name.Equals("Enter"))
{
if (method.ReturnType == typeof(IEnumerator))
{
hasEnterRoutine = true;
EnterRoutine = Delegate.CreateDelegate(typeof(Func<IEnumerator>), this, method) as Func<IEnumerator>;
if (EnterRoutine == null)
Debug.Log("[Enter transition 매핑 실패]");
else
Debug.Log("[Enter transition 매핑 성공]");
}
else
{
EnterCall = Delegate.CreateDelegate(typeof(Action), this, method) as Action;
}
}
else if(method.Name.Equals("Exit"))
{
if (method.ReturnType == typeof(IEnumerator))
{
hasExitRoutine = true;
ExitRoutine = Delegate.CreateDelegate(typeof(Func<IEnumerator>), this, method) as Func<IEnumerator>;
if (ExitRoutine == null)
Debug.Log("[Exit transition 매핑 실패]");
else
Debug.Log("[Enter transition 매핑 성공]");
}
else
{
ExitCall = Delegate.CreateDelegate(typeof(Action), this, method) as Action;
}
}
else if(method.Name.Equals("Update"))
{
UpdateCall = Delegate.CreateDelegate(typeof(Action), this, method) as Action;
}
}
}
}
해당 프로젝트에서 사용한 길찾기 알고리즘이 여러 개선사항이 있어 수정한 과정을 기록해 놓았습니다.
