築夢角落

致力於用最生活化的例子讓所有人都能懂程式,也喜歡分享動漫、小說心得,以及自己的所見所聞、所思所想。

【實作】以Unity實現SRPG的棋盤式移動

最後更新時間 : 2022-06-03 | viewed : 211

SLG演算法設計

我大學的專題做的是3D遊戲,當時我們小組選用Unity來開發棋盤式回合制戰鬥遊戲,也就是常聽到的SLGSRPG

由於這篇主要是我在巴哈發表的【實作分享】以Unity實作棋盤式戰鬥遊戲(SLG)的續篇,所以主要會著重在SRPG的移動路徑演算法的說明,有關於Unity專案的使用說明、遊戲模式的說明,請見我的巴哈文章。

 

前言


接下來要分享的內容是我大學時寫的,雖然有點不成熟,甚至還把C#當作C語言在寫,但我現在回頭再看那時寫的程式依然覺得很好讀懂

或許正是因為當時總是直線思考,所以才能把事情解釋得簡單明瞭,這是現在的我難以做到的。

因此我不打算重寫一篇,請容我原封不動把那時寫的內容貼上來吧。

 

Unity版本


我們開發時用的Unity版本是4.x,後來因為有人問在其他Unity版本是否可用,所以我有試過把專案匯入Unity5.6,雖然會有很多Error,但是只要照Error訊息去更新Unity函式庫的API,依然是可以使用的,更高的版本應該也是如此。

 

角色「移動」指令功能


在這裡,我們先以一個實例來說明移動的部份。

假設我方的一名角色,其可移動範圍為三格,我們可以得到如圖1的結果。白色格子棋盤的大小,綠色格子出發點藍色格子可移動範圍

 

棋盤式遊戲

(圖1)

 

以此類推,若可移動範圍為五格,則藍色格子的分佈範圍將如圖2所示。

 

棋盤式遊戲

(圖2)

 

但此時,若是我們的角色處於棋盤的邊界,由於不可讓角色走到棋盤外藍色格子的分佈將會產生變化,如圖3所示。

 

棋盤式遊戲邊界

(圖3)

 

由此可知,棋盤的邊界會令可移動範圍縮減。

換句話說,我們將棋盤邊界視為一種障礙物,並定下不可跨越障礙物的規則。

除了棋盤邊界以外,若是在可移動範圍內出現任何我方或敵方的角色,我們也會將其視為障礙物。

舉例來說,若角色原本可移動範圍為五格,而這時剛好有名敵方角色出現在這範圍裡,將會導致如圖4的結果。

 

棋盤式遊戲上的怪物

(圖4)

 

從圖4中可知,藍色格子為可移動範圍,黃色格子為不可移動的範圍。

只要和圖3比較一下,便可得知黃色格子原本是可以到達的,但由於目前受到敵方角色(障礙物)阻撓,因此無法順利前往。

以上就是我們所希望的結果,同時也是我們為遊戲的戰鬥方式所定的規則。

但實際進行遊戲時,我們無法事先得知障礙物的分佈情形,所以必須設計一套有效的演算法,來替我們即時計算出可移動範圍

首先,我們必須先準備好四個一維陣列,每個陣列裡面必須儲存不同的資料。

我們先用兩個陣列分別儲存我方與敵方角色的座標值,如圖5所示。

 

SRPG演算法

(圖5)

 

接著,我們要開始計算A(5, 5)可移動範圍

我們先定義一個變數move,並令 move = 5,意味著A的可移動範圍為五格,並將這個初值存放在第三個陣列(mCount)中。

到這裡為止,我們已經用了三個陣列,最後一個陣列(canMove)我們用來存放所有可到達的座標值,並且從A的座標值開始儲存。如圖6所示。

 

SLG演算法

(圖6)

 

完成以上的初始配置之後,接下來將以「廣度優先演算法」實現我們的需求

我們先以A為出發點,向正Y方向「探索」一格。

所謂的「探索」,便是確認該格內是否存在障礙物,於是我們把(5, 5+1)的座標,拿去和monster以及partner這兩個陣列做比對,若是這兩個陣列中皆不存在(5, 5+1)的座標值,表示該格不存在障礙物。

如圖7所示。

 

棋盤式遊戲演算法

(圖7)

 

完成這項檢查後,我們已確認(5, 5+1)為可行走的格子,於是將該座標值存入canMove陣列中,同時也將move減去1,存入mCount的陣列裡。

這裡所代表的意義是,當我們探索到(5, 6)的位置時我們只能再往外探索四格直到move = 0之後便不能再向外探索

如此一來,最後才能得到可移動範圍為五格的結果

如圖8所示。

 

SRPG的廣度優先演算法

(圖8)

 

重複上述步驟,依序探索上、下、左、右之後,我們可以得到如圖9的結果

同時,這也是可移動範圍為一格時的結果

 

SLG廣度優先演算法

(圖9)

 

現在,A的周邊範圍已經被我們探索完了,為了繼續探索下去,我們必須找出另一個新出發點,並以新出發點為中心,照上述的方式依序探索上、下、左、右。

決定新出發點的方式,是從canMove陣列中取出當前出發點的下一筆座標值。

以剛才的結果來說,當前出發點(舊出發點)為A的座標(5, 5),而下一筆資料則為(5, 6),所以(5, 6)成為了新出發點。

