読者です 読者をやめる 読者になる 読者になる

AIプログラムとかUnityゲーム開発について

探索や学習などを活用したAI系ゲームを作りたいと思います。

簡単コードで光線飛ばして経路探索

f:id:yasu9780:20161122184012p:plain

 簡単な仕組みで自前で経路探索をやってみました。

 画面上の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");
                }
            }
        }
    }
}
広告を非表示にする