Question How to handle physics in the background?

My task is the following - finding a path through an unknown 3D area, I have already made the code and checked it, everything works, in short the principle is this

Code (CSharp):

1. public List<Vector3> GetRoute(Vector3 start, Vector3 target){
2. List<Vector3> Route = new List<Vector3>();
3. ....
4. while(true){
5.      // next step search logic
6.      // checking with Physics.CheckBox and Physics.BoxCast whether it is possible to step onto the next cell
7.      // if yes, then write down the step and try to go further, or write down what is impossible and select another direction
8.      }
9. // logic for calculating the "shortest path" using AStar
10. return route;
11. }

the problem is that it can be processed both 0.01 sec and 0.3 sec, the latter of course does not fit into the frame and will cause a freeze.

The question is how to parallelize this miracle, run it in the background, in several threads, in general, how to complete this task without freezing the main thread?

As I understand it, using Job will not work since Physics work only in the main thread (as I understand it), there is no point in using coroutines either, anyway, physics processing is only in the main thread and you can just as well interrupt the loop at some iteration and continue in the next frame, the transition to ECS, of course, is not discussed, since all this generally needs to be completely redone ...

in general - what options are there, in which direction to dig, what is better to use, how to deal with it?

 

The way to achieve this is to simulate the physics manually. I simulate physics in the editor with a loop like this:

Code (CSharp):

1. void RunPhysics(float seconds) {
2.     Physics.autoSimulation = false;
3.     float secs = 0;
4.     while (secs < seconds) {
5.         Physics.Simulate(Time.fixedDeltaTime);
6.         secs += Time.fixedDeltaTime;
7.     }
8.     Physics.autoSimulation = true;
9. }
10.  

You can also create a separate physics scene where you can run your separate physics stuff. It's quite simple in the end and works like a charm, I'm using it to show the player simulated results before he makes his selection.

https://learn.unity.com/tutorial/multi-scene-physics#5fb96f14edbc2a7ff2348496

 

I understand correctly that the presented method physicsScene.Raycast.... will it work in multithreading?

 

Using a physics scene, it's a separate scene and the physics will only advance when you call Physics.Simulate. And yes, raycasts will work if you use them on the physics scene.

Whatever you mean by multithreading - Unity is single thread. You can put your physics simulation calls in your main FixedUpdate or make a coroutine for it.

 

my main goal is to find the path in 3d, so I would use navmesh, but because of the specifics of building the world I can’t, or rather it will be expensive, the terrain changes dynamically, the objects too, so I’m looking for a way to dynamically find the path, I did it, but I need it somehow run in the background or multi-threaded, and since I am checking using Physics.CheckBox and Physics.BoxCast, I cannot do this.

so I’m thinking which way to choose for my purpose, where to stop, what is the most optimal way to use in my case, what approach ...

 

You need to know all these in order to effectively run your A*. You need to know the points when you want to start a new search, and parametrize the search in a way that it optimizes performance.

If you want to compute these on-the-fly, you want an iterative A* method (or coroutine) that you can run eg in your Update with small increments. You likely want to use an A* variant like IDA* that supports this sort of iterative search where it makes a better solution with each iteration using some heuristics.

I think your problem here is not running physics in the background but how to iterate your A*. I don't know why you believe you can't use Physics boxcasts with this. You don't need to boxcast where your player is, you can do that in any position, wherever the A* search is currently proceeding.

 

A* calculates the best path from an already prepared set of nodes (segments of positions from and to), since I have dynamics that I don’t have pre-prepared nodes, as a result, I need to create them on the fly using checks.

or I need to have a pre-prepared map of the area with a pre-scanned area, but the size of such an array scares me, about 8k records at least in the array.

so I'm thinking - to fill in advance an array weighing about 100 MB (it seems to me a bit too much), or to search dynamically, but how will it work if several go to the other side of the map at the same time ... when taking into account the 1000x1000 terrain

I can't decide yet which model I need for the optimal solution...

 

I'm not sure if you understand what you are talking about. A* is a graph traversal algorithm. It uses a graph of nodes. These nodes take a couple of bits in size, so if you have 8k of those, it will never come to 100 MB.

Instead of A* you can use iterative variants that return sub-optimal solutions for example within a pre-determined depth and heuristics. Depending on what you need to calculate, you can calculate just a part of the route and take the best suboptimal solution. I think most games would just calculate the A* a couple of nodes down the graph and stop there, take the best one using the final distance as heuristic.

 

my node consists of two vectors (position from and to) as well as the cost of the path, and that turns out to be 7 floats, 28kb (float 4 kb like)

I also had an idea, I want to try to do the following - when the game starts, a coroutine is launched that, starting from the center, will scan the entire area and write data to text documents, each document will contain 1000 points, so you get 1000 documents in each 1000 points each, when we look for a path, it will not scan a point, but get data from the required dock, that is, load the required dock into an array for processing, while the docks themselves will lie in temporary files.

I think this is a good idea, what do you think?
(then for A* there will already be prepared data for calculation)

 

Judging from your comments I recommend you'd study AI pathfinding a bit, to get more ideas and to understand better how it works.

 

from what I already understood - dynamically obtaining the path during the game is expensive, since physics works in one thread, the conclusion is that you need to store the data somewhere, finding the path from the received data is not a problem, the problem is in finding and storing the path, in general the question remains where it is advisable to store this data - in RAM (in dictionaries) or in documents and load data from them at the right time.

Or am I not on the right track?
If not, then recommend in which direction to go, what exactly needs to be studied?

 

Just study AI pathfinding, watch some videos or read. To get a full picture of how it works and what options you have.

7 floats doesn't take 28 kb of memory, does it? Your one million node network is small potatoes and takes a couple of meg from your multi-gig RAM.

The reason why you don't want to do that is not because of memory but because of the efficiency of your pathfinding. You need to analyse your map into a graph first, and you don't seem to have done that. This graph doesn't need to be like 1 node per game metre grid, but it can be analysed and created based on your map topology. This graph creation is one part of what you need to do.

The second part is how to run your AI. Coroutines don't change anything in terms of performance, they're just a way of handling jobs that take up several frames, and you need to manually yield the execution. And here I don't think you understand that there are several variants of A* and several ways of running it, and this will 100% affect the performance and the output. You need to understand completely which approach is suitable for your game.

 

..

A float is 4 bytes, not 4000 bytes.

If your world is dynamic and constantly changing then you can't really do any precalculating of data. It's questionable whether you should even allow your AI to be able to use pathfinding in a dynamic world as it seems a little unfair. Humans with their big brains can't figure out a path when they can't see beyond the wall in front of them, so why should the AI?.

I think if it was some sort of 3D platform game where both the AI and the player are able to see the entire world laid out before them then it would be fair to allow the AI to use path finding.

So it seems the best solution is going to depend on just how open and how dynamic the world is.

If the world is full of walls that are constantly changing then it may be best to drop path finding and just let your AI fumble its way through the dynamic world. Because that's what the human player is going to be doing.