貪食蛇移動(dòng)算法分析

摘 要：貪食蛇是一款經(jīng)典的小游戲，生于80年代的青年們絕對(duì)不陌生，那時(shí)候接觸貪食蛇小游戲就是從諾基亞手機(jī)開始的。貪食蛇游戲里包含許多的程序算法，但是，很少有詳細(xì)介紹到蛇體的運(yùn)動(dòng)算法。貪食蛇游戲設(shè)計(jì)得好不好，重點(diǎn)是看蛇體的運(yùn)動(dòng)，蛇體運(yùn)動(dòng)是隨著蛇體長度的增大和身體扭曲點(diǎn)的增多而變得更加復(fù)雜。本文主要針對(duì)貪食蛇的移動(dòng)進(jìn)行算法的分析與設(shè)計(jì)。

關(guān)鍵詞：貪食蛇；動(dòng)態(tài)數(shù)組；循環(huán)單鏈表；c語言；程序設(shè)計(jì)

中圖分類號(hào)：TP312

貪食蛇是一個(gè)產(chǎn)生于1970年代中后期的計(jì)算機(jī)游戲。此款游戲在1990年代由于小屏幕設(shè)備引入而流行起來，我們接觸得最多的是手機(jī)游戲，在游戲中，玩家操控著一條長線，它會(huì)一直前進(jìn)，通過操控方向鍵來改變線頭的朝向，當(dāng)觸碰到屏幕上隨機(jī)產(chǎn)生出來的物體，就立刻吃掉一件食物，它的線長會(huì)增加一節(jié)，移動(dòng)的速度逐漸加快，同時(shí)也讓游戲的難度逐漸加大。貪食蛇可以被很多不同的編程語言實(shí)現(xiàn)，實(shí)現(xiàn)的難度不大，文件內(nèi)容較小，在實(shí)現(xiàn)的過程中要編碼者充分熟練編程語言的語法，和鍛煉編碼者的邏輯處理思維。所以，貪食蛇被很多高校作為程序?qū)嵅倬毩?xí)課程內(nèi)容。貪食蛇的程序里有個(gè)重點(diǎn)和難點(diǎn)是蛇體移動(dòng)算法，若能解決，這程序基本完成一半了，故針對(duì)蛇體移動(dòng)算法進(jìn)行分析和設(shè)計(jì)。

1 蛇體移動(dòng)算法的思路分析

在游戲中，蛇體的運(yùn)動(dòng)規(guī)律是一節(jié)緊跟著一節(jié)蠕動(dòng)的，有個(gè)特性是蛇體的每一個(gè)節(jié)點(diǎn)都會(huì)經(jīng)過頭部所經(jīng)過的位置，除蛇頭外，蛇體的每個(gè)節(jié)點(diǎn)的目的位置是他前一個(gè)節(jié)點(diǎn)的所在的位置。以上是從運(yùn)動(dòng)規(guī)律去分析，其實(shí)在算法 上可以理解為，蛇頭在運(yùn)動(dòng)方向增加一節(jié)點(diǎn)，蛇尾減少節(jié)點(diǎn)，從而達(dá)到蛇體移動(dòng)的目的，稱為頭插尾刪法。這種方法易于操作，降低移動(dòng)失誤率。以下在11×14的格子空間里模擬蛇體的運(yùn)動(dòng)，每個(gè)格子尺寸是15×15px。蛇體移動(dòng)過程見圖1。從圖1可以清楚看到，通過頭插尾刪法，在指定方向上增加一節(jié)點(diǎn)，實(shí)現(xiàn)前進(jìn)或者改變方向，然后刪除末尾節(jié)點(diǎn)，中間節(jié)點(diǎn)部分不用操作，就可以實(shí)現(xiàn)蛇體按照指定的方向移動(dòng)，并且能夠準(zhǔn)確地保持原本蛇體形態(tài)，蛇體轉(zhuǎn)動(dòng)彎曲的效果更加靈活，能是適應(yīng)于大多復(fù)雜的扭曲點(diǎn)。

2 移動(dòng)算法的實(shí)現(xiàn)

