0
\$\begingroup\$

The goal is to be able to climb any ledge, even if the ledge is an odd shape. Therefore, I found a script that searches for viable "climb holds" along any mesh of any shape. You can then use these as points for your character to grab on to and shimmy along.

This is that script:

using System.Collections.Generic;
using UnityEngine;



[ExecuteInEditMode]
public class anchorpoints : MonoBehaviour
{
    protected struct Triangle
    {
        public Vector3 v1;

        public Vector3 v2;

        public Vector3 v3;

        public int index;
    }

    protected struct SharedEdge
    {
        public Vector3 v1;

        public Vector3 v2;
    }

    protected struct TrianglePair
    {
        public Triangle t1;

        public Triangle t2;

        public SharedEdge e;
    }

    private const float UP_THRESHOLD = 60f;

    private const float MIN_DIFF = 60f;

    private const float MAX_DIFF = 120f;

    private const float MIN_HH_DIST = 0.2f;

    private const float MIN_TRIANGLE_AREA = 0.1f;

    private const bool DEBUG = false;

    private const bool FULL_HOLD_PASS = false;

    private List<TrianglePair> trianglePairs;

    private Mesh mesh;

    private int[] triangles;

    private Vector3[] vertices;

    private Vector3[] normals;

    private Transform tr;

    private GameObject activeGameObject;

    private void Start()
    {
        Transform[] componentsInChildren = GetComponentsInChildren<Transform>();
        activeGameObject = base.gameObject;
        if (componentsInChildren.Length != 0)
        {
            for (int i = 0; i < componentsInChildren.Length; i++)
            {
                GameObject gameObject = componentsInChildren[i].gameObject;
                if (!gameObject.activeInHierarchy)
                {
                    continue;
                }
                activeGameObject = gameObject;
                tr = gameObject.transform;
                gameObject.tag = "Climbable";
                trianglePairs = new List<TrianglePair>();
                MeshFilter component = gameObject.GetComponent<MeshFilter>();
                if (!(component == null))
                {
                    mesh = component.sharedMesh;
                    triangles = mesh.triangles;
                    vertices = mesh.vertices;
                    normals = mesh.normals;
                    PopulateTrianglePairs();
                    if (trianglePairs.Count > 0)
                    {
                        CrawlMeshForHandholds();
                    }
                }
            }
        }
        else
        {
            tr = base.gameObject.transform;
            base.gameObject.tag = "Climbable";
            trianglePairs = new List<TrianglePair>();
            MeshFilter component2 = base.gameObject.GetComponent<MeshFilter>();
            mesh = component2.sharedMesh;
            triangles = mesh.triangles;
            vertices = mesh.vertices;
            normals = mesh.normals;
            PopulateTrianglePairs();
            if (trianglePairs.Count > 0)
            {
                CrawlMeshForHandholds();
            }
        }
        UnityEngine.Object.DestroyImmediate(this);
    }

    private void PopulateTrianglePairs()
    {
        for (int i = 0; i < triangles.Length; i += 3)
        {
            Vector3 v = tr.TransformPoint(vertices[triangles[i]]);
            Vector3 v2 = tr.TransformPoint(vertices[triangles[i + 1]]);
            Vector3 v3 = tr.TransformPoint(vertices[triangles[i + 2]]);
            int num = 0;
            int num2 = i - 3;
            int num3 = i + 3;
            while ((num2 > 0 || num3 < triangles.Length) && num < 3)
            {
                if (num2 > 0)
                {
                    Vector3 vector = tr.TransformPoint(vertices[triangles[num2]]);
                    Vector3 vector2 = tr.TransformPoint(vertices[triangles[num2 + 1]]);
                    Vector3 vector3 = tr.TransformPoint(vertices[triangles[num2 + 2]]);
                    if (FindSharedEdge(v, v2, v3, vector, vector2, vector3, out SharedEdge e))
                    {
                        num++;
                        Triangle t = default(Triangle);
                        t.v1 = v;
                        t.v2 = v2;
                        t.v3 = v3;
                        t.index = i;
                        Triangle t2 = default(Triangle);
                        t2.v1 = vector;
                        t2.v2 = vector2;
                        t2.v3 = vector3;
                        t2.index = num2;
                        if (!TrianglePairsContains(t, t2))
                        {
                            TrianglePair item = default(TrianglePair);
                            item.t1 = t;
                            item.t2 = t2;
                            item.e = e;
                            trianglePairs.Add(item);
                        }
                    }
                    num2 -= 3;
                }
                if (num3 >= triangles.Length)
                {
                    continue;
                }
                Vector3 vector4 = tr.TransformPoint(vertices[triangles[num3]]);
                Vector3 vector5 = tr.TransformPoint(vertices[triangles[num3 + 1]]);
                Vector3 vector6 = tr.TransformPoint(vertices[triangles[num3 + 2]]);
                if (FindSharedEdge(v, v2, v3, vector4, vector5, vector6, out SharedEdge e2))
                {
                    num++;
                    Triangle t3 = default(Triangle);
                    t3.v1 = v;
                    t3.v2 = v2;
                    t3.v3 = v3;
                    t3.index = i;
                    Triangle t4 = default(Triangle);
                    t4.v1 = vector4;
                    t4.v2 = vector5;
                    t4.v3 = vector6;
                    t4.index = num3;
                    if (!TrianglePairsContains(t3, t4))
                    {
                        TrianglePair item2 = default(TrianglePair);
                        item2.t1 = t3;
                        item2.t2 = t4;
                        item2.e = e2;
                        trianglePairs.Add(item2);
                    }
                }
                num3 += 3;
            }
        }
    }

    private void CrawlMeshForHandholds()
    {
        for (int i = 0; i < trianglePairs.Count; i++)
        {
            TrianglePair trianglePair = trianglePairs[i];
            Vector3 normal = GetNormal(trianglePair.t1);
            Vector3 normal2 = GetNormal(trianglePair.t2);
            Triangle triangle = trianglePair.t1;
            Triangle triangle2 = trianglePair.t2;
            float num = Vector3.Dot(Vector3.up, normal);
            float num2 = Vector3.Dot(Vector3.up, normal2);
            Vector3 vector;
            Vector3 vector2;
            if (num > num2)
            {
                vector = normal;
                vector2 = normal2;
            }
            else
            {
                vector = normal2;
                vector2 = normal;
                triangle = trianglePair.t2;
                triangle2 = trianglePair.t1;
            }
            if (!(Vector3.Angle(Vector3.up, vector) > 60f) && !(Vector3.Angle(vector, vector2) < 60f) && !(Vector3.Angle(vector, vector2) > 120f))
            {
                float y = ((triangle.v1 + triangle.v2 + triangle.v3) / 3f).y;
                if (!(((triangle2.v1 + triangle2.v2 + triangle2.v3) / 3f).y > y))
                {
                    AddHandholds(trianglePair.e, vector, vector2);
                }
            }
        }
    }

    private void AddHandholds(SharedEdge e, Vector3 up, Vector3 fn)
    {
        Vector3 vector = e.v2 - e.v1;
        if (vector.magnitude < 0.2f)
        {
            GameObject gameObject = AddHold(e.v1, up, fn, activeGameObject.transform);
            AddHold(e.v2, up, fn, gameObject.transform);
            return;
        }
        Vector3 normalized = vector.normalized;
        Transform transform = AddHold(e.v1, up, fn, activeGameObject.transform).transform;
        for (float num = 0.2f; num < vector.magnitude; num += 0.2f)
        {
            transform = AddHold(e.v1 + normalized * num, up, fn, transform).transform;
        }
    }

    private GameObject AddHold(Vector3 position, Vector3 up, Vector3 fn, Transform prev)
    {
        GameObject gameObject = new GameObject();
        gameObject.transform.position = position;
        gameObject.tag = "Anchor";
        gameObject.name = "ClimbHold";
        gameObject.layer = 19;
        gameObject.isStatic = true;
        gameObject.transform.rotation = Quaternion.LookRotation(-fn, up);
        gameObject.transform.parent = activeGameObject.transform;
        return gameObject;
    }

    private bool TrianglesEqual(Triangle t1, Triangle t2)
    {
        if (t1.v1 == t2.v1 && t1.v2 == t2.v2)
        {
            return t1.v3 == t2.v3;
        }
        return false;
    }

    private bool TrianglePairsContains(Triangle t1, Triangle t2)
    {
        for (int i = 0; i < trianglePairs.Count; i++)
        {
            TrianglePair trianglePair = trianglePairs[i];
            if ((TrianglesEqual(t1, trianglePair.t1) || TrianglesEqual(t1, trianglePair.t2)) && (TrianglesEqual(t2, trianglePair.t1) || TrianglesEqual(t2, trianglePair.t2)))
            {
                return true;
            }
        }
        return false;
    }

    private bool FindSharedEdge(Vector3 v1, Vector3 v2, Vector3 v3, Vector3 vt1, Vector3 vt2, Vector3 vt3, out SharedEdge e)
    {
        Vector3[] array = new Vector3[3]
        {
                v1,
                v2,
                v3
        };
        Vector3[] array2 = new Vector3[3]
        {
                vt1,
                vt2,
                vt3
        };
        for (int i = 0; i < array.Length; i++)
        {
            for (int j = 0; j < array2.Length; j++)
            {
                if (!(array[i] == array2[j]))
                {
                    continue;
                }
                for (int k = 0; k < array.Length; k++)
                {
                    for (int l = 0; l < array2.Length; l++)
                    {
                        if (k != i && l != j && array[k] == array2[l])
                        {
                            e = default(SharedEdge);
                            e.v1 = array[i];
                            e.v2 = array[k];
                            return true;
                        }
                    }
                }
            }
        }
        e = default(SharedEdge);
        return false;
    }

    private Vector3 GetNormal(Triangle t)
    {
        Vector3 lhs = t.v2 - t.v1;
        Vector3 rhs = t.v3 - t.v2;
        return Vector3.Cross(lhs, rhs).normalized;
    }
}

This is really cool. However, it ends up creating an unreasonable amount of ClimbHold gameobjects in your scene. For instance, a simple 10x10x10 cube will end up as a parent of over 200 ClimbHold gameobjects!

I had an idea to only generate ClimbHolds within a certain Player radius and delete them again when outside of the radius, but this too would create too much overhead. So the question is, what is a good way to find climb hold annotations of meshes in a scene, in a way that still allows for good performance?

\$\endgroup\$
2
  • \$\begingroup\$ This would be a very expensive script to be executing at runtime, every time the player approaches a new mesh or moves around a large one. I don't think your proposal of deleting and re-creating climb holds in a radius is likely to perform well. What I'd recommend instead is getting rid of the overhead of game objects for every climb hold - store them as arrays of points or point-normal pairs instead. Then 200 points is something like 4 kb of memory - nothing you'll miss - and takes up no overhead processing in your scene. Generate at design time and load on demand. \$\endgroup\$
    – DMGregory
    Commented Dec 21, 2022 at 13:59
  • \$\begingroup\$ Thank you. Though, do you have a recommended method for the "load on demand" part? (Not asking for code, just general suggestions) I'm still pretty new to Unity. And, doing a version of this script which outputs arrays instead of GameObjects and then doing "ExecuteInEditMode" might work for the "generate at design time" portion? \$\endgroup\$
    – imdog
    Commented Dec 21, 2022 at 21:08

1 Answer 1

0
\$\begingroup\$

I had an idea to only generate ClimbHolds within a certain Player radius and delete them again when outside of the radius, but this too would create too much overhead. So the question is, what is a good way to find climb hold annotations of meshes in a scene, in a way that still allows for good performance?

The answer is in array reuse and a fast radius calculation.

The radius calculations for each direction on the grid needs to use the Manhattan distance abs(dx) + abs(dy) + abs(dy).

The size of the computed grid array is 1.5 times the max movement speed, rounded up to the next int, in each direction (should be square, or a box circumscribed about the radius, but much faster and known at design time), to allow per-computation time and loading allowance for multiple meshes.

The array would contain an array of ClimbHold instances to be checked against. Obejcts falling into multiple grids are stored multiple times.

When the position moves outside the current grid square, shift the entire array and fill in the missing cells.

The "trick" here is after the initial load computations on the array, only new new elements require computation.

The real risk is in memory fragmentation, but given the released memory is close in size to the new allocated size(if not a different pool will be used, giving the same end effect), fragmentation will be handled by the GC in a uniform manner when needed.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .