当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 利用SDK实现迷宫算法

VC++
VC++：小编浅谈VC中定制串行化
VC++：小编浅谈DDB的创建
VC++：浅谈JSF 生命周期
VC++：小编浅谈静态连接库
VC++：应用程序执行机制之WinMain函数
VC++：CRecordset类中的修改、添加和删除记录
vc2008下载地址

No. « 25 26 27 28 »

技术文章搜索

关键字

VC++ 中的 利用SDK实现迷宫算法

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 86 ::
收藏到网摘: n/a

老调重提,利用 SDK 实现迷宫算法

作者：赖锋


下载本文示例源代码

我近来重看了数据结构的书,现在的教材还是使用C/C++的编写的算法,编译还是在console mode进行, 如果能把这些数据结构的算法使用在SDK上,那么就可以开发出 Windows 程序的算法程序提高学习,不用在 单调的console mode 中看着冷冰冰的字符来学习数据结构了,这样学习一方面可以学习调用 Windows API 和 Windows编程,另一方面可以学习数据结构. 希望我这样的学习方法对那些初学 Windows 的朋友有一些帮助.
这是使用 SDK 开发出来的迷宫程序(F1 键开始).



迷宫算法还是老路子,回溯法和堆栈实现,我采用的是堆栈实现. 使用双向链表摸拟堆栈,使用一个 ptrFirst 和一个 ptrLast 和作为堆栈的栈底和栈顶指针, 定义一 个堆栈元素结构, 这个结构保存迷宫中的位置. 

typedef struct _tagNode {	int	nRow;	int	nColumn;	struct _tagNode* next;	struct _tagNode* previou;} Node;
定义一个标记数组
BOOL bPass[ Row ][ Column ];	// Row 和 Column 为迷宫大小.
迷宫算法的主要伪代码的实现方式.
A.从开始位置开始,判断小球的各个方向是否可行,若一个方向可行,则向该方向移动.
前进的位置进栈.
条件: 前进方向是墙, 则该方向不能向前.
前进和方向如果是经过的,则该方向不能向前.
	if ( CanMove( gnRow, gnColumn, right ) )	{	gnColumn += moveRight; // 前进	bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置	// gnRow, gnColumn 位置入栈.	}	else if ( CanMove( gnRow, gnColumn, left ) ) // right 方不通, 向左.	{	gnColumn += moveLeft; // 前进	bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置	// gnRow, gnColumn 位置入栈.	}	else if ( CanMove( gnRow, gnColumn, forward ) ) // left 方不通, 向前.	{	gnColumn += moveForward; // 前进	bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置	// gnRow, gnColumn 位置入栈.	}	else if ( CanMove( gnRow, gnColumn, back ) ) // forward 方不通, 向后.	{	gnColumn += moveBack; // 前进	bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置	// gnRow, gnColumn 位置入栈.	}
B.各个方向不能可行,退回前一个位置,利用退栈操作,回到 A.
	else if ( CanMove( gnRow, gnColumn, back ) )	{}
A, B 不断重复, 直到找到出口, 或遍历迷宫(栈空)
	if 为迷宫出口	bSearch = FALSE;	if 栈为空 // 没有出口,	bSearch = FALSE;
从这个算法我们就可以利用 SDK 来实现这个迷宫, 但是有几个问题必须要注意的,第一个, 在纯 C/C++开发中(不调用API) 是,我们的循环是使用 while( 1 ) { ...... } 来实现的,但是在 Windows 编程之 中,每个 Windows 程序是消息驱动的( Event driven ), 它本身就是无限循环的,这样一来, 你要改变一 下你的想法, 我们不使用 while( 1 ){ .... } 来实现循环, 要用消息来实现循环, 这个消息是 Windows 程序自已发出的, 我们不用添加自定义的消息. ::SetTimer( .... ); 可以每隔固定时间发出一个 WM_TIMER 的消息, 这样我们就可以利用这个消息来实现循环, 因为这每隔固定时间就有一个消息, 所以我们可以利用这个消息控制小球的速度. 利用一个 flag 来判断循环是否可以结束, 而不使用 break.
case WM_TIMER:	if ( bStart )	Start();	if ( bSearch )	Search();	// bSearch 循环结束标志. 找到出口或栈为空, bSearch = FALSE.	return 0;
其次第二个注意的问题, 在 SDK 中, 使用的数据都是 static 或 global 的, 所以对全局数据的操作地方(读写操作)最好能够在一个函数内完成, 避免过多的使用修改函数而使变量条理不清, 在源代码中你可以看 到, 在 Search() 中, 只对全局变量 ptrFirst, ptrLast, gnRow, gnColumn 操作, 其它函数不负责数据的 操作.

第三个问题, 资源分配释放的问题, 对于占用的资源, 在接到 WM_DESTROY 消息进行内存释放.

剩下的,就只需要学习贴图的技巧就行了, 这些比较简单, 只要看看源代码就可以明白的了, 我只是在这儿 说明怎样造成小球的运动效果, 小球一旦移动时, 把它的移动前位置屏蔽掉, 就这样地重复过程就可以造成 运动效果.

附带的源代码中有两个贴图的小程序,写得尽量简单,对刚学