根據(jù)蛇體的算法思路分析，要選用一種合適的數(shù)據(jù)結(jié)構(gòu)去實(shí)現(xiàn)算法，邏輯思路轉(zhuǎn)化成數(shù)據(jù)結(jié)構(gòu)思路去實(shí)現(xiàn)。要實(shí)現(xiàn)蛇體移動(dòng)算法有很多，能實(shí)現(xiàn)程序的編程語言也有多種，無論哪種語言實(shí)現(xiàn)，但算法的思路都是固定的?？偟膩碇v，算法是思路，編程語言只是實(shí)現(xiàn)算法思路的工具，算法是程序的靈魂。實(shí)現(xiàn)算法大體分為兩步，第一步是圖像處理，就是算出下一刻位置的坐標(biāo)，在指定坐標(biāo)處填充蛇頭圖像，再將尾節(jié)點(diǎn)的圖像設(shè)置為背景圖像或顏色；第二步是數(shù)據(jù)結(jié)構(gòu)處理，總結(jié)兩種比較好的數(shù)據(jù)結(jié)構(gòu)處理算法，動(dòng)態(tài)數(shù)組法和鏈表法，本文作者選用C語言實(shí)現(xiàn)。

2.1 動(dòng)態(tài)數(shù)組法。有人會(huì)提出用數(shù)組實(shí)現(xiàn)，一般數(shù)組是指靜態(tài)數(shù)組，也就是定義時(shí)候在內(nèi)存上分配好空間大小，在運(yùn)行時(shí)是不能改變這大小，所以對(duì)于蛇體的擴(kuò)展有極大的限制，處理不好會(huì)導(dǎo)致資源的浪費(fèi)和內(nèi)存的泄露等一些列問題。動(dòng)態(tài)數(shù)組是指在聲明時(shí)沒有確定數(shù)組大小的數(shù)組，即忽略方括號(hào)中的下標(biāo)；當(dāng)要用它時(shí)，C語言中用malloc語句重新指出數(shù)組的大小。[1]使用動(dòng)態(tài)數(shù)組的優(yōu)點(diǎn)是可以根據(jù)用戶需要，有效利用存儲(chǔ)空間。故選用動(dòng)態(tài)數(shù)組來解決靜態(tài)數(shù)組的缺點(diǎn)。

主要算法思路：

（1）用使用malloc分配指定長度字節(jié)的內(nèi)存塊，初始化構(gòu)造動(dòng)態(tài)的數(shù)組。

（2）獲取移動(dòng)的方向。一般定義變量direct存儲(chǔ)方向，在xy軸上，1代表正方向，-1代表負(fù)方向。

（3）利用公式計(jì)算出最新的最新的坐標(biāo)位置。新坐標(biāo)=頭坐標(biāo)+格子寬度×direct。

（4）移動(dòng)數(shù)組內(nèi)的坐標(biāo)值，從后向前移動(dòng)覆蓋，更新數(shù)組坐標(biāo)數(shù)據(jù)。

（5）更新數(shù)組末尾坐標(biāo)值。如果是前行或轉(zhuǎn)向操作，直接將新坐標(biāo)替換掉數(shù)組末尾坐標(biāo)，若是蛇體長度增加，先判斷蛇體長度是否達(dá)到長度上限，若達(dá)到，則用realloc語句動(dòng)態(tài)添加新空間，再數(shù)組末尾后一位插入新坐標(biāo)值。

主要代碼如下：

int xf=0，yf=0，i=0，xo=0，yo=0；

switch（f）{

case 1：yf=-1；break；

case 2：xf=-1；break；

case 3：yf=1；break；

case 4：xf=1；break；}

//在數(shù)組尾部計(jì)算新坐標(biāo)

xf=（s->node+s->length-1）->x+2*NUM_R*xf；

yf=（s->node+s->length-1）->y+2*NUM_R*yf；

//記錄頭坐標(biāo)的值

xo=s->node->x；

yo=s->node->y；

//在新坐標(biāo)處繪制新結(jié)點(diǎn)

