簡単な仕組みで自前で経路探索をやってみました。
画面上のWaypointに球をおいておくと、球と球の間で光線が飛ぶ=通行可能という仕組みで、経路パスを求めます。
次に、スタート球とゴール球を指定して、経路探索を呼ぶと、通行可能なパスを探索して最短経路を求めます。
画面の例では、Navi(2)球がスタート位置で、Navi(5)球をゴールとして探索させた例です。
複数の経路が求まりますが、一番距離が短いのは、2->7->5の経路とわかります。
UnityのNavMeshは、大量のポイントを三次元に配置して、そのポイント間の移動の可否を調べて、経路情報を生成しているようですが、このプログラムでは、あらかじめ手動で、ポイントを配置しておく方法です。
どのポイントとポイントが繋がっているかは、調べてくれます。
LineRendereは、一筆書きで全部つながってしまうので、移動可能なパス毎に、LineRendereは動的生成して表示させました。
そうしないと、通行できないポイント間も勝手に線が引かれます。
実は、ここが一番はまりました(´・ω・`)
GameObject gm =Instantiate((GameObject)Resources.Load("point"), sp, Quaternion.identity) as GameObject;
ここでloadしてるのは、emptyObjectにLineRendereだけAddしたprefabです。LineRendereをパス毎に動的に生成するためのダミーみたいなもんです。
探索手法としては、通行可能なポイントの組を配列で持っておいて、開始ポイントから、次のポイントをすべて調べて、そこにゴールが無い場合は、次のポイントからさらに次のポイントと、再帰的に探索します。
探索アルゴリズムには、深さ優先探索と幅優先探索がありますが、深さ優先で、いきなり無限深さで探索すると、実は1手で見つかるゴールがあるのに、先に探索開始した経路が深いとそこで延々はまってしまいます。
なので、反復深化という方法で、探索深さをだんだん深くしていくと、そういう無駄が起こりません。
反復深化/アルゴリズム講座
for (int i = 1; i < 5; i++) { ret = ""; search(dic["Navi (2)"], dic["Navi (5)"], 0, i); }
ただ、同じ探索を繰り返すので、通常はハッシュ表などで探索結果を残してやるとベターです。
また、一度通ったポイントを再び通ると、循環経路になって探索が終わらないので、履歴を持っておいてチェックしています。
ぶっちゃっけそんなに複雑な経路を探索させるわけではないので、ポイントが10個とか20個程度だと、アルゴリズムはどうでもいいです。
コンピュータ将棋やオセロみたいに1秒に100万手探索するような場合はアルゴリズムが非常に大事ですが。
ここが履歴チェックです
bool flag = false; for (int j = 0; j < depth + 1; j++) if (history[j] == i) { flag = true; break; } if (flag) continue;
もうちょっと複雑な経路でも探索ができるかしらべてみましょう。
光線飛ばして経路生成なので、ポイントを立体配置しても、経路探索はできるはずなので、それも調べてみます。
wpが各point。dicはpoint名称からwpの要素番号を引く連想配列。pathは通行可能なpointの二組の配列。
historyは、これまでの探索経路。pointのtagはFinishにしてください。
using UnityEngine; using System.Collections; using System.Collections.Generic; using UnityEngine.UI; public class Navi : MonoBehaviour { List<GameObject> wp; Dictionary<string,int> dic = new Dictionary<string, int>(); bool[,] path = new bool[10, 10]; int[] history = new int[100]; string ret; void Start () { wp = new List<GameObject>(); int no =0; foreach (GameObject n in GameObject.FindGameObjectsWithTag("Finish")) { dic.Add( n.name,no++); wp.Add(n); } makePath(); ret = ""; for (int i = 1; i < 5; i++) { ret = ""; search(dic["Navi (2)"], dic["Navi (5)"], 0, i); } GameObject.Find("/Canvas/Text").GetComponent<Text>().text = ret; } void Update () { } void search(int sp,int dp,int depth,int limit) { if (depth >= limit) { indent(depth); ret += "->limit\n"; return; } history[depth] = sp; if (path[sp, dp] == true) { history[depth + 1] = dp; indent(depth); ret += wp[sp].name+"->" + wp[dp].name + ":GOAL dist="+CalcDistance(depth+1)+"\n"; return; } for(int i=0;i<10;i++) { if (sp == i) continue; bool flag = false; for (int j = 0; j < depth + 1; j++) if (history[j] == i) { flag = true; break; } if (flag) continue; if( path[sp,i]==true) { indent(depth); ret += wp[sp].name+"->" + wp[i].name; // ret += " !"; // for (int j = 0; j < depth+1; j++) ret += wp[history[j]].name+"|"; ret += "\n"; search(i, dp,depth+1,limit); } } } void indent(int depth) { for (int i = 0; i < depth; i++) ret += " "; } float CalcDistance(int depth) { float dist = 0; for (int j = 1; j <= depth + 1; j++) { dist += Vector3.Distance(wp[history[j-1]].transform.position, wp[history[j]].transform.position); } return dist; } void makePath() { RaycastHit hit; int layerMask = LayerMask.GetMask("Water"); for (int i=0;i<wp.Count;i++) { for (int j = i+1; j < wp.Count; j++) { Vector3 sp = wp[i].transform.position; Vector3 dp = wp[j].transform.position; Vector3 dir = (dp-sp).normalized; // if (!Physics.SphereCast(sp,0.5f,dir,out hit, 100f,layerMask)) if (!Physics.Linecast(sp, dp, out hit, layerMask)) { Debug.Log(wp[i].name + "->" + wp[j].name + "=OK"); path[i, j] = path[j, i] = true; GameObject gm =Instantiate((GameObject)Resources.Load("point"), sp, Quaternion.identity) as GameObject; LineRenderer LR; LR = gm.GetComponent<LineRenderer>(); LR.enabled = true; LR.SetWidth(.2f, .2f); LR.SetVertexCount(2); LR.SetPosition(0, sp); LR.SetPosition(1, dp); } else { path[i, j] = path[j, i] = false; Debug.Log(wp[i].name + "->" + wp[j].name + "=NG"); } } } } }