Mine Finder

1. 소개 ¶

이름 : Mine Finder
참여 : 강석천 (99, 1002)
기간 : 2002. 2. 10 ~ 2.23 (문서화 작업과정 포함해서.. 2주 걸릴듯.)
목표 : 윈도우의 지뢰찾기 프로그램과 직접 대화, 지뢰를 스스로 찾아내는 프로그램을 만든다.
개발툴 : Visual C++ 6.0, cppunit 1.62, SPY++, 지뢰찾기 2000, 98버전
동기 : 심심해서. 손목저려서. -_-;
개발방법 : XP 의 일부분 소폭적용.
시스템 : 듀론 1G 256RAM WIN 2000

2. 계획 ¶

2.1. schedule ¶

특별히 잡은바 없음. --;
2월 16일까지 프로그래밍 완료. 2월 23일까지 문서화 완료.

목표수정 - 뜻하지 않은 문제로. -_-; 2월 28일. 말일까지는 어떻게든! --;

2.2. 기능 spec ¶

윈98, 윈2000 지뢰찾기 프로그램 지원 (현재 2000 은 제대로 지원. 98 쪽 호환성 높이기중)
추후 프로그램이 커질 경우 '눈' 부분과 '지능' 부분을 따로 빼낼 수 있도록 궁리.
- '눈' 해당 부분 - 지뢰찾기 프로그램으로부터 비트맵을 얻어 데이터로 변환하는 루틴 관련부. 현재 bitmap 1:1 matching 부분이 가장 부하가 많이 걸리는 부분으로 확인됨에 따라, 가장 개선해야 할 부분.
- '지능' 해당 부분 - 변환된 데이터를 근거로 해야 할 행동을 결정하는 부분. 기본적인 형태는 유한상태머신을 띈다.
  - 추후 DP 로 확장된다면 StrategyPattern 과 StatePattern 등이 이용될 것 같지만. 이는 추후 Refactoring 해 나가면서 생각해볼 사항. 프로그램이 좀 더 커지고 Refactoring 이 이루어진다면 DLL 부분으로 빠져나올 수 있을듯. ('빠져나와야 할 상황이 생길듯' 이 더 정확하지만. -_-a)

3. 진행 상황 ¶

2월 10일
- 지뢰찾기 프로그램의 윈도우 핸들을 얻고 해당 메세지를 보내어서 지뢰찾기 프로그램을 구동하는 루틴 관련 SpikeSolution. (아.. UnitTest 코드 넣기가 애매해서 안넣었다. 궁리해봐야 할 부분같다.)
- 지뢰찾기 프로그램의 윈도우 핸들을 얻은뒤 DC를 얻은후 화면 캡쳐. 그리고 캡쳐한 비트맵을 근거로 하여 데이터로 변환하는 루틴 관련 SpikeSolution
2월 11일
- Main Design, Algorithm 1차 완성. 어느정도 Refactoring의 추구.
2월 13일
- 알고리즘 최적화 궁리. 3가지정도 대안 모색.
- 98 버전의 지뢰찾기와 2000 버전의 지뢰찾기가 비트맵데이터가 달라서 생기는 문제 어느정도 해결.
- 현재 속도
  - Begineer mode 최고기록 1초, 평균 4-7초.
  - Middle mode 최고기록 21초, 평균 30~50초 안쪽.
  - Expert mode 최고기록 151초. 단, 깰 수 있는 확률 낮음. -_-; 아. 확률높은 찍기 알고리즘이 필요하다는. --;
2월 26일
- 도큐먼트 추가중. (일주일을 푸욱 놀았다는. -_-;)
2월 27일
- Expert mode 51초, Middle mode 11초 기록. 알고리즘 최적화에 대한 다른 관점 잡음. (하지만, 여전히 깰 수 있는 확률 낮음)
2월 28일, 3월 1일
- Expert mode 깰 수 있는 확률을 높임. 최적화내에서 해결할 방법은 더 힘들듯. 98과의 호환성 향상문제 해결이후 종료 예정.
3월 1일 종료.

4. 종료후 감상기(?) ¶

