原创 扫雷游戏的启示

微软操作系统带的扫雷游戏很经典,以前没玩过,看别人玩过,最近在网上找了些扫雷的资料就尝试着玩了玩,发现很好玩的,里面还孕育着一些尚未解决的难题,我根据自己的理解从三方面谈谈对这个游戏的编写和突破.

一.生成地图分布图

根据随机数生成地雷分布地图,就是没有显示的被覆盖的信息,以ditu[64][64]个点举例的话,先根据需要的地雷数随机生成地雷对应的横纵坐标.

for(i=0;i<地雷总数;i++)

{

横坐标=f(随机函数)纵坐标=f(随机函数)

if判断,如果此处是雷,从新生成地雷坐标

}

地图生成后,还需要表示出无地雷处的点的周围的地雷数,这个采用嵌套循环即可.

for(i=0;i<64;i++)

for(j=0;j<64;j++)

{

此点的上下左右四面八方是否有雷,用一个计数器记录此点周围存在的雷数

循环完毕后把计数器赋予此点的坐标,此点有雷可以用一个特定的数字表示.

用0表示无雷,1表示一个雷依次类推.

循环时注意边界上的点不用检测到四面八方.

}

经过上面的步骤,就可以得到tidu[][]的信息,每个点有不同的值,不同的值赋予不同的含义.

二.游戏的操作部分编写

首先呈现的是一个完全覆盖的游戏图,这个过程主要是检测按键,根据不同的按键进行不同的操作.单片机时可以用4个键检测光标的移动,用于模拟鼠标移动,当移动到某个点上,此点闪烁或者其他方式区别于其他点.然后主要是用2个按键用于游戏的进行,不仿称其为左键右键.

总的循环过程如下:

检测左键按下:

如果此点有雷,游戏结束

如果此点无雷但周围有雷,将此点信息周围分布的雷数显示出来

如果此点无雷并且周围无雷,需要将与此点相连的无雷的点都显示出来,可以从地图数组信息上向上下左右方向分别检测它们的值是否有雷,如果有雷显示并且终止这个方向的循环,再检测到的无雷点上都要进行这样的循环.

检测被挖出的点的数量,也就是无雷点的个数,如果等于总数减去雷数的时候,游戏通过.

检测右键按下:

用一个状态值记录是第几次按下,第一次按下表示此处有雷(小红旗图标),第二次按下表示此处可疑(问号图标),第三次按下表示恢复原状.

一个点的状态如下:隐蔽(游戏初试画面),显示(显示此周围的雷数)肯定有雷(此点有雷,游戏结束)可能有雷(小红旗)此处有疑问(问号).游戏初试为满屏幕的隐蔽画面.

点错游戏结束后显示肯定有雷,并且显示所有雷的分布并显示.点对则进行显示,显示周围的雷数,并进行游戏成功的检测.右键主要其标记作用,用于刷新显示,配合工兵扫雷.

二.机器人扫雷

前2个方面站在作者上简要地讨论游戏的编写,最后这个问题是站在读者的角度上如何通过算法实现对游戏的快速排雷.这个问题可以追索到一个深刻的计算机问题,NP-Complete,在网上可以查到很多的资料,有兴趣的可以看看.在此我简单地引用一个例子介绍下.

NP 是 Non-deterministic Polynomial 的缩写,  NP 问题通俗来说是其解的正确性能够被很容易检查的问题, 这里"很容易检查"指的是存在一个多项式检查算法.

例如, 著名的推销员旅行问题(Travel Saleman Problem or TSP):  假设一个推销员需要从香港出发, 经过广州, 北京, 上海,  ....., 等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达， 但票价不等。现在假设公司只给报销 $C 块钱, 问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 $C ?

推销员旅行问题显然是 NP 的. 因为如果你任意给出一个行程安排, 可以很容易算出旅行总开销. 但是, 要想知道一条总路费小于 $C 的行程是否存在, 在最坏情况下, 必须检查所有可能的旅行安排! 这将是个天文数字.

NP-complete 问题是所有 NP 问题中最难的问题. 它的定义是, 如果你可以找到一个解决某个 NP-complete 问题的多项式算法, 那么所有的 NP 问题都将可以很容易地解决. 搞学术的朋友可以详细了解下NP-complete ,感觉跟离散数学,概率,逻辑门这些东西有蛮大关系的.

我附件里面是自己下的一点点关于扫雷和NP-complete 的资料,有需要的可以下来看看,的确很小的游戏有时候蕴涵着很深的问题.

https://static.assets-stash.eet-china.com/album/old-resources/2008/9/23/115a807b-adfc-4a67-8951-b3c8d3f89714.rar