优化A算法搜索连连看图块配对和消除次序

黄艾璇 王 亮

(1.华中师范大学第一附属中学 武汉 430223)(2.华中光电技术研究所 武汉 430223)

优化A算法搜索连连看图块配对和消除次序

黄艾璇1王 亮2

(1.华中师范大学第一附属中学 武汉 430223)(2.华中光电技术研究所 武汉 430223)

针对连连看游戏这种具有小循环特性的动态不确定路径搜索问题,论文根据游戏特点,通过对几种搜索算法分析比较,设计并实现了一种优化的A算法,对连连看图块配对和图块对消除次序进行搜索。实验证明论文算法是一种高效实用的动态搜索方法,有效减少了因图块组对不合适或图块对消除次序不合适造成的死锁。

动态不确定; 广义搜索; 深度搜索; A算法; 图块对

Class Number TP18

1 引言

搜索技术是人工智能应用于游戏中的最基本的问题之一,是人工智能一个重要的研究内容。

游戏连连看是在许多带有图案的小方块中找出相同的图块,如果两个相同图块可以用三根以内的直线相连,则可以将两图块消除,一定时间内将所有图块消完即过关进入下一个难度关卡。

以图块配对作为结点,连连看游戏属于一种具有小循环特性的动态不确定路径搜索问题,动态和小循环的特点,造成搜索计算量巨大且很容易陷入死循环,此类寻路问题难度较大。当前将搜索算法应用于连连看的只有寻找两相同图块之间连通路径[1～2]。

由于连连看一个关卡中相同图案的图块不只有两个,因此相同图块组对是有多个选择的;有的关卡中,各个图块位置也不是固定的,会朝某一个方向移动,填补已消除图块的空位,因此图块的消除顺序也不是随意的。如果图块组对不合适或图块消除顺序不对,经常发生可消的图块对越来越难找,甚至出现图块未完全消完已找不到可以消除的图块对了,需要图块重新排序。

连连看游戏消除步数固定,图块对与图块对之间没有空间的关联性,不存在寻找最短路径问题;图块连通性相对简单,采用盲目搜索算法(广度优先、深度优先)或启发式搜索(A*算法)此类单步搜索算法计算量大、速度慢,无太大必要[3];而通过搜索算法找到较优的图块配对和较优的图块对消除顺序,可达到减小死锁的目的。

2 问题分析及算法选择

人工智能中比较成熟的有盲目搜索算法和启发式搜索算法,盲目搜索算法主要有广度优先算法和深度优先算法,启发式搜索算法用得较多的是A算法和A*算法[4]。

图1 广义搜索树

广义优先算法(BFS),从根结点出发,接着遍历根结点的所有子结点,再遍历子结点的所有子结点,以此类推,一层一层向下寻找,直至找到终点。广义优先算法是完备的,总能找到最优路径,但搜索算法时间和空间复杂度较高。

图2 深度搜索树

深度优先算法(DFS),从根结点出发,沿着一条路并一直走下去,直到遇到障碍或者没有达到目标点,于是返回上一层换一条路重新走,直至找到终点。深度优先算法一般比广义优先算法耗时短,但深度搜索不完备,可能搜到错误路上,陷入死循环或找到的不是最优答案[5～6]。

启发式搜索A和A*算法均是深度优先算法的改进,A算法定义一个评价函数F,对当前的搜索状态进行评估,找出最有希望的结点为扩展,A算法中评价函数设计是重点。

A*算法把到达当前结点的消耗代价和从该结点到目标点的预估消耗结合起来对结点进行评价

F(n)=g(n)+h(n)

(1)

F(n)是节点n的估价函数,g(n)为从起始点到结点n的路径消耗,一般取结点在状态树中的深度;h(n)为从结点n到目标点的最低消耗估计,通常取结点n到终点的曼哈顿距离。[7～8]

连连看从开始到过关一般有很多条路可以走,只需选一条即可。连连看结点是动态的,每个结点在多个不同的层上都可能出现,结点数量几乎是无限的,全遍历的广义搜索是不可能完成的任务。由于连连看结点深度有限,有利于基于深度优先的搜索方式,但同样由于结点是动态的,且具有小循环特性,当一条路径无结果,回溯时,很容易进入死循环中。针对这种动态多目标路径搜索[9～11]需要通过引入一些评估因子找到一条不易进入死循环的较优路径。