디자인 부분에서의 TFP의 중요성을 놓친것이 화근이 되었다는. -_-; 추후 알고리즘 부분으로 들어가면서 TFP를 게을리 한 점과 프로그램 돌아간다는 점에서의 즐거움에 시간낭비가 좀 심했다는..~
미션 크리티컬한 문제였다면 그냥 넘어가면 안될 일이지만. -_-; 장난감 가지고 노는 기분으로 한 일이였던지라.~ 그리 무게감을 가지고 한 일이 아닌 관계로 특별히 나쁘진 않았다.
현실에서 가상으로 다시 현실로. 암튼 '1002 보기에 좋았더라'. 여전히 멍청한 넘이고 주사위 던지는 넘이지만 (오호.. Random Open 때 주사위 돌리는 애니메이션을 넣을까. ^^;)
지금쯤 다시 짜라고 한다면 TFP를 좀 더 제대로 추구할 수 있을 것도 같다. (이 점에서 TFP를 할때 SpikeSolution 에 대한 어느정도의 충분한 시간을 두는 점이 좋을 것 같다는 생각이 들었다. 초기 SpikeSolution 으로 해당 부분을 간단하게 대강 해보고, Test를 할 수 있는 부분에 대한 구체화하기.)
CppUnit 를 쓸때에는 MFC 라이브러리들이 static 으로 링킹이 안되는 것 같다. 좀 더 살펴봐야겠다.

5. 참조 문서 ¶

MSDN

----
영현 형 신기해~ ㅎㅎㅎ bitmap data로 숫자들과 거시기들을 구분한건가..ㅡㅡa.. spy 좋구만..

해성 오오.. Artificial Intelligence..

근데 저 스펠링이 맞나..

1002 뭐. 어차피 노가다를 해도 컴터가 하는 것을. -_-v 이로서 즐기게 되는 게임이 하나 줄어버리는건가. --;; A.I. 라고 붙이기엔 너무 단순해서 좀 쪽 팔리는군. --;

6. Opening ¶

습관성으로 여는 프로그램 Best: 1. Explorer 2. 프리셀 3. 지뢰찾기. -_-;

NSISIde 소스를 만지작 거리던중 피곤해서 지뢰찾기를 하게 되었다. 조옴 무리를 했는지(?) 손목이 저려오기 시작했다. 그러다가 갑자기 '퍽' 하고 동시 다발적으로 여러가지 생각을 하게 되었는데, 하나는 예전에 학교에서 열렸던 '선배님들과의 만남' 에서 소프트캠프에 있는 환국선배가 했던 말이였다.

프로그래밍이 뭐라고 생각하세요? 여러가지 답이 나올수 있겠지만, 저는 현실세계에 있는 것들을 가상세계로 모델링하는 것이라고 생각했어요.

자.. 노가다를 하고 있는 나의 저려오는 손목을 모델링해보자. -_-..

7. User Story ¶

지뢰찾기 프로그램은 윈도우에 기본적으로 내장된 프로그램을 이용한다.
기본적으로는 Begineer Mode 만을 지원한다.
컴퓨터는 현재의 지뢰찾기 프로그램 상황을 알아서 판단하고, 해당 행동을 결정한다.
컴퓨터가 실패했을 경우 자동으로 다시 시작하여, 사용자가 중지시키거나 지뢰를 다 찾을때까지 프로그램을 계속 진행시킨다.

8. 간단 작업 준비 ¶

Spy++
Visual C++ (2개 열어두고 쓴다. 하나는 해당 부분부분 연습용 코드 만들 곳. 하나는 메인소스 만들 곳)
인덱스 카드 & 필기구 - CRC 를 쓰건 UserStory를 쓰건..~ 단,
지뢰찾기
CppUnit - 이번 플밍때 윈도우 메세지 관련 처리에 대해서는 코드를 작성못했다. (이 부분에 대해서는 전통적인 Manual Test방법을 쓸 수 밖에. GUI Testing 관련 글을 더 읽어봐야 겠다. 아직 더 지식이 필요하다.) 단, 나중에 비트맵 분석부분 & Refactoring 시에 TFP 를 할 수 있게 되었다.

9. Start. 어디서 부터 잡아갈까.. 데이터 모으기 ¶

