Hi guys, I want to find the shortest path using Dijkstra. If i use the algorithm my project has low fps for 3 seconds. If i use StartCoroutine it works slow and CPU is 100% (for 4000 nodes).
I am trying to use a thread, it works on private void Start() method, but on Update() methos, it is worst…, my project is breaked for 2 mins and I dont know why.
It’s like when my thread is working, the main thread with unity is not…
My Code:
DRAWPATH.cs
private void Start()
{
PathRequestManager.RequestPath(new PathRequest(StartNode, EndNode, OnPathFound));
}
public void OnPathFound(List<Waypoint> waypoints, bool pathSuccessful)
{
if (pathSuccessful)
{
path = new List<Waypoint>(waypoints);
Line = GetComponent<LineRenderer>();
Line.transform.position = this.transform.position;
Line.positionCount = path.Count;
for (int i = 0; i < path.Count; ++i)
{
Line.SetPosition(i, path[i].transform.position);
}
}
}
private void Update()
{
Dijkstra();
//Dijkstra();
//Dijkstra2();
}
/*
private List<Vector3> GetPath()
{
List<Vector3> path = new List<Vector3>();
Waypoint aux = StartNode;
Vector3 position = aux.transform.position;
position.y += 3;
path.Add(position);
do
{
if (aux.outs.Count != 0)
{
aux = aux.getNextWaypoint();
position = aux.transform.position;
position.y += 3;
path.Add(position);
}
else
break;
} while (aux != EndNode);
return path;
}
*/
private void Dijkstra()
{
if ((path.Count > 0) && (GetDistance(path[0].transform.position) < 10))
{
path.remove(path[0]);
PathRequestManager.RequestPath(new PathRequest(path[0], EndNode, OnPathFound));
}
}
REQUESTMANAGER.cs
public class PathRequestManager : MonoBehaviour
{
Queue<PathResult> results = new Queue<PathResult>();
static PathRequestManager instance;
PathFinding pathFinding;
void Awake()
{
instance = this;
pathFinding = GetComponent<PathFinding>();
}
void Update()
{
if (results.Count > 0)
{
int itemsInQueue = results.Count;
lock (results)
{
for (int i = 0; i < itemsInQueue; i++)
{
PathResult result = results.Dequeue();
result.callback(result.path, result.success);
}
}
}
}
public static void RequestPath(PathRequest request)
{
ThreadStart threadStart = delegate {
instance.pathFinding.FindPath(request, instance.FinishedProcessingPath);
};
threadStart.Invoke();
}
public void FinishedProcessingPath(PathResult result)
{
lock (results)
{
results.Enqueue(result);
}
}
}
public struct PathResult
{
public List<Waypoint> path;
public bool success;
public Action<List<Waypoint>, bool> callback;
public PathResult(List<Waypoint> path, bool success, Action<List<Waypoint>, bool> callback)
{
this.path = path;
this.success = success;
this.callback = callback;
}
}
public struct PathRequest
{
public Waypoint pathStart;
public Waypoint pathEnd;
public Action<List<Waypoint>, bool> callback;
public PathRequest(Waypoint _start, Waypoint _end, Action<List<Waypoint>, bool> _callback)
{
pathStart = _start;
pathEnd = _end;
callback = _callback;
}
}
You’re going to need to turn on Deep Profile and disable all logging in the relevant functions to get any sort of meaningful profiler data. A lot of the Unity API does not support multi-threading, so I’m guessing you’re just getting thousands of errors in your console.
As a general optimization, you definitely do not need to find a path every single frame.
I have no error on Console.
I want to find the shortest path after I reached the next node.
When my thread start the fps is good, the CPU is good, but the main Thread is blocked until my thread is done
You don’t have to have actual error messages. Somewhere you are creating thousands of messages in the unity log system. Debug.Log, Debug.LogWarning, Debug.LogError or Debug.LogException. The profiler clearly shows that some debugging log calls a stackTrace method, which will be called, even if you do not have an error somewhere(the normal Debug.Log also shows you where it comes from in your codebase)
Check your console, if there are logs. I would be surprised if there aren’t any. Edit: I am surprised
If there aren’t you can log your code more thoroughly.
You can use Profiler.BeginSample(“my sample”) and Profiler.EndSamle(); to check if a piece of code is causing the problems. This is a good way to identify the source of the problem without disabling parts of your code just to check where the problem is.
And turn on deep profile as it is menitioned above, it will give you more detailed profiling results.
I don’t know how Action callback actually works, but this could be the culprit. Some Unity calls take away a lot of performance when called often, like calling Update() on lots of MonoBehaviours. You could write a custom UpdateManager that manually calls a ManualUpdate() method.
I found here Profiler showing LogStringToConsole, what is that? that sometimes logs are not displayed in the editor log window, if there are too many. Check the Editor Log file, if there are any other logs.
Wrap it around parts of your code. If the deep profile wont work it probably is because there is just too much happening.
Example:
Profiler.BeginSample("My method");
// some code
int number = 0;
for (int i = 0; i < 100000; i++)
{
Profiler.BeginSample("Inside of a for loop");
number += number;
Profiler.EndSample();
}
Profiler.EndSample();
Okay, so now is the time to start a deep profile first, if it crashes you may want to create a smaller map to test this.
After that use Profiler.BeginSample to check the parts of your code. You are somewhere allocating around 6 kilobytes of memory that you destroy afterwards. Probably a class that gets created and destroyed afterwards. Lists and Dictionaries can be problematic too as they increase their size when they are full, but only a certain amount.
It seems you still have many calls that create a lot of garbage. You should try to fix that problem, before you think about threading. Schrink your size to a few nodes so that the editor and your machiene can handle a deep profile. If a deep profile does not work even in a small test scene, then something is probably very wrong. I would suggest bypassing threads at first at see if that is the problem.
I don’t have much experience with threading in unity, but I think that the thread will always block the main thread if you access any unity methods or scripts.
If i run my program without threading, it works pretty fine. We know that dijkstra algorithm its a good one but with a lot of operations. All I want is to calculate my shortest path with a new thread, but my thread blocks the main thread of unity.
