If a Path is blocked by Part1 at waypoint index 10, the .Blocked event fires correctly.
However, if the path is then further blocked by Part2 at waypoint 6, the event ignores this.
If Part3 then blocks the path at waypoint 14, the .Blocked event fires.
(If Part3 and Part1 are then removed, .Blocked will fire for Part2.)
Expected behaviour: All obstacles should be reported by the event since the pathfinding agent could be anywhere along the path.
Happens in Roblox Studio and online with 100% reliability.
Your report is accurate, Path.Blocked() is only firing for the furthermost blocked waypoint.
This is typically enough, as paths need to be updated as soon as blockedWaypointIdx >= agentWaypointIdx.
Regardless, we think we need to fix this behavior.
We are also considering adding a new Path.Unblocked event to help with ignoring dynamic obstacles that only block the path temporarily.
But could you explain your use case in more detail?
Why do you need all the blocked waypoints? Are you reusing the same path for multiple agents?
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)
Hi @chess123mate!
We rolled out the fix for Path.Blocked, along with the new Unblocked signal.
You are providing good use cases, thanks for the complete answer.
But it look like many of them are workarounds motivated a slow Path.ComputeAsync response. Minutes to complete is not acceptable. If you have repro cases that you can share with us privately, I can dm you and we will take a look to see what’s going on. A microprofiler capture would also be helpful.
The AgentGroup idea is interesting. We are working on a similar concept that we will introduce for steering, local avoidance and formations, but it’s still in the works.
Hi @portenio
I have taken some measurements in two places:
Place #1: Obstacle Course
Description (or the place is attached below if you want to see it): On a baseplate with 5k parts of varying size (of size 12 or less in each dimension) distributed randomly in a ~1000x1000 area, with 1000 paths calculated (jumping disabled). The waypoints are displayed with parts which become collidable before the Blocked events are connected (thereby blocking all the waypoints), and then the Blocked events are listened to (starting at the same time).
Pathfinding for these 1000 paths completed in 1.5 seconds
CheckOcclusionAsync on the newly created paths takes ~ 6 seconds and discovers that 32 of the paths are invalid (note: nearly half of them start invalid if JumpingEnabled = true)
1000 paths took 32 seconds for Blocked to stop firing (despite only taking 6 seconds to finish pathfinding)
100 paths took ~3 seconds for Blocked to stop firing
Throughout this test, the framerate maintained 60fps (with minor deviations).
I repeated the test in an actual server (instead of in “Run” mode in Studio) and got similar results.
Files:
Obstacle Course.rbxl (108.3 KB) (The script outputs the timing of everything except how long it takes for the Blocked event to stop firing, which is easy to calculate with Output timestamps enabled. After the script finishes with CheckOcclusionAsync, set workspace.Blocked.Value = true to connect the Blocked events.)
(Note: one microprofiler capture that took place while paths were being computed also had rasterizeTile interspersed with some of the computePath blocks - you can see the same thing in the Real Place - Compute Path microprofilers)
Place #2: A real game
Description: The place has huge terrain and tens of thousands of parts with test routes of varying magnitudes (from very small to the 3k stud limit) that connect major points of interest (with jumping enabled); these paths go up to the 3k stud limit in size:
Failed paths sometimes took nearly 30 seconds to compute
Successful paths (all of which were 2089 studs or less) took up to 16 seconds to compute (though numerous completed in less than a second); the smallest path had 330 waypoints (this one took 5.2 seconds); the largest had 734 (and took 0.5 seconds).
Blocking all waypoints of all paths simultaneously caused their Blocked events to to keep finding new obstacles for 10.7 seconds (there were 17 paths with a combined 8339 waypoints)
For reference, in the Obstacle Course place, the 1000 paths have over 80k waypoints combined
I expect that having even 5x as many paths in this place would therefore cause reaction times of nearly a minute.
Files:
(DM me if you need the rbxl and I’ll see what I can do (I’d have to check with someone), but I think the microprofiler results show the same sort of thing in both places)
In case you’re wondering if some other part of the “real place” is responsible:
I performed all tests without players
The pathfinding test script waited until the time returned by Heartbeat:Wait() was less than 0.1 (and the script reports waiting for ~15 seconds for this to happen)
Once the place starts up, only a couple scripts were running, and their combined activity was less than 2% (and usually less than 1%)
To my knowledge, there shouldn’t be any physics going on aside from some unanchored parts