오른손 법칙 과 Vector

저번 강의에서 미로를 만들어 보았다면 이번엔 간단한 길찾기를 구현해보았다. A* 알고리즘이 이 강의 최종 보스같은 건가 보다. 일단 구현하기 위해 이진트리나 다른 알고리즘을 구현해야하기 때문에 오른손 법칙이라는 걸로 간단히 구현해보았다.

 

강의는 전체적으로 쉬워서 보는 내내 재미있었다. 역시 아는게 짜릿해. 그중 기억에 남는거 몇개만 적어보자.

길찾는 로직을 구현하는데 간단히 Switch 문으로 구현을 했었다. 하지만 강의는 아름다운 코드진행을 보여주었다. 이런걸로 눈이 반짝이는 나를 보며 1년전의 나와 다른 모습을 느끼게 되었다. 정말 개발자가 되어가는 과정인건가...

 

 나는 내가 개발자라고 생각하지 않는다. 난 아직 아무것도 혼자서 개발할 수 없기 때문이다. 게임이라는 건물을 짖기 위해, 클라이언트, 네트워크를 통한 통신, 통신완료된 데이터 저장, 이를 편하게 구현할 다양한 클라우드 서비스를 구현하지 못한다. 천천히 모든걸 공부해보고 싶다. 아름다운 게임하나를 짖기위한 건축가가 되기 위해 노력해야한다. 그리고 언젠간 스스로 게임을 전반적으로 만들 수 있는 개발자가 되고 싶다. 먼가 자소서 쓰는 기분인데...ㅋㅋㅋㅋ

 

아무튼 다시 본론으로 넘어와서

 

while (pos != dest)
	{
		//1.	현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인.
		//2.	현재 바라보는 방향 기준으로 전진할 수 있는가?
		//3.	왼쪽으로 방향을 전환한다.
		int32 newDir = (_dir - 1 + DIR_COUNT) % DIR_COUNT; //현재 기준의 오른쪽
		if (IsGo(pos + front[newDir]) ) //1 구현
		{
			_dir = newDir;
			pos += front[_dir];

			_path.push_back(pos);
		}
		else if (IsGo(pos + front[_dir])) //2 구현
		{
			pos += front[_dir];

			_path.push_back(pos);
		}
		else //3 구현
		{
			_dir = (_dir + 1) % DIR_COUNT;
		/*	switch (_dir)
			{
			case DIR_UP:
				_dir = DIR_LEFT;
					break;
			case DIR_LEFT:
				_dir = DIR_DOWN;
				break;
			case DIR_DOWN:
				_dir = DIR_RIGHT;
				break;
			case DIR_RIGHT:
				_dir = DIR_UP;
				break;
			default:
				break;
			}*/
		}
	}
    
    enum Dir
{
	DIR_UP =0,
	DIR_LEFT = 1,
	DIR_DOWN =2,
	DIR_RIGHT = 3,

	DIR_COUNT = 4
};

while 문에서 Switch를 저렇게 한줄로 축약한 코드는 아름답다. 역시 짬은 무시못한다. 이러한 걸 생각하기 위해 사전에 Enum 코드를 생각하여 만들었단다. 난 단순하게 쭉 짜는데... 생각을 하면 얼마나 멋있게 만들 수 있는가? 아마 나도 몇달 지나면 당연한 코드가 되겠지.

 

그리고 또 하나, Render을 어떻게 구현하는지 궁금했는데. 일단 길을 다 연산한 후, vector로 저장하여 시간을 조절하며 구현하는 걸 보고 좋은 걸 배워간다.

void Player::Update(uint64 deltaTick)
{	
	if (_pathIndex >= _path.size())
		return;
	
	_sumTick += deltaTick;
	if (_sumTick >= MOVE_TICK)
	{
		_sumTick = 0;

		_pos = _path[_pathIndex];
		_pathIndex++;
	}

}

 이제 아마 본론으로 들어가 기초적인 알고리즘을 다룰 예정인거 같다. 솔직히 한번 공부했던 자료들이라서, 쉬운거 같다. 데이터 베이스를 같이 공부할 필요성을 느낀다.

 

 

