- Home /
Automatic Node Connection - Help
Hi
I am trying to create a Node Based Pathfinding System inorder to make the AI choose the path that is safest(Has most Cover objects) of all .For which i am using Dijkstras Algorithm
At first i thought of using Raycast Method but i have two problems
I dont know how to raycast in circular manner(Raycast in full 360 degress)
and secondly the raycasted distance varied from node to node
Is there a way to find out which Node should affect which Node That is Automatically Connect( Link Nodes ) with one another other than having to assign manually
Here are some thoughts
Find all nodes that are within a radius x
Check those nodes visibility by raycasting
Link visible nodes
Answer by Bunny83 · Dec 31, 2013 at 12:08 AM
I'm not sure what you mean by 360° raycast. Where do you need such a raycast when you have distinct nodes? Like @Sundar said you just iterate through all your nodes and raycast (probably both ways) to see if there's something in the way.
//C#
public Node[] nodes;
void LinkNodes()
{
for (int i = 0; i < nodes.Length; i++)
{
Vector3 start = nodes[i].transform.position,
for(int n = i+1; n < nodes.Length; n++)
{
Vector3 end = nodes[n].transform.position;
if (Physics.Linecast(start, end, yourLayerMask))
continue;
if (Physics.Linecast(end, start, yourLayerMask))
continue;
// Link node i and n
}
}
}
It's important if your nodes have colliders to exclude them from the layermask. Only cast the rays against blocking geometry, so don't forget to setup your layers.
Hi @Bunny83 Thnaks for fast reply but the problem with this method is as it is O(n^2) it might be a bit slower(Way faster than 360 deg raycast) at runtime as i only want to connect the Final Node with the nodes which can affect them
By 360 Raycast all i meant was casting a ray starting from 0 to 360(Sorry wasnt quite thinknig correcltly at that moment as i was really tired when i tried to implement the algorithm)
Note **I tried your scrip*t but it doesnt seem to work* at all the node lenght always rea$$anonymous$$ 0 no matter what(tried altering it but it only adds it self)
Do you mean you wanted to cast 360 raycasts one each degree? That would result in a quite bad result depending on the distance since the gap between two rays will increase with the distance. Also your nodes would need some kind of collider. $$anonymous$$y method just checks if there's something in the way.
Of course the complexity is O(n^2) but you usually setup the node-graph once at start. I don't understand why you only need the connections with the final node... The final node is usually choosen dynamically at runtime. Do you plan to check the connections each time you want to calculate a path?
I got the feeling that your "final" node is your target position and you just want to deta$$anonymous$$e which is the nearest visible node. Is that right?
In that case you just need O(n). You could first filter only near nodes but that might fail depending on your world.
So it that's your actual problem you just need the "inner" loop and set "start" to your target position. You just iterate once through all nodes to see which ones are visible and finally pick the nearest. $$anonymous$$eep in $$anonymous$$d that this could result in a strange path:
You probably want to create a temporary node at the target, link them with all visible nodes (O(n)) and then run the pathfinding with your temporary node as target node. $$anonymous$$eep in $$anonymous$$d that you have to remove the temp node and links after the pathfinding.
Thanks @Bunny83 for quick reply
Do you plan to check the connections each time you want to calculate a path?
Yes thats exactly what i plan to do
I got the feeling that your "final" node is your target position and you just want to deta$$anonymous$$e which is the nearest visible node. Is that right?
Not exactly any ways i seem to face problem withe D*ijkstra's alogrithm it doesnt stop* when it reaches final node and sometimes it doesnt even go to final node before breaking out i tried to impliment(First time)
Would you $$anonymous$$d to lookat the script
Thanks
Would you $$anonymous$$d to lookat the script
Uhm, script?
Hi @Bunny83 Here is the script it is converted to .txt format as Unity Website dosent allow me upload .cs files
The problem is the script continues to search even after reaching final node and sometimes it breaks even before reachinf final node
Can you please look at it
Thanks
Ps the script look long but the problem lies in Agent class
the first calss
Your answer
Follow this Question
Related Questions
A node in a childnode? 1 Answer
How can i modify a float in another script in C#? 1 Answer
Distribute terrain in zones 3 Answers
How to select an object with TOUCH and change its animation 2D 1 Answer
C# More Accurate or Larger Raycast 1 Answer