Unity3D/TowerDefence 2014.08.06 23:17


오늘은 드디어 길찾기를 만들겠습니다.

타워디펜스 게임을 만들면서 가장 중요하다고 생각한게 길찾기였습니다.
뭐...미리 길이 정해져있는 게임이라면 굳이 길찾기를 안하고, 웨이포인트를 몇몇개 찍어두면 훨씬 쉽게 만들수 있지만,
우리가 만들것은 지형이 계속 변하게 되니까, 길찾기 가 가장중요한 부분이 됩니다.
(아...그냥 웨이포인트방식으로 만들고 다음에 다시만들껄...ㅜ.-)

우선 길찾기 알고리즘중 가장 잘알려져있고 최적화된것은 A*(에이스타) 인데, 뭐...좀 복잡해서 설명하고, 이해하기 쉬운방식으로 넣겠습니다.
차후에 A* 를 적용하셔도 상관은 없습니다.
(우리가 하려는 방식도 비슷하게 계산하는 방법이 있긴한데, 잘 살펴보진 않았네요..A스타랑 비교해보면 A스타가 약 2배정도 계산이 적어서 더 빠르긴 한것 같네요..)

우리가 구현할 pathFinder에 대한 설명은 http://andwhy.tistory.com/76 에서 확인하시고,

바로 스크립트로 넘어가겠습니다.

Point.cs

using System;
namespace common
{
	public class Point
	{
		public int x = 0;
		public int y = 0;
		public Point(int _x, int _y)
		{
			x = _x;
			y = _y;
		}
		public string ToString()
		{
			return "Point[x: "+x +", y: "+y+"]";
		}
		public Point clone()
		{
			return new common.Point(x, y);
		}
		public bool isEqual(Point p)
		{
			return (p.x == x) && (p.y == y);
		}
		public static bool operator ==(Point p1,Point p2){
			if (object.ReferenceEquals(null, p1))return object.ReferenceEquals(null, p2);
			if (object.ReferenceEquals(null, p2))return object.ReferenceEquals(null, p1);
			return p1.isEqual(p2); 
		}
		public static bool operator !=(Point p1,Point p2){
			if (object.ReferenceEquals(null, p1))return !object.ReferenceEquals(null, p2);
			if (object.ReferenceEquals(null, p2))return !object.ReferenceEquals(null, p1);
			return !p1.isEqual(p2); 
		}
		public override bool Equals(object p1)
		{
			return this.isEqual((Point) p1);
		}
		public override int GetHashCode()
		{
			return ToString().GetHashCode();
		}
	}
	
}

이전 Point.cs파일에 몇가지 함수를 추가합니다.

함수들

public string ToString()

디버깅시 좌표를 좀더 편하게 보기위해 만든 함수.

public Point clone()

자신과 동일한 Point객체를 하나 더 만듭니다.

public bool isEqual(Point p)
public static bool operator ==(Point p1,Point p2)
public static bool operator !=(Point p1,Point p2)

if문 등에서 Point끼리 비교하기 위한 함수들

public override bool Equals(object p1)
public override int GetHashCode()

Dictionary 에서 키값으로 Point를 쓰기 위해서 구현 해줍니다.


PathFinder.cs

using System.Collections;
using System.Collections.Generic;
using common;
using Debug = UnityEngine.Debug;
public class PathFinder{
	private static PathFinder _instance = null;
	public static PathFinder instance
	{
		get{
			if(_instance == null)_instance = new PathFinder();
			return _instance;
		}
	}
	public PathFinder()
	{
		init();
	}

	private MapData mapData;
	private int[,] orgMap;
	private bool isSearching = false;
	private int searchCount = 0;
	private Point goalPoint;

	public void init()
	{
		mapData = new MapData();
		isSearching = false;
		searchCount =0;
	}

