AI getting stuck into corner of the map

Unity Engine
,
1

Hello everyone! I use Ai Behaviors Made Easy for my game development. I was going to ask how can I stop Ai from becoming forced into the corners of a map when it’s fleeing from player,so it doesn’t look like it’s “running in place”? How can I start improving the flee state, so it’s more realistic - so the player cant force the ai into the corners of the map when it’s fleeing? How that would look in a script? I’m guessing I have to use raycast so the Ai detects when it’s close to a wall or corner of the map and so it needs to create a new waypoint (away from the player)? Please help me out!

Here’s what I mean : - Find & Share on GIPHY

2

A quick and dirty way to deal with this problem would be to place colliders at the edge of the map and have the agent avoid those areas if they trigger it. To me though this looks more like a bit of a raycast solution where your agent should detect how far away it is from the ledge you’ve got so it knows that it exists.The reason this is happening is because the agent doesn’t really know that the barrier exists, so naturally it’s going to be dumb and just keep running in that direction while getting stuck to get away from the player.

When dealing with any kind of NPC or computer ‘player’ you as the programmer have to take into account everything that the player sees and interacts with if you want to make believable enemies. Otherwise they’ll simply break if the player does something unexpected which is why playtesting is so important.

3 Likes
3

There’s no general case that will work 100% of the time.

For instance if you’re blocking the only way out of an area with an enemy inside it, what could he do?

One way that works pretty well is to pre-author a bunch of points around the edge of your level and have the enemy simply choose the farthest one and path towards it until the enemy decides it can relax again and come back. This won’t address the above case of you blocking his way or otherwise waiting for him at a turn, but it’s a better way than just pure “run away,” which as you noted leads to corner-heading.

1 Like
4

Can someone please provide a script example?

5

I see. And thank you for your response. Can you provide an example of how that would look in code though?

6

Just look up the raycast documentation and tutorials, then it’s just a matter of placing the raycast correctly and using tags. It’s the same concept as when you learn to shoot with a raycast, you’re just using it in a different way.

1 Like
7

Hi Lethn, I found a way to DETECT when the Ai is CLOSE to the corner of the map. Once it’s close enough, then, Debug.Log (‘‘Message’’);. However I dont know how can i set the ai’s waypoint AWAY from that edge and also ,then, AWAY from the player. Here’s the code I found works so far :

                    UnityEngine.AI.NavMeshHit hit;
                    float distanceToEdge = 1;


                    if (UnityEngine.AI.NavMesh.FindClosestEdge(transform.position, out hit, UnityEngine.AI.NavMesh.AllAreas))
                    {
                        distanceToEdge = hit.distance;
                    }

                    if (distanceToEdge < 1f)
                    {
                        Debug.Log("Corner");
                    }
8

An option among others for selecting a position away from the player on the navmesh is to select a navmesh vertex that is far away from the pursuer, and apply an offset so that the waypoint stay inside the navmesh instead of being on the vertex.

1 Like
9

Actually this method only finds edges not the actual corners. Is there a way for it to detect CORNERS only?

10

If Unity do not provide a built-in solution for detecting corners you can always implement a clean navmesh edges detection that do not only return the nearest, in which case you have a corner when you detect 2 or more edges in the detection radius which are facing each other, with an angle threshold as parameter. Or if you are only interested in L shape corners, not any too tight passage way that your NPC cant get through, you can restrict this edges detection to edges that are adjacents. You can also bake L shapes corners so that at run time it’s just a matter of checking distances from these baked corners positions.

1 Like
11

Hi and thank you for your response. Can you please provide script example? Would love to see how that would look in a code.

12

Let say your detection return these 2 edges:
Vector3 e0;
Vector3 e1;
Vector3 up = Vector3.up;

  • They are facing each other if 0 <= Vector3.Angle( e1, e2, up ) <= threshold

(Do not take it literally, you have to make sure that the edges vectors are computed in such a way that the angle reflect the corner one)

1 Like
13

I made you an exemple:

When you press Play, the class NavMeshAnalytics computes 3 things:

  • bake NavMesh boundaries edges (blue lines in the screenshot)
  • bake NavMesh areas that are layer ignoring (blue lines in the screenshot)
  • bake corners (yellow spheres in the screenshot)

You can know if you are near a corner with NavMashAnalytics.IsNearCorner( Vector3 pos, float dist ). Or you can create triggers from code at these locations.

Link to sample project is here: https://drive.google.com/file/d/1NIMtkMJqXgQXyXCBfG0eLKGEZEMpYIPv/view?usp=sharing

PS: if your level is moving, you of course first convert pos in the navmesh local space. (Games like God Of War have moving nav meshes that follow moving level chunks). But Unity is mainly a toy, so it’s possible it only supports static nav meshes as the navmesh baking tool suggest.

7749402--974925--screenshot.jpg
7749402--974925--screenshot.jpg1499×917 194 KB

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

//************************************************************************************
//
//************************************************************************************

public class NavMeshAnalytics : MonoBehaviour
{
    //********************************************************************************
    //
    //********************************************************************************

    public struct Edge { public int v0, v1; public Edge( int param_v0, int param_v1 ) { v0 = param_v0; v1 = param_v1; } }

    public struct Area { public List< int > edges; }

    //********************************************************************************
    //
    //********************************************************************************

    static private NavMeshTriangulation NAVMESH_DATAS      = default;

    static private List< Edge >         NAVMESH_BOUNDARIES = new List< Edge     >( 8  );

    static private List< Area >         NAVMESH_AREAS      = new List< Area     >( 8  );

    static private List< Vector3  >     NAVMESH_CORNERS    = new List< Vector3  >( 64 );

    //********************************************************************************
    //
    //********************************************************************************

    static public void Clear()
    {
        NAVMESH_BOUNDARIES.Clear();

        NAVMESH_AREAS.Clear     ();

        NAVMESH_CORNERS.Clear   ();
    }

    //********************************************************************************
    //
    //********************************************************************************

    static public void Bake()
    {
        Clear();

        NAVMESH_DATAS = NavMesh.CalculateTriangulation();

        BakeBoundaries();

        BakeAreas     ();
                 
        BakeCorners   ();
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private bool TriContains( Vector3[] verts, int[] tris, int t, int v )
    {
        if( verts == null )
        {
            if( v == tris[ t     ] ) return true;

            if( v == tris[ t + 1 ] ) return true;

            if( v == tris[ t + 2 ] ) return true;
        }
        else
        {
            Vector3 pos = verts[ v ];

            if( pos == verts[ tris[ t     ] ] ) return true;

            if( pos == verts[ tris[ t + 1 ] ] ) return true;

            if( pos == verts[ tris[ t + 2 ] ] ) return true;
        }


        return false;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private List< int > GetAdjacentTris( int[] tris, int v )
    {
        List< int > result = new List< int >( 8 );

        for( int t = 0, nb_tris = tris.Length; t < nb_tris; t += 3 )
        {
            if( TriContains( null, tris, t, v ) ) result.Add( t );
        }

        return result;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private bool EdgesAreConnected( Vector3[] verts, Edge e0, Edge e1 )
    {
        if( verts == null )
        {
            if( ( e0.v0 == e1.v0 ) || ( e0.v0 == e1.v1 ) ) return true;

            if( ( e0.v1 == e1.v0 ) || ( e0.v1 == e1.v1 ) ) return true;
        }
        else
        {
            Vector3 e0_v0 = verts[ e0.v0 ];

            Vector3 e1_v0 = verts[ e1.v0 ];

            Vector3 e1_v1 = verts[ e1.v1 ];

            if( ( e0_v0 == e1_v0 ) || ( e0_v0 == e1_v1 ) ) return true;


            Vector3 e0_v1 = verts[ e0.v1 ];

            if( ( e0_v1 == e1_v0 ) || ( e0_v1 == e1_v1 ) ) return true;
        }

        return false;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private bool IsBoundaryEdge( Vector3[] verts, int[] tris, int t, int v0, int v1 )
    {
        for( int other = 0, nb_tris = tris.Length; other < nb_tris; other += 3 )
        {
            if( other != t )
            {
                if( TriContains( verts, tris, other, v0 ) && TriContains( verts, tris, other, v1 ) )
                {
                    return false;
                }
            }
        }

        return true;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private List< Edge > GetBoundaryEdges( Vector3[] verts, int[] tris )
    {
        List< Edge > edges = new List< Edge >( 16 );

        for( int t = 0, nb_tris = tris.Length; t < nb_tris; t += 3 )
        {
            Edge e0 = new Edge( tris[ t     ], tris[ t + 1 ] );

            Edge e1 = new Edge( tris[ t + 1 ], tris[ t + 2 ] );

            Edge e2 = new Edge( tris[ t + 2 ], tris[ t     ] );

            if( IsBoundaryEdge( verts, tris, t, e0.v0, e0.v1 ) ) edges.Add( e0 );

            if( IsBoundaryEdge( verts, tris, t, e1.v0, e1.v1 ) ) edges.Add( e1 );

            if( IsBoundaryEdge( verts, tris, t, e2.v0, e2.v1 ) ) edges.Add( e2 );
        }

        return edges;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private bool GetNextConnectedEdge( Vector3[] verts, List< Edge > edges, int e_bgn, ref int e_cur, BitArray consumed )
    {
        for( int other = 0, count = edges.Count; other < count; ++other )
        {
            if( consumed.Get( other ) == false )
            {
                if( EdgesAreConnected( verts, edges[ e_cur ], edges[ other ] ) )
                {
                    e_cur = other;

                    return   true;
                }
            }
        }

        return false;
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private void BakeBoundaries()
    {
        NAVMESH_BOUNDARIES.Clear();

        NAVMESH_BOUNDARIES = GetBoundaryEdges( NAVMESH_DATAS.vertices, NAVMESH_DATAS.indices );

        Debug.Log( $"NavmeshAnalytics: baked {NAVMESH_BOUNDARIES.Count} boundary edges" );
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private void BakeAreas()
    {
        NAVMESH_AREAS.Clear();

        Vector3[]   verts = NAVMESH_DATAS.vertices;

        BitArray consumed = new BitArray( NAVMESH_BOUNDARIES.Count );

        for( int e = 0, count = NAVMESH_BOUNDARIES.Count; e < count; ++e )
        {
            if( consumed.Get( e ) == false )
            {
                Area  area = new Area();

                area.edges = new List< int >( 16 );

                NAVMESH_AREAS.Add( area );


                int e_bgn = e;

                int e_cur = e;

                area.edges.Add( e_bgn );

                consumed.Set( e_bgn, true );

                while( GetNextConnectedEdge( verts, NAVMESH_BOUNDARIES, e_bgn, ref e_cur, consumed ) )
                {
                    area.edges.Add( e_cur );

                    consumed.Set( e_cur, true );
                }

                for( int E = 0; E < area.edges.Count; ++E )
                {
                    int  i0 = area.edges[ E ];

                    int  i1 = area.edges[ ( E + 1 ) % area.edges.Count ];

                    Edge e0 = NAVMESH_BOUNDARIES[ i0 ];

                    Edge e1 = NAVMESH_BOUNDARIES[ i1 ];

                    if( verts[ e0.v1 ] != verts[ e1.v0 ] )
                    {
                        int tmp = e1.v1;

                        e1.v1 = e1.v0;

                        e1.v0 = tmp;

                        NAVMESH_BOUNDARIES[ i1 ] = e1;
                    }
                }
            }
        }

        Debug.Log( $"NavmeshAnalytics: baked {NAVMESH_AREAS.Count} areas" );
    }

    //********************************************************************************
    //
    //********************************************************************************

    static private void BakeCorners()
    {
        NAVMESH_CORNERS.Clear();

        Vector3[] verts = NAVMESH_DATAS.vertices;

        for( int a = 0; a < NAVMESH_AREAS.Count; ++a )
        {
            Area area = NAVMESH_AREAS[ a ];

            for( int e = 0; e < area.edges.Count; ++e )
            {
                Edge    e0 = NAVMESH_BOUNDARIES[ area.edges[ e ] ];
                   
                Edge    e1 = NAVMESH_BOUNDARIES[ area.edges[ ( e + 1 ) % area.edges.Count ] ];

                Vector3 s0 = ( verts[ e0.v1 ] - verts[ e0.v0 ] );

                Vector3 s1 = ( verts[ e1.v1 ] - verts[ e1.v0 ] );

                if( ( 180f - Vector3.Angle( s0, s1 ) ) <= 90.0f )
                {
                    NAVMESH_CORNERS.Add( verts[ e0.v1 ] );
                }
            }
        }

        Debug.Log( $"NavmeshAnalytics: baked {NAVMESH_CORNERS.Count} corners" );
    }

    //********************************************************************************
    //
    //********************************************************************************
 
    static public bool IsNearCorner( Vector3 pos, float dist )
    {
        float sqr_dist = dist * dist;

        for( int c = 0; c < NAVMESH_CORNERS.Count; ++c )
        {
            Vector3 corner = NAVMESH_CORNERS[ c ];

            Vector3 sep    = corner - pos;

            if( sep.sqrMagnitude < sqr_dist ) return true;
        }

        return false;
    }
 
    //********************************************************************************
    //
    //********************************************************************************

    private void Awake() { Bake(); }

    //********************************************************************************
    //
    //********************************************************************************

    private void OnDrawGizmos()
    {
        Color restore = Gizmos.color;

            Vector3[] verts = NAVMESH_DATAS.vertices;

                int[]  tris  = NAVMESH_DATAS.indices;

            int    nb_verts = ( verts != null ) ? verts.Length : 0;

            int    nb_tris  = ( tris  != null ) ? tris.Length  : 0;

            if( nb_verts > 0 )
            {
                Gizmos.color  = Color.red;

                Vector3  size = Vector3.one * 0.2f;

                for( int v = 0; v < nb_verts; ++v )
                {
                    Gizmos.DrawCube( verts[ v ], size );
                }


                Gizmos.color = Color.blue;

                for( int a = 0; a < NAVMESH_AREAS.Count; ++a )
                {
                    Area area = NAVMESH_AREAS[ a ];

                    for( int e = 0; e < area.edges.Count; ++e )
                    {
                        Edge edge = NAVMESH_BOUNDARIES[ area.edges[ e ] ];

                        Gizmos.DrawLine( verts[ edge.v0 ], verts[ edge.v1 ] );
                    }
                }


                Gizmos.color = Color.yellow;

                for( int c = 0; c < NAVMESH_CORNERS.Count; ++c )
                {
                    Gizmos.DrawSphere( NAVMESH_CORNERS[ c ], 0.5f );
                }
            }

        Gizmos.color = restore;
    }
}
1 Like
14

I had totally forgot about that.

Here: https://drive.google.com/file/d/1NIMtkMJqXgQXyXCBfG0eLKGEZEMpYIPv/view?usp=sharing
The nearest points on detected edges within the radius parameter are the magenta cubes.

I recommend using a BSP or something in that spirit to speed up edges detection. The order of operations is usually as follow:

  • BSP or similar → edge bounding box/sphere intersection → GetNearestPointOnEdge()

7750956--975198--screenshot1.jpg

    //********************************************************************************
    //
    //********************************************************************************

    static private bool GetNearestPointOnEdge( Vector3 pos, Edge edge, float sqr_dist, ref Vector3 p )
    {
        Vector3 v0 = NAVMESH_DATAS.vertices[ edge.v0 ];

        Vector3 v1 = NAVMESH_DATAS.vertices[ edge.v1 ];

        Vector3 V  = v1  - v0;

        Vector3 v  = pos - v0;

        if     ( Vector3.Dot( v,        V       ) <= 0.0f ) p = v0;

        else if( Vector3.Dot( pos - v1, v0 - v1 ) <= 0.0f ) p = v1;

        else   { Vector3 unit_V = V.normalized; p = v0 + ( Vector3.Dot( v, unit_V ) * unit_V ); }

        return ( p - pos ).sqrMagnitude <= sqr_dist;
    }

    //********************************************************************************
    //
    //********************************************************************************
 
    public struct EdgeHit
    {
        public Vector3 p;
     
        public EdgeHit( Vector3 param_p ) { p = param_p; }
    }

    static public bool FindNearestEdges( Vector3 pos, float dist, ref List< EdgeHit > edges )
    {
        if( edges == null ) edges = new List< EdgeHit >( 8 );

        else                edges.Clear();


        float   sqr_dist = dist * dist;

        Vector3 p = Vector3.zero;

        for( int e = 0, nb_edges = NAVMESH_BOUNDARIES.Count; e < nb_edges; ++e )
        {
            if( GetNearestPointOnEdge( pos, NAVMESH_BOUNDARIES[ e ], sqr_dist, ref p ) )
            {
                edges.Add( new EdgeHit( p ) );
            }
        }

        return edges.Count > 0;
    }
2 Likes
15

Wow. This is phenomenal. More than I could ask for. Thank you. But, I have no idea where to even begin, like it’s complicated and excellent at the same time haha…
I’m having trouble understanding how in the world I would integrate this in the Ai script. Here is the part of the script that makes the ai flee from the player :

case FleeMode.AwayFromNearestTaggedObject:
Vector3 nearestObjectPosition = fsm.GetClosestPlayer(objectFinder.GetTransforms()).position;
Vector3 fsmPosition = fsm.aiTransform.position;
Vector3 direction = (fsmPosition - nearestObjectPosition).normalized * stopFleeDistance;

result = fsmPosition + direction;
break;

Lets just say if the ai reaches the corner of the map, then i would simply want Debug.Log (“message”); (Im going to get to more complicated stuff, like setting waypoints, when it’s near the corner - away from it and away from player, later on). How can I go on about achieving something like that? Can you provide an example with the script I’ve given? Anyway, thank you alot for your help and time, Im going to put this thread on “resolved”, cause, I guess, there’s all I need to make things work. But as of now, can you help me with the integration?

16

To integrate it you add a game object in your test scene and attach the NavMeshAnalytics to it.
From your AI script you can call NavMeshAnalytics.IsNearCorner( this.transform.pos, );
Tweak NavMeshAnalytics accessors and change them from private to public according to your needs.
As you become more comfortable with coding, throw away this exemple and use your own mesh analytics.

1 Like
17

Can you please edit the script example I’ve given you?

18 
case FleeMode.AwayFromNearestTaggedObject:
Vector3 nearestObjectPosition = fsm.GetClosestPlayer(objectFinder.GetTransforms()).position;
Vector3 fsmPosition = fsm.aiTransform.position;
Vector3 direction = (fsmPosition - nearestObjectPosition).normalized * stopFleeDistance;
result = fsmPosition + direction;

if( NavMeshAnalytics.IsNearCorner( fsmPosition, <detection radius> ) )
{
   Debug.Log( "Cornered" );
   select a destination far from nearestObjectPosition
   plot a path to reach destination
   switch to RallyDestinationMode from inside your path calculation completion callback
}
break;

You calc a path with Unity - Scripting API: AI.NavMesh.CalculatePath
You assign a path to your AI with Unity - Scripting API: AI.NavMeshAgent.SetPath
You check the path calc completion with Unity - Scripting API: NavMeshPath and Unity - Scripting API: AI.NavMeshPath.status

1 Like
19

Serge, what is wrong with this script? Why am i getting errors:

error CS0246: The type or namespace name ‘NavMeshAnalytics’ could not be found (are you missing a using directive or an assembly reference?)

error CS0246: The type or namespace name ‘NavMeshAnalytics’ could not be found (are you missing a using directive or an assembly reference?)

error CS0103: The name ‘NavMeshAnalytics’ does not exist in the current context

NavMeshAnalytics navMeshAnalytics;

                    navMeshAnalytics = GameObject.FindGameObjectWithTag("Game").GetComponent<NavMeshAnalytics>();

                    if (NavMeshAnalytics.IsNearCorner(fsmPosition, 5 ))
                    {
                        Debug.Log("Cornered");
                    }
20

Never mind. Moved the NavMeshAnalytics script to the same folder as the ai flee state script. Now it works! Thank you for everything! Good luck to you.