< http://anond.hatelabo.jp/20070... | http://anond.hatelabo.jp/20070... >

2007-07-12

■迷路作成プログラムをVC++2005でやってみた。

http://anond.hatelabo.jp/20070711013155　こちらの宿題を作ってみました。

http://anond.hatelabo.jp/20070711080519　で参加を宣言した者です。

#include "stdafx.h"
#include <time.h>
#include <conio.h>
#include <list>

using namespace std;

enum MMError {
	MME_None = 0,
	MME_SizeError,
	MME_MemoryAllocError,
	MME_NotInitialized,
};

enum MMKind {
	MMK_None = 0,
	MMK_Space,		// 通路
	MMK_Filled,		// 埋まってるところ。掘れる。
	MMK_Wall,		// 壁。掘れないところ。
};

//
// 迷路実体管理用クラス定義
//
class CMazeMatrix
{
public:
	CMazeMatrix();
	virtual ~CMazeMatrix();

public:
	virtual bool	Initialize(int nXSize, int nYSize);	// 初期化すると同時に、外壁まで作ってしまう。
	virtual MMKind	GetAt(int nXPos, int nYPos);
	virtual bool	SetAt(int nXPos, int nYPos, MMKind kind);

	MMError	GetLastError() {return m_lastError;}


protected:
	inline	int calcIndex(int nXPos, int nYPos) {return nYPos * m_nXSize + nXPos;}
	bool	finalize();

protected:
	MMKind	*m_pMaze;
	int		m_nXSize;
	int		m_nYSize;

	MMError	m_lastError;
};

//
// 実体管理用クラス実体
//
CMazeMatrix::CMazeMatrix()
{
	m_pMaze = NULL;
	m_nXSize = 0;
	m_nYSize = 0;
	m_lastError = MME_None;
}

CMazeMatrix::~CMazeMatrix()
{
	finalize();
}


bool CMazeMatrix::Initialize(int nXSize, int nYSize)
{
	finalize();

	int nSize = nXSize * nYSize;
	if ((__int64)nSize != (__int64)nXSize * (__int64)nYSize) {
		m_lastError = MME_SizeError;
		return false;
	}
	m_pMaze = new MMKind[nSize];
	if (m_pMaze == NULL) {
		m_lastError = MME_MemoryAllocError;
		return false;
	}

	m_nXSize = nXSize;
	m_nYSize = nYSize;

	int nCnt;
	for (nCnt = 0; nCnt < nSize; nCnt++) 
		m_pMaze[nCnt] = MMK_Filled;

	for (nCnt = 0; nCnt < m_nXSize; nCnt++) {
		m_pMaze[calcIndex(nCnt, 0)] = MMK_Wall;
		m_pMaze[calcIndex(nCnt, m_nYSize - 1)] = MMK_Wall;

	}

	for (nCnt = 0; nCnt < m_nYSize; nCnt++) {
		m_pMaze[calcIndex(0, nCnt)] = MMK_Wall;
		m_pMaze[calcIndex(m_nXSize - 1, nCnt)] = MMK_Wall;
	}
	return true;
}

MMKind	CMazeMatrix::GetAt(int nXPos, int nYPos)
{
#ifdef _DEBUG
	if (nXPos < 0 || nXPos >= m_nXSize ||
		nYPos < 0 || nYPos >= m_nYSize)
	{
		m_lastError = MME_SizeError;
		return MMK_None;
	}
#endif
	return m_pMaze[calcIndex(nXPos, nYPos)];
}

bool	CMazeMatrix::SetAt(int nXPos, int nYPos, MMKind kind)
{
#ifdef _DEBUG
	if (nXPos < 0 || nXPos >= m_nXSize ||
		nYPos < 0 || nYPos >= m_nYSize)
	{
		m_lastError = MME_SizeError;
		return false;
	}
#endif
	m_pMaze[calcIndex(nXPos, nYPos)] = kind;
	return true;
}

bool	CMazeMatrix::finalize()
{
	if (m_pMaze != NULL) {
		delete [] m_pMaze;
		m_pMaze = NULL;
	}
	return true;
}


