2010-06-11

连连看游戏开发实践(1) – 算法

Views: 14955 | Add Comments

从本篇文章开始, 我将写一序列游戏开发的文章, 讲述做一个连连看游戏的例子, 既锻炼自己, 也帮助别人. 最终, 游戏会加上网络功能.

连连看算法

如图, 为了找出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

本篇文章介绍了一个命令行下的连连看游戏程序, 下一篇文章将给连连看做一个图形外壳, 用鼠标来选择两点.

示例源码下载: llk.zip: 命令行下的连连看游戏源码, 包含Windows下的可执行程序.

原发在: http://www.benegg.com/game/archives/34.html

Related posts:

  1. 如何让 PHP json_encode 函数不转义中文?
  2. 告诉我应该选择哪一个Linux发行版
  3. jQuery 设置复选框选中状态的 BUG
  4. PHP str_replace 函数的参数设计不合理之处
  5. 开发搜索引擎 – PHP中文分词
Posted by ideawu at 2010-06-11 17:01:13

Leave a Comment