游戏者在玩连连看时会遵守一些基本的技巧,如多个连通区间之间的障碍块要先消除,如图3中B型图块,右边两个组合消除较好;只此一对的孤对图块先消除,如图3中A型图块,只此两个,先消;外围图块消除对别的图块移动动态影响小的可先消除等。将游戏技巧构建评价函数F,可实现启发式搜索,减少回溯,增加搜索速度。针对图块配对和图块消除顺序,选择A算法进行搜索比较合适,其中F估值是算法关键。

图3 游戏技巧示意

3 A算法设计和实现

连连看消除顺序排列计算程序由以下几个部分组成:

1) 获取连连看图片

本文选择宠物连连看3.1无敌版,采用截屏方法直接从屏幕上copy正在运行连连看图片。此版本连连看背景较单一,图块之间用一个像素黑线分隔,方便对图块进行分割和读取。

2) 将连连看图片按连连看网格分割成一个个独立图块

分别在水平和垂直方向统计连连看图像每行和每列像素灰度之和。设置一个阈值,小于此阈值即为块与块之间的边界。

3) 遍历所有图块,找出相同的图块

两图块对应像素灰度相减,相同图块由于像素灰度相同,相减后基本为黑色,如图5所示。根据相减后图像中所有像素剩余灰度之和判断是否相同图块。

图4 连连看图片获取及图块分割

图5 寻找相同图块

4) 相同图块连通性计算

对A、B两块按先横后纵两个方向进行扫描。以横向扫描为例,找到A和B左右空格范围(包括A、B自身),找出两者空格公共范围,在公共范围内检查是否有一条竖线空格可以将两者连接,如能连说明此两块是连通的,否则再在纵方向对A、B进行扫描,如图6所示[3]。

图6 两图块连通性判断

5) 结点配对块估值

对结点配对块估值是A算法的关键。

连连看游戏当前层一般有多个可消除的图块对,要关注的是先消谁后消谁及消除顺序对达到最终成功通关的影响。常用A或A*算法中选择的结点在状态树中的深度或此结点到终点的曼哈顿距离作为估值对消块次序无效。

根据连连看游戏技巧,假定A、B两图块可连通,设计估值函数为

F(A,B)=(S/2-1)+G(A)+G(B)

(2)

S当前与A相同的图块数量。G(A)、G(B)分别为消掉图块A、B后整体结构松散性度量函数,其公式为

G(A)=1-CH+1-CV

(3)

CH是以A为交叉点横轴方向上未消A前最大空腔与消掉A后最大空腔之比,CV是以A为交叉点纵轴方向上未消A前最大空腔与消掉A后最大空腔之比。

6) 搜索算法实现

搜索算法多采用一个OPEN和一个CLOSE两个栈表对结点进行管理,比较适合稳态结点管理。

根据连连看图块对动态变化的特点,采用动态生成结点数据结构,结点之间用指针关联,建立深度搜索树。

typedef struct CONN_CLASS{

POINT pair_A; //配对图块A位置

POINT pair_B; //配对图块B位置

double F_value; //此结点估价值

CONN_CLASS * leftson; //左子结点指针

CONN_CLASS * parent; //父结点指针

CONN_CLASS * rightbro; //右兄弟结点指针

}CONN_CLASS;

图7 数据结构链表建立深度搜索树

图8 A搜索算法流程

图块配对和图块消除顺序A搜索算法实现流程如图8所示。

A算法每进行下层一结点搜索,都要扩展当前层结点,计算它们的F值,选择F值最小的节点向下扩展,链表中记录了大量的结点,增加了存储量和可能搜索宽度。

针对连连看的特点,可采用特别方法减小链表存储空间:对于F=0的几个结点(孤对且消除后别的图块位置不移动的结点)可以看成一个结点,一次消除,且此层所有右兄弟结点全部取消。对于此层的回溯直接跳到上一层。

4 算例测试

对多个连连看图像块进行了动态测试,采用正常的深度搜索算法,很容易走到死循环,出现死锁,采用优化的A算法对路径进行估值,多数可一次找到较优路径,实现通关。图9为两幅连连看,图块分别向下和向上移动补充空格,采用随机搜索或人工配对均死锁,采用优化A算法搜索,均一次找到通关的较优路径,见右表。

5 结语

本文仿照游戏技巧设计了A算法对连连看图块配对和图块对消除顺序进行搜索;针对连连看特点,改进A算法减小链表存储空间,减小了算法的计算量;搜索算法减小了图块组对不合适或图块消除顺序不合适而死锁的情况。

[1] 胡正红.一种寻路算法在游戏中的应用[J].山西电子技术,2009(6):53-54. HU Zhenghong. Application of a Path-finding Method in Game Development[J]. Shanxi Electronic Technology,2009(6):53-54.

[2] 胡正红,张俊花.A*算法在游戏寻路中的应用[J].山西电子技术,2012(1):55-57. HU Zhenghong, ZHANG Junhua. Application of A* Algorithm in Game Path-finding Development[J]. Shanxi Electronic Technology,2012(1):55-57.

[3] icekiller.连连看核心算法详解[EB/OL].http://bbs.9ria.com/thread-63206-1-1.html. icekiller. explain in detail about the kernel algorithms of LianLinakan[EB/OL]. http://bbs.9ria.com/thread-63206-1-1.html.

[4] 人工智能算法综述[EB/OL].http://www.docin.com/p-70067975.html. The Summary of artificial intelligence[EB/OL]. http://www.docin.com/p-70067975.html.

[5] 严蔚敏.数据结构[M].北京:清华大学出版社,1997. YAN Weiming. Data Structure[M]. Beijing: Tsinghua University Press,1997.

[6] 关丽霞.广度优先寻路算法在手机游戏寻路中的应用[J].清远职业技术学院学报,2012(12):57-60. GUAN Lixia. The Application of Breadth-first Search Algorithm in Mobile Game Path-finding Development[J]. Journal of Qingyuan Polytechnic,2012(12):57-60.

[7] 鄢靖丰,陶少华,夏方玉.基于单元树结构的广度优先P2P搜索算法[J].计算机工程,2011(9):135-137. YAN Jingfeng, TAO Shaohua, XIA Fangyu. Breadth First P2P Search Algorithm Based on Unit Tree Structure[J]. Computer Engineering,2011(9):135-137.

[8] 胡荣,未召弟,符杨.基于深度优先遍历算法的配电网拓扑动态检测[J].上海电力学院学报,2010(4):109-118. HU Rong, WEI Zhaodi, FU Yang. Distribution Network Topology Dynamic Detection Based on Depth first Search Algorithm[J]. Journal of Shanghai University of Electric Power,2010(4):109-118.

[9] 周军锋,陈伟,费春苹,等.BiRch:一种处理k步可达性查询的双向搜索算法[J].通信学报,2015(8):50-60. ZHOU Junfeng, CHEN Wei, FEI Chunping, et al. BiRch: a bidirectional search algorithm for k-step reachability queries[J]. Journal on Communications,2015(8):50-60.

[10] 魏唯,欧阳丹彤,吕帅,等.动态不确定环境下多目标路径规划方法[J].计算机学报,2011(5):837-846. WEI Wei, OUYANG Dantong, LV Shuai, et al. Multiobjective Path Planning under Dynamic Uncertain Environment[J]. Chinese Journal of Computers,2011(5):837-846.

[11] 魏唯,欧阳丹彤,吕帅,等.结合增量与启发式搜索的多目标问题处理方法[J].计算机研究与发展,2010(11):1954-1961. WEI Wei, OUYANG Dantong, LV Shuai, et al. An Approach Combining Incremental Search and Heuristic Search for Solving Multiobjective Problems[J]. Journal of Computer Research and Development,2010(11):1954-1961.

Optimization of A Algorithm for the Search of the LianLinakan Picture Patch Matching and the Elimination Order

HUANG Aixuan1WANG Liang2

(1. High School Affiliated to Central China Normal University, Wuhan 430223) (2. Huazhong Institute of Electro-Optics, Wuhan 430223)

In view of the dynamic uncertain path searching problem with small loop characteristic, according to the characteristics of the Lianliankan game, through analyzing and comparing several search algorithms, this paper designs and implements a kind of optimized A algorithm, and searches the Lianliankan picture patch matching and the picture patch couple elimination order. The experiment proves that, the proposed algorithm is a kind of high speed and accurate dynamic search algorithm, and effectively avoids the dead lock caused by the non-fitness of the picture patch couple or the picture patch elimination order.

dynamic uncertain, generalized search, depth search, A algorithm, picture patch couple

2016年8月11日,

2016年9月27日

黄艾璇,女，研究方向：人工智能。王亮,男,硕士研究生,工程师,研究方向:信号处理。

TP18

10.3969/j.issn.1672-9722.2017.02.023