格線式路徑尋找

在本教學中，我們將以二維陣列網格製作路徑尋找模擬。這會讓我們了解如何為遊戲製作路徑尋找活動。我們會用空白方形物件做為圖塊，將網格視覺化，再用圓形物件做為角色，讓它能依照我們的指令在網格區域中移動。

I. 設定物件

我們的專案只會用到四種物件：綠色角色、藍色圖塊、白色障礙物，以及用來設定和視覺化網格的 Grid 標籤。

角色

我們的角色是一個空白物件，x 軸與 y 軸的縮放比例皆為 50%。將它的碰撞形狀設為圓形，讓它看起來像下方圖片中的樣子。這個物件會有三個預先定義的屬性：所在圖塊、上一個圖塊和目標圖塊。將這些屬性的預設值設為 0，避免之後嘗試取得屬性時遇到 null 值。

圖塊物件

再建立一個空白物件，用來呈現網格中的圖塊。它的縮放比例同樣為 50%，並且只有一個預先定義的屬性：所在圖塊。也將這個值設為 0。

障礙物物件

再建立一個空白物件，做為網格中的障礙物。這是一個縮放比例為 40% 的白色空白物件。角色無法移動到有障礙物的圖塊上。

Grid 標籤

這個標籤會包含用來設定和視覺化網格的行為。它有預先定義的屬性：start x，值為 4；以及 start y，值為 3。這些值是偏移量，會做為參考值，用於產生圖塊，讓網格整齊地置中。

角色／圖塊的預先定義屬性：

此處的圖塊是指一個大小為 2 的陣列，其中包含根據網格設定的 x 和 y 值。

• 所在圖塊 - 物件目前所在網格圖塊的值
• 上一個圖塊 - 角色先前移動經過的圖塊
• 目標圖塊 - 角色將前往的圖塊

II. 設定網格

我們會在 Grid 標籤中定義二維陣列並產生網格。這個物件的主要工作有兩項：設定陣列，以及將陣列視覺化。我們先來製作設定陣列的行為組合。

設定陣列 - 行為組合

首先，建立一個名為「Grid」的空陣列。這個陣列會包含我們的二維陣列。我們會建立一個名為「x row count」的方塊容器，值為 24；再建立一個名為「y row」的空陣列，裡面有 18 個空值。

行為組合中的第一個行為是迴圈，重複次數設為「x row count」。每次執行迴圈時，我們都會將一個空的 y row 加入「Grid array」。如此一來，就會建立一個維度為 24x18 的巢狀陣列。

請注意，我們在行為組合的開頭連接了一個未啟用的註解，以避免這個根行為自動執行。根行為是不會由任何事件觸發、直接放在介面中的行為。

將網格視覺化 - 行為組合

這裡主要要做的是逐一查看「Grid array」中的每個值，並產生圖塊物件。我們也會在迴圈中加入條件，讓它能在圖塊物件上方產生白色障礙物。

首先，取得「y row array」的陣列數量，以及這個物件的「start x」和「start y」屬性值。

建立一個重複次數為「x row count」的迴圈。每次執行迴圈時，將迴圈索引值與「start x」屬性值相加。這會得到稍後用來設定產生圖塊位置的絕對 x 座標。接著建立「y row loop」，重複次數為「y row count」。每次執行迴圈時，將迴圈索引值與「start y」屬性值相加，這樣就會得到絕對 y 座標。

在「y row loop」中加入這些值後，接著產生藍色物件。將它的存活物件數量上限設為 999，因為網格需要大量圖塊；持續時間也設為 0。接著將產生的物件移到 x 點位置，其值來自 x 迴圈的「add values」；y 點位置則使用 y 迴圈的「add values」。

接著，新增一個含有 2 個空值的陣列，命名為「On tile」，我們只會將它當做陣列佔位符使用。移動圖塊物件後，修改「On tile」陣列，將索引 0 的值替換為「x row loop」的值。接著新增另一個陣列修改行為，將索引 1 的值替換為「y row index」。這就是物件將做為「on tile」屬性的網格 x 和 y 座標。

現在，為產生的物件設定屬性，使用動態索引鍵「on tile」，並將值設為「On tile - array」。

仍在 y row loop 中，我們要加入產生白色障礙物的條件。這個行為組合有 5 分之 2 的機率執行，讓網格更具隨機性。接著，我們會在「Grid」陣列中，將該座標的值標記為 1，表示該座標上已產生障礙物。

首先，產生一個介於 1 到 5 的隨機數。如果這個數字小於或等於 2，就產生障礙物。將它的存活物件數量上限設為 999，並將它移到先前產生的藍色圖塊相同的位置，持續時間也設為 0。

