黃艾璇 王 亮

(1.華中師范大學第一附屬中學 武漢 430223)(2.華中光電技術(shù)研究所 武漢 430223)

優(yōu)化A算法搜索連連看圖塊配對和消除次序

黃艾璇1王 亮2

(1.華中師范大學第一附屬中學 武漢 430223)(2.華中光電技術(shù)研究所 武漢 430223)

針對連連看游戲這種具有小循環(huán)特性的動態(tài)不確定路徑搜索問題,論文根據(jù)游戲特點,通過對幾種搜索算法分析比較,設(shè)計并實現(xiàn)了一種優(yōu)化的A算法,對連連看圖塊配對和圖塊對消除次序進行搜索。實驗證明論文算法是一種高效實用的動態(tài)搜索方法,有效減少了因圖塊組對不合適或圖塊對消除次序不合適造成的死鎖。

動態(tài)不確定; 廣義搜索; 深度搜索; A算法; 圖塊對

Class Number TP18

1 引言

搜索技術(shù)是人工智能應用于游戲中的最基本的問題之一,是人工智能一個重要的研究內(nèi)容。

游戲連連看是在許多帶有圖案的小方塊中找出相同的圖塊,如果兩個相同圖塊可以用三根以內(nèi)的直線相連,則可以將兩圖塊消除,一定時間內(nèi)將所有圖塊消完即過關(guān)進入下一個難度關(guān)卡。

以圖塊配對作為結(jié)點,連連看游戲?qū)儆谝环N具有小循環(huán)特性的動態(tài)不確定路徑搜索問題,動態(tài)和小循環(huán)的特點,造成搜索計算量巨大且很容易陷入死循環(huán),此類尋路問題難度較大。當前將搜索算法應用于連連看的只有尋找兩相同圖塊之間連通路徑[1～2]。

由于連連看一個關(guān)卡中相同圖案的圖塊不只有兩個,因此相同圖塊組對是有多個選擇的;有的關(guān)卡中,各個圖塊位置也不是固定的,會朝某一個方向移動,填補已消除圖塊的空位,因此圖塊的消除順序也不是隨意的。如果圖塊組對不合適或圖塊消除順序不對,經(jīng)常發(fā)生可消的圖塊對越來越難找,甚至出現(xiàn)圖塊未完全消完已找不到可以消除的圖塊對了,需要圖塊重新排序。

連連看游戲消除步數(shù)固定,圖塊對與圖塊對之間沒有空間的關(guān)聯(lián)性,不存在尋找最短路徑問題;圖塊連通性相對簡單,采用盲目搜索算法(廣度優(yōu)先、深度優(yōu)先)或啟發(fā)式搜索(A*算法)此類單步搜索算法計算量大、速度慢,無太大必要[3];而通過搜索算法找到較優(yōu)的圖塊配對和較優(yōu)的圖塊對消除順序,可達到減小死鎖的目的。

2 問題分析及算法選擇

人工智能中比較成熟的有盲目搜索算法和啟發(fā)式搜索算法,盲目搜索算法主要有廣度優(yōu)先算法和深度優(yōu)先算法,啟發(fā)式搜索算法用得較多的是A算法和A*算法[4]。

圖1 廣義搜索樹

廣義優(yōu)先算法(BFS),從根結(jié)點出發(fā),接著遍歷根結(jié)點的所有子結(jié)點,再遍歷子結(jié)點的所有子結(jié)點,以此類推,一層一層向下尋找,直至找到終點。廣義優(yōu)先算法是完備的,總能找到最優(yōu)路徑,但搜索算法時間和空間復雜度較高。

圖2 深度搜索樹

深度優(yōu)先算法(DFS),從根結(jié)點出發(fā),沿著一條路并一直走下去,直到遇到障礙或者沒有達到目標點,于是返回上一層換一條路重新走,直至找到終點。深度優(yōu)先算法一般比廣義優(yōu)先算法耗時短,但深度搜索不完備,可能搜到錯誤路上,陷入死循環(huán)或找到的不是最優(yōu)答案[5～6]。

啟發(fā)式搜索A和A*算法均是深度優(yōu)先算法的改進,A算法定義一個評價函數(shù)F,對當前的搜索狀態(tài)進行評估,找出最有希望的結(jié)點為擴展,A算法中評價函數(shù)設(shè)計是重點。

A*算法把到達當前結(jié)點的消耗代價和從該結(jié)點到目標點的預估消耗結(jié)合起來對結(jié)點進行評價

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

(1)

F(n)是節(jié)點n的估價函數(shù),g(n)為從起始點到結(jié)點n的路徑消耗,一般取結(jié)點在狀態(tài)樹中的深度;h(n)為從結(jié)點n到目標點的最低消耗估計,通常取結(jié)點n到終點的曼哈頓距離。[7～8]

連連看從開始到過關(guān)一般有很多條路可以走,只需選一條即可。連連看結(jié)點是動態(tài)的,每個結(jié)點在多個不同的層上都可能出現(xiàn),結(jié)點數(shù)量幾乎是無限的,全遍歷的廣義搜索是不可能完成的任務。由于連連看結(jié)點深度有限,有利于基于深度優(yōu)先的搜索方式,但同樣由于結(jié)點是動態(tài)的,且具有小循環(huán)特性,當一條路徑無結(jié)果,回溯時,很容易進入死循環(huán)中。針對這種動態(tài)多目標路徑搜索[9～11]需要通過引入一些評估因子找到一條不易進入死循環(huán)的較優(yōu)路徑。

游戲者在玩連連看時會遵守一些基本的技巧,如多個連通區(qū)間之間的障礙塊要先消除,如圖3中B型圖塊,右邊兩個組合消除較好;只此一對的孤對圖塊先消除,如圖3中A型圖塊,只此兩個,先消;外圍圖塊消除對別的圖塊移動動態(tài)影響小的可先消除等。將游戲技巧構(gòu)建評價函數(shù)F,可實現(xiàn)啟發(fā)式搜索,減少回溯,增加搜索速度。針對圖塊配對和圖塊消除順序,選擇A算法進行搜索比較合適,其中F估值是算法關(guān)鍵。

圖3 游戲技巧示意

3 A算法設(shè)計和實現(xiàn)

連連看消除順序排列計算程序由以下幾個部分組成:

1) 獲取連連看圖片

本文選擇寵物連連看3.1無敵版,采用截屏方法直接從屏幕上copy正在運行連連看圖片。此版本連連看背景較單一,圖塊之間用一個像素黑線分隔,方便對圖塊進行分割和讀取。

2) 將連連看圖片按連連看網(wǎng)格分割成一個個獨立圖塊

分別在水平和垂直方向統(tǒng)計連連看圖像每行和每列像素灰度之和。設(shè)置一個閾值,小于此閾值即為塊與塊之間的邊界。

3) 遍歷所有圖塊,找出相同的圖塊

兩圖塊對應像素灰度相減,相同圖塊由于像素灰度相同,相減后基本為黑色,如圖5所示。根據(jù)相減后圖像中所有像素剩余灰度之和判斷是否相同圖塊。

圖4 連連看圖片獲取及圖塊分割

圖5 尋找相同圖塊

4) 相同圖塊連通性計算

對A、B兩塊按先橫后縱兩個方向進行掃描。以橫向掃描為例,找到A和B左右空格范圍(包括A、B自身),找出兩者空格公共范圍,在公共范圍內(nèi)檢查是否有一條豎線空格可以將兩者連接,如能連說明此兩塊是連通的,否則再在縱方向?qū)、B進行掃描,如圖6所示[3]。

圖6 兩圖塊連通性判斷

5) 結(jié)點配對塊估值

對結(jié)點配對塊估值是A算法的關(guān)鍵。

連連看游戲當前層一般有多個可消除的圖塊對,要關(guān)注的是先消誰后消誰及消除順序?qū)_到最終成功通關(guān)的影響。常用A或A*算法中選擇的結(jié)點在狀態(tài)樹中的深度或此結(jié)點到終點的曼哈頓距離作為估值對消塊次序無效。

根據(jù)連連看游戲技巧,假定A、B兩圖塊可連通,設(shè)計估值函數(shù)為

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

(2)

S當前與A相同的圖塊數(shù)量。G(A)、G(B)分別為消掉圖塊A、B后整體結(jié)構(gòu)松散性度量函數(shù),其公式為

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

(3)

CH是以A為交叉點橫軸方向上未消A前最大空腔與消掉A后最大空腔之比,CV是以A為交叉點縱軸方向上未消A前最大空腔與消掉A后最大空腔之比。

6) 搜索算法實現(xiàn)

搜索算法多采用一個OPEN和一個CLOSE兩個棧表對結(jié)點進行管理,比較適合穩(wěn)態(tài)結(jié)點管理。

根據(jù)連連看圖塊對動態(tài)變化的特點,采用動態(tài)生成結(jié)點數(shù)據(jù)結(jié)構(gòu),結(jié)點之間用指針關(guān)聯(lián),建立深度搜索樹。

typedef struct CONN_CLASS{

POINT pair_A; //配對圖塊A位置

POINT pair_B; //配對圖塊B位置

double F_value; //此結(jié)點估價值

CONN_CLASS * leftson; //左子結(jié)點指針

CONN_CLASS * parent; //父結(jié)點指針

CONN_CLASS * rightbro; //右兄弟結(jié)點指針

}CONN_CLASS;

圖7 數(shù)據(jù)結(jié)構(gòu)鏈表建立深度搜索樹

圖8 A搜索算法流程

圖塊配對和圖塊消除順序A搜索算法實現(xiàn)流程如圖8所示。

A算法每進行下層一結(jié)點搜索,都要擴展當前層結(jié)點,計算它們的F值,選擇F值最小的節(jié)點向下擴展,鏈表中記錄了大量的結(jié)點,增加了存儲量和可能搜索寬度。

針對連連看的特點,可采用特別方法減小鏈表存儲空間:對于F=0的幾個結(jié)點(孤對且消除后別的圖塊位置不移動的結(jié)點)可以看成一個結(jié)點,一次消除,且此層所有右兄弟結(jié)點全部取消。對于此層的回溯直接跳到上一層。

4 算例測試

對多個連連看圖像塊進行了動態(tài)測試,采用正常的深度搜索算法,很容易走到死循環(huán),出現(xiàn)死鎖,采用優(yōu)化的A算法對路徑進行估值,多數(shù)可一次找到較優(yōu)路徑,實現(xiàn)通關(guān)。圖9為兩幅連連看,圖塊分別向下和向上移動補充空格,采用隨機搜索或人工配對均死鎖,采用優(yōu)化A算法搜索,均一次找到通關(guān)的較優(yōu)路徑,見右表。

5 結(jié)語

本文仿照游戲技巧設(shè)計了A算法對連連看圖塊配對和圖塊對消除順序進行搜索;針對連連看特點,改進A算法減小鏈表存儲空間,減小了算法的計算量;搜索算法減小了圖塊組對不合適或圖塊消除順序不合適而死鎖的情況。

[1] 胡正紅.一種尋路算法在游戲中的應用[J].山西電子技術(shù),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*算法在游戲?qū)ぢ分械膽肹J].山西電子技術(shù),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] 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學出版社,1997. YAN Weiming. Data Structure[M]. Beijing: Tsinghua University Press,1997.

[6] 關(guān)麗霞.廣度優(yōu)先尋路算法在手機游戲?qū)ぢ分械膽肹J].清遠職業(yè)技術(shù)學院學報,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] 鄢靖豐,陶少華,夏方玉.基于單元樹結(jié)構(gòu)的廣度優(yōu)先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] 胡榮,未召弟,符楊.基于深度優(yōu)先遍歷算法的配電網(wǎng)拓撲動態(tài)檢測[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] 魏唯,歐陽丹彤,呂帥,等.動態(tài)不確定環(huán)境下多目標路徑規(guī)劃方法[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] 魏唯,歐陽丹彤,呂帥,等.結(jié)合增量與啟發(fā)式搜索的多目標問題處理方法[J].計算機研究與發(fā)展,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