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

黃艾璇 王 亮

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

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

黃艾璇1王 亮2

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

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

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

Class Number TP18

1 引言

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

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

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

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

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

2 問(wèn)題分析及算法選擇

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

圖1 廣義搜索樹(shù)

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

圖2 深度搜索樹(shù)

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

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

A*算法把到達(dá)當(dāng)前結(jié)點(diǎn)的消耗代價(jià)和從該結(jié)點(diǎn)到目標(biāo)點(diǎn)的預(yù)估消耗結(jié)合起來(lái)對(duì)結(jié)點(diǎn)進(jìn)行評(píng)價(jià)

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

(1)

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

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

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

圖3 游戲技巧示意

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

連連看消除順序排列計(jì)算程序由以下幾個(gè)部分組成:

1) 獲取連連看圖片

本文選擇寵物連連看3.1無(wú)敵版,采用截屏方法直接從屏幕上copy正在運(yùn)行連連看圖片。此版本連連看背景較單一,圖塊之間用一個(gè)像素黑線(xiàn)分隔,方便對(duì)圖塊進(jìn)行分割和讀取。

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

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

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

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

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

圖5 尋找相同圖塊

4) 相同圖塊連通性計(jì)算

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

圖6 兩圖塊連通性判斷

5) 結(jié)點(diǎn)配對(duì)塊估值

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

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

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

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

(2)

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

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

(3)

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

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

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

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

typedef struct CONN_CLASS{

POINT pair_A; //配對(duì)圖塊A位置

POINT pair_B; //配對(duì)圖塊B位置

double F_value; //此結(jié)點(diǎn)估價(jià)值

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

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

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

}CONN_CLASS;

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

圖8 A搜索算法流程

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

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

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

4 算例測(cè)試

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

5 結(jié)語(yǔ)

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

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

[6] 關(guān)麗霞.廣度優(yōu)先尋路算法在手機(jī)游戲?qū)ぢ分械膽?yīng)用[J].清遠(yuǎn)職業(yè)技術(shù)學(xué)院學(xué)報(bào),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] 鄢靖豐,陶少華,夏方玉.基于單元樹(shù)結(jié)構(gòu)的廣度優(yōu)先P2P搜索算法[J].計(jì)算機(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)拓?fù)鋭?dòng)態(tài)檢測(cè)[J].上海電力學(xué)院學(xué)報(bào),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] 周軍鋒,陳偉,費(fèi)春蘋(píng),等.BiRch:一種處理k步可達(dá)性查詢(xún)的雙向搜索算法[J].通信學(xué)報(bào),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] 魏唯,歐陽(yáng)丹彤,呂帥,等.動(dòng)態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J].計(jì)算機(jī)學(xué)報(bào),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] 魏唯,歐陽(yáng)丹彤,呂帥,等.結(jié)合增量與啟發(fā)式搜索的多目標(biāo)問(wèn)題處理方法[J].計(jì)算機(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日

黃艾璇,女，研究方向：人工智能。王亮,男,碩士研究生,工程師,研究方向:信號(hào)處理。

TP18

10.3969/j.issn.1672-9722.2017.02.023