连连看游戏开发实践(1) - 算法
benegg
从本篇文章开始, 我将写一序列游戏开发的文章, 讲述做一个连连看游戏的例子, 既锻炼自己, 也帮助别人. 最终, 游戏会加上网络功能.
**连连看算法
如图, 为了找出A, B两点之间的连接路径, 首先过这两点作4条线段, 线段的两端便是地图边缘, 两条与横坐标轴平行, 另两条与纵坐标轴平
行. 先考虑与横坐标轴平行的两条.
在两条线段上各取一点C和D, 此两点处在一条与纵坐标轴平行的直线上. 那么, ACDB这条路径便是一条可能的A, B两点的连通路径.
C, D两点在两条线段上移动, 直到找出一条有效的连通路径, 或者最终得出结论不存在这样的路径.
按同样的方式在与纵坐标轴平行的两条线段上查找.
**算法优化
两点的连通路径应该是最短的, 所以, 查找从A, B所处的矩形的中线开始, 同时从上下左右4个方面查找, 可以找到看起来最短的连通路径.
**连连看算法的编程语言实现
程序创建一个方形的格子地图, 并随机在格子上生成障碍. 用户输入想要连接的A, B两点, 然后系统输出两点的连通线(A, C, D, B).
算法作如下几个判断:
* A, B不是同一点.
* A, B两点的图形相同.
* AC, CD, DB 3条线段连通, 检查时不包括线段端点.
* 如果C, D不是与A, B重合, C, D必须无障碍.
判断停止条件:
* C, D任意一点到达屏幕边界.
程序执行效果图:
0 1 2 3 4
+---------------+
0 | 1 1 3 2 | 0
1 | 3 1 1 | 1
2 | 3 3 | 2
3 | 3 1 | 3
4 | 1 1 | 4
+---------------+
0 1 2 3 4
input point(x1,y1 x2,y2): 3,0 0,3
path: (3,0) - (3,2) - (0,2) - (0,3)
0 1 2 3 4
+---------------+
0 | 1 1 * @ 2 | 0
1 | 3 * 1 1 | 1
2 | 3 * 3 | 2
3 | @ * * 1 | 3
4 | 1 1 | 4
+---------------+
0 1 2 3 4
本篇文章介绍了一个命令行下的连连看游戏程序, 下一篇文章将给连连看做一个图形外壳, 用鼠标来选择两点.
示例源码下载: 命令行下的连连看游戏源码, 包含Windows下的可执行程序.