koobas.hobune.stream
Waypoint tree structure
Hello everyone! I have a question for a waypoint system that i am building. I want to make a AI that follows a player through way points in a side view envoirment. And we had the idea to make waypoints and link them together so it can check what waypoint each waypoint is connected to.
All the waypoints have waypoint script on them that has a gizmos function and a List off a class of waypoints it is connected too.
The problem is that i don't know how to loop through the objects and save them as a route from begin to end.
Hope that you guys can help me with this.
Put the [1] and [2] links on separate lines - without that, your pics won't show up and we won't be able to help you easily.
Its not entirely clear what you are trying to achieve, but it sounds like a breadth first search might help. http://en.wikipedia.org/wiki/Breadth-first_search
If you've got a list of waypoints then you probably need to use A* to search the links to find the correct route to the player? Is that what you are trying to do?
The pictures should be fixed now sorry for the late reaction. Anyways what i am trying to do is making a waypoint system that has the links in the waypoint self. As you can see in the picture above i hope atleast is that the waypoint script(this is on the waypoint) has a list of connecting waypoint info. In here you can store a waypoint that the current waypoint is connected too. i can already search for the waypoint that is the closest to the Ai and his target and also can find it while looping through all the waypoint connections. $$anonymous$$y problem is that i can 't trace back what waypoints it used too get to his target waypoint.
@EvilWarren this is exactly what i am looking for any tips ? I will be doing research myself in the mean time aswell but every help is welcome ;D
Simple tree example with sample code to run using depth first search. Only the TreeNode class is needed for the search, the other code is to show you how it runs. If this helps mark this as answered to close off the question and thumb up any posters who helped you.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class TreeNode
{
public List<TreeNode> children;
public string value;
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 TreeTest : MonoBehaviour {
// Use this for initialization
void Start () {
TreeNode root, target;
root = new TreeNode("Root");
{
root.children.Add(new TreeNode("a0"));
{
root.children[0].children.Add(new TreeNode("a0b0")); // node 0,0
{
root.children[0].children[0].children.Add(new TreeNode("a0b0c0")); // leaf 0,0,0
root.children[0].children[0].children.Add(new TreeNode("a0b0c1")); // leaf 0,0,1
root.children[0].children[0].children.Add(new TreeNode("a0b0c2")); // leaf 0,0,2
}
root.children[0].children.Add(new TreeNode("a0b1")); // node 0,1
{
root.children[0].children[1].children.Add(new TreeNode("a0b1c0")); // leaf 0,1,0
root.children[0].children[1].children.Add(new TreeNode("a0b1c1")); // leaf 0,1,1
root.children[0].children[1].children.Add(new TreeNode("a0b1c2")); // leaf 0,1,2
}
}
root.children.Add(new TreeNode("a1"));
{
root.children[1].children.Add(new TreeNode("a1b0")); // node 1,0
{
root.children[1].children[0].children.Add(new TreeNode("a1b0c0")); // leaf 1,0,0
{
root.children[1].children[0].children[0].children.Add(new TreeNode("a1b0c0d0")); // leaf 1,0,0,0
}
root.children[1].children[0].children.Add(new TreeNode("a1b0c1")); // leaf 1,0,1
}
}
root.children.Add(new TreeNode("a2"));
{
root.children[2].children.Add(new TreeNode("a2b0")); // node 2,0
{
root.children[2].children[0].children.Add(new TreeNode("a2b0c0")); // leaf 2,0,0
root.children[2].children[0].children.Add(new TreeNode("a2b0c1")); // leaf 2,0,1
}
}
target = root.children[1].children[0].children[1]; // set node to find as leaf 1,0,1
}
List<TreeNode> path = root.FindPath(target);
string stringPath = "";
foreach(TreeNode tn in path)
{
if(tn != root)
{
stringPath += "->";
}
stringPath += tn.value;
}
Debug.Log(stringPath);
}
}
Thx for the code sample i think i can do alot with it to make it work. And for all the others that helped my thx guys for the help. Later on when i fixed it for myself for the other people that are interested i will post my code how i fixed it. Thx all! And for everyone else that helped me i don't have yet a high enough reputation to thumb you guys up =[
Well i finaly got it working with my waypoints etc. It now runs onmousedown for testing purpse so don't mind that but this is the end result for those who wonder how i did it.
this is the class that runs through the waypoints: using System; using System.Collections.Generic; using System.Linq; using UnityEngine; using System.Collections;
[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;
public List<TreeNode> root = new List<TreeNode>();
private TreeNode target;
private List<string> treeNodeNames = new List<string>();
// Use this for initialization
private void OnMouseDown()
{
root = new List<TreeNode>();
treeNodeNames = new List<string>();
root.Add(new TreeNode(startPoint.GetComponent<InfoHolder>().Infos.str));
treeNodeNames.Add(root[0].value);
LoopFunction(startPoint,root[0].children);
if (root[0].children.Count > 0 && root[0].children[0].children.Count != 0)
{
target = root[0].children[0].children[0];
print("hi");
}
else if( root[0].children.Count > 0)
{
target = root[0].children[0];
print("hi2");
}
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 LoopFunction(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 (!containsObject)
{
print(oHolder);
treeNodeNames.Add( oHolder );
tnList.Add(new TreeNode(oHolder));
LoopFunction(o, tnList.Last().children);
}
}
}
}
This is the class that holds the information:
using System;
using System.Collections.Generic;
using UnityEngine;
using System.Collections;
[Serializable]
public class Info
{
public string str;
public List <GameObject> NextInLineList = new List<GameObject>();
public Info(string s)
{
str = s;
}
}
public class InfoHolder : MonoBehaviour
{
public Info Infos;
void OnDrawGizmos()
{
Gizmos.color = Color.red;
Gizmos.DrawWireSphere(transform.position, 0.5f);
foreach (GameObject o in Infos.NextInLineList)
{
Gizmos.DrawLine(transform.position, o.transform.position);
}
}
}
Thx you all for all the help and i hope some other people can use this for themself aswell.
