[C++] 6월 11일 코딩 테스트 수업

a* 알고리즘 

 

#pragma once
#include <stdio.h>
#include "node.h"
#include "heap.h"

class C_ASTAR
{
private:
	enum { E_MAX = 10 };

	int m_arMap[E_MAX][E_MAX]{};
	C_NODE m_arNode[E_MAX][E_MAX]{};

	C_HEAP m_cHeap;

private:
	void linkNode(int nY, int nX);
	float length(int nDstY, int nSrcY, int nDstX, int nSrcX);

public:
	C_ASTAR();
	void init();
	void make(int nStartY, int nStratX, int nEndY, int nEndX);
};

 

#include "astar.h"

C_ASTAR::C_ASTAR() :
	m_arNode{},
	m_arMap
	{
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 0, 0, 0, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 0, 1, 1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 1, 1, 1, 1, 1, 0, 0, 1},
		{1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
		{1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	}
{
}

void C_ASTAR::linkNode(int nY, int nX)
{
	// 6 5 4
	// 7   3
	// 0 1 2
	int arWay[8][2]{	{1,-1}, {1,0},  {1,1}, 
						{0,1},          {-1,1}, 
						{-1,0}, {-1,-1},{0,-1}};

	for (int i = 0; i < 8; i++)
	{
		int nCY = arWay[i][0] + nY;
		int nCX = arWay[i][1] + nX;

		if (nCX >= 0 && nCX < E_MAX && nCY >= 0 && nCY < E_MAX && m_arMap[nCY][nCX] == 0)
		{
			m_arNode[nY][nX].arChild[i] = &m_arNode[nCY][nCX];
		}
	}
}

float C_ASTAR::length(int nDstY, int nSrcY, int nDstX, int nSrcX)
{
	return sqrtf((float)((nDstY - nSrcY) * (nDstY - nSrcY) + (nDstX - nSrcX) * (nDstX - nSrcX)));
}

void C_ASTAR::init()
{
	for (int i = 0; i < E_MAX; i++)
	{
		for (int j = 0; j < E_MAX; j++)
		{
			m_arNode[i][j].nY = i;
			m_arNode[i][j].nX = j;
			linkNode(i, j);
		}
	}
	m_cHeap.init();
}

void C_ASTAR::make(int nStartY, int nStratX, int nEndY, int nEndX)
{
	C_NODE* pSnode = &m_arNode[nStartY][nStratX];
	m_cHeap.addNode(pSnode);


	C_NODE* pTop = m_cHeap.top();
	pTop->bVisit = true;

	float arDist[8]{ 1.414f, 1.0f, 1.414f, 1.0f ,1.414f, 1.0f ,1.414f, 1.0f };

	for (int i = 0; i < 8; i++)
	{
		pTop->arChild[i];

		// 배열중에 있는것만 고른다
		// 방문한 적이 없어야한다.
		C_NODE* pChild = pTop->arChild[i];
		if (pChild && !pChild->bVisit)
		{
			// 거리 계산 -> 부모 합산 G값
			// F G H 관련 작업을 해야함
			// F = G + H
			// H = child의 위치 - 도착 위치
			float G = pTop->G + arDist[i];
			float H = length(nEndY, nEndX, pChild->nY, pChild->nX);
			float F = G + H;

			if (pChild->nIndex != 0)
			{
				// F값을 비교해서 작으면 교체한 다음 갱신한다.
				// F값이 크면 그냥 버린다.
			}
			else
			{
				// addNode 한다..???
			}
		}
	}
}

 

#pragma once

#include <stdio.h>
#include <vector>
#include "node.h"

class C_HEAP
{
private:
	std::vector<C_NODE*> m_vBuffer;
	bool (*m_pCompare)(C_NODE*&, C_NODE*&);

private:
	static bool force(C_NODE*& pDst, C_NODE*& pSrc);
	
	void swap(int nDst, int nSrc);
	void moveUp(int nDst, bool (*pFunc)(C_NODE*&, C_NODE*&));
	void moveDown(int nDst, bool (*pFunc)(C_NODE*&, C_NODE*&));


public:
	static bool less(C_NODE*& pDst, C_NODE*& pSrc);
	static bool greater(C_NODE*& pDst, C_NODE*& pSrc);

public:
	C_HEAP() = default;
	void init(int nBufferSize = 50, bool (*pFunc)(C_NODE*&, C_NODE*&) = less);
	void addNode(C_NODE* pNode);
	void print();
	C_NODE* top();
	void pop(bool bDelete = true);
	C_NODE* getNode(int nIndex);
	void updataNode(C_NODE* pNode);
	
};

 

#include "heap.h"

bool C_HEAP::less(C_NODE*& pDst, C_NODE*& pSrc)
{
	return pDst->F < pSrc->F;
}

bool C_HEAP::greater(C_NODE*& pDst, C_NODE*& pSrc)
{
	return pDst->F > pSrc->F;
}

bool C_HEAP::force(C_NODE*& pDst, C_NODE*& pSrc)
{
	return true;
}


void C_HEAP::swap(int nDst, int nSrc)
{
	C_NODE* pTmp = m_vBuffer[nDst];
	m_vBuffer[nDst] = m_vBuffer[nSrc];
	m_vBuffer[nSrc] = pTmp;

	m_vBuffer[nDst]->nIndex = nDst;
	m_vBuffer[nSrc]->nIndex = nSrc;
}

void C_HEAP::moveUp(int nDst, bool (*pFunc)(C_NODE*&, C_NODE*&))
{
	int nUp = nDst / 2;
	if (nUp == 0)
		return;

	if (pFunc(m_vBuffer[nDst], m_vBuffer[nUp]))
	{
		swap(nDst, nUp);
		moveUp(nUp, pFunc);
	}
}

void C_HEAP::moveDown(int nDst, bool(*pFunc)(C_NODE*&, C_NODE*&))
{
	int nL = nDst * 2;
	int nR = nL + 1;

	if (nL >= m_vBuffer.size())
		return;

	int nSelect = nL;

	if (nR <= m_vBuffer.size() && !pFunc(m_vBuffer[nL], m_vBuffer[nR]))
		nSelect = nR;

	if (pFunc(m_vBuffer[nSelect], m_vBuffer[nDst]))
	{
		swap(nSelect, nDst);
		moveDown(nSelect, pFunc);
	}
}

void C_HEAP::init(int nBufferSize, bool (*pFunc)(C_NODE*&, C_NODE*&))
{
	m_pCompare = pFunc;
	m_vBuffer.reserve(nBufferSize);
	m_vBuffer.push_back(nullptr);
}

void C_HEAP::addNode(C_NODE* pNode)
{
	if (m_vBuffer.size() == m_vBuffer.capacity())
		return;

	m_vBuffer.push_back(pNode);
	pNode->nIndex = (int)(m_vBuffer.size() - 1);

	moveUp((int)m_vBuffer.size() - 1, m_pCompare);
}

void C_HEAP::print()
{
	for (int i = 1; i < m_vBuffer.size(); i++)
	{
		//printf("%d ", m_vBuffer[i]->nData);
	}
	printf("\n");
}

C_NODE* C_HEAP::top()
{
	if (m_vBuffer.size() <= 1)
		return nullptr;

	return m_vBuffer[1];
}

void C_HEAP::pop(bool bDelete)
{
	if (m_vBuffer.size() <= 1)
		return;

	int nLast = (int)m_vBuffer.size() - 1;
	swap(nLast, 1);
	
	if(bDelete)
		delete m_vBuffer[nLast];

	m_vBuffer.pop_back();

	moveDown(1, m_pCompare);
}

C_NODE* C_HEAP::getNode(int nIndex)
{
	return m_vBuffer[nIndex];
}

void C_HEAP::updataNode(C_NODE* pNode)
{
	moveUp(pNode->nIndex, force);
	pop(false);
	addNode(pNode);
}

 

#pragma once

class C_ASTAR;
class C_HEAP;

class C_NODE
{
	friend C_HEAP;
	friend C_ASTAR;

private:
	int nX;
	int nY;

	float F;
	float G;
	float H;
	C_NODE* pParent;
	C_NODE* arChild[8]{};

	int nIndex;
	bool bVisit;
};

 

#include <iostream>

#include "astar.h"

int main()
{
	C_ASTAR cAstar{};

	cAstar.init();
	cAstar.make(1, 1, 8, 3);
}