基于java環境下的連連看游戲研究畢業論文-資料下載頁

　　

【正文】 標圖案，則可以直線相連接結束搜索。否則。依次從隊列集合中的空格子出發，分別找到它們的相鄰格，不在隊列中則加到隊列中。判斷目標圖案是否在新加的格子中．如果找到則結柬搜索。依次類推，最終找到目標圖案。在擴展的過程中，記下每個格子來自于哪個格子，并記錄轉彎數，如果轉彎數小于等于2，則兩個相同圖案間存在路徑，否則沒有找到連通路徑。此算法的明顯特點是“層層推進”，擴展點會隨著探索深度急劇增加。相應地。需要大量的空間來保存中間數據?？臻g冗余度和復雜度比較大。深度優先搜索：把起始格staG(xl，y1)壓入棧，然后擴展與start(x1，y1)直接相鄰的上、下、左、右四個方向的格子到棧中，判斷這些格子中是否有目標圖案，如果有結束搜索。否則壓出最后一個格子，沿著某個方向探索通路，若遇到阻礙，判斷是否目標圖案，如果是結束搜索．否則返回上一個格子換個方向繼續探索。直到所有的通路都走過。為保證在任何位置上都能沿原路退回，防止死循環，這種算法需要大量的堆棧來保存數據。這樣找到的路徑不一定是最短路徑．需要對找到的路徑進行比較對比，增加了空間復雜度和時間復雜度．3本文算法3．1數據結構描述合理的數據結構為算法的設計和實現提供了有利的保障，算法易于理解和實現，易于編程，時問和空間復雜度大大降低。為此，首先將每個方塊定義為一個類。public class Square{public int id； ／／每個方塊的身份號，如果兩個方塊的id一樣。則說明兩個方塊是同樣的圖案；public Width一40} ／／方塊寬度public Height=40； ／／方塊高度public int i； ／／方塊的數組橫坐標，對方塊的操作是通過數組進行的；public int j； ／／方塊的數組縱坐標public Square Target； ／／表示目標方塊public Path=hew array()。}／／記錄連通路徑定義Target使用一個類存儲另一個類的引用．可以引用Target得到它的全部。使用數組Path來記錄連接路徑。利用二維數組map[Rows][Cols]表示對應的方塊．其中．第0行和第Rows行。第0列第Cols表示方塊的外圍。Rows、Cols比實際的方塊行數、列數多2；當數組值取l表示該位置有圖，取0表示無圖；初始化數據時，設置方塊的外圍數組值為0，其他數組值為1。其對應的矩陣描述如圖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尋路規則的算法設計“連連看”游戲中尋路分為橫向尋路和縱向尋路兩種[1]：橫向尋路是從起點A(xl，y1)橫向走一定的步長，再豎向走到與目標點相同的橫坐標)c2，接著再橫向走到目標點B(x2，y2)。縱向尋路是從起點A(x1．y1)豎向走一定步長，接著橫向走到與目標點B相同的縱坐標y2，再豎向走到目標點B(xZ，y2)。A，B兩點在一條直線上連通是橫向／縱向尋路時橫向／縱向步長為0的特例．第一步：起始方塊和目標方塊是否同一方塊，如果是不同方塊id值是否一致；if(start==start．Target start．id!=start．Target．id)；第二步：存儲起始方塊、目標方塊的坐標．定義節點對象，臨時路徑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()； ／／定義節點對象var tempPath：Array=new Array()； ／／定義臨時路徑第三步：取橫向尋路的步長變量i=0；第四步：初始counts=0。將臨時路徑數組tempPath清空。循環掃描橫向尋路；并記錄障礙數counts．記錄結點node，將結點壓入tempPath中，如果counts=l，說明尋路成功，如果start．1ength沒有記錄過路徑則保存尋到的通路，已記錄過連接路徑將其與剛搜索的臨時路徑比較，如不是最短路徑將tempPath存入路徑數組start．1ength。返回真值。第五步；i+1；第六步：如果iCols轉第四步，否則轉下一步。第七步：橫向尋路循環結束，進行縱向尋路，過程同第三步——第六步。第八步：如果尋路不成功，返回假值3．3算法的程序實現應用ActionScript3進行了編程設計，程序代碼簡單容易改for(var i：uint—O；iCols；i++){ ／／橫向尋路vat counts：uint=o； ／／路徑中的障礙數tempPath．splice(0)f ／／清空數組var step：int=(yli)?一l：1；／／設置步長的間隔for(var j=yl，j!=i；j+=step){counts+=map[x1][j], ／／計算路徑中的障礙數node={x：xl，Y：j)； ／／記錄節點tempPath．push(node)I／／node節點壓人數組的末尾(入棧)}step=(xlx2)?1 ：l；for(j=xl；j!=x2；j+=step){counts+=map[j][i]；node={x：j，y：i}；tempPath．push(node)}／／node節點壓人數組的末尾}step=(iy2)?l：一l；for(j—i，j!=y2；j+=step){counts+=mapEx2][j]；node一{x：x2，y：j}；tempPath．push(node)； ／／節點壓入數組的末尾}if(counts==1){if(start．Path．1ength一=0||tempPath．1engthstart．Path．1ength){start．Path=tempPath．slice()；}／／復制數組tempPath到start．Path4算法比較本尋路算法主要是運用循環依次計算通路，主要的開銷在通路障礙數的計算上。算法主要過程是逐條累加計算每條通路中的障礙數，路徑長度是臨時路徑數組的長度。時間復雜度為o(m*n)，空間方面主要需要一個方塊類定義方塊，一個節點對象記錄節點，一個數組記錄臨時路徑，空間復雜度為o(m+n)。雖然計算的節點多，但是相對廣度搜索和深度搜索．本算法方法簡單，計算各個節點是最快的．不需要頻繁調用函數分配大量的數據空問。使用相對廣度搜索和深度搜索需要使用遞歸方法解決．要走的路很多幾乎遍歷節點，并且有些路還會相交．相交的時候，還得檢查哪根線的折點少。并且還有不少的路是根本不可能行得通的。會導致遞歸級數很高。用經典算法編程序時．牽涉到回溯、遞歸等較復雜的算法，代碼繁瑣容易出錯。尤其牽涉到復雜數據結構棧(深度優先搜索)、隊列(廣度優先搜索)的操作，調試跟蹤比較麻煩。而用本算法進行編程時．只用到數組這個簡單形象的數據結構，算法也簡單，相應的編程代碼也簡短高效。5結束語本論文主要提出了一種解決連連看尋路問題的算法．并應用ActionScript3進行了編程設計，程序代碼簡單容易改編，可以應用在游戲設計繞過障礙的路徑搜索。附錄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