接著，如果障礙物有成功產生，就儲存該座標已被障礙物佔據的資訊。我們會將該座標標記為 1。首先，取得「Grid」陣列中索引為「x row loop」的值。這個值會是一個「y row」陣列。修改這個「y row」，將索引「y row loop」的值替換為 1，做為標記值。由於這項值修改只會套用到該值本身，不會套用到「Grid」陣列，因此還必須修改「Grid」陣列。將「Grid」陣列中索引「x row loop」的值替換為「modify y row - array」。

執行後，應該會呈現如下的結果。

III. 按下圖塊時

若要與網格互動，我們需要設定一個行為組合，讓每次按下藍色圖塊時都會執行。第一次按下時，角色會出現在網格中；之後每次再按下圖塊，就會開始尋找路徑。

在藍色物件中建立一個行為組合，包含三個主要步驟：重設角色的上一個圖塊、設定所在圖塊／目標圖塊，接著加入顏色動畫，讓畫面顯示觸碰事件。

首先，取得圖塊物件的「on tile」屬性。將角色的「previous tile」屬性設為 0。角色會避免移回「上一個圖塊」，因此每次按下圖塊時都要重設「previous tile」。

接著，取得角色的「on tile」屬性。第一個 if 條件是檢查「on tile」的值是否等於 0。這表示角色尚未出現，條件會成立。如果成立，就將角色的「on tile」屬性設為圖塊物件的「on tile」屬性值。然後取得圖塊物件的位置，將角色移到相同的 x、y 座標，持續時間設為 0。

如果「on tile」的值不等於 0，就將角色的「target tile」屬性設為圖塊物件的「on tile」屬性值。這表示角色已經位於網格中，接著便能執行「find path」行為組合。目前我們還沒有這個行為組合；完成本教學後面的部分，就能再回來設定「find path」行為組合。

角色成功放置在網格後，我們只要讓按下圖塊的事件呈現在畫面上即可。首先加入根行為「get color」，取得圖塊原本的顏色。按下圖塊後，將圖塊物件的顏色設為黑色，持續時間為 0；接著再將它的顏色恢復為原本的值，持續時間設為 0.2。

按下藍色圖塊後，結果應如下所示。

IV. 執行 Find Path 行為組合

在本教學的最後一部分，我們將製作一個演算法，找出角色前往目的地時可以移動到的最近圖塊。每當角色在網格中移動一格，這個行為組合就會再次執行。

我們會在角色物件中設定這個演算法，主要包含三個步驟：尋找相鄰圖塊、找出最近的相鄰圖塊，以及移動到該相鄰圖塊。

尋找相鄰圖塊

在這個部分，我們會收集角色可以移動到的所有相鄰圖塊。我們會檢查四個方向的相鄰圖塊，確認上面是否有障礙物，或角色先前是否已經走過該圖塊。

首先，新增「Adjacent tiles」陣列、一個含有 2 個空值的「Direction」陣列，以及四個各含有 2 個值的方向陣列：N (0,1)、S (0,-1)、E (1,0)、W (-1,0)。

行為組合中的第一個行為是清空相鄰圖塊陣列。由於這個行為組合會重複執行，因此每次都需要重設收集到的「adjacent tiles」。接下來四個行為會修改「Direction」陣列。我們依序將四個方向陣列的值設定到「Direction」陣列，接著執行下方的行為組合。這樣就能建立一個每次執行時都會使用不同「Direction」陣列值的迴圈。

取得方向後，只要將方向的 x 和 y 值分別與角色「on tile」屬性的 x 和 y 值相加即可。接著，我們就能取得「Grid」陣列中對應的目標值，判斷該圖塊是否已標記為有障礙物。

「Direction x」是「Direction」陣列索引 0 的值；「get on tile x」是「get on tile」索引 0 的值。將「direction x」和「get on tile x」相加，即可得到 Target x。y 值也以同樣方式計算，但目標索引為 1。

「Target y row」是「Grid」陣列中索引為「Target x」的陣列值。接著，「Target index in y row」是「Target y row」陣列中索引為「Target y」的值。這就是網格中的對應座標，可用來判斷該座標是否已標記為有障礙物。

如果「Target index in y row」的值為 1，表示目標圖塊已標記為有障礙物。如果這個值不等於 1，我們就能繼續執行行為組合。

由於 Target x 和 Target y 通過了條件檢查，我們新增一個名為「New adjacent tile」的空圖塊陣列，用來儲存 Target x 和 Target y 的值。我們會將 Target x 設為「New adjacent tile」索引 0 的值，並將 Target y 設為索引 1 的值。

接著，取得角色的「previous tile」屬性。如果「previous tile」不等於「new adjacent tile」，表示角色先前沒有走過這個新圖塊。此時，我們就能安全地將「New Adjacent tile」附加到「Adjacent tiles」陣列中。等角色成功移動到另一個圖塊後，再設定「previous tile」的值。

「你可以將這個行為組合擴展為八個方向的陣列，讓角色能朝對角線方向移動。」

