51일차. 충돌처리, 자료구조 - Sort

충돌체 처리를 위해, Physics 를 활용하여 QuadColider, CircleColider 을 제작한다.

 

#pragma once

#include "Engine/Input.h"
#include "Engine/Physics.h"
#include "Engine/Quadrangle.h"
#include "Engine/Rendering.h"
#include "Engine/Time.h"

struct QuadColider
{
	QuadColider()
	{
		Skin.Length = { 250, 250 };
		Skin.Location = { 300, 0 };
		Skin.Name = "Image/GBB";

		Body.Length = { 250, 250 }; // 충돌체의 모양
		Body.Center = { 300, 0 }; // 충돌체 방향 잡는것.
	}

	void Update()
	{
		if(Engine::Input::Get::Key::Press(VK_NUMPAD4))
			Skin.Location[0] = Body.Center.x -= Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press(VK_NUMPAD6))
			Skin.Location[0] = Body.Center.x += Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press(VK_NUMPAD8))
			Skin.Location[1] = Body.Center.y += Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press(VK_NUMPAD2))
			Skin.Location[1] = Body.Center.y -= Speed * Engine::Time::Get::Delta();

		Skin.Render();
	}

	float const Speed = 500;
	Engine::Rendering::Image::Component		Skin{};
	Engine::Physics::Component<Quadrangle>	Body{};

};

#pragma once

#include "Engine/Input.h"
#include "Engine/Physics.h"
#include "Engine/Circle.h"
#include "Engine/Rendering.h"
#include "Engine/Time.h"

struct CircleColider
{
	CircleColider()
	{
		Skin.Length = { 250, 250 };
		Skin.Location = { -300, 0 };
		Skin.Name = "Image/GBC";

		Body.Radius = 125;
		Body.Center = { -300, 0 }; // 충돌체 방향 잡는것.
	}

	void Update()
	{
		if (Engine::Input::Get::Key::Press('A'))
			Skin.Location[0] = Body.Center.x -= Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press('D'))
			Skin.Location[0] = Body.Center.x += Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press('W'))
			Skin.Location[1] = Body.Center.y += Speed * Engine::Time::Get::Delta();
		if (Engine::Input::Get::Key::Press('S'))
			Skin.Location[1] = Body.Center.y -= Speed * Engine::Time::Get::Delta();

		Skin.Render();
	}

	float const Speed = 500;
	Engine::Rendering::Image::Component	Skin{};
	Engine::Physics::Component<Circle>	Body{};

};

---

위 항목의 CircleColider 와 QuadColider의 코드는 비슷함 으로 CircleColider 기준으로 설명한다.

 

CircleColider는 struct로 구성되어 있으나, 생성시 자동으로 선언되는 함수인 생성자 를 만들어줄 수 있다.

 

생성자는 public에 해당하는, 외부이미지의 Skin과 PhysicsColider를 담당할 Body를 복사대입 해준다.

 

Skin은 이미지의 사이즈를 의미하고, Center는 이미지의 중심축을 말한다.

Body.Radius는 원형의 반지름을 말한다.

 

그 후, TempGame.cpp의 전역부분에 QC와 CC를 선언해준뒤,

QuadColider QC;
CircleColider CC;

중략....


	QC.Update();
	CC.Update();

	if (QC.Body.Collide(CC.Body) == true)
	{
		QC.Skin.Name = "Image/RBB";
		CC.Skin.Name = "Image/RBC";
	}
	else
	{
		QC.Skin.Name = "Image/GBB";
		CC.Skin.Name = "Image/GBC";
	}

Update부분 안에 위와같은 항목을 삽입한다.

 

Collide는 D3dx.dll의 항목을 의미한다.

위와같이, 각 이미지파일이 겹쳤을 때 빨간색으로 바뀌면 성공이다.

 

---

Sort 자료구조를 재구현 해보자.

/*
	Big O 표기법
	O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)
	
	피봇을 가장 좌측, 가장 중앙 둘중 하나로 정한다.

	L과 R이라고 하여, 왼쪽 가장 오른쪽값을 결정한다.
	
	피봇이 L과 R을 비교하여 가장작은지 큰지 확인하고
	
	더 작은쪽으로 이동한다.
	그러다가 더 큰쪽을 작은쪽과 이동한다.

*/

#include <iostream>

using namespace std;

void QuickSort(int* arr, int start, int end)
{
	if(start >= end) return;

	int pivot = start;
	int left = start + 1;
	int right = end;

	while (left <= right)
	{
		while(arr[left] < arr[pivot] && left <= end)
			left++; // 작으면 이동시킨다.
		while (arr[right] > arr[pivot] && right >= start)
			right--; // 작으면 이동시킨다.

		if(left >= right) break;

		swap(arr[left], arr[right]);
	}
	swap(arr[pivot], arr[right]);
	
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);

}

void Print(int* arr, int size, string str)
{
	cout << str << endl;
	for(int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;

}

int main()
{
	int arr[10];
	
	for (int i = 0; i < 10; i++)
	{
		cin >> arr[i];
	}

	Print(arr, 10, "PREV : ");
	QuickSort(arr, 0, 9);
	Print(arr, 10, "NEXT : ");
	return 0;
}

위와같이, QuicKSort 코드를 사용하여 pivot값을 재설정하여 sort할 수 있다.

 

QuickSort

• 하나의 리스트를 피벗(pibot)을 기준으로 두개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.
• 다음 단계들로 이루어진다.
  1. 분할(Divide) : 입력 배열을 피벗을 기준으로 2개로 (피벗 기준으로 작은건 왼쪽, 큰건 오른쪽) 분할한다.
  2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환호출하여 다시 분할정복 한다.
  3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 결합한다.
• 순환호출이 한번 진행될 때 마다, 값 하나의 위치가 정해지게 됨 으로 반드시 종료된다.