Unity - 簡易2D地圖路徑尋找(Path finding)暴力搜尋法(Brute Force Search)

　　在製作2D地圖的時候，如果在地圖上有配置許多的目標點，例如村莊、洞穴、城堡等等，有些時候會希望角色可以在設定好的這些座標點上移動。
　　像是角色目前在A地點要移動到D地點，按下移動後就會A->B->C->D走到目標，如果地圖並不複雜龐大的話，此時就可以使用簡單的路徑取得，也就是本篇使用的方法，使用暴力搜尋法把所有可能的路徑全部找出來。

　　雖然在製作上不算太困難，但是既然是使用Unity那就要順便利用一下編輯器的方便性，讓編輯的人可以在Inspector當中直接編輯各個節點連結的資訊，所以就把這個功能製作成一個Component來使用。

public GameObject[] connectedNode; //因為要讓編輯的人可以在Inspector當中編輯節點的資訊，所以這邊要準備一個public陣列，就可以在Unity中把節點的GameObject放進去
public void GetPath(GameObject from, GameObject to, List<List<GameObject>> totalPath, List<GameObject> oldList)
{
    //這邊製作一個方法給前一個來源點跟最終目標點的資訊，以及所有路徑的List跟當前路徑的List，因為是參照所以這個方法就不用回傳值了
    ...
    //這邊可以做一些停止判斷，像是已經加過這個點那就停止這段搜尋返回上一個節點

    foreach(GameObject go in connectedNode)
    {
        //接著如果上面的判斷都過，接著就從設定好的nodes去取得下一個節點物件，然後取得下一個節點資訊直到停止
        GetPath(this.gameObject, to, totalPath, copyList);
    }
}

　　基本上概念就是做成這樣的Component，這樣做完後把這個Component放到當作節點的空GameObject上就可以用了，但是在編輯的時候會發現一個問題，那就是節點一多起來，有時候會不清楚那些編輯過那些沒有，所以這部分還可以使用OnDrawGizmos()在編輯視窗中加上一些輔助線條來幫助編輯。

void OnDrawGizmos() 
{
    foreach (GameObject go in connectedNode) 
    {
        Gizmos.color = Color.yellow;
        PathNode node = go.GetComponent(typeof(PathNode)) as PathNode;
        foreach(GameObject reflect in node.connectedNode)
            if(reflect == this.gameObject) Gizmos.color = Color.cyan;

        Gizmos.DrawLine(this.transform.position, go.transform.position);
    }
}

基本上就是去跑每個節點，然後使用Gizmos.DrawLine()把點做個連線，這邊多加個判斷是如果只有單向的就顯示黃色，雙向的顯示青色，在編輯上會更清楚那些點還需要編輯。
　　使用上來說可以給每個節點加上Tag或是預先做好列表，使用Tag的話可以類似這樣。

GameObject from = GameObject.FindGameObjectWithTag("Tag1");
GameObject to = GameObject.FindGameObjectWithTag("Tag2");
List<List<GameObject> totalPath = new List<List<GameObject>();
List<GameObject> newList = new List<GameObject>();
PathNode node = from.GetComponent(typeof(PathNode)) as PathNode;
node.GetPath(from, to, totalPath, newList);

然後就可以取得totalPath的資訊了，接著就可以看是不是要排序來取得最短路徑這樣。



--
實作測試(選擇起始點跟終點，然後點選GetPath取得路徑，使用Next切換不同的路徑，此部分為所有路徑非最短路徑)



--
路徑取得的Code部分

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class PathNode : MonoBehaviour {

    public GameObject[] connectedNode; //準備一個GameObject陣列，這樣你就可以在Unity inspector當中設定數量跟配置物件

    //在編輯器中畫出輔助線條，讓編輯節點更容易一點
    void OnDrawGizmos() 
    {
        foreach (GameObject go in connectedNode) 
        {
            if(go == null)
                continue;

            Gizmos.color = Color.yellow;
            PathNode node = go.GetComponent(typeof(PathNode)) as PathNode;
            foreach(GameObject reflect in node.connectedNode)
                if(reflect == this.gameObject) Gizmos.color = Color.cyan;

            Gizmos.DrawLine(this.transform.position, go.transform.position);
        }
    }

    public void GetPath(GameObject from, GameObject to, List<List<GameObject>> totalPath, List<GameObject> oldList)
    {
        if (oldList.Contains (this.gameObject))
            return; //如果目前這個節點已經在List裡了那就回上一個點

        oldList.Add (this.gameObject); //把目前這個節點加入List
        if (this.gameObject == to) 
        {
            totalPath.Add(oldList); //如果目前這個節點是你的目標點，就把這串List加入totalPath裡面，並回到上一個節點
            return;
        }

        //尋找下一個節點
        for (int i = 0; i < connectedNode.Length; ++i) 
        {
            if(connectedNode[i] == from)
                continue; //略過你來的那個節點

            //複製一份新的List
            List<GameObject> copyList = new List<GameObject>();
            foreach(GameObject go in oldList) copyList.Add(go);

            PathNode node = connectedNode[i].GetComponent(typeof(PathNode)) as PathNode;
            node.GetPath(this.gameObject, to, totalPath, copyList);
        }
    }
}

　　接下來如果要取得最短路徑也就不難了，可以直接比較每個路徑的節點數量取最少的，或者是計算節點的距離來取得實際上最短的路徑，都可以隨自己去控制了。