- Home /
DFS & BFS help needed
Hello everyone,
I have been asking before about a Tree structure waypoint system and the awnsers helped me alot. Now i run into the next point. I made a bfs and dfs function to test them both out and they sort of work the problem i have is that i also have waypoints that link with each other so there are multiple options to run. Anyone a good idea how i could fix this best.
Thx already for the help this is my code:
[Serializable]
public class TreeNode
{
public string value;
public List<TreeNode> children;
public TreeNode( string s )
{
value = s;
children = new List<TreeNode>();
}
public List<TreeNode> FindPath(TreeNode target)
{
List<TreeNode> path = new List<TreeNode>();
path.Add(this);
if (target == this)
{
return path;
}
foreach (TreeNode tn in children)
{
List<TreeNode> childPath = tn.FindPath(target);
if (childPath != null)
{
path.AddRange(childPath);
return path;
}
}
return null;
}
}
public class DFSTest : MonoBehaviour
{
public GameObject startPoint;
private GameObject gameObjectHolder;
private Queue<TreeNode> tnQueue = new Queue<TreeNode>();
public List<string> testList = new List<string>();
public List<TreeNode> root = new List<TreeNode>();
private TreeNode target;
private List<string> treeNodeNames = new List<string>();
private void OnMouseDown()
{
DFSearch();
}
void BFSearch()
{
tnQueue = new Queue<TreeNode>();
treeNodeNames = new List<string>();
tnQueue.Enqueue(new TreeNode(startPoint.GetComponent<InfoHolder>().Infos.str));
treeNodeNames.Add(tnQueue.Peek().value);
LoopFunctionBF(startPoint);
}
void LoopFunctionBF(GameObject holderObject)
{
while (tnQueue.Count>0)
{
TreeNode tn = tnQueue.Dequeue();
testList.Add(tn.value);
if (tn.value == "g2")
{
print("found it");
return;
}
foreach (GameObject treeNode in holderObject.GetComponent<InfoHolder>().Infos.NextInLineList)
{
var holder = treeNode.GetComponent<InfoHolder>().Infos.str;
if (!treeNodeNames.Contains(holder))
{
tnQueue.Enqueue(new TreeNode(holder));
treeNodeNames.Add(holder);
print(treeNode.GetComponent<InfoHolder>().Infos.str);
LoopFunctionBF(treeNode);
}
}
}
}
void DFSearch()
{
root = new List<TreeNode>();
treeNodeNames = new List<string>();
root.Add(new TreeNode(startPoint.GetComponent<InfoHolder>().Infos.str));
treeNodeNames.Add(root[0].value);
LoopFunctionDF(startPoint, root[0].children);
if (root[0].children.Count > 0 && root[0].children[0].children.Count != 0)
{
target = root[0].children[1].children[0].children[0].children[0].children[0].children[0].children[0];
}
else if (root[0].children.Count > 0)
{
target = root[0].children[0];
}
else
{
return;
}
List<TreeNode> path = root[0].FindPath(target);
string stringPath = "";
foreach (TreeNode treeNode in path)
{
if (treeNode != root[0])
{
stringPath += "->";
}
stringPath += treeNode.value;
}
Debug.Log(stringPath);
}
private void LoopFunctionDF(GameObject checkObject, List<TreeNode> tnList)
{
foreach (GameObject o in checkObject.GetComponent<InfoHolder>().Infos.NextInLineList)
{
string oHolder = o.GetComponent<InfoHolder>().Infos.str;
bool containsObject = treeNodeNames.Contains(oHolder);
if (oHolder == "g2")
{
treeNodeNames.Add(oHolder);
tnList.Add(new TreeNode(oHolder));
print("found target");
return;
}
if (!containsObject)
{
print(oHolder);
treeNodeNames.Add( oHolder );
tnList.Add(new TreeNode(oHolder));
LoopFunctionDF(o, tnList.Last().children);
}
}
}
}
It's atm testing code so lil bit messy but it should be readable.
Comment
Best Answer
Answer by DanielJF · Mar 17, 2014 at 04:02 PM
Fixed it i forgot some connections in the inspector.