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

a* 알고리즘

 

#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;
	int nTmp;
};

 

#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 nDstX, int nSrcY, int nSrcX);

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

 

#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 nDstX, int nSrcY, 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 nStartX, int nEndY, int nEndX)
{
	C_NODE* pSnode = &m_arNode[nStartY][nStartX];
	m_cHeap.addNode(pSnode);

	C_NODE* pTop = nullptr;
	do
	{
		pTop = m_cHeap.top();
		m_cHeap.pop();
		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++)
		{
			C_NODE* pChild = pTop->arChild[i];
			if (pChild && !pChild->bVisit)
			{
				float G = pTop->G + arDist[i];
				float H = length(nEndY, nEndX, pChild->nY, pChild->nX);
				float F = G + H;

				if (pChild->nIndex != 0 && F < pChild->F)
				{
					pChild->F = F; pChild->G = G; pChild->H = H; pChild->pParent = pTop;
					m_cHeap.updateNode(pChild);
				}
				else
				{
					pChild->F = F; pChild->G = G; pChild->H = H; pChild->pParent = pTop;
					m_cHeap.addNode(pChild);
				}
			}
		}
	} while (nEndX != pTop->nX || nEndY != pTop->nY);


	C_NODE* pNode = pTop;
	while (pNode->pParent)
	{
		static int nData = 1;
		pNode->nTmp = nData;
		nData++;
		pNode = pNode->pParent;
	}

}

void C_ASTAR::print()
{
	for (int i = 0; i < E_MAX; i++)
	{
		for (int j = 0; j < E_MAX; j++)
		{
			printf("%2d ", m_arNode[i][j].nTmp + m_arMap[i][j]);
		}
		printf("\n");
	}
}

 

#pragma once

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

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

private:
	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*&));
	static bool force(C_NODE*& pDst, C_NODE*& pSrc);

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

	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();
	C_NODE* getNode(int nIndex);
	void updateNode(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()
{
	if (m_vBuffer.size() <= 1)
		return;

	int nLast = (int)m_vBuffer.size() - 1;
	swap(nLast, 1);
	m_vBuffer.pop_back();

	moveDown(1 , m_pCompare);
}

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

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

 

 

#include <iostream>
#include "astar.h"

int main()
{
	C_ASTAR cAstar{};

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