	public void setMapData(int[,] _map)
	{
		orgMap = _map;
		mapData.setMapData(orgMap);
	}
	public Point[] getPath(Point current, int targetIdx)
	{
		if(!checkInMapPoint(current)||!checkInMapIndex(targetIdx))return null;
		mapData.setMapData(orgMap);
		Debug.Log("START SEARCHING.. ");
		isSearching = true;
		searchCount = 1;
		setPathCount(new List<Point>(){current}, targetIdx, 100);
		if(goalPoint == null) return null;
		List<Point> pList = findPath();
		if(pList == null) return null;
		return pList.ToArray();
	}
	private void setPathCount(List<Point> pList, int targetIdx)
	{
		if(orgMap==null)return;
		setPathCount(pList, targetIdx, orgMap.GetLength(0) * orgMap.GetLength(1));
	}
	private void setPathCount(List<Point> pList, int targetIdx, int max)
	{
		if(!isSearching)return;
		List<Point> _List = new List<Point>();
		foreach(Point p in pList)
		{
			List<Point> retList = recordPath(p, targetIdx);
			if(retList!=null&&retList.Count>0){_List.AddRange(retList);}
		}
		if(_List.Count==0){Debug.Log ("SEACHING FAIL!!!!");return;}
		searchCount++;
		if(searchCount>=max){isSearching = false; return;}
		
		setPathCount(_List, targetIdx, max);
	}
	private List<Point> recordPath(Point p, int targetIdx)
	{
		if(!isSearching)return null;
		if(orgMap[p.x, p.y] == targetIdx)
		{
			isSearching = false;
			mapData.map[p.x,p.y] = searchCount;
			goalPoint = p;
			Debug.Log("SEACHING COMPLETE!!!!   : "+searchCount);
			return null;
		}
		List<Point> rList = null;
		if(mapData.map[p.x,p.y] == 0)
		{
			mapData.map[p.x,p.y] = searchCount;
			rList = new List<Point>();
			getNeighbours(p, ref rList);
		}
		return rList;
	}
	private void getNeighbours(Point p, ref List<Point> rList)
	{
		if(p.x>0 && mapData.map[p.x - 1,p.y] == 0)rList.Add(new Point(p.x-1,p.y));
		if(p.y>0 && mapData.map[p.x,p.y - 1] == 0)rList.Add(new Point(p.x,p.y-1));
		if(p.x<orgMap.GetLength(0)-1 && mapData.map[p.x + 1, p.y] == 0)rList.Add(new Point(p.x+1,p.y));
		if(p.y<orgMap.GetLength(1)-1 && mapData.map[p.x, p.y + 1] == 0)rList.Add(new Point(p.x,p.y+1));
	}
	private List<Point> findPath()
	{
		List<Point> pathList = new List<Point>();
		Point temPoint = goalPoint;
		int _count = searchCount - 1;
		while(_count>0)
		{
			pathList.Insert(0,temPoint.clone());
			getPathPoint(ref temPoint, _count);
			_count --;
		}
		pathList.Insert(0,temPoint);
		if(isSearching)
		{
			isSearching = false;
			return null;
		}
		return pathList;
	}
	private void getPathPoint(ref Point p, int count)
	{
		if(p.y<mapData.map.GetLength(1)-1 && mapData.map[p.x, p.y+1] == count)
		{
			p.y += 1;
			return;
		}
		if(p.x<mapData.map.GetLength(0)-1 && mapData.map[p.x+1, p.y] == count)
		{
			p.x += 1;
			return;
		}
		if(p.y>0 && mapData.map[p.x, p.y-1] == count)
		{
			p.y -= 1;
			return;
		}
		if(p.x>0 && mapData.map[p.x-1, p.y] == count)
		{
			p.x -= 1;
			return;
		}
	}
	private bool checkInMapPoint(Point p)
	{
		if(orgMap==null)return false;
		if(p.x<0||p.y<0)return false;
		if(p.x >= orgMap.GetLength(0) ||p.y >= orgMap.GetLength(1))return false;
		return true;
	}
	private bool checkInMapIndex(int idx)
	{
		if(orgMap==null)return false;
		foreach(int _idx in orgMap)
		{
			if(idx == _idx)return true;
		}
		return false;
	}
}