尋找最近的相鄰圖塊

收集到可用的相鄰圖塊後，只要找出距離角色目標圖塊最近的相鄰圖塊即可。我們會使用目標圖塊和相鄰圖塊的 x、y 值，透過距離公式計算。

這個行為組合包含兩個主要部分：初始化計算所需的變數，以及在迴圈中計算圖塊距離。

a. 初始化變數

首先，取得相鄰圖塊的陣列數量。接著取得角色的「target tile」屬性，並取得它的 x 和 y 值。我們要新增 2 個方塊容器：「Min distance」和「Target tile index」。將「Min distance」的初始值設為 9999，並將「Target tile index」設為 0。由於我們要從起點開始找出距離最短的圖塊，因此要將最小距離設為一個很大的數字。「Target tile index」則是「Adjacent tiles」陣列中，與「target tile」距離最近之圖塊的參考索引。

這裡的主要目標，是取得「Adjacent tiles」陣列中距離「target tile」最近的圖塊索引。

b. 計算圖塊距離

在這個行為組合中，我們會在迴圈中計算每個相鄰圖塊的距離。迴圈會重複「adjacent tiles count」次，並使用迴圈索引，取得「Adjacent tiles」陣列中的圖塊值。

取得該相鄰圖塊的 x 和 y 值，然後使用下列公式計算「target tile」與「adjacent tile」之間的距離：

distance = sqrt((x2 - x1)^2+(y2 - y1)^2)
x1 = Target x
x2 = Adjacent x
y1 = Target y
y2 = Adjacent y

首先將 x 和 y 值相減，再各自與自身相乘以取得平方值；接著將這些值相加，最後對相加結果開根號，即可得到距離。

如果「Distance」的值小於「Min distance」方塊容器的值，就將「target tile index」設為目前的迴圈索引，也就是在「Adjacent tiles」陣列中取得的圖塊索引。我們也會將「Min distance」方塊容器的值設為「Distance」的值，以便和下一個迴圈圖塊比較。

迴圈結束後，我們便完成了所有相鄰圖塊的比較，也取得了距離「target tile」最近的相鄰圖塊索引。

移動到相鄰圖塊

在本教學的最後一個行為組合中，我們會將角色移動到最近的相鄰圖塊。如果角色尚未移動到「target tile」，就再次執行整個「Find Path」行為組合。

首先，檢查「Adjacent tiles count」是否大於 0，確保至少找到一個可用的相鄰圖塊後才移動。

接著，使用前一個行為組合中「Target tile index」的值，取得「Adjacent tiles」陣列中對應的值，藉此「Get the nearest tile」。

若要取得角色將移動到的確切位置，我們需要該圖塊的 x、y 值，以及「Grid」標籤的「start x」和「start y」屬性值。將「nearest tile」的 x 值與「start x」值相加，y 值也以相同方式相加。相加後的值就是角色將移動到的目標 x、y 座標。

移動到該位置之前，先將角色的「previous tile」設為目前的「on tile」屬性值。這個「on tile」值可以從前面的行為組合中取得。接著將角色移動到目標座標，持續時間設為 0.2。

「Move to point」行為完成後，將角色的「on tile」屬性設為「Get nearest tile」陣列值。如果「Get nearest tile」陣列值不等於角色的「target tile」，就再次執行「Find Path」行為組合，也就是重新執行整個行為組合。「target tile」屬性值可以從前一個行為組合中取得。

按下任意藍色圖塊，並等角色出現在網格中後，就會執行「Find Path」行為組合，讓角色在圖塊之間移動。

結論

在本教學中，我們學會了如何使用名為「Grid」的陣列製作物件路徑尋找活動。這個陣列可用來儲存圖塊是否被佔據的資訊。你可以延伸這個概念，在「Grid」陣列中使用物件 ID 做為資訊，而不只是使用數字。如此一來，我們就能取得更可靠的路徑尋找資訊。例如，可以取得該物件 ID 的屬性，判斷物件是否仍存在，以及是否允許角色踏上它所在的圖塊。

本教學只介紹了路徑尋找的基本概念。這個方法的一個缺點是，它無法找出通往目標圖塊的最短路徑，只會檢查目前的相鄰圖塊，因此可能導致角色陷入無法抵達目的地的移動循環。

不過，我們可以擴展路徑尋找演算法來解決這個問題。逐一重新檢查找到的相鄰圖塊，取得它們的相鄰圖塊，直到找到目標圖塊為止。每個找到的最近相鄰圖塊都會加入清單中。為避免無限循環，可以加入條件：如果某個相鄰圖塊已經檢查過，就不要將它加入清單。此外，也要限制迭代次數上限，避免因為目標圖塊距離太遠或無法找到而造成無限循環。迭代找到目標圖塊後，就結束迭代，再依照圖塊清單讓角色逐格移動。