setfillcolor（YELLOW）； //設(shè)置填充顏色

fillcircle（xf，yf，NUM_R）； //繪制新結(jié)點(diǎn)

clear（xo，yo）； //將原始頭結(jié)點(diǎn)設(shè)置為背景顏色

//移動(dòng)數(shù)組內(nèi)的xy值，從后向前移動(dòng)覆蓋，更新數(shù)組坐標(biāo)數(shù)據(jù)

for（i；ilength-1；i++）{

（s->node+i）->x=（s->node+i+1）->x；

（s->node+i）->y=（s->node+i+1）->y；}

//更新尾結(jié)點(diǎn)

if（addnode！=1）{ //前行或轉(zhuǎn)向操作，直接將新坐標(biāo)替換掉數(shù)組末尾坐標(biāo)

（s->node+s->length-1）->x=xf；

（s->node+s->length-1）->y=yf；}

else{ //長度增加，在數(shù)組末尾后一位插入新坐標(biāo)值

if（s->length>=maxsize）s->node=（snode*）realloc（s->node，（s->length +STACKINCREMENT）*sizeof（snode））； //長度達(dá)到上限，動(dòng)態(tài)添加空間

（s->node+s->length）->x=xf；

（s->node+s->length）->y=yf；

}

2.2 鏈表法。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)，也可以是不連續(xù)的）。以此，為了表示每個(gè)數(shù)據(jù)元素與其直接后繼數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素來說，除了存儲(chǔ)其本身的信息之外，還需要存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。[2]也就是說在鏈表內(nèi)的每個(gè)數(shù)據(jù)元素需要有兩部分信息組成，一是數(shù)存儲(chǔ)數(shù)據(jù)信息的數(shù)據(jù)域，二是存儲(chǔ)直接后繼存儲(chǔ)位置的指針域。在存儲(chǔ)分配方式，鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素；在時(shí)間性能，鏈表在插入和刪除時(shí)間復(fù)雜度僅為O（1），便于插入和刪除；在空間性能，鏈表不需要分配存儲(chǔ)空間，只要有就可以分配，元素的個(gè)數(shù)不受限制。根據(jù)元素的結(jié)構(gòu)不同，鏈表的表示形式可分為：單鏈表、循環(huán)鏈表、雙向鏈表。而循環(huán)單鏈表，又分只帶頭指針、只帶尾指針、和帶頭尾指針的三種形式。只帶頭指針形式的循環(huán)單鏈表，可直接操控頭結(jié)點(diǎn)，但操控尾結(jié)點(diǎn)，則需要將鏈表的所有結(jié)點(diǎn)遍歷一遍，時(shí)間復(fù)雜度O（n），對(duì)于貪食蛇需要同時(shí)操控頭尾部分的邏輯要求，該形式循環(huán)單鏈表的效率就大大降低。只帶尾指針和帶頭尾指針形式的循環(huán)單鏈表，對(duì)操控頭尾結(jié)點(diǎn)的效率基本一樣，但只帶尾指針形式的循環(huán)單鏈表在空間上優(yōu)于帶頭尾指針形式的鏈表。綜合上述的分析，本文選用帶尾結(jié)點(diǎn)的循環(huán)單鏈表去實(shí)現(xiàn)貪食蛇的數(shù)據(jù)結(jié)構(gòu)處理算法。

主要算法思路：

（1）初始化構(gòu)造指定長度的帶尾結(jié)點(diǎn)的循環(huán)單鏈表。

（2）獲取移動(dòng)的方向。一般定義變量direct存儲(chǔ)方向，在xy軸上，1代表正方向，-1代表負(fù)方向。

（3）利用公式計(jì)算出最新的最新的坐標(biāo)位置。新坐標(biāo)=頭坐標(biāo)+格子寬度×direct。

（4）構(gòu)造新結(jié)點(diǎn)，存儲(chǔ)新坐標(biāo)位置。使用malloc函數(shù)構(gòu)造出結(jié)點(diǎn)，將坐標(biāo)數(shù)據(jù)存入到數(shù)據(jù)域。