public class MapData
{
	public int[,] map;
	public MapData()
	{
	}
	public void setMapData(int[,] _map)
	{
		int w = _map.GetLength(0);
		int h = _map.GetLength(1);
		map = new int[w, h];
		int x,y;

		for(x = 0; x < w; x++)
		{
			for(y = 0; y < h; y++)
			{
				if(_map[x,y] > 0 && _map[x,y] < 10)
					map[x,y] = -1;
				else
					map[x,y] = 0;
			}
		}
	}
}



라이브러리..

using Debug = UnityEngine.Debug; 유니티 엔진을 임포트 하셔도 상관없습니다.


싱글톤

    private static PathFinder _instance = null;
    public static PathFinder instance
    {
        get{
            if(_instance == null)_instance = new PathFinder();
            return _instance;
        }
    }
    public PathFinder()
    {
        init();
    }

이전에 봤던 싱글톤과 비슷하지만, 이쪽이 정석입니다. 객체가 없으면 새로운 객체를 만들어서 리턴해줍니다.

변수들

private MapData mapData;     패스파인더에 사용할 맵노드 클레스입니다.     PathFinder.cs파일 아래쪽에 보시면 MapData라는 클래스를 하나 더 선언했는데, C#에선 한파일에 여러 클래스파일을 선언해    서 사용할수 있습니다.     MapData가 하는 역할은 갈수 없는 셀은 -1로 표시하고, 갈수 있는길은 0으로 표시해둡니다.     길을 찾을때 값이 0인 셀들만 검색해서 찾고 찾은셀은 seachCount 값을 넣어줄겁니다.
    private int[,] orgMap;
원본 맵입니다. 보통 길찾기라면 굳이 필요없지만, 이번엔 목표지점이 정해져있지않고, 특정인덱스를 찾아가기 때문에 필요합니다.
    
private Point goalPoint; 목표지점 포인트 좌표 입니다. 특정인덱스를 맵에서 검색해서 목표지점을 정해줍니다.


함수들

public void setMapData(int[,] _map)

gameManager  에 있는 wallMap을 MapData 로 변형해줍니다.


public Point[] getPath(Point current, int targetIdx)

외부에서 호출하는 길찾기 매쏘드 입니다. 현재 위치와 목표 인덱스를 가지고 길을 찾습니다. 현재위치가 맵상에 없는 위치이거나, 목표인덱스가 맵상에서 찾을수 없을경우 굳이 검색을 하지 않아도 되기때문에 첫번째 줄에서 검사하여, return 시켜버립니다. 길찾기를 한번할때마다 mapData를 초기화 시켜주고, 시작점부터 카운터를 올려가며 탐색을 시킵니다.("setPathCount()" 재귀함수 사용). 탐색이 끝나고, 목표지점까지 갈수있는길이 있는지 없는지 확인후에, 목표지점에서 시작점까지 오는 최단거리를 검색합니다.("findPath()" 재귀함수 사용).

private void setPathCount(List<Point> pList, int targetIdx, int max)