//
// 迷路作成用クラス定義
//
class CMazeMaker
{
public:
	CMazeMaker();
	virtual ~CMazeMaker();

public:
	bool	Initialize(int nXSize, int nYSize);

	// 力業。ループで回す。メモリは食わない。
	// 美しくない。
	bool	Generate1();

	// 掘った箇所をスタックに積んで、掘れなくなったらスタックを戻す。
	// 綺麗だけれど、迷路のサイズを増やすとスタックオーバーフローが起こる。
	bool	Generate2();

	// Generate2をlistに置き換えたもの。
	// stdを使ってしまったのが心残り。
	bool	Generate3();

	MMError	GetLastError() {return m_lastError;}

protected:
	bool	finalize();
	bool	checkPos(int nXPos, int nYPos, int nXAdd, int nYAdd);
	int		process(int nXPos, int nYPos);
	void	dig(int nXPos, int nYPos);
	bool	makeStartGoal();
	virtual	CMazeMatrix* matrixAllocate();

protected:
	int		m_nXSize;
	int		m_nYSize;
	CMazeMatrix *m_pMatrix;
	MMError	m_lastError;
};


CMazeMaker::CMazeMaker()
{
	m_nXSize = 0;
	m_nYSize = 0;
	m_pMatrix = NULL;
	m_lastError = MME_None;
}

CMazeMaker::~CMazeMaker()
{
	finalize();
}

bool CMazeMaker::Initialize(int nXSize, int nYSize)
{
	finalize();

	m_pMatrix = matrixAllocate();

	if (m_pMatrix == NULL) {
		m_lastError = MME_MemoryAllocError;
		return false;
	}

	if (m_pMatrix->Initialize(nXSize, nYSize) == false) {
		m_lastError = m_pMatrix->GetLastError();
		return false;
	}

	m_nXSize = nXSize;
	m_nYSize = nYSize;

	return true;
}

CMazeMatrix* CMazeMaker::matrixAllocate()
{
	return new CMazeMatrix;
}

bool CMazeMaker::finalize()
{
	if (m_pMatrix != NULL) {
		delete m_pMatrix;
		m_pMatrix = NULL;
	}
	return true;
}


// スタート位置と、ゴールの位置を作成。外壁部分に穴を開ける。
// 今回のアルゴリズムでは、外壁のすぐ内側が通路になっていないことがあるので
// その場合には箇所を移動させる。
// どこをとっても通路が見あたらない場合には、エラーとする。
// （乱数の発生具合がとても意地悪な場合を考えると、可能性は少なくとも0ではない。）
//
bool CMazeMaker::makeStartGoal()
{
	// スタート地点を左の壁の上の方に
	int nCnt = 0;
	for (nCnt = 1; nCnt < m_nYSize - 1; nCnt++) {
		if (m_pMatrix->GetAt(1, nCnt) == MMK_Space) {
			m_pMatrix->SetAt(0, nCnt, MMK_Space);
			break;
		}
	}
	if (nCnt == m_nXSize - 1) {
		return false;
	}

	// ゴール地点を右の壁の下の方に
	for (nCnt = m_nYSize; nCnt > 0; nCnt--) {
		if (m_pMatrix->GetAt(m_nXSize - 2, nCnt) == MMK_Space) {
			m_pMatrix->SetAt(m_nXSize - 1, nCnt, MMK_Space);
			break;
		}
	}
	if (nCnt == 0) {
		return false;
	}
	return true;
}


// 現在位置nXPos, nYPosからみて、nXAdd、nYAddを足した位置に移動できるかをチェック
// 移動先が埋まっている状態で、さらに三方が通路以外に覆われているなら、OKとする

