连连看游戏设计.pdf

写书评，赢取《编程之美--微软技术面试心得》/BCZM.asp 连连看游戏设计 连连看是一种很受大家欢迎的小游戏。微软亚洲研究院的实习生 们就曾经开发过一个类似的游戏——Microsoft Link-up。 图1-17 连连看游戏示意图 图 1-17 为 Microsoft Link-up 的一个截图。如果用户可以把两 个同样的图用线（连线拐的弯不能多于两个）连到一起，那么这两个 头像就会消掉，当所有的头像全部消掉的时候，游戏成功结束。游戏 头像有珍稀动物、京剧脸谱等。Microsoft Link-up 还支持用户输入 的图像库，微软的同事们曾经把新员工的漫画头像加到这个游戏中， 让大家在游戏之余也互相熟悉起来。 假如让你来设计一个连连看游戏的算法，你会怎么做呢？要求说 明： 1. 怎样用简单的计算机模型来描述这个问题？ 2. 怎样判断两个图形能否相消？ 3. 怎样求出相同图形之间的最短路径（转弯数最少，路径经过的 格子数目最少）。 4. 怎样确定目前是处于死锁状态，如何设计算法来解除死锁？ 写书评，赢取《编程之美--微软技术面试心得》/BCZM.asp 分析与解法 连连看游戏的设计，最主要包含游戏局面的状态描述，以及游戏 规则的描述。而游戏规则的描述就对应着状态的合法转移（在某一个 状态，有哪些操作是满足规则的，经过这些满足规则的操作，会到达 哪些状态）。所以，自动机模型适合用来描述游戏设计。 下面是一个参考的连连看游戏的伪代码： 代码清单 1-22 生成游戏初始局面 Grid preClick = NULL, curClick = NULL; while(游戏没有结束) { 监听用户动作 if(用户点击格子(x, y)，且格子(x, y)为非空格子) { preClick = curClick; curClick.Pos = (x, y); } if(preClick != NULL curClick != NULL preClick.Pic curClick.Pic FindPath(preClick, curClick) != NULL) { 显示两个格子之间的消去路径 消去格子preClick, curClick; preClick = curClick = NULL; } } 从上面的整体框架可以看到，完成连连看游戏需要解决下面几个 问题： 1. 生成游戏初始局面。 2. 每次用户选择两个图形，如果图形满足一定条件（两个图形一 样，且这两个图形之间存在少于3个弯的路径），则两个图形都 写书评，赢取《编程之美--微软技术面试心得》/BCZM.asp 能消掉。给定具有相同图形的任意两个格子，我们需要寻找这 两个格子之间在转弯最少的情况下，经过格子数目最少的路径。 如果这个最优路径的转弯数目少于3，则这两个格子可以消去。 3. 判断游戏是否结束。如果所有图形全部消去，游戏结束。 4. 判断死锁，当游戏玩家不可能再消去任意两个图像的时候，游 戏进入“死锁”状态。如图1-18，该局面中已经不存在两个相 同的图片相连的路径转弯数目小于3的情况。 在死锁的情况下，我们也可以暂时不终止游戏，而是随机打乱局 面，打破“死锁”局面。 图1-18 连连看死锁的情况 首先思考问题：怎样判断两个图形能否相消？在前面的分析中， 我们已经知道，两个图形能够相消的充分必要条件是这两个图形相同， 且它们之间存在转弯数目小于 3 的路径。因此，需要解决的主要问题 是，怎样求出相同图形之间的最短路径。首先需要保证最短路径的转 弯数目最少。在转弯数目最少的情况下，经过的格子数目也要