글쌔. 무엇부터 해 나가야 할 것인가. 일단은 지뢰찾기 프로그램을 제어할 수 있는 프로그램이여야 하고, 지뢰찾기 알고리즘도 필요할테고.. 우어. 정신없다. 일단은 생각나는 것들에 대해 하나하나 잡아봐야겠다.

일단, 소위 말하는 '꺼리' 들을 찾기 위해 Spy++ 을 실행시켰다.

http://zeropage.org/~reset/zb/data/spy_1.gif

[GIF external image]

지뢰찾기 프로그램의 윈도우클래스 이름이 '지뢰 찾기' 였다. 윈도우 OS 의 특징상 해당 윈도우 핸들간 메세지의 발생에 따라 해당 윈도우프로시저에서 처리가 된다. 해당 윈도우 핸들은 윈도우 클래스 이름을 아는 이상 FindWindow 함수를 이용해서 찾으면 될 것이다.

각각 메뉴들에 대해 처리를 하기 위해 Message 를 캡쳐해봤다.

http://zeropage.org/~reset/zb/data/spy_2.gif

[GIF external image]

beginner 에 해당하는 메뉴클릭시 발생하는 메세지는 WM_COMMAND 이고, ID는 wParam 으로 521이 날라간다. 즉, 해당 메뉴의 ID가 521 인 것이다. (우리는 컨트롤 아이디를 쓰지만 이는 resource.h 에서 알 수 있듯 전부 #define 매크로 정의이다.) 각각 찾아본 결과, 521,522,523 이였다.

지뢰 버튼을 열고 깃발체크를 위한 마우스 클릭시엔 WM_LBUTTONDOWN, WM_RBUTTONDOWN 이고, 단 ? 체크관련 옵션이 문제이니 이는 적절하게 처리해주면 될 것이다. 마우스클릭은 해당 Client 부분 좌표를 잘 재어서 이를 lParam 에 넘겨주면 될 것이다.

손에 대한 모델링이여서 그런지 손에만 집착하게 되었군. -_-; 이 일을 위해서는 손, 눈, 머리가 있어야 하겠는데. 마우스 노가다를 위한 손, 해당 지뢰찾기 상태를 봐야 할 눈, 그리고 해당 상황에 따른 판단, 지시를 해야 할 머리의 모델링. (단, 여기에 각각에 대해 조건을 붙인다면 '지뢰찾기프로그램을 위한' 이라는 말이 붙겠지만.)

눈에 해당하는 부분은 어떻게 할까.. 하나는 신이 되는 방법이 있고 하나는 사람이 되는 방법이 있다. -_-; 즉, 하나는 직접 지뢰찾기 프로그램의 메모리부분을 얻어낸 뒤, 그중에 배열에 해당되는 부분 (어떤 데이터구조일지는 모르겠지만, 배열일 것 같다. -_-;)을 얻어내서 보던지, 아니면 사람처럼 화면을 봐야 할 것이다. 애석하게도 나는 지뢰찾기의 창조자도 아니고 윈도우의 창조자는 더더욱 아니므로. -_-; 후자를 선택하게 된다.

원리는 간단하다. 윈도우 핸들을 얻을 수 있다면, 해당 윈도우에 대한 DC를 얻을 수 있을 것이다. DC를 얻을 수 있다면, BitBlt 을 이용, 비트맵을 메모리DC 쪽으로 복사할 수 있을테니까. (간단한 캡쳐 프로그램시 이용할 수 있다.) 단, 화면을 복사하려는 프로그램이 다른 프로그램에 가려지면 안되겠다.

머리는? 지뢰찾기 알고리즘에 해당되는 부분은. 으흐~ 나중에. -_-; 대강 이쯤 해서 각 부분부분에 대해 맞는지를 알아보기 위한 프로그램을 간단하게 짰다.

1차일부분코드 - 손과 눈에 해당하는 부분 코드를 위한 간단한 예제코드들 모음. 그리고 지뢰찾기 프로그램을 제어하는 부분들에 대해 Delegation 시도. (CMinerControler 클래스는 처음 '막 짠' 코드로부터 지뢰찾기 제어부분 함수들을 클래스화한것임)

10. User Story & Engineering Task ¶

여기서는 Task Estmiate 를 생략했다. (그냥 막 나간지라. ^^;)

지뢰찾기 프로그램은 윈도우에 기본적으로 내장된 프로그램을 이용한다.
- 현재 열려있는 프로그램 중에서 지뢰찾기 프로그램을 윈도우 클래스 이름으로 찾아낸다.
- 지뢰찾기 프로그램을 조작한다. (Mode 변환, 재시작, 지뢰체크, 빈칸 열기 등)
  - 지뢰찾기 프로그램에게 해당 행동 Message를 보낸다.
- 지뢰찾기 프로그램의 화면을 Capture, 분석한뒤 데이터화한다.

기본적으로는 Begineer Mode 만을 지원한다.
컴퓨터는 현재의 지뢰찾기 프로그램 상황을 알아서 판단하고, 해당 행동을 결정한다.
- 지뢰찾기 프로그램 비트맵 데이터를 근거로 수치데이터화한다.
  - 게임 시작 & 게임중인 상태 확인
  - 게임 실패인 상태 확인
  - 게임 클리어인 상태 확인
  - 빈칸, 깃발체크, 숫자들 등 Cell들에 대한 상태 확인
- 지뢰찾기 판단 알고리즘을 만든다.
  - 깃발 체크를 해야 할 때
  - 빈칸을 열어야 할 때
  - 빈칸 찍기를 해야 할 때

컴퓨터가 실패했을 경우 자동으로 다시 시작하여, 사용자가 중지시키거나 지뢰를 다 찾을때까지 프로그램을 계속 진행시킨다.
- 게임 실패인 상태에 대한 확인하기.
- 프로그램을 다시 시작하도록 조작하기.

11. First ¶

1차제작소스
- 유의 : 이때는 Windows ME, Windows 2000 이상에서만 실행가능하다. (지뢰찾기 비트맵이 98과 다르다)
- 기록 : 초급 8-9초, 중급 90-100초, 고급쪽은 너무 느려서 테스트 포기. -_-;

처음에는 전체에 대한 환경설정을 하게 된다. 기본적인 클래스는 다음과 같다.

CMinerBitmapAnalyzer	비트맵을 분석, 데이터화한다.
CMinerController	지뢰찾기 프로그램에 대한 화면 캡쳐, 모드변환, 버튼 클릭 등의 제어를 한다
CMineSweeper	실질적인 두뇌에 해당되는 부분. CMinerController 와 CMinerBitampAnalyzer 를 멤버로 가지며, 이를 이용하여 게임상황분석, 지뢰찾기관련 판단 등을 한다

일종의 애니메이션을 하는 캐릭터와 같다. 타이머가 Key Frame 에 대한 이벤트를 주기적으로 걸어주고, 해당 Key Frame 에는 현재 상태에 대한 판단을 한뒤 동작을 한다. 여기서는 1초마다 MineSweeper 의 동작을 수행하게 된다.

~cpp 
void CMinerFinderDlg::OnButtonStart() 
{
	// TODO: Add your control notification handler code here
	m_mineSweeper.Start ();
	SetTimer (1000, 100, NULL);
}

void CMinerFinderDlg::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	int nRet = Excute ();
	if (nRet == MINERMODE_CLEAR) 
		KillTimer (1000);
	
	CDialog::OnTimer(nIDEvent);
}