bool CMazeMaker::checkPos(int nXPos, int nYPos, int nXAdd, int nYAdd)
{
	if (m_pMatrix->GetAt(nXPos + nXAdd, nYPos + nYAdd) != MMK_Filled) 
		return false;

	if (nXAdd == 0) {
		if (m_pMatrix->GetAt(nXPos - 1, nYPos + nYAdd * 2) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos    , nYPos + nYAdd * 2) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + 1, nYPos + nYAdd * 2) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos - 1, nYPos + nYAdd ) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + 1, nYPos + nYAdd ) != MMK_Space)
		{
			return true;
		}
	} else {
		if (m_pMatrix->GetAt(nXPos + nXAdd * 2, nYPos - 1) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + nXAdd * 2, nYPos    ) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + nXAdd * 2, nYPos + 1) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + nXAdd , nYPos - 1) != MMK_Space &amp;&amp;
			m_pMatrix->GetAt(nXPos + nXAdd , nYPos + 1) != MMK_Space)
		{
			return true;
		}
	}
	return false;
}


static const int moveInfo[4][2] = {
	{-1, 0},
	{0, -1},
	{1, 0},
	{0, 1},
};

int CMazeMaker::process(int nXPos, int nYPos)
{
	int digCount=0;
	int aryMove[4] = {0};	

	if (m_pMatrix->GetAt(nXPos, nYPos) != MMK_Space) {
		return 0;
	}
	while (1) {
		int nMoveCount = 0;

		for (int nCnt = 0; nCnt < 4; nCnt++) {
			if (checkPos(nXPos, nYPos, moveInfo[nCnt][0], moveInfo[nCnt][1]) == true) {
				aryMove[nMoveCount] = nCnt;
				nMoveCount++;
			}
		}
		if (nMoveCount == 0) {
			break;
		}
		
		int nMove = ((rand() >> 1) % nMoveCount);
		nXPos = nXPos + moveInfo[aryMove[nMove]][0];
		nYPos = nYPos + moveInfo[aryMove[nMove]][1];
		m_pMatrix->SetAt(nXPos, nYPos, MMK_Space);
		digCount++;
	}
	return digCount;
}


bool CMazeMaker::Generate1()
{
	// 開始点は1, 1から。（ループの先頭
	m_pMatrix->SetAt(1, 1, MMK_Space);

	::srand((unsigned int)time(NULL));
	
	int nXCnt;
	int nYCnt;

	for (nXCnt = 1; nXCnt < m_nXSize - 1; nXCnt++) {
		for (nYCnt = 1; nYCnt < m_nYSize - 1; nYCnt++) {
			while (process(nXCnt, nYCnt) != 0) {}
		}
	}
	return makeStartGoal();
}


void CMazeMaker::dig(int nXPos, int nYPos)
{
	m_pMatrix->SetAt(nXPos, nYPos, MMK_Space);

	int aryMove[4] = {0};	

	while (1) {
		int nMoveCount = 0;

		for (int nCnt = 0; nCnt < 4; nCnt++) {
			if (checkPos(nXPos, nYPos, moveInfo[nCnt][0], moveInfo[nCnt][1]) == true) {
				aryMove[nMoveCount] = nCnt;
				nMoveCount++;
			}
		}
		if (nMoveCount == 0) {
			break;
		}
		
		int nMove = ((rand() >> 1) % nMoveCount);

		dig(nXPos + moveInfo[aryMove[nMove]][0], nYPos + moveInfo[aryMove[nMove]][1]);
	}
}

bool CMazeMaker::Generate2()
{
	::srand((unsigned int)time(NULL));
	int nXStart = ((rand() >> 1) % (m_nXSize - 2)) + 1;
	int nYStart = ((rand() >> 1) % (m_nYSize - 2)) + 1;
	dig(nXStart, nYStart);
	return makeStartGoal();
}

struct PosInfo {
	int xPos;
	int yPos;
};

