프로그래밍 700

게임의 이펙트를 표시하고 사용하기 위해 사용하는 방식을 이야기한다. 대체적으로 Quad형태로 1차원평면으로 표시하는 경우와 3DObject를 생성하여 Object를 사용해서 이펙트를 표기하는 방법이다. Quad를 사용하는 방법은 대체적으로 과거에 최적화를 위해 사용하는 방식이고, 요즘에는 컴퓨팅 파워가 많이 발전해서, 오브젝트 생성방식을 사용한다. 일단, Quad형태로 뒷배경을 사용하는 방법을 사용해보자. #pragma once class BillboardScene : public Scene { private: const UINT COUNT = 1000; public: BillboardScene(); ~BillboardScene(); // Scene을(를) 통해 상속됨 void Update() overr..

A*알고리즘을 이해하기 위해서는 Dijkstra 알고리즘을 이해해야 한다. 일반적으로, Dijkstra알고리즘은 A*알고리즘의 하위호환이라고 이해하면 될 것이다. Dijkstra 알고리즘 간선간 연결되어있는 노드들을 예시로 들어보자. 이제 각 거리간 시간이 걸리는 정도를 계산하고 넣어보자. 이제 여기에서 전방위 순환을 하면서 가장 가까운 거리를 찾는 것 이다. 위와 같은 방식을 비슷하게 사용하나, 더 효율적인 방법으로 A*알고리즘 이 있다. 근처 Node를 순환하면서 필요한 인접Node만 탐색하는 방식으로. 전체순환을 할 필요가 없어 더 효율적이다. 각 계산수식을 살펴보자. float AStar::GetDiagonalManhattanDistance(int start, int end) { Vector3 s..

그래프로 이루어진 맵에서 Point to Point간의 최단경로를 찾는데 사용되는 알고리즘 중 하나이다. 각 노드간의 가중치가 존재하는 그래프에서 사용된다. 먼저, F, G, H 개념을 이해해야 한다. F는 결과값으로, G + H를 의미한다. G는 Start-> Now까지의 가중치 이다. H는 Now-> End까지의 가중치 이다. Node는Index, F, G, H, State, From 값을 가진다고 가정한다. Index는 Node의 번호를 의미한다. 1번node, 2번node 등을 이야기 한다. State는 Open, Close의 상태 두가지를 가진다. From은 전 Node의 Index값을 가진다. Node는 생성시 항상 Open으로 둔다. 순서 출발 노드 선택 출발노드를 선택하고, 선택노드까지의 ..

A*알고리즘을 통해 Terrain에서 움직이는 Object를 구현해보자. 먼저 A*알고리즘을 구성해주는 AStar를 정의한다. #pragma once class AStar { public: AStar(UINT width = 20, UINT height = 20); ~AStar(); // Render: 그리드의 현재 상태를 표시합니다 (디버깅 또는 시각화 목적). void Render(); // SetNode: 지형 정보로 A* 그리드를 초기화합니다. void SetNode(Terrain* terrain); // FindCloseNode: 주어진 위치를 기반으로 가장 가까운 노드를 찾습니다. int FindCloseNode(Vector3 pos); // GetPath: 시작 노드에서 종단 노드까지의 최적 ..

경로탐색 알고리즘 중 하나로, 시작점부터 목표점까지의 최단경로를 찾는데 사용되는 알고리즘 으로, 그래프 탐색 알고리즘중 하나이다. 목표 꼭짓점까지 가는 최단경로를 찾아내는 알고리즘으로, 각 꼯짓점에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 휴리스틱( huristic )추정값을 매기는 방법을 사용한다. 기본적인 개념은 다이스트라 알고리즘과 비슷하게 들어간다. 기본정의 시작지점에서 목표지점까지 가는 최단경로를 찾는데 사용되는 알고리즘이다. f(n)이 최소가 되는 노드를 우선해서 탐색한다. f(n) = g(n) + h(n)이며, g(n) = start -> n 까지의 비용 h(n) = n에서 End까지의 비용이다. 휴리스틱 함수 휴리스틱은 정해진 알고리즘을 사용하여, 가능한 최소비용에 대한 해를 구하..

어떠한 문제를 해결하기 위해 사용되는 규칙 또는 방법으로, 최적의 해를 찾는데 도움이 되는 추정치를 의미한다. 전체 탐색 공간을 줄이고, 계산비용을 낮추기 위해 사용되며, 일반적으로 근사값을 제공하게 된다. 휴리스틱 함수는 다음 두가지 특성을 가져야 한다. 가능한 실제비용을 넘기지 말아야 한다. 휴리스틱 함수는 실제 비용보다 작거나 같아야 한다. 즉, 휴리스틱이 실제 비용을 과하게 추정하지 말아야 한다. 계산이 빠르고 간결해야 한다. 휴리스틱 함수는 빠르게 계산되어야 한다. 만약, 계산시간을 합쳤을 때 그냥 가는거보다 느리다면, 그냥 이동시키는게 더 낫기 때문이다.