void CMinerFinderDlg::OnButtonStop() 
{
	// TODO: Add your control notification handler code here
	KillTimer (1000);
}

int CMinerFinderDlg::Excute ()
{
	return m_mineSweeper.Excute ();
}

MineSweeper 의 Excute 의 방법은 일종의 유한 상태 머신의 형태이다. 단지 Switch ~ Case 만 쓰지 않았을뿐이지만. 그리 큰 장점이 보이지는 않은 관계로 일단은 그냥 이렇게.

~cpp 
int CMineSweeper::Excute ()
{
	CBitmap* pBitmap = CaptureClient ();

	ConvertBitmapToGameMode (pBitmap);
	ConvertBitmapToData (pBitmap);

	if (m_nCurrentGameMode == MINERMODE_GAMEOVER) {
		Start ();
		return m_nCurrentGameMode;
	}

	// Todo : Matrix 를 근거로 하여 할 일의 설정.
	// 할 일 : 
	int nRet = 0;

	CMinerFinderDlg* pDlg = (CMinerFinderDlg*)m_pDlg;
	
	//		Flag 의 체크. 횟수세기.
	nRet = CheckFlag ();
	if (nRet) {
		pDlg->PrintStatus ("Action : CheckFlag - %d rn", nRet);
		return m_nCurrentGameMode;
	}

	//		Open. 횟수세기.
	nRet = OpenBlocks ();
	if (nRet) {
		pDlg->PrintStatus ("Action : OpenBlocks - %d rn", nRet);
		return m_nCurrentGameMode;
	}

	//		찍기. --;
	RandomOpen ();
	pDlg->PrintStatus ("Action : Random Open rn");

	return m_nCurrentGameMode;
}

