3DUnity NavmeshAgentに高低差のあるマップ内で到達可能な座標をランダムで渡してあげたい

Question

前提・実現したいこと

タイトルの通り、NavmeshAgentに高低差のあるマップ内で到達可能な座標をランダムで渡してあげたいです。
マップは高低差があり、形が変わったりはしないです。

実装は出来ているのですが、さらにいい方法が無いかお聞きしたいです。

2通りの実装が出来ていますが、それぞれ欠点があり悩んでいます。

1つ目
マップ内の大きさを取って置き、その範囲からランダムで決める
メリット:
マップの四隅?が分かればその範囲内でランダムで座標を決められる
デメリット:
マップの四隅の隅々までnavmeshがあるならともかく
高低差があったり範囲内に隙間が多くなったりすると複数検索を掛けなくてはならず結構処理も重くなる

2つ目
マップ内に予め目的地候補のオブジェクトを置いてそこからランダムで選ぶ
メリット:
自分でマップ周辺に置いてあるので余程外した位置に置かなければ1回の検索で100%当てられる
デメリット:
予めオブジェクトを置くのが大変
今後マップは拡張していくのでその度にオブジェクト追加するのは...とか思ってます。

マップ内に予め目的地候補のオブジェクトを置いてそこからランダムで選ぶ

今行っている実装方法

一つ目の方法

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

// マップ内の大きさを取って置き、その範囲からランダムで決める
public class AutoMove : MonoBehaviour
{
    private Vector3 nagativeMapRange = new Vector3(-9f, 0, -19f);
    private Vector3 positiveMapRange = new Vector3(27f, 6, 19f);

    private NavMeshAgent agent;
    private float searchRange = 1f;
    private int maxSearchCount = 100;

    private void Start()
    {
        agent = GetComponent<NavMeshAgent>();
        agent.isStopped = false;
    }

    private void Update()
    {
        if (agent.hasPath == false && agent.pathPending == false)
        {
            agent.destination = GetNextDestination();
        }
    }

    // 次の目的地を探す
    // ランダムで座標を決めるので複数回チャレンジする
    // 1回の時もあれば30回探す時も...
    private Vector3 GetNextDestination()
    {
        NavMeshHit navMeshHit;

        for (int i = 0; i < maxSearchCount; i++)
        {
            Vector3 rndPos = new Vector3(
                Random.Range(nagativeMapRange.x, positiveMapRange.x),
                Random.Range(nagativeMapRange.y, positiveMapRange.y),
                Random.Range(nagativeMapRange.z, positiveMapRange.z));

            if (NavMesh.SamplePosition(rndPos, out navMeshHit, searchRange, NavMesh.AllAreas) == true)
            {
                Debug.Log($"{i}回目で目的地発見");
                return navMeshHit.position;
            }
        }

        Debug.LogWarning("目的地見つからなかった★");
        return Vector3.zero;
    }
}

二つ目の方法

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

// マップ内に予め目的地候補のオブジェクトを置いてそこからランダムで選ぶ
public class AutoMove : MonoBehaviour
{
    private List<Vector3> destinationPoints = new List<Vector3>();
    private NavMeshAgent agent;
    private System.Random rnd = new System.Random();

    private int destParentChildCount;
    private float searchRange = 1f;

    private void Start()
    {
        agent = GetComponent<NavMeshAgent>();
        Transform destParent = GameObject.FindGameObjectWithTag("DestinationParent").transform;
        destParentChildCount = destParent.childCount;

        for (int i = 0; i < destParentChildCount; i++)
        {
            destinationPoints.Add(destParent.GetChild(i).transform.position);
        }
    }

    private void Update()
    {
        if (agent.hasPath == false && agent.pathPending == false)
        {
            agent.destination = GetNextDestination();
        }
    }

    // 次の目的地を探す
    // 余程でたらめな場所に置かなければ反応する
    private Vector3 GetNextDestination()
    {
        int rndIndex = rnd.Next(0, destParentChildCount - 1);
        Vector3 targetPoint = destinationPoints[rndIndex];

        NavMeshHit navMeshHit;
        if (NavMesh.SamplePosition(targetPoint, out navMeshHit, searchRange, NavMesh.AllAreas) == true)
        {
            Debug.Log("目的地発見");
            return navMeshHit.position;
        }

        Debug.LogWarning("目的地見つからなかった★");
        return Vector3.zero;
    }
}

Answer 1

直接的なアプローチならNavmeshのエリアからランダムな点を計算してしまうというやり方が考えられます。ちょっと調整しないと難しそうですけど

たとえば下記のスクリプトはマウスクリックしている間、Navmesh有効な位置にCubeをひたすら生成していきます（生成しているのは位置を視覚的に分かりやすくするため）
私の環境だとNavmeshから少しはみ出す奴もいたので、ここで座標を割り出したあとにNavmeshに収まるかどうかをダブルチェックしたほうが良いかもしれません。

たとえばNavMesh.SamplePositionを使うと指定した範囲内の NavMesh で最も近い点を探せるのでそういうのを組み合わせてもらうとか。あとはRaycastとかでそもそも地面存在しているかチェックするとか。

参考：https://answers.unity.com/questions/857827/pick-random-point-on-navmesh.html

参考：https://answers.unity.com/questions/475066/how-to-get-a-random-point-on-navmesh.html

※こっちは自分を中心とした指定の範囲からランダムな位置を取得する方法です。参考までに

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