기초적인 알고리즘을 배우는데

배열 vs 동적 배열 vs 연결 리스트에 대해 정리해준다. 

 

배열은 그냥 배열이다. 

사용자가 직접 메모리에 공간을 할당하고 배열을 만든다.  그렇기 때문에 연속적인 메모리 공간을 할당받을 수 있지만, 한번 할당하면, 추가 혹은 삽입 등이 불가하다. 연속적인 메모리 공간에 할당받기에 메모리 접근이 편리하다.

 

동적 배열의 대표적인 예는 vector이다. 메모리 공간에 배열을 할당하며, 배열을 추가할 시, 다른 공간에 연속적인 배열을 새로 생성하고 값을 이전한다. 

 

 위 콘솔창을 보면 vec.capacity()의 경우 63에서 94로 늘어난 것을 볼 수 있다. 즉 동적 배열이 새로운 메모리에 할당된건데, 63번째 배열까지 기존에 사용하던 동적배열에 저장하다 63이 초과되면 1.5배의 크기의 배열 94를 새로 생성하고 값을 이동한 후, 다시 배열을 추가하는 모습을 볼 수 있다. C#을 사용하며 List계열 함수를 쓰고 시간 복잡도를 외워 쓰고 있었는데, 왜 그런 시간 복잡도가 나오는지 이해할 수 있는 실험이다. 물론 List는 연결리스트겠지만.

 

여기서 알 수 있는건 vec.size()는 메모리에 할당된 vec의 크기이며, vec.capacity()는 미리 메모리를 잡아 놓은 크기이다. vector가 생성된다고 해서 할당된 크기가 size만큼이 아니며, 실제는 capacity만큼의 메모리 크기를 갖고 있다는 점을 알아야 한다. size는 실직적으로 사용한 배열이 되는 것이고, capacity는 메모리에 할당된 실질적 크기라고 생각해야한다.

 

재밌는 점은 1.5배씩 메모리에 할당 된 동적배열은 커질 수록 메모리 크기가 커지기 때문에, 데이터를 이동해야하는 비용이 점점 적어지게 되어 효율적으로 변할 수 있다. 메모리는 점점 커지겠지만.

또한,

 Clear()를 하여도 메모리 크기는 변하지 않는다.

이러한 Vector를 분해해본다. 

 

template<typename T>
class Vector
{
public:
	Vector()
	{

	}
	~Vector()
	{
		if (_data)
			delete[] _data;
	}

	void puch_back(const T& value)
	{
		if (_size == _capacity)
		{
			int newCapacity = _capacity * 1.5;
			if (newCapacity == _capacity)
				newCapacity++;
			
			reserve(newCapacity);
		}

		_data[_size] = value;
		_size++;
	}

	void reserve(int capacity)
	{
		if (_capacity >= capacity)
			return;

		_capacity = capacity;

		T* newData = new T[_capacity];

		for (int i = 0; i < _size; i++)
			newData[i] = _data[i];

		if (_data)
			delete[] _data;

		_data = newData;
	}

	T& operator[](const int pos) { return _data[pos]; }

	int size() { return _size; }
	int capacity() { return _capacity; }

	void Clear()
	{
		if (_data)
		{
			delete[] _data;
			_data = new T[_capacity];
		}
		_size = 0;
	}
private:
	T* _data = nullptr;
	int _size = 0;
	int _capacity = 0;
};

이렇게 간단하게 구현해보았다. 여기서 보면 size와 capacity가 어떻게 이루어지고 있는지를 볼 수 있는데, 동적 배열의 단점인 배열의 크기를 넘으면 데이터를 복사하는 비용을 배열의 크기N만큼 이루어지지만 Capacity를 초기에 크기를 예상하고 할당한다면, 데이터 복사비용을 줄일 수 있다. 

 

위의 그림과 초기 그림을 비교하면 capacity의 크기가 고정되어 데이터를 넣는걸 볼 수 있다. 이는 데이터 복사비용이 발생하지 않은 좀 더 효율적인 연산이 가능한 vector임을 볼 수 있다.