시작점부터 목표점까지 갈수있는 길을 표시합니다. pList는 현재 탐색중인 셀들의 리스트 입니다.처음엔 1개로 시작하지만, 상하좌우 의 인접한 셀들이 계속 추가 됩니다. pList의 Point좌표들을 돌면서 각각 셀에 seachCount를 표시하고(시작점의 seachCount는 1입니다.), 표시된 셀의 인접한 셀들을 다음검색목록(_List)에 추가합니다. 만일 pList의 Point들을 다 돌고도 인접한 셀이 더이상없다면, 더이상은 갈길이 없으므로 막혀있는길입니다. 최대치를 넣어서, 최대치 이상으로 검색될경우 길이 없다고 처리해버립니다.(없어도 되지만 재귀함수가 무한으로 도는걸방지합니다.) 다음검색목록이 비어있지않고, 목적지까지 길을 찾지도 못했다면 다음검색목록을 가지고 다시 setPathCount함수를 실행합니다. (길을 찾거나, 길이 없을때까지 이함수를 계속 실행하게 됩니다.만일 조건인 잘못되어서 무한으로 함수가 돌게 된다면 유니티를 강제 종료하는것이외엔 멈출수 없습니다.

private List<Point> recordPath(Point p, int targetIdx)

위의 setPathCount 에서 pList의 Point 좌표에 seachCount를 실제로 넣어주고, 주변 셀들을 리턴해주는 함수입니다. 만일 현재 Point p가, targetIdx와 일치 한다면 goalPoint에 현재 p를 넣고, 더이상 탐색을 하지 않도록 다음 검색할 셀이 없다고 리턴해줍니다. isSearching 값도 false로 변경해서 더이상은 검색하지 않도록 합니다. 만일 p가 targetIdx가 아니라면 seachCount를 현재 포인트좌표에 넣어주고, 상,하,좌,우 셀들중 값이 '0'인 셀(한번도 검색하지 않은 셀)들만 찾아서 리턴해줍니다.

private List<Point> findPath()     도착점부터 시작점까지 가는길을 구하는 함수입니다.     도착점에 표시된 searchCount 값을 시작으로, point의 상,하,좌,우 의 셀을 검색해서 현재 count값보다 하나 작은 카운트    값을 찾아서("getPathPoint()") 이동합니다.     이동후엔 카운트값이 1 이될때까지 계속 검색("getPathPoint()" 재귀함수 사용)합니다.     카운트가 1인지점은 시작지점이기때문에 1까지 검색이 완료되었으면 검색한 Point값을 차례대로 리턴해줍니다.


마지막 findPath()에서 리턴된 List<Point> 값이 최종으로 찾아진 길입니다. 만일 null이 나오게 된다면, 갈수 없는길이란 이야기죠.


GameManager.cs

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using common;

public class GameManager : MonoBehaviour {
	private static GameManager _instance = null;
	public static GameManager instance
	{
		get{
			if(_instance == null)Debug.LogError("GameManager is NULL");
			return _instance;
		}
	}

	void Awake()
	{
		_instance = this;
		init();
	}
	//=========================================
	public float cellSize = 40.0f;
	public int[,] wallMap = 
	{{1, 1, 1, 1, 1, 11, 11, 11, 1, 1, 1, 1, 1},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{1, 1, 1, 1, 1, 111, 111, 111, 1, 1, 1, 1, 1}};
	[HideInInspector]
	public List<UnitBase> unitList = new List<UnitBase>();
	public Transform unit_field;
	public UnitBase unit_marine;

	private void init()
	{
		unitList.Clear();

		initPathFinder();
	}
	void addUnit()
	{
		UnitBase unit = Instantiate(unit_marine) as UnitBase;
		unit.transform.parent = unit_field;
		Point startPoint = getStartPoint();
		unit.transform.localPosition = new Vector3(startPoint.x * cellSize + cellSize/2.0f, -startPoint.y * cellSize - cellSize/2.0f);
		unit.setStartPoint(startPoint);

	}
	Point getStartPoint()
	{
		//check startPoints
		List<Point> startPointList = new List<Point>();
		int _w = wallMap.GetLength(0);
		int _h = wallMap.GetLength(1);
		int x,y;
		for (x = 0; x < _w; x++)
		{
			for(y = 0; y < _h; y++)
			{
				if(wallMap[x,y] >= 10 && wallMap[x,y] <= 100)
				{
					startPointList.Add(new Point(x,y));
				}
			}
		}
		if(startPointList.Count == 0)
		{
			Debug.LogError("Not Found Start Position");
			return null;
		}
		int ranIdx = Random.Range(0,startPointList.Count);
		return startPointList[ranIdx];
	}
	public void initPathFinder()
	{
		PathFinder.instance.setMapData(wallMap);
	}
	void OnGUI()
	{
		if(GUI.Button( new Rect( 10, 10, 100, 40), "Add Unit"))
		{
			addUnit();
		}
	}
}

약간의 스크립트가 추가되었습니다.

-Awake 시에 init()함수 호출.
-PathFinder초기화해주는 initPathFinder 함수 추가.
-init함수에 initPathFinder()함수 호출.

public void initPathFinder() 에대해선 위에서 만든 PathFinder초기화가 전부라서 따로 설명은 하지 않습니다.



UnitBase.cs


using UnityEngine;
using System.Collections;
using common;

public class UnitBase : MonoBehaviour {

	public float moveSpeed = 1.0f;
	public tk2dSpriteAnimator spr;
	private enum CHAR_ANI {UP, DOWN, LEFT, RIGHT, DESTROY};
	private string[] charAniStr = new string[]{"walk_up","walk_down","walk_left","walk_right","destroy"};
	// Use this for initialization
	void Start () {
	}
	private bool isMoveAble = false;
	// Update is called once per frame
	void Update () {
		if(!isMoveAble)return;
		float _speed = GameManager.instance.cellSize * Time.deltaTime * moveSpeed;
		int tx = nextPoint.x - startPoint.x;
		int ty = nextPoint.y - startPoint.y;

		float dx = _speed * tx;
		float dy = -_speed * ty;
		float rx = (nextPoint.x * GameManager.instance.cellSize + GameManager.instance.cellSize/2.0f) - this.transform.localPosition.x;
		float ry = (-nextPoint.y * GameManager.instance.cellSize - GameManager.instance.cellSize/2.0f) - this.transform.localPosition.y;
		bool isCloseX = false;
		bool isCloseY = false;
		if(Mathf.Abs(dx)>Mathf.Abs(rx)||dx==0){dx = rx;isCloseX = true;}
		if(Mathf.Abs(dy)>Mathf.Abs(ry)||dy==0){dy = ry;isCloseY = true;}
		this.transform.localPosition += new Vector3(dx , dy , 0);
		if(isCloseX && isCloseY)
		{
			if(pathArr.Length <= pathIndex + 1)
			{
				isMoveAble = false;
				return;
			}
			setNextPoint();
		}
	}
	private Point[] pathArr;
	private Point startPoint;
	private Point nextPoint;
	private int pathIndex =0;
	public void setStartPoint(Point p)
	{
		startPoint = p;
		getPath();
		nextPoint = pathArr[pathIndex];
		showCharDir();
		isMoveAble = true;
	}
	public void getPath()
	{
		Point[] pArr = PathFinder.instance.getPath(startPoint, 111);
		if(pArr == null){Debug.Log("NULL path");return;}
		pathArr = pArr;
		//pathArr = new Point[]{new Point(startPoint.x + 1, startPoint.y), new Point(startPoint.x + 2, startPoint.y), new Point(startPoint.x + 2, startPoint.y+1), new Point(startPoint.x + 2, startPoint.y)};
		pathIndex = 0;
	}
	private void setNextPoint()
	{
		startPoint = nextPoint;
		pathIndex++;
		nextPoint = pathArr[pathIndex];
		showCharDir();
	}
	private void showCharDir()
	{

		if(startPoint.x<nextPoint.x)
			spr.Play (charAniStr[(int)CHAR_ANI.RIGHT]);
		else if(startPoint.x>nextPoint.x)
			spr.Play (charAniStr[(int)CHAR_ANI.LEFT]);
		else if(startPoint.y>nextPoint.y)
			spr.Play (charAniStr[(int)CHAR_ANI.UP]);
		else if(startPoint.y<nextPoint.y)
			spr.Play (charAniStr[(int)CHAR_ANI.DOWN]);
		spr.ClipFps *= moveSpeed;
	}
}


UnitBase 클래스에선 getPath()함수 부분만 임시로 넣었던 Path에서 PathFinder를 통해 실제 검색한 길을 찾아오도록만 수정되었습니다.

public void getPath()
{
Point[] pArr = PathFinder.instance.getPath(startPoint, 111);
if(pArr == null){Debug.Log("NULL path");return;}
pathArr = pArr;
pathIndex = 0;
}

이대로 Play버튼을 눌러서 확인해보면 유닛들이 녹색 시작점에서 파란색 시작점까지 잘 걸어가는걸 볼수 있습니다.
벽이있을때 어떻게 돌아가는지 확인하고 싶다면, GameManager.cs의 wallMap에 중앙쯤을 적당히 1로 변경해서 벽을 만들어서 플래이 해보시면 됩니다.(길이 없다면 에러가 날껍니다.)

이상으로 길찾기 1편을 마치고, 다음번엔 런타임에서 맵을 변경하고, 바로 새로운 경로를 찾아갈수 있도록 구현해보겠습니다.



신고
posted by andwhy

티스토리 툴바