public class NavTest : MonoBehaviour
{
    private void Update() {
        if (Input.GetMouseButton(0)) {
            var obj = GameObject.CreatePrimitive(PrimitiveType.Cube);
            obj.transform.position = GetRandomLocation();
        }
    }

    Vector3 GetRandomLocation() {
        NavMeshTriangulation navMeshData = NavMesh.CalculateTriangulation();

        // Pick the first indice of a random triangle in the nav mesh
        int t = Random.Range(0, navMeshData.indices.Length - 3);

        // Select a random point on it
        Vector3 point = Vector3.Lerp(navMeshData.vertices[navMeshData.indices[t]], navMeshData.vertices[navMeshData.indices[t + 1]], Random.value);
        Vector3.Lerp(point, navMeshData.vertices[navMeshData.indices[t + 2]], Random.value);

        return point;
    }
}

Comments

[paraprara]

ありがとうございます。
上記のコードを参考に自分で納得いくコードが出来ました。
どうしても頂点の密度に左右されてしまいますが、その際は他の回答者様から頂いた方法を使用しようと思います。

```
Vector3 GetRandomLocation()
{
NavMeshTriangulation navMeshData = NavMesh.CalculateTriangulation();
// random 0~Navmeshに存在する面数
int t = Random.Range(0, navMeshData.areas.Length - 1);
Vector3 triVertsTotalPos = Vector3.zero;

// 面[i]番の中心を測る
for(int i = 0; i < 3; i++)
{
triVertsTotalPos += navMeshData.vertices[navMeshData.indices[t * 3 + i]];
}
Vector3 point = triVertsTotalPos / 3;

return point;
}
```

[Bongo]

頂点の密度によって分布が偏るのが困るようでしたら、面を選択する時に「メッシュ表面のランダムな座標を計算する　前編 - おねむゲーマーの備忘録」（https://sleepygamersmemo.blogspot.com/2019/01/random-point-on-mesh-surface.html ）のような感じで面の面積に比例した重みでランダムに選ぶようにする...というのも試す価値があるんじゃないかと思います。
ランダム選択のたびに重みを計算するのだと処理コストがかさんでしまうでしょうが、NavMeshがゲーム実行中に変化しないのでしたら、記事中にある下ごしらえをゲーム開始時にでも済ませておけばかなり効率化できるんじゃないでしょうか。

[paraprara]

こんなやり方もあるものなんですね...
この方法ならばどのマップでも均等に配置できます！
ありがとうございました！

Answer 2

話がよくわかりませんが，

1つ目

の方法で，「（乱数で選んだ）任意の場所の可否を判断できる」のであれば，
ある時点において，あらかじめ「OKな場所のリスト」みたいなのを作っておくことができるように思えます．

そのような初期処理の結果さえ持っておけるならば，
「リストから乱数で選び出す」で済むように思えます．

Comments

[paraprara]

いえ、一つ目の方法は決して100%たどり着ける座標を持っているわけではありません。

そもそも目的の決め方として
1.目的地を探す種となる座標を決める
2.その周辺にnavmeshを検索(Navmesh.SamplePosition())してその地点を目的地としています

そこで1つ目の方法ではマップの範囲線内(上記画像でいうとマップを囲っているあの長方形のBOX内)の座標をランダムで決めて、その周辺にnavmeshがあるか探しています。

例) 最小座標X:-8 最小座標X:8 最小座標Y:0 最小座標Y:9 最小座標Z:-4 最大座標Z:12 のマップ
これらの値があれば、(-8,0,-4)~(8,9,12)の範囲でランダムで座標を選べます。
そうするとマップの範囲線内のランダムな値を確実に得ることが出来ますが
その周辺にnavmeshがあるとは限らないのです...
例えば、上の画像内のマップ、端っこは結構スカスカですよね？
しかもnavmeshを検索するのに必要なNavmesh.SamplePosition()ですが検索する範囲はあまり大きく出来ません。今のところ1mです。
基本的に1回の検索ではヒットしないので、何回も検索する必要があるのですがこれが結構重いので1つ目のやり方はここが問題なのです。

[paraprara]

すみません、何か勘違いしていたようです。
>> 1つ目の方法で，「（乱数で選んだ）任意の場所の可否を判断できる」のであれば，
ある時点において，あらかじめ「OKな場所のリスト」みたいなのを作っておくことができるように思えます．

つまり最初にnavmeshをランダムである程度の数検索しておき、そこからランダムで決めるべきと言う事でしょうか？
それでしたら確かにいい方法と思います。
ただかなりの数の座標を持たないと目的地が大きく偏ってしまうのでは..とは思いますが
毎回検索するより軽そうで良いですね。一回で出来ますし。

[fana]

> ただかなりの数の座標を持たないと目的地が大きく偏ってしまうのでは..とは思いますが

これは「２つ目」の方法にも言えることですよね．
つまりこの回答は，「２つ目」でいうところの目的地候補を手動じゃなくて自動で用意する，みたいな話になりますね．

[fana]

持っておくのは別に「座標」じゃなくてもいいですし．
例えば「この範囲内であればどこでもOK」みたいな範囲のリストとかでもいいかもしれません．
これなら，乱数で選んだ範囲内についてさらに乱数で座標を選ぶ形になります．
リストの要素数を削減できるでしょう．（リストを作る処理は大変かもですけど）

[paraprara]

なるほど、確かに何も全体指定する必要は無いですね...
図のように四角い部屋がのみのマップならかなり楽にはなりますね。
ありがとうございました！