Hi,
i’m in the process of designing the movement logic for a multiplayer game with click to move and non player characters and i’m currently stuck on some logical issues when thinking about how i need to design re-pathing when the movement destination changed.
I don’t use built-in movement components, as i will need to react to path search failures for specific requests at some point, so my plan is to do the search and movement directly.
The basic issue i have stems from the asynchronous nature of both processes.
These are my thoughts:
Ideal scenario:
A destination set command comes in → queue path search and return path when complete.
Now what if in the meantime (while searching the path) a new destination is requested.
A) cancel the current path?
if this continues, as long as a path is not returned within a timeframe lower than the request interval, no path will be calculated at all. And even if it was returned, i would have to cancel the path’s usage as well, as it’s outdated now.
B) queue the latest incoming request until the current one has finished?
this means the returned path is always behind by one request and could effectively be discarded anyway, which basically returns it to case A)
C) only allow requesting paths in certain intervals?
this potentially means worse UX for players and makes it more complex to code around for NPCs, plus i cannot be sure that the chosen interval is enough for the variable search timeframe or have to chose a (most of the time unnecessarily) larger generally-safe interval, which feels like using arbitrary magic numbers.
D) use B) but stitch the latest calculated path with the previous (currently in use) one, gradually diverting into the most current direction
this would allow moving while the latest search is still in progress, but is computationally more involved, and something that just now came to my mind
If i knew that only two consecutive destination requests came in then i’d logically only use the last of those (cancel the first), but with no insight into the future where more could arrive in short intervals, i’m not sure how to apply canceling, queuing or waiting.
Maybe i’m overcomplicating the issue somewhere, and i’d be glad to have that pointed out.
Is there a pattern for how this is typically done?
I’m not following this logic-- can you explain what you mean by this? Because I’d believe that you just would cancel the old requested path and request a new one. Maybe I’m missing something here but I can’t imagine a scenario that plays out where you cancel the old path and generate a new one, but get no path?
For some help, I’d recommend using the Pathfinding.ECS.AutoRepathPolicy struct. It has some convenience functions for when it’s reasonable to recalculate the path.
The built-in movement scripts typically solve it like this:
Recalculate the path if:
– The AutoRepathPolicy says so (which is typically at regular intervals, or if the destination has changed a lot since last time)
– The path is stale, for example if the graph next to the agent was updated.
– Never recalculate the path if the agent is already recalculating it. Check again once the path finished calculation.
Just repeat this logic. Request a path, cancel the old, the new one is now being generated. Get a new request, cancel the one previously being generated. and so on. As long as new requests come in to cancel the previously in progress one, this will never come to a result. This is what i tried to describe there.
I hope my reply didn’t sound like a rude disregarding of what you said, i wanted to answer the other commenter’s question.
But i had a look at the AutoRepathPolicy. It seems the main takeaway is recalculating the path at a constant interval (obviously if the destination changed). There seems to be fail handling behaviour, that might matter later on. I’m still not sure how it solves the logical issues i’m having.
I think that it mainly makes one important assumption to avoid these, that path calculations will not take longer than the minimum recalculation interval.
My game is intended to be a multiplayer where the server part will run on an ultra-cheap vps, so i assume that path calculations can take longer than a chosen tradeoff interval (reactivity/performance), but maybe that’s not true for reasons i don’t understand (maybe the interval to check (Time.time) will also be prolonged/stretched by cpu overload, so requeuing will happen at intervals in the same time-relation as results come in?)
Or maybe scaling the interval by cpu-load might work around this. But i feel like i want there to be an easier solution, like not needing to calculate unnecessary intermediate solutions if the destination already changed. But that brings me to the initial canceling problem.
I think i would need to understand what happens with the interval check and threaded path calculations when the cpu is slightly overloaded first.
Or is there anything in the AutoRepathPolicy that i missed, that adresses these logical issues (if these are even real issues)?
No. What I’m saying is that if the script wants to recalculate its path, but it is already calculating one, it will just wait until the path that is being calculated is done. That way you don’t have to cancel path calculations except in exceptional circumstances.
Ok, i misunderstood.
If i now understand correctly, then this is case B); in a point and click scenario where the user clicks a point to the left, then directly afterwards a point to the right of the character, the path movement to the left will always happen, and first. From a reactive gameplay perspective i would expect the movement to be canceled and prepared for right-directed movement (but canceling as mentioned has the potential for the never-start-to-move situation).
But these thoughts are not based on real observations yet. I just wanted to factor in network delays as well and wanted to make sure that repathing doesn’t introduce additional undesired delays.
So, maybe i shouldn’t even account for cpu overload, as in that case the whole gameplay will suffer anyway and basically just assume that path calculations will never be slower than a certain natural reactivity threshold (~200ms), in which case the interval repathing will do just fine.
I think i’ll just go with this, as it seems there’s no logical solution otherwise.
Sure. That’s why I hedged with “exceptional circumstances” above. For maximum responsiveness, one can definitely manually cancel the pending path when a user gives the agent an action. This is fine as it is quite rare (relatively speaking).