bool CMazeMaker::Generate3()
{
	::srand((unsigned int)time(NULL));
	int nXStart = ((rand() >> 1) % (m_nXSize - 2)) + 1;
	int nYStart = ((rand() >> 1) % (m_nYSize - 2)) + 1;

	m_pMatrix->SetAt(nXStart, nYStart, MMK_Space);

	list<PosInfo> posList;

	PosInfo info = {nXStart, nYStart};
	posList.push_back(info);

	while (posList.size() != 0) {
		int nXPos = (posList.rbegin())->xPos;
		int nYPos = (posList.rbegin())->yPos;

		int aryMove[4] = {0};	

		int nMoveCount = 0;

		for (int nCnt = 0; nCnt < 4; nCnt++) {
			if (checkPos(nXPos, nYPos, moveInfo[nCnt][0], moveInfo[nCnt][1]) == true) {
				aryMove[nMoveCount] = nCnt;
				nMoveCount++;
			}
		}
		if (nMoveCount == 0) {
			posList.pop_back();
			continue;
		}
		
		int nMove = ((rand() >> 1) % nMoveCount);

		info.xPos = nXPos + moveInfo[aryMove[nMove]][0];
		info.yPos = nYPos + moveInfo[aryMove[nMove]][1];

		m_pMatrix->SetAt(info.xPos, info.yPos, MMK_Space);

		posList.push_back(info);
	}

	return makeStartGoal();
}

//
// コンソール出力用
class CMazeMakerConsole : public CMazeMaker
{
public:
	CMazeMakerConsole(){};
	virtual ~CMazeMakerConsole(){};

public:
	void Output();
};

void CMazeMakerConsole::Output()
{
	for (int nYCnt = 0; nYCnt < m_nYSize; nYCnt++) {
		for (int nXCnt = 0; nXCnt < m_nXSize; nXCnt++) {
			if (m_pMatrix->GetAt(nXCnt, nYCnt) == MMK_Space) {
				printf(".");
			} else {
				printf("#");
			}
		}
		puts("");
	}
	_getch();
}

// 
//
int _tmain(int argc, _TCHAR* argv[])
{
	CMazeMakerConsole maker;

	do {
		if (false == maker.Initialize(75, 50)) {
			puts("Initialize Error");
			return 0;
		}
	} while (false == maker.Generate3()); //失敗するのは、スタート、ゴールが作れなかった場合。偶然そういうことになることもあるので、そうなったら作り直す。


	maker.Output();

	return 0;
}

最初に昔の記憶を頼りにCMazeMaker::Generate1()を作ったけれど、美しくなかったのでGenerate2()を作成。迷路のサイズを増やすとスタックオーバーフローになるので、Generate3()を作成。一応、満足。

###########################################################################
.....##...#.#.##.....##......#....#...#.#.#.........#.##.........##.#.....#
#.#.##..#.#......###..###.##.#.##.#.###...#.#####.#....##.######....##.##.#
#.#..##.#.#.##.###.##.....##...#....#...#.....##..#.##.#..##...####..#..#.#
#.##..###.#..#..##..###.#..###.#.####.###.#####..####..#.##..#....##.##.#.#
#..##.....##.##..##...#.##..#######...#.#.#...#.##....##.#..###.#..#.##.###
#.####.#####.###.###.##..####.......###.###.#.###..##.#..#.##...##.#..#...#
#....###......#..#.#....##....########..##..#..#..#####.######.##..##.##.##
#.##..##.######.##...####..#####....#..##..###.#.##.##..#......#..###..#..#
#..##.#...##....#..#.#..#.##.#...#.##.##..##.....#.....####.####.##.##.##.#
##..#...#..#.#######...##....#.#####..#..#########.##.##.#..##...##..#....#
###.########.##...##########.#...##..##.##.##...####..#....##..###..#####.#
#.#..##...##..#.#.....##.....##.##..##..#...###.#.#..###.####.##...##.....#
#.##.#..#..##.#.#####.#..#####..#..##..##.#.....#...##.#.#....####.#..#####
#..#.#.###.#..#.....#...##.....##.##..##..##.##.#.###....####.#.#..#.###..#
#.##.#.##....######.########.###..#..###.##..#....#.##.#...#..#...##...##.#
#..#.#..###.##.#....#..#.....##..###..#...#.#######....#.#.#.##.#.####.##.#
##.#.##.##...#.#.#####...#####..##.##.##.##......#####.###.#.#..#..#.#..#.#
##....#..###...#....#..#.....#.##...#.#...#.#.##.....#..##.#...###...##...#
#..#####...########.####.##.##....#...#######..#####.####..#####.########.#
#.##.#.###..#.....#....###...###########...###..##...#....##.........##...#
#..#....###...#.#.####..#..#.....#.#.....#..#..##..###.#.##..#######.#..###
##.####...#######...###.##.#.###.#...######.####..##...#.#..##...#...#.##.#
#....####...#...###...#..#.#..####.#....#.....#..##..#.###.##..#.#.###.#..#
####...#..#.#.#..####.##.####......####.#####.##..#.##...#..####.#.#...#.##
##.###.#.##.#.##.#.#...#....##.######.#.##..#.###.######.##...#..#...###..#
#..##..#.####.##.#...#.####..#........#..##....##...##....###...######...##
#.##..##..##..#..##.####..##.#.######.##..####..#.#..##.###.#.#..#.##..#..#
#.##.####.#..##.##..##...###.###...#...##.##.##.####.#..#...####.#..#.###.#
#.#...#...#.###..##..#.#...#..#..#...#..#..#.##..##..#.##.#..##..##.#...###
#...#...#.#...##..##...#.####.####.#######.#..##.#..##..#.##..##..#...#...#
#.###########.###..#####....#...##.#..#....##..#...####.#..##..##.#######.#
#....#....##..#.##....###.#####..#...##.######.#####.##.##.###....#.....#.#
###.##.#.##..##..####..#..#...##.###.##......#...##.....##..########.##.#.#
#.#.#..#..#.####.#..##...##.#.#..#....######.#.#....#.#..##.#...##...#....#
#...#.###...#......####.##..#...###.###...##.#.######.#.##..#.#..##.####.##
#.#.#.#.#####.###.##....#..######.#.##..#..#.#..#.....#..##...##.#...#....#
#.###.#...##...#..#..####.##.#.##.#.#..##.##.##.#.###.##..######.#.#.####.#
#..##.#.#..#.#.####.###.#..#......#...#####..#..#...####.##..#.#.###.##...#
##..#...##.#.#.#........##.#.#.#.####..#....#######..##...##...#..#...###.#
###.######.#.#...####.#..#.#.###.#..##.#.####....###..###..##.###.###...#.#
#...#...#..#####...##.####.#..#....##..#..#...##...##...##......#..####.#.#
#.###.#...##...#####..##...##.#.##.#..###.#.######..##.###########.#....#.#
#..#..##.##..#.#...#.##..######..###.##.#....###.##.##...#.......#.#.#.####
#.##.###..#.##...#.###..##....##........#.##..#...#..#.#.#.###.#.#.###....#
#..#...##.#..#####..##.####.#.##.############...#.##.#.#.#...#.###..##.##.#
##.###..###.##...##.#..#....#..###....##....#######..#.###.###...##..###..#
#...###..#...##.###.#.##.#####...#.##.#..##.#...#...##..#...###.####.#...##
#.#...##...#......#......#.....#...#....##....#...#..##...#...#........#...
###########################################################################

ちなみに http://anond.hatelabo.jp/20070711194709　これを聞いたのは自分。

かなりたくさん書けることがわかりました。

Permalink | 記事への反応(0) | 00:34

記事への反応 -
  • http://anond.hatelabo.jp/20070711013155

    元増田じゃないけど、面白そうだから、今日会社から帰ったら参加してみよう。 迷路なんて、15年以上前に作ったっきりだなぁ。 アルゴリズムも忘れたけど、だがそれがいい。

    • 迷路作成プログラムをVC++2005でやってみた。

      http://anond.hatelabo.jp/20070711013155　こちらの宿題を作ってみました。 http://anond.hatelabo.jp/20070711080519　で参加を宣言した者です。 #include &quot;stdafx.h&quot;#include &lt;time.h&gt;#include &lt;conio.h&gt;#include ...

記事への反応（ブックマークコメント）

人気エントリ

注目エントリ

ログイン ユーザー登録
ようこそ ゲスト さん