koobas.hobune.stream
Creating custom pathfinding solution stack overflow
Hey guys, I was attempting to implement a fully 3D pathfinding system for the drone AI in my game. The environments are completely enclosed by colliders. To do this I decided I would create an ScriptableWizard to automatically populate my levels with nodes to later be used in conjunction with Dijkstra's algorithm to enable pathfinding. The basic algorithm is as follows:
Start from an initial position within one of the level's rooms.
Instantiate a node there
Raycast outward in all six directions (forward, back, up down, left,right)
If the space to the left, right, whatever is clear, instantiate another node there.
Run the same raycast test from this new position
The reason this works is each node itself has a box collider, therefore a new node can never be instantiated on top of a previous one.
Anyways, all this works great for small levels. But if my space becomes too large, I get the following error message:
StackOverflowException
UnityEngine.Object.Internal_InstantiateSingle (UnityEngine.Object data, Vector3 pos, Quaternion rot) (at C:/buildslave/unity/build/artifacts/generated/common/runtime/UnityEngineObjectBindings.gen.cs:63)
UnityEngine.Object.Instantiate (UnityEngine.Object original, Vector3 position, Quaternion rotation) (at C:/buildslave/unity/build/Runtime/Export/UnityEngineObject.cs:80)
CreateNavmesh.ComputeNode (Vector3 position) (at Assets/Editor/CreateNavmesh.cs:27)
CreateNavmesh.ComputeNode (Vector3 position) (at Assets/Editor/CreateNavmesh.cs:36)
My full code is below:
using UnityEditor;
using UnityEngine;
public class CreateNavmesh : ScriptableWizard
{
public Transform startpos;
public Transform navmesh_obj;
public float grid_len = 1f;
public float boxwidth = 1f;
[MenuItem("Navmesh_3D/Compute Navmesh")]
static void CreateWizard()
{
ScriptableWizard.DisplayWizard<CreateNavmesh>("Create Navmesh", "Go!");
}
void OnWizardCreate()
{
Debug.Log("Pressed Button Create");
ComputeNode(startpos.position);
}
void ComputeNode(Vector3 position) {
Instantiate(navmesh_obj, position, Quaternion.identity);
if (Vector3.Distance(position, startpos.position) < 50) // My way of making sure this does not get out of control
{
if (!Physics.Raycast(position, Vector3.up, grid_len + boxwidth))
{
ComputeNode(position + Vector3.up * grid_len);
}
if (!Physics.Raycast(position, Vector3.down, grid_len + boxwidth))
{
ComputeNode(position + Vector3.down * grid_len);
}
if (!Physics.Raycast(position, Vector3.left, grid_len + boxwidth))
{
ComputeNode(position + Vector3.left * grid_len);
}
if (!Physics.Raycast(position, Vector3.right, grid_len + boxwidth))
{
ComputeNode(position + Vector3.right * grid_len);
}
if (!Physics.Raycast(position, Vector3.forward, grid_len + boxwidth))
{
ComputeNode(position + Vector3.forward * grid_len);
}
if (!Physics.Raycast(position, Vector3.back, grid_len + boxwidth))
{
ComputeNode(position + Vector3.back * grid_len);
}
}
}
}
I believe the stack overflow is the result of the really deep recursion resultant from my algorithm. Is there a better way of doing this? Any help would be much appreciated.
Hey, I figured this out. Your have to use something called the Stack class.
$$anonymous$$y new ComputeNode function looks as follows:
void ComputeNode(Vector3 position) {
Stack<Vector3> stack = new Stack<Vector3>();
stack.Push(position);
Vector3 currentpos;
while (stack.Count!=0)
{
// Do something
currentpos = stack.Pop();
// Push other objects on the stack.
Instantiate(navmesh_obj, currentpos, Quaternion.identity);
if (Vector3.Distance(currentpos, startpos.position) < 50) // $$anonymous$$y way of making sure this does not get out of control
{
if (!Physics.Raycast(currentpos, Vector3.up, grid_len + boxwidth))
{
stack.Push(currentpos+Vector3.up*grid_len);
}
if (!Physics.Raycast(currentpos, Vector3.down, grid_len + boxwidth))
{
stack.Push(currentpos + Vector3.down * grid_len);
}
if (!Physics.Raycast(currentpos, Vector3.left, grid_len + boxwidth))
{
stack.Push(currentpos + Vector3.left * grid_len);
}
if (!Physics.Raycast(currentpos, Vector3.right, grid_len + boxwidth))
{
stack.Push(currentpos + Vector3.right * grid_len);
}
if (!Physics.Raycast(currentpos, Vector3.forward, grid_len + boxwidth))
{
stack.Push(currentpos + Vector3.forward * grid_len);
}
if (!Physics.Raycast(currentpos, Vector3.back, grid_len + boxwidth))
{
stack.Push(currentpos + Vector3.back * grid_len);
}
}
}
}
No more stack overflow, even with hundreds of thousands of nodes!
