General Question about manual path recalculation logic

1

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 :thinking:

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?

2

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?

3

Hi

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.
4

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.

5

Yes. And I recommend:

Never recalculate the path if the agent is already recalculating it. Check again once the path finished calculation.

You can check if the path is calculated using path.IsDone() or seeker.IsDone().