如圖10所示。

這裡我們可以注意到,新出發點的替換順序,正好就是我們過去的「探索」順序。

 

廣度優先演算法

(圖10)

 

在這裡,我們可以注意到有兩件事情發生了。

首先,新出發點的正Y方向有障礙物存在,我們可以透過將(5, 6+1)與monster陣列比對,發現陣列中確實存在(5, 7)的座標值,意即這格為「不可走」的座標

發生這種狀況的時候,就不必將該格的座標值存入canMove陣列中也不需將move減去1

簡單來說,就是略過所有處理程序,如此一來該格就等同於「不可走」(因為未被記錄於canMove陣列中)。

接著,當我們向下探索的時候,又發生了第二件事。

我們可以清楚地看到,向下探索的那格,正好就是我們先前的出發點,於是我們可以理解成「那格已經探索過了,而且確認為可走」。

所以,我們在探索的同時,除了必須將探索的座標值與monster以及partner做比對之外也必須與canMove陣列做比對,若是能在canMove裡找到當前探索的座標值,就立刻放棄後續的處理程序,以防重複記錄「可行走的座標格」,導致計算錯誤。

至於圖10中「向左」及「向右」探索則無任何狀況發生,所以只需依照正常的處理程序計算即可。意即將探索的座標值存入canMove陣列中,並將move的值減1存入mCount陣列。

只要以迴圈方式不斷進行上述的運算,最後就能得出如圖11的結果。

 

SLG怎麼計算行走範圍

(圖11)

 

雖然本例是以「只有一隻怪物」的情況做描述,但實際上這個方法可以用於任何情況

得出如圖11後,玩家可讓角色移動至藍色範圍內的任一點。

這時我們又會遇到一個新的問題:該如何尋找從A點到B點的最短路徑

如圖12所示。

 

廣度優先演算法的最短移動路徑

(圖12)

 

比起前面的問題,這個問題其實相對簡單。

還記得我們用來存放move值的mCount陣列嗎?

現在,我們只要將move值從陣列取出放在對應的座標點上就能得到如圖13的結果

所謂「對應的座標點」,意思是mCount[0]的move值放在canMove[0]的座標上

mCount[1]的move值,放在canMove[1]的座標上,以此類推。

能夠像這樣對應座標與move值,是因為我們當初在儲存資料的時候,始終讓mCount與canMove在每個步驟階段都使用同一個索引值來存取變數。

 

計算最短移動路徑的方法

(圖13)

 

現在,我們可以很清楚地看到藍色範圍內的每一個方格,都標有一個數字,即該座標所對應的move值

從圖13中我們可以觀察到,距離A點越近的點其數字越大;反之,離A點越遠的點其數字越小

稍後我們將利用這項特性,完成「最短路徑」的演算。

值得一提的是,雖然從「尋路」的過程來看我們是欲從A點前往B點,但是為了減化演算法的複雜度,以及提升程式執行的效率,在實際進行運算的時候我們是以「從B點返回A點」的路徑當作最短路徑

如圖14所示。

 

計算最短路徑

(圖14)

 

依據上述,我們必須找出從B點回到A點的最短路徑,但只要仔細觀察的話,必定能發現上圖中的玄機。

我們以B作為出發點並且只要延著數字較大的方向走最後必能回到A點

並且,只要再將這條路徑反轉一下正好就變成從A點到B點的最短路徑

所以我們這時必須再準備一個空陣列,記錄從B點返回A點的路徑,最後再將陣列內容倒印,就能得到我們想要的結果。如圖15所示。

 

廣度優先演算法最短路徑

(圖15)

 

棋盤「移動」指令功能的演算法,到此算是介紹完畢了,最後只要將所有的陣列清空、將所有的變數回歸成初值,以便下一次的路徑計算,就算是大功告成了。

至於實際讓物體(角色)移動的方法,會根據使用不同的作業環境而有不同,本專題使用的環境為「Unity」,移動時需配合Unity所提供的函數庫進行運算。

 

完整範例下載


請至我的Google雲端硬碟下載:Unity範例(SLG、SRPG)

 

結語


我第一次接觸程式是高三的時候,在學校有C(用於8051)、Arduino、組合語言的實習課,一個學期接觸三種東西,而且是在連基礎概念都沒有的情況下,那時候我學得非常差,大部份的同學也跟我一樣。

升上大學之後,我寫程式的能力也沒有進步太多,幾乎都是拼拼湊湊靠運氣試出來的,而且大多還得靠其他同學幫忙。

直到大三下學期,我們這組在專題上卡關,SLG的這個棋盤問題沒人解得出來,為了解決這個問題,我才下定決心從零開始把程式學好。

這是對我而言很重要的一個轉捩點,我就是從這個時候開始瞭解程式,也知道怎麼找到適合自己的方法去學習每一項技藝或學問,掌握了「學習如何學習」的能力,也確定了畢業之後要從事程式設計的工作。

這有點說來話長,之後我想再開一個「生活嘀咕」的板塊,分享我生命中大大小小的事,也包括這件對我意義重大的事。

 

希望有幫助到你!

 

 
我要留言!
 

X
暱稱(選填)
email(選填,僅站長可見。)
留言 To:#