Error with the bfs algorithm That I can not understand

Question

I use the bfs algorithm to find the shortest way to get from point to point the points are scattered on the map but I have Error that I can not understand

botAiScript.cs

 public class botAiScript : MonoBehaviour
 {
     public List<NodeScript> AllNodes = new List<NodeScript>();
     public NodeScript ClosestNode;
     public NodeScript TargetNode;
     public Transform Target;
     public List<NodeScript> Path;
     public Movement mvmt;
     public float minDist;
     public float maxDist;
     public List<NodeScript> result;
     void Awake()
     {
         //Path = new List<NodeScript>();
         result = new List<NodeScript>();
         AllNodes = FindObjectsOfType<NodeScript>().ToList();
     }
     NodeScript GetClosestNodeTo(Transform t)
     {
         Debug.Log("2");
         NodeScript fNode = null;
         float minDistance = Mathf.Infinity;
         foreach (var node in AllNodes)
         {
             float distance = (node.transform.position - t.position).sqrMagnitude;
             if (distance < minDistance)
             {
                 minDistance = distance;
                 fNode = node;
             }
         }
         return fNode;
     }
     private List<NodeScript> Breadthwise(NodeScript start, NodeScript end)
     {
         Debug.Log("3");
         result = new List<NodeScript>();
         List<NodeScript> visited = new List<NodeScript>();
         Queue<NodeScript> work = new Queue<NodeScript>();
 
         start.history = new List<NodeScript>();
         visited.Add(start);
         work.Enqueue(start);
 
         while (work.Count > 0)
         {
             Debug.Log("4");
             NodeScript current = work.Dequeue();
             if (current == end)
             {
                 //Found Node
                 result = current.history;
                 result.Add(current);
                 return result;
                 Debug.Log("5");
             }
             else
             {
                 //Didn't find Node
                 Debug.Log("6");
                 for (int i = 0; i < current.neighbors.Length; i++)
                 {
                     Debug.Log("7");
                     NodeScript currentNeighbor = current.neighbors[i];
                     if (!visited.Contains(currentNeighbor))
                     {
                         Debug.Log("8");
                         currentNeighbor.history = new List<NodeScript>(current.history);
                         currentNeighbor.history.Add(current);
                         visited.Add(currentNeighbor);
                         work.Enqueue(currentNeighbor);
                     }
                 }
             }
         }
         //Route not found, loop ends
         return null;
     }
 
     void Update()
     {
         if (!GetClosestNodeTo(Target).Equals(TargetNode))
         {
             Debug.Log("1");
             Breadthwise(GetClosestNodeTo(transform), GetClosestNodeTo(Target));
         }
         //MoveTowardsPath();
     }
 }

NodeScript.cs

 public class NodeScript : MonoBehaviour
 {
     public NodeScript[] neighbors;
     public List<NodeScript> history = new List<NodeScript>();
     public void OnDrawGizmos()
     {
         Gizmos.DrawIcon(transform.position, "blendsampler");
         foreach(var node in history)
         {
             Gizmos.DrawLine(transform.position, node.transform.position);
         }
     }
 }

Thanks for the help

Answer 1

Your code works fine.

The only thing you were doing wrong is interpreting the results.

alt text

SOURCE FILES

AiComponent.cs

 using System.Collections.Generic;
 using UnityEngine;
 
 [ExecuteAlways]
 public class AiComponent : MonoBehaviour
 {
     
     public Transform Target = null;
     public NodeComponent[] AllNodes = null;
     public List<NodeComponent> result = null;
     
     
     void Awake ()
     {
         AllNodes = FindObjectsOfType<NodeComponent>();
     }
 
     void Update ()
     {
         Breadthwise( GetClosestNodeTo(transform) , GetClosestNodeTo(Target) );
     }
 
     #if UNITY_EDITOR
     void OnDrawGizmos ()
     {
         if( result!=null && result.Count>1 )
         {
             Gizmos.color = new Color( 1 , 0 , 0 , 0.8f );
             for( int i=0 ; i<result.Count-1 ; i++ )
             {
                 Gizmos.DrawLine( result[i].transform.position , result[i+1].transform.position );
                 UnityEditor.Handles.Label( result[i].transform.position , $"waypoint #{i}" );
             }
             UnityEditor.Handles.Label( result[ result.Count-1 ].transform.position , $"waypoint #{result.Count-1}" );
             Gizmos.DrawSphere( transform.position , 0.1f );
         }
     }
     #endif
 
     List<NodeComponent> Breadthwise ( NodeComponent start , NodeComponent end )
     {
         // Debug.Log($"Breadthwise( {start} , {end} )");
         result = new List<NodeComponent>();
         var visited = new List<NodeComponent>();
         var work = new Queue<NodeComponent>();
 
         start.history = new List<NodeComponent>();
         visited.Add( start );
         work.Enqueue( start );
 
         // Debug.Log($"work.Count: {work.Count}");
         while( work.Count>0 )
         {
             NodeComponent current = work.Dequeue();
             if( current==end )
             {
                 //Found Node
                 // Debug.Log("Found Node");
 
                 result = current.history;
                 result.Add(current);
 
                 return result;
             }
             else
             {
                 //Didn't find Node
                 // Debug.Log("Didn't find Node");
 
                 for( int i=0 ; i<current.neighbors.Length ; i++ )
                 {
                     // Debug.Log("\t7");
                     NodeComponent currentNeighbor = current.neighbors[i];
                     if( !visited.Contains(currentNeighbor) )
                     {
                         // Debug.Log("\t\t8");
                         currentNeighbor.history = new List<NodeComponent>( current.history );
                         currentNeighbor.history.Add(current);
                         visited.Add(currentNeighbor);
                         work.Enqueue(currentNeighbor);
                     }
                 }
             }
         }
         //Route not found, loop ends
         return null;
     }
 
     NodeComponent GetClosestNodeTo ( Transform t )
     {
         // Debug.Log($"GetClosestNodeTo( {t} )",t);
         Vector3 destination = t.position;
         NodeComponent fNode = null;
         float minDistSq = float.PositiveInfinity;
         foreach( var node in AllNodes )
         {
             float distSq = ( node.transform.position - destination ).sqrMagnitude;
             if( distSq<minDistSq )
             {
                 minDistSq = distSq;
                 fNode = node;
             }
         }
         return fNode;
     }
 
 }

NodeComponent.cs

 using System.Collections.Generic;
 using System.Linq;
 using UnityEngine;
 
 public class NodeComponent : MonoBehaviour
 {
 
     public NodeComponent[] neighbors = new NodeComponent[0];
     public List<NodeComponent> history = new List<NodeComponent>();
 
     #if UNITY_EDITOR
     void OnDrawGizmos ()
     {
         Gizmos.DrawIcon( this.transform.position , "blendsampler" );
         
         Gizmos.color = new Color( 1 , 1 , 1 , 0.1f );
         foreach( var neighbor in neighbors )
             Gizmos.DrawLine( this.transform.position , neighbor.transform.position );
     }
     void OnDrawGizmosSelected ()
     {
         Gizmos.color = new Color( 1 , 0.92f , 0.016f , 1f );
         for( int i=0 ; i<history.Count-1 ; i++ )
                 Gizmos.DrawLine( history[i].transform.position , history[i+1].transform.position );
     }
     [UnityEditor.MenuItem( "CONTEXT/"+nameof(NodeComponent)+"/"+nameof(ConnectSelectedNodes) )]
     [UnityEditor.MenuItem( "GameObject/"+nameof(ConnectSelectedNodes)+" %q" )]
     static void ConnectSelectedNodes ()
     {
         if( Application.isPlaying ) return;
 
         var selected = UnityEditor.Selection.GetFiltered<NodeComponent>( UnityEditor.SelectionMode.TopLevel );
         if( selected.Length<2 ) return;
         UnityEditor.Undo.RecordObjects( selected , nameof(ConnectSelectedNodes) );
 
         foreach( var A in selected )
         foreach( var B in selected )
         if( A!=B )
         {
             if( !A.neighbors.Any( (other) => other==B ) )
             {
                 System.Array.Resize( ref A.neighbors , A.neighbors.Length+1 );
                 A.neighbors[ A.neighbors.Length-1 ] = B;
             }
             UnityEditor.EditorUtility.SetDirty( A );
         }
     }
     #endif
     
 
 }

Error with the bfs algorithm That I can not understand

1 Reply

SOURCE FILES

Your answer

Follow this Question

Related Questions