（5）新結(jié)點(diǎn)插入到循環(huán)單鏈表尾部。

newNode->next=rear->next；//新結(jié)點(diǎn)的指針指向尾指針?biāo)附Y(jié)點(diǎn)的指針指向的結(jié)點(diǎn)位置。

rear->next=newNode；//尾指針?biāo)附Y(jié)點(diǎn)的指針指向新結(jié)點(diǎn)。

rear=newNode；尾指針指向新結(jié)點(diǎn)。

（6）刪除第一個(gè)結(jié)點(diǎn)。刪除尾指針?biāo)附Y(jié)點(diǎn)的指針指向的結(jié)點(diǎn)。

rear->next=rear->next->next；//將尾指針指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。

3 上述兩種算法的時(shí)間復(fù)雜度分析

使用動(dòng)態(tài)數(shù)組算法的T（n）=O（n），鏈表算法的T（n）=O（1）。

用n的問題規(guī)模大小逐漸增大地運(yùn)行一步蛇體地動(dòng)所消耗的時(shí)間復(fù)雜度對(duì)比圖，見圖2。由圖2可以得出，使用動(dòng)態(tài)數(shù)組算法處理，隨著蛇體的長度不斷增大，每一動(dòng)一次所用的操作數(shù)量會(huì)線性增加，所消耗的時(shí)間也會(huì)增多，但鏈表法隨著問題規(guī)模的增大依然是恒定保持不變。依據(jù)上述理論，分別用兩種不同算法，在問題規(guī)模不斷增大情況下，記錄時(shí)間損耗，見圖3。用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，蛇的結(jié)點(diǎn)在100000以內(nèi)，所用的操作數(shù)量還能接受，若蛇的結(jié)點(diǎn)數(shù)達(dá)到一定規(guī)模數(shù)量（規(guī)模數(shù)量>100000）時(shí)，就會(huì)嚴(yán)重影響移動(dòng)的速度和性能，然而鏈表算法實(shí)現(xiàn)的運(yùn)算中，時(shí)間依然保持在0.000秒以下。

4 結(jié)束語

結(jié)果表明，兩種算法都可以實(shí)現(xiàn)貪食蛇的移動(dòng)，但有性能的差異。動(dòng)態(tài)數(shù)組算法比較適合于結(jié)點(diǎn)數(shù)量比較少的情況下使用，鏈表法則與結(jié)點(diǎn)的數(shù)量無關(guān)。

參考文獻(xiàn)：

[1]百度百科.C語言動(dòng)態(tài)數(shù)組[EB/OL].http：//baike.baidu.com/link？url=FDQAvU2yUgg4A4d5GPgP8_L_vxpdyc-NIDIz053cILXoTLlDUBTljd77HCe8CMkIYFlpQoQMf3nRoQqqdZxX9K

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）（第1版）[M].北京：清華大學(xué)出版社，2011.

[3]徐艷.貪食蛇游戲的結(jié)構(gòu)程序設(shè)計(jì)流程[J].科技廣場，2010（01）：110-111.

[4]劉云，羅永能.基于51單片機(jī)的貪食蛇游戲機(jī)開發(fā)[J].福建電腦，2009（07）：147-148.

[5]譚浩強(qiáng).C程序設(shè)計(jì)（第4版）[M].北京：清華大學(xué)出版社，2010.

作者簡介：張嘉利（1987-），男，廣東廣州人，教師，助工，軟件設(shè)計(jì)師，工學(xué)學(xué)士，研究方向：程序設(shè)計(jì)、系統(tǒng)架構(gòu)、移動(dòng)平臺(tái)開發(fā)；陳成勛（1987-），男，廣東汕尾人，.Net軟件開發(fā)工程師，軟件設(shè)計(jì)師，工學(xué)學(xué)士，研究方向：搜素引擎原理、Oracle數(shù)據(jù)挖掘。

作者單位：廣州現(xiàn)代信息工程職業(yè)技術(shù)學(xué)院 信息工程系，廣州 510663；惠州TCL移動(dòng)通信有限公司，廣東惠州 516006