Quick answer: Yes, either one agent repeating a route and/or multiple agents using common routes - and it needs to be efficient enough to support dozens or perhaps hundreds of agents (so I can’t use work-arounds like creating several paths per agent).
If Blocked and Unblocked existed and reported all changes, this would enable a few things I was trying to do recently:
- If we know that obstacles are often small and short-lived (this is easier to know if Blocked also transmits what is blocking the path, see below), we can wait until the agent gets closer to the obstruction before pathfinding around it (in case it moves out of the way)
- We could have two agents pathfind towards each other using a single path (with jumping disabled). This can be done now, but in the event of an obstacle, the only safe thing to do is to discard the whole path and repathfind until the agents are close enough to each other. With the enhanced events, we can be confident that we’ll be notified of all obstacles and so can safely ignore ones behind both agents (or even in between them, if the agents don’t need to get too close and the obstacle is small - though answering “is it small” requires knowledge of the part/assembly that is causing the obstruction, suggested below)
- Pathfinding once over long distances for routes that agent(s) will be using repeatedly and reusing the same Path object for all agents (with jumping disabled to allow for both directions of travel with a single path). This would be performed when the server starts up before any obstructions can be added by players. When an obstacle is added, instead of abandoning the path, short detours could be calculated around the obstacle. For example, if I could find out that there’s a particularly large obstacle* blocking waypoints 20-21, I could use agent speed and what the obstruction is to determine how far around each obstacle I should go to perform a reasonable pathfind; in this example, perhaps create a detour from waypoint 17 directly to waypoint 24. In case the obstacle goes away, I could delay the pathfinding for this detour until an agent was a second or two away from either of the chosen waypoints (meaning perhaps when they reach waypoint 12 going forward or 29 going backward). Once all obstacles are cleared, the original path’s waypoints can be used again. If no agents are near a particular path, the Blocked/Unblocked events could be disconnected temporarily for efficiency. (Note: in PathfindingService’s current state, one can’t create detours around obstacles mid-path, but one can re-use the original path by periodically querying
:CheckOcclusionAsync(1) until the path is clear, but since many of the paths are long, this becomes an efficiency concern.)
– * If the Blocked event could send
minIndex, maxIndex, part:BasePart (minIndex and maxIndex indicating which indices are affected because of
part and anything that
part is connected to, since you wouldn’t want it to fire 10x just because 10 connected parts start obstructing the path), this would enable:
- Agents could ignore the obstruction if they can pass through it due to the collision type (though an option for this in CreatePath would make more sense)
- The agent may be able to move or attack the obstacle and so knows it will be able to get through it (though, again, if there’s no way to specify this during CreatePath, this isn’t ideal - but see AgentGroup idea below for a superior method of handling this)
- If the obstacle is a player-built wall that might be part of a sprawling structure, this may impact how to pathfind around it (for instance, for future agents it may make sense to recalculate the whole path starting at waypoint 1 since the original route may be completely blocked off, requiring a completely different direction).
(If this were added, it might make sense to have CheckOcclusionAsync return more information about the obstacle as well, or perhaps allow it or a variant function to return a list of all current obstacles - the min/maxIndex blocked and the assembly doing the blocking in each case.)
- If the Blocked event must stay as it is, use case #3 can still work so long as it triggers for each blocked waypoint (even if a single part blocks 10 waypoints). If the Blocked event will only trigger for one waypoint regardless of the obstacle size yet still only reports one index, then use cases #2 and #3 would not work unless we make assumptions that the obstacle will always be small (which it won’t always be).
Note: Since the original pathfinding (when the server starts up) is about finding the optimal paths with no obstructions, it’d be important to not let players add obstructions before the process completes. It’d be valuable to ask the engine to alter the pathfinding processing budget - the current cap is quite limiting and can take minutes to complete when given several dozen longer paths through large terrain, and it’s not good design to prevent players from constructing/moving/destroying anything for the first several minutes! Further, once you get enough paths, the response time of an agent due to a new obstruction can be even as high as a minute!
An alternative to players having to wait when the server starts up would be if we could construct a Path from a list of waypoints, we could also pathfind everything while editing the map, serialize the lists in scripts/StringValues, then load them up when the server starts up (and then we’d still be able to benefit from the Blocked/Unblocked events).
Some other ideas:
- Even in the simplest algorithms, Roblox has to check the entire path for obstacles, even if the agent is 75% of the way to the end of the path. Being able to work with the engine to reduce time spent checking unnecessary parts of the route would improve efficiency (for instance, with a
:SetObstacleCheckingEnabled(enabled, minSegmentIndex=1, maxSegmentIndex=#wayPoints - 1) function, where segment index 1 means the segment between waypoints 1 and 2 - though the function should probably be designed to support being able to just specify an agent’s current waypoint index (that they’ve reached) for the common one-agent-per-path case
- Others have mentioned the inability to incorporate things as simple as doors/destructable walls (and many other features) into agent algorithms. This could be solved with an
AgentGroup class (it might take in an AgentParams table that also supports specifying the agent collision group) that could be used when creating paths to enable us to communicate to the engine how to treat obstacles:
:SetObstacleCost(part, cost) (where
part means the entire assembly that
part is in;
cost could be measured in time or studs or whatever’s convenient for the engine)
- If SetObstacleCost can be called while an assembly is not parented to the workspace, that’d be good, but if it’s better to insist that it be parented to the workspace, then either the pathfinder needs to give a frame (or partial frame) for a script to parent the assembly to the workspace and then configure it before the patfinder considers the assembly in any Blocked events/pathfinding solutions OR would need a
.GetObstacleCost(part)->cost callback that is called for such occasions
- Functions to support those other features, like weighting or portals, could also be added to this instance
- The AgentGroup instance would be useful in configuring a group/team of agents that act the same way (not all agents will want to treat the same things as destructible, for instance)
- It might be good to be able to modify the list of what’s ignored. Currently Humanoids are ignored no matter what (last time I checked, even if the parts in the model are anchored), whereas some mobile objects should probably be classified as “will likely move at any time and so should be ignored” (ex imagine an autonomous robot or animal that doesn’t use Humanoids or a game that doesn’t use Humanoid-based players)