11.1. Profiling ¶

~cpp 
Profile: Function timing, sorted by time
Date:    Tue Feb 26 19:16:26 2002


Program Statistics
------------------
    Command line at 2002 Feb 26 19:00: "F:WorkingTempMinerFinderDebugMinerFinder" 
    Total time: 223521.679 millisecond
    Time outside of functions: 28.613 millisecond
    Call depth: 23
    Total functions: 660
    Total hits: 37532338
    Function coverage: 52.1%
    Overhead Calculated 5
    Overhead Average 5

Module Statistics for minerfinder.exe
-------------------------------------
    Time in module: 223493.066 millisecond
    Percent of time in module: 100.0%
    Functions in module: 660
    Hits in module: 37532338
    Module function coverage: 52.1%

        Func          Func+Child           Hit
        Time   %         Time      %      Count  Function
---------------------------------------------------------
   86270.513  38.6    86270.513  38.6 18252086 CDC::GetPixel(int,int) (mfc42d.dll)
   53966.631  24.1   223296.921  99.9      855 CWinThread::PumpMessage(void) (mfc42d.dll)
   28819.313  12.9   150892.058  67.5    93243 CMinerBitmapAnalyzer::CompareBitmapBlock(class CDC *,class CDC *,int,int,int,int,class CDC *,int,int) (minerbitmapanalyzer.obj)
   18225.064   8.2    61776.601  27.6  9126043 CMinerBitmapAnalyzer::CompareBitmapPixel(class CDC *,class CDC *,int,int,unsigned long) (minerbitmapanalyzer.obj)
   17577.168   7.9    17577.168   7.9  9126043 CDC::SetPixel(int,int,unsigned long) (mfc42d.dll)
    5146.101   2.3    53721.330  24.0      104 CMineSweeper::CheckFlag(void) (minesweeper.obj)
    4748.690   2.1     4974.806   2.2       74 CMineSweeper::OpenBlocks(void) (minesweeper.obj)
    2496.582   1.1     2506.333   1.1       27 CMineSweeper::RandomOpen(void) (minesweeper.obj)
    1504.775   0.7     1504.775   0.7    85245 CDC::DeleteDC(void) (mfc42d.dll)
     944.596   0.4      944.596   0.4    85245 CDC::CreateCompatibleDC(class CDC *) (mfc42d.dll)
     492.930   0.2   111257.841  49.8    32492 CMinerBitmapAnalyzer::ConvertBitmapToBlock(int,int) (minerbitmapanalyzer.obj)
     383.392   0.2      383.392   0.2    85245 CDC::SelectObject(class CBitmap *) (mfc42d.dll)
     348.243   0.2      348.243   0.2    42702 CWnd::ReleaseDC(class CDC *) (mfc42d.dll)
     326.552   0.1      326.552   0.1      221 CWnd::SetWindowTextA(char const *) (mfc42d.dll)
     294.378   0.1      295.578   0.1     2619 CWnd::DefWindowProcA(unsigned int,unsigned int,long) (mfc42d.dll)
     251.949   0.1      251.949   0.1    42702 CWnd::GetDC(void) (mfc42d.dll)
     201.741   0.1      225.112   0.1      221 CEdit::LineScroll(int,int) (mfc42d.dll)
     184.900   0.1      184.900   0.1   208404 CMineSweeper::GetData(int,int) (minesweeper.obj)
     155.178   0.1    42649.225  19.1     9944 CMinerBitmapAnalyzer::ConvertBitmapToNumber(int,int) (minerbitmapanalyzer.obj)
     134.201   0.1   154139.803  69.0      157 CMineSweeper::ConvertBitmapToData(class CBitmap *) (minesweeper.obj)

위의 결과를 보면, 가장 많이 호출되어 시간을 점유하는 것은 GetPixel와 PumpMessage이다. mfc의 함수와 윈도우 메세지드리븐 방식에 대해서는 수정할 수 없다 하더라도, 해당 함수에 대해서 호출 횟수를 줄이는 방법은 강구해야 할 것이다.

GetPixel 은 어디서 호출될까? Edit->Find in Files 를 하면 해당 프로젝트내에서 GetPixel이 쓰인 부분들에 대해 알 수 있다.

~cpp 
Searching for 'GetPixel'...
F:WorkingTempMinerFinderMinerBitmapAnalyzer.cpp(65):	if (bmpdc->GetPixel (bmpStartX,bmpStartY) != rgbColor)
F:WorkingTempMinerFinderMinerBitmapAnalyzer.cpp(135):			rgb = screendc->GetPixel (nX+nBi,nY+nBj);
2 occurrence(s) have been found.

GetPixel은 다음과 같은 화면 캡쳐로 얻은 비트맵에 대해 비교하여 같은 데이터임을 판독하는 부분에 쓰였다.

~cpp 
BOOL CMinerBitmapAnalyzer::CompareBitmapPixel (CDC* pDC, CDC* bmpdc, int bmpStartX, int bmpStartY, COLORREF rgbColor) 
{
	if (bmpdc->GetPixel (bmpStartX,bmpStartY) != rgbColor)
		return FALSE;
	else
		return TRUE;
}

BOOL CMinerBitmapAnalyzer::CompareBitmapBlock (CDC* pDC, CDC* screendc, int nX, int nY, int nWidth, int nHeight, CDC* bmpdc, int nSrcX, int nSrcY)
{
	int nBi, nBj;
	COLORREF rgb;

	for (nBi=0;nBi<nWidth;nBi++) {
		for (nBj=0;nBj<nHeight;nBj++) {
			rgb = screendc->GetPixel (nX+nBi,nY+nBj);
			pDC->SetPixel (nX+nBi,nY+nBj,rgb);
			
			if (!CompareBitmapPixel (pDC, bmpdc, nSrcX + nBi, nSrcY + nBj, rgb)) return FALSE;
		}
	}

	return TRUE;
}

즉, 저 함수들을 최적화 시키던지, 아니면 저 함수들이 호출되는 횟수를 줄여야 하는 것이다.

12. Second - 최적화의 시도 ¶

2차제작소스
- 유의 : 여전히 Windows ME, Windows 2000 이상에서만 실행가능하다. (지뢰찾기 비트맵이 98과 다르다)
- 기록 : 초급 2-3초, 중급 21~40초, 고급쪽은 너무 느려서 테스트 포기. -_-;
- 반성 : 차라리 순수 TFP 로 해 나갈걸 그랬다는 생각이 든다. 테스트 코드에 대한 아이디어를 제대로 못내었다. (아.. 타성에 젖으면 안되건만. --; TFP중 막힐때 예전방식으로 플밍하려고 하는게 문제이다. -_-;)

12.1. 최적화 방안의 궁리 ¶

목표는 Func time 이 많이 걸리는 함수들에 대해서 그 횟수를 줄이는 방법.

비트맵의 종류가 한정적이라는 점에서 착안, Block 전체에 대한 비교대신 한줄에 대한 비교로 바꿨다. (블럭마다 숫자들의 색이 다르므로, 이를 이용하면 속도 향상을 이끌어 낼 수 있겠다.)

~cpp 
BOOL CMinerBitmapAnalyzer::CompareBitmapCenterLine (CDC* screendc, int nX, int nY, int nWidth, int nHeight, CDC* bmpdc, int nSrcX, int nSrcY)
{
	int nBi, nBj;
	COLORREF rgb;
	nBj = int(nHeight / 2);

	// for optimizing...
	for (nBi=int(nWidth / 4);nBi<nWidth-int(nWidth / 4);nBi++) {
		rgb = screendc->GetPixel (nX+nBi,nY+nBj);
	
		if (!CompareBitmapPixel (bmpdc, nSrcX + nBi, nSrcY + nBj, rgb)) return FALSE;
	}

	return TRUE;
}

Flag 체크부분 효율화 - 기존의 방식은 Flag 을 하나씩 체크하고 난 뒤, 다시 전체 비트맵을 읽어오는 방식이였다. 이에 대해 Flag 를 체크할 수 있는 부분에 대해 한꺼번에 체크하도록 알고리즘을 수정했다. 이는 전체 비트맵을 읽어오는 횟수를 줄여주므로, 효율성이 높아진다.

~cpp 
int CMineSweeper::CheckFlag ()
{
	int nCount = 0;
	int nCheckCount = 0;

	CMinerFinderDlg* pDlg = (CMinerFinderDlg*)m_pDlg;

	for (int i=0;i<m_nArrMaxY;i++) {
		for (int j=0;j<m_nArrMaxX;j++) {
			if (IsNumber (GetData (j,i))) {
				// 숫자인 경우. 
				nCount = GetAroundClosedCount (j,i) + GetAroundFlagCount (j,i);

				if (nCount == GetData(j,i) && GetAroundClosedCount (j,i)) {
					SetFlagsAround (j,i);
					
					// CBitmap* pBitmap = CaptureClient ();
					// ConvertBitmapToData (pBitmap);

					nCheckCount ++;
				}
			}
		}
	}

	return nCheckCount;
}

13. Third - 최적화 시도 2 ¶

3차제작소스
지역 우선 검색법 - 이벤트를 빨리 발생하기 위한 방법. 이전에 지뢰체크를 하거나 빈칸을 연 곳을 기준으로 검색범위를 점점 넓혀가는 방법
문제점의 발생 - windows 98 이하버전의 지뢰찾기 비트맵부분
4차제작소스
windows 98 이하 버전 지뢰찾기 지원. (완벽하진 않음)

14. Fourth - 최적화 시도 3 ¶

5차제작소스
초반 무차별 찍기 기능 추가하기
Status 표시창 주기적으로 지워주기 - 진행상황이 길어지면 길어질수록 부하가 많이 걸린다.
Open Block 에 대해서 한꺼번에 일괄처리 - 의외로 효과가 높은 방법 (궁극적으로는 Excute 수행 횟수를 줄여주므로)
추후 알고리즘 최적화에 대한 궁리
- 지역 우선 비트맵 분석 & 데이터화 - 무조건 전체 비트맵을 데이터화 하는대신, 탐색하려는 기점을 잡고 그 기점을 중심으로 데이터화하려는 범위를 넓혀가는 방법
- Random Open 에 대한 확률 높이기 방법 궁리
  - 해당 빈칸들에 대해서 주위의 숫자들의 합이 가장 낮은 빈칸을 여는 것.
- Smart Random Open - 현재 열 수 있는 Cell 수를 기준으로 Random Open 횟수를 조절하는 방식

15. Fifth - 최적화 시도 4 ¶

6차제작소스
Random Open 에 대한 확률 높이기 시도 - 해당 빈칸들에 대해서 주위의 숫자들의 합이 가장 낮은 빈칸을 50%의 확률로 열기 시도. 비교적 빈칸을 여는 확률이 높아지긴 했다. (단, 의미없는 곳이 열리는 경우가 많다는점에서 개선의 여지필요)
Smart Random Open - 현재 열 수 있는 Cell 수를 기준으로 Random Open 횟수를 조절함. 전체 Cell 수의 1/8 비율.
98호환버그수정소스

16. Thread ¶

안녕하세요, 강석천님. 여기 이렇게 글 쓰는게 맞는지 모르겠네요.
검색을 하다가 우연히 MineFinder 페이지를 발견했습니다. 상당히 재미있더군요, 소스를 무척 깔끔하게 이해하기 쉽도록 만드셔서 무척 인상깊게 봤습니다. 다름이 아니오라 질문이 있어서 이렇게 글을 남깁니다. 지뢰찾기 알고리즘에서 각 블럭의 상태를 비트맵으로 비교를 하고 있는데 지뢰찾기 윈도우의 비트맵 데이타를 어떻게 추출하셨는지 궁금합니다. 제가 윈도우 초보라서 그런지 몰라도 무척 궁금하네요. 그 방법을 다른 응용 어플리케이션에서 얼마든 응용할 수 있을 것 같아서요. 답변 부탁드립니다. --동우

관심있게 봐 주셔서 감사합니다.

제가 한 비트맵 데이터 추출 방법은 일반적인 윈도우 캡처 프로그램의 원리와 비슷합니다. FindWindow 를 이용, 지뢰찾기 프로그램의 윈도우 핸들을 얻은뒤, 이를 가지고 해당 윈도우의 비트맵을 얻어내는 것이지요. 기타 제작 과정과 아이디어는 MineFinder 페이지에 서술해놓았습니다. --1002

답변 감사드립니다. 제가 질문드리고자 했던 포인트는 GetClientRect API를 통해 윈도우의 클라이언트 영역을 가져와서 실제 비교하는 IDB_BITMAP_MINES 비트탭 리소스를 말씀드린 것이였습니다. IDB_BITMAP_MINES 비트맵 리소스도 GetClientRect 를 통해 추출하신건가요? 만약 그 API로 추출하셨다고 해도 클라이언트 영역 전체가 캡쳐가 되었을 텐데 숫자와 버튼등을 픽셀 단위로 어떻게 추출해서 IDB_BITMAP_MINES 리소스로 만드셨는지 궁금합니다. MineFinder 페이지에는 IDB_BITMAP_MINES 리소스를 만드는 이야기는 없어서요. --동우

리소스 화일은 그냥 화면캡쳐한 뒤 포토샵에서 잘랐습니다.

(좀 노가다 틱하지만 가장 간단한 해결책이 아닐까 하는 생각. 2년전 일이여서 정확히 기억 안나지만 95용 지뢰찾기와 2000용 지뢰찾기 2번 작업했었을겁니다. 약간 그림이 다르고 이미지좌표도 조금은 달라서. ^^)--1002

강석천님. MineFinder를 win32 API로 컨버전 해서 제 홈페이지에 코드 분석 강좌 페이지를 만들까 합니다. 물론 원저자와 원작 페이지의 링크를 분명히 표시할 것입니다. 그렇게 win32 API 버전으로 수정해서 제 홈페이지에 게시를 할 수 있을지요. 석천님의 허가를 부탁드립니다. --동우

출처(링크)만 표기하시면 자유롭게 이용하셔도 됩니다. 홈페이지 링크주세요.

(혹시 전에 지뢰찾기 어셈레벨에서 분석하여 MineFinder 만드신 분이신가요? 저는 인간까지만 모델링 했지만, 신을 모델링한. ^^;) --1002

저의 홈페이지는 http://ssrnet.snu.ac.kr/~leedw 입니다. MineFInder는 잘 모르겠구요, 지뢰찾기를 디스어셈블링해서 프로세스 메모리 맵 안의 0x1005700 번지가 지뢰찾기의 전체 상태 맵 배열이란건 알고 있습니다. 이곳 맵 상태 배열에서 7번째 비트가 1로 셋팅되어 있으면 그것에 해당되는 x, y좌표가 지뢰가 있는 곳이지요. 그래서 지뢰찾기 맵핵을 만들었더랬습니다. 저는 '해부학자'를 모델링 했다고하면 되겠네요. 어쨌든 허락해 주셔서 감사합니다.

--동우

조동영이가 중급으로 19초도 해냈습니다;; 어디서 05학번중에 김소현이라는 친구가 손으로 초급 10초 안팍이 나온다고 들었습니다. - 톱아보다

초급은 나도 9초까진 해봤음. 그래도 내가 본 최고는 97의 희진누님.; (고급 50-60초대) --1002

----
프로젝트분류

Contents