- Home /
Error with the bfs algorithm That I can not understand
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
private void List<NodeScript>(Breadthwise,(NodeScript start, NodeScript end))
is not a valid syntax. More like:
private List<NodeScript> Breadthwise ( NodeScript start , NodeScript end )
Thanks now there is no error but the code does not work I tried to check where the problem is so I divided the code into numbers and saw in the consile that for numbers 7 and 8 it does not go in so it says the problem is in lines 55 to 65
I would love if you could help me understand why
the problem is in lines 60 to 70 I resent the code below
If you have problems understanding how this code works then it's a sign it is not a solution you need. Try nav meshes instead - those are reasonably fast, proven and ready to use.
If nav meshes don't fit your use case, then there is plenty of open-source node-based pathfinding implementations on the github, for example this one.
I do not want to use one ready I want to succeed the code I built because I fabricated on it for a long time
Answer by andrew-lukasik · Jun 21, 2021 at 01:21 PM
Your code works fine.
The only thing you were doing wrong is interpreting the results.
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
}
I did not understand what I need to change for it to work because for me the list of results at the end remains empty
Maybe your scene contained nodes that were disconnected from the rest of the graph thus preventing completion.
Definitely download assets I attached then. It contains a scene where your code works fine.
Your answer
![](https://koobas.hobune.stream/wayback/20220613035308im_/https://answers.unity.com/themes/thub/images/avi.jpg)