【正文】 標(biāo)圖案，則可以直線相連接結(jié)束搜索。否則。依次從隊(duì)列集合中的空格子出發(fā)，分別找到它們的相鄰格，不在隊(duì)列中則加到隊(duì)列中。判斷目標(biāo)圖案是否在新加的格子中．如果找到則結(jié)柬搜索。依次類推，最終找到目標(biāo)圖案。在擴(kuò)展的過(guò)程中，記下每個(gè)格子來(lái)自于哪個(gè)格子，并記錄轉(zhuǎn)彎數(shù)，如果轉(zhuǎn)彎數(shù)小于等于2，則兩個(gè)相同圖案間存在路徑，否則沒(méi)有找到連通路徑。此算法的明顯特點(diǎn)是“層層推進(jìn)”，擴(kuò)展點(diǎn)會(huì)隨著探索深度急劇增加。相應(yīng)地。需要大量的空間來(lái)保存中間數(shù)據(jù)?？臻g冗余度和復(fù)雜度比較大。深度優(yōu)先搜索：把起始格staG(xl，y1)壓入棧，然后擴(kuò)展與start(x1，y1)直接相鄰的上、下、左、右四個(gè)方向的格子到棧中，判斷這些格子中是否有目標(biāo)圖案，如果有結(jié)束搜索。否則壓出最后一個(gè)格子，沿著某個(gè)方向探索通路，若遇到阻礙，判斷是否目標(biāo)圖案，如果是結(jié)束搜索．否則返回上一個(gè)格子換個(gè)方向繼續(xù)探索。直到所有的通路都走過(guò)。為保證在任何位置上都能沿原路退回，防止死循環(huán)，這種算法需要大量的堆棧來(lái)保存數(shù)據(jù)。這樣找到的路徑不一定是最短路徑．需要對(duì)找到的路徑進(jìn)行比較對(duì)比，增加了空間復(fù)雜度和時(shí)間復(fù)雜度．3本文算法3．1數(shù)據(jù)結(jié)構(gòu)描述合理的數(shù)據(jù)結(jié)構(gòu)為算法的設(shè)計(jì)和實(shí)現(xiàn)提供了有利的保障，算法易于理解和實(shí)現(xiàn)，易于編程，時(shí)問(wèn)和空間復(fù)雜度大大降低。為此，首先將每個(gè)方塊定義為一個(gè)類。public class Square{public int id； ／／每個(gè)方塊的身份號(hào)，如果兩個(gè)方塊的id一樣。則說(shuō)明兩個(gè)方塊是同樣的圖案；public Width一40} ／／方塊寬度public Height=40； ／／方塊高度public int i； ／／方塊的數(shù)組橫坐標(biāo)，對(duì)方塊的操作是通過(guò)數(shù)組進(jìn)行的；public int j； ／／方塊的數(shù)組縱坐標(biāo)public Square Target； ／／表示目標(biāo)方塊public Path=hew array()。}／／記錄連通路徑定義Target使用一個(gè)類存儲(chǔ)另一個(gè)類的引用．可以引用Target得到它的全部。使用數(shù)組Path來(lái)記錄連接路徑。利用二維數(shù)組map[Rows][Cols]表示對(duì)應(yīng)的方塊．其中．第0行和第Rows行。第0列第Cols表示方塊的外圍。Rows、Cols比實(shí)際的方塊行數(shù)、列數(shù)多2；當(dāng)數(shù)組值取l表示該位置有圖，取0表示無(wú)圖；初始化數(shù)據(jù)時(shí)，設(shè)置方塊的外圍數(shù)組值為0，其他數(shù)組值為1。其對(duì)應(yīng)的矩陣描述如圖2所示：0，0，0，0，0，0，0．0，0，00，1，1，1，1，1，1，1，1，00，1，1，1，1，1，1，1，1，00，1，1，1，1，1，1，1，1，00，1，1，1，1，1，1，1，1，00，1，1．1．1，1，1，l，1，00，l，1．1，1．1．1，1，1，00，0，0，0，0，0．0．0，0，0 圈2初始化矩陣3．2尋路規(guī)則的算法設(shè)計(jì)“連連看”游戲中尋路分為橫向?qū)ぢ泛涂v向?qū)ぢ穬煞N[1]：橫向?qū)ぢ肥菑钠瘘c(diǎn)A(xl，y1)橫向走一定的步長(zhǎng)，再豎向走到與目標(biāo)點(diǎn)相同的橫坐標(biāo))c2，接著再橫向走到目標(biāo)點(diǎn)B(x2，y2)。縱向?qū)ぢ肥菑钠瘘c(diǎn)A(x1．y1)豎向走一定步長(zhǎng)，接著橫向走到與目標(biāo)點(diǎn)B相同的縱坐標(biāo)y2，再豎向走到目標(biāo)點(diǎn)B(xZ，y2)。A，B兩點(diǎn)在一條直線上連通是橫向／縱向?qū)ぢ窌r(shí)橫向／縱向步長(zhǎng)為0的特例．第一步：起始方塊和目標(biāo)方塊是否同一方塊，如果是不同方塊id值是否一致；if(start==start．Target start．id!=start．Target．id)；第二步：存儲(chǔ)起始方塊、目標(biāo)方塊的坐標(biāo)．定義節(jié)點(diǎn)對(duì)象，臨時(shí)路徑tempPath；var xl：uint 2 start．ilvar ylluint2 start．jlvar x2：uint=start．Target．i；var y2luint=start．Target．j；var node：0bjeet=new 0bject()； ／／定義節(jié)點(diǎn)對(duì)象var tempPath：Array=new Array()； ／／定義臨時(shí)路徑第三步：取橫向?qū)ぢ返牟介L(zhǎng)變量i=0；第四步：初始counts=0。將臨時(shí)路徑數(shù)組tempPath清空。循環(huán)掃描橫向?qū)ぢ罚徊⒂涗浾系K數(shù)counts．記錄結(jié)點(diǎn)node，將結(jié)點(diǎn)壓入tempPath中，如果counts=l，說(shuō)明尋路成功，如果start．1ength沒(méi)有記錄過(guò)路徑則保存尋到的通路，已記錄過(guò)連接路徑將其與剛搜索的臨時(shí)路徑比較，如不是最短路徑將tempPath存入路徑數(shù)組start．1ength。返回真值。第五步；i+1；第六步：如果iCols轉(zhuǎn)第四步，否則轉(zhuǎn)下一步。第七步：橫向?qū)ぢ费h(huán)結(jié)束，進(jìn)行縱向?qū)ぢ?，過(guò)程同第三步——第六步。第八步：如果尋路不成功，返回假值3．3算法的程序?qū)崿F(xiàn)應(yīng)用ActionScript3進(jìn)行了編程設(shè)計(jì)，程序代碼簡(jiǎn)單容易改for(var i：uint—O；iCols；i++){ ／／橫向?qū)ぢ穠at counts：uint=o； ／／路徑中的障礙數(shù)tempPath．splice(0)f ／／清空數(shù)組var step：int=(yli)?一l：1；／／設(shè)置步長(zhǎng)的間隔for(var j=yl，j!=i；j+=step){counts+=map[x1][j], ／／計(jì)算路徑中的障礙數(shù)node={x：xl，Y：j)； ／／記錄節(jié)點(diǎn)tempPath．push(node)I／／node節(jié)點(diǎn)壓人數(shù)組的末尾(入棧)}step=(xlx2)?1 ：l；for(j=xl；j!=x2；j+=step){counts+=map[j][i]；node={x：j，y：i}；tempPath．push(node)}／／node節(jié)點(diǎn)壓人數(shù)組的末尾}step=(iy2)?l：一l；for(j—i，j!=y2；j+=step){counts+=mapEx2][j]；node一{x：x2，y：j}；tempPath．push(node)； ／／節(jié)點(diǎn)壓入數(shù)組的末尾}if(counts==1){if(start．Path．1ength一=0||tempPath．1engthstart．Path．1ength){start．Path=tempPath．slice()；}／／復(fù)制數(shù)組tempPath到start．Path4算法比較本尋路算法主要是運(yùn)用循環(huán)依次計(jì)算通路，主要的開銷在通路障礙數(shù)的計(jì)算上。算法主要過(guò)程是逐條累加計(jì)算每條通路中的障礙數(shù)，路徑長(zhǎng)度是臨時(shí)路徑數(shù)組的長(zhǎng)度。時(shí)間復(fù)雜度為o(m*n)，空間方面主要需要一個(gè)方塊類定義方塊，一個(gè)節(jié)點(diǎn)對(duì)象記錄節(jié)點(diǎn)，一個(gè)數(shù)組記錄臨時(shí)路徑，空間復(fù)雜度為o(m+n)。雖然計(jì)算的節(jié)點(diǎn)多，但是相對(duì)廣度搜索和深度搜索．本算法方法簡(jiǎn)單，計(jì)算各個(gè)節(jié)點(diǎn)是最快的．不需要頻繁調(diào)用函數(shù)分配大量的數(shù)據(jù)空問(wèn)。使用相對(duì)廣度搜索和深度搜索需要使用遞歸方法解決．要走的路很多幾乎遍歷節(jié)點(diǎn)，并且有些路還會(huì)相交．相交的時(shí)候，還得檢查哪根線的折點(diǎn)少。并且還有不少的路是根本不可能行得通的。會(huì)導(dǎo)致遞歸級(jí)數(shù)很高。用經(jīng)典算法編程序時(shí)．牽涉到回溯、遞歸等較復(fù)雜的算法，代碼繁瑣容易出錯(cuò)。尤其牽涉到復(fù)雜數(shù)據(jù)結(jié)構(gòu)棧(深度優(yōu)先搜索)、隊(duì)列(廣度優(yōu)先搜索)的操作，調(diào)試跟蹤比較麻煩。而用本算法進(jìn)行編程時(shí)．只用到數(shù)組這個(gè)簡(jiǎn)單形象的數(shù)據(jù)結(jié)構(gòu)，算法也簡(jiǎn)單，相應(yīng)的編程代碼也簡(jiǎn)短高效。5結(jié)束語(yǔ)本論文主要提出了一種解決連連看尋路問(wèn)題的算法．并應(yīng)用ActionScript3進(jìn)行了編程設(shè)計(jì)，程序代碼簡(jiǎn)單容易改編，可以應(yīng)用在游戲設(shè)計(jì)繞過(guò)障礙的路徑搜索。附錄BApplication of a Pathfinding Method in Game Development1 Problem description and analysisGame Lianliankan associated with the name implies is to find things. Its interface with the pattern of many small rectangular blocks. These small boxes arranged in a big long rectangular solid rectangular block or blocks of empty thread. Lianliankangame tests the player39。s eye. Rule is: In the limited time, the same pattern with three less than two cards together on the line can be eliminated, as long as the plete elimination of all patterns can all win. The socalled able to connect, that is: either horizontal or vertical. The same pattern from the connection between the two can not be more than two bends, where the connection can not be eliminated from the pattern has not yet been on. Analyze the connection, we can see, generally in three situations: a straight line connected。 there is a break point of connection。 connection with two break points:Lianliankan game design is how to use simple puter model to describe the same problem, design rules to determine whether the elimination of two of the same pattern, to identify and show the two patterns with the best path. focusing on the design pathfinding algorithm.2 classical algorithmLianliankan technical difficulties of the game is the path between the same twophase search pattern. Classical algorithm is breadthfirst search and depth first search.Breadthfirst search: first to the starting grid start (xl, y1) pressure on people queue. Then extended with the start (xl, y1) directly adjacent to the up, down, left, and right directions of the grid to the queue. If these goals in the extended grid pattern, you can straight line connecting the end of the search. Otherwise. Followed by a space from the queue in the subset of starting, respectively, of adjacent cells to find them, not the queue is added to the queue. Target pattern to determine whether the newly added grid. If you find the end Cambodia search. And so on, and ultimately find the target pattern. In the expansion process, the record from which each lattice grid, and record the number of turns, if turning is less than or equal to 2, the same pattern exists between the two paths, or do not find the path connectivity. Distinctive features of this algorithm is advancing layers extension point will be explored with the depth increased dramatically. Accordingly. Requires a lot of space to hold intermediate data. Redundancy and plexity of space is relatively large.Depthfirst search: the starting grid staG (xl, y1) onto the stack, and then extended with the start (x1, y1) directly adjacent to the up, down, left, and right directions of the grid to the stack to determine the grid Are there patterns in the target, if