Improving Pathfinding Quality With New Algorithm

[Update] November 15, 2024


Hello Creators,

As you know, pathfinding is a crucial component to enable rich NPC behavior that enhances the overall user experience. Over the past few years, we’ve received your reports on the many quality issues related to the Pathfinding service. Similar to the recent improvements in memory and performance, we have focused on making significant improvements to pathfinding quality this year.

We identified three major issues where fixes would have the greatest impact: poor quality path generation, paths not properly accounting for agent size / environment features, and paths failing to generate (properly or at all) due to poor Navmesh generation.

Today, we are releasing an opt-in algorithm update that focuses on all three of these pathfinding quality issues (see below for examples).

Based on community feedback, we’re also reintroducing the return of partial paths when the full path is not found. Partial paths are best effort and may not always return the optimal partial path.

While this new behavior should fix many problems, we are releasing it as opt-in and relying on your feedback so that we can make improvements before making this the default via 3 phase rollout over the course of 2025. We recommend you try it in a test place first to confirm you are happy with the new behavior before publishing it in your experience.

We do not anticipate any memory or compute time regressions as a result of these fixes and enhancements, but please reach out or reply below if you observe any performance issues.

How to enable the new Pathfinding algorithm and fixes

In order to not disrupt live experiences, we’re providing three options for this property:.

  • Default: This will use the production algorithm for now. Once we move to opt-out in mid 2025, this would use the new pathfinding algorithm going forward.
  • Disabled: This will use the production algorithm even after we update the default behavior
  • Enabled: This will opt your experience into the new pathfinding algorithm and fixes.

To enable this algorithm, click on Workspace → Properties → PathfindingUseImprovedSearch as shown below.


Issues addressed by this update: before and after

Path Zig-Zagging

View details

Pathfinding service generates zig zag paths when the straight path is available. Many reported examples.

Before:

After:

Additional examples

View details

Before:

After:

Before:

After:

Before:

After:

Path Quality: Path too close to the wall cause agent to get stuck

View details

PathfindingService computes paths that would result in an agent getting stuck when direct LOS is available between start and goal

Before:

image4

After:

image16

Pathfinding service is **Still** broken

Before:

image3

After:

image6

Paths not using Agent’s size

View details

PathfindingService doesn't always use agent params; makes service unusable for large characters

Before:

After:

Path going through walls

View details

PathfindingService computes invalid paths under specific circumstances when using PathfindingModifiers

Similar Issues we believe this should fix:

Before:

After:

Pathfinding giving bad paths in terrain due to bad navmesh

View details

Engine Bug: Pathfinding service is arbitrarily inable to path some terrain - #2 by Markaaron

Before:

After:

Before:

After:

Returning Partial Paths

View details

PathFindingService Giving Closest Path To Object - #15 by focasds

Before (No Path):

After (Partial Path up to the blocked entrance):


How to get partial path results from the Pathfinding response

To get partial path results, please make sure to select PathfindingUseImprovedSearch property > Enabled. Partial paths can only be returned when PathfindingUseImprovedSearch is Enabled.

In order to maintain backwards compatibility, we are introducing PathSettings in agentParameters. When calling the CreatePath(agentParameters) API, you can specify if you need a partial path by setting PathSettings.SupportPartialPath = true as shown in the example below (the default will be false). If PathSettings.SupportPartialPath is true and computeAsync only finds a partial path, then instead of setting Path.Status to Enum.PathStatus.NoPath, it will set Path.Status to Enum.PathStatus.ClosestNoPath. If PathSettings.SupportPartialPath is false or not set in the agentParameters, then PathStatus will only return NoPath or Success depending on whether the path to the destination was found. Please see the code example below.

local path = game.PathfindingService:CreatePath({
 AgentRadius = 2,
 AgentHeight = 5,
 AgentCanJump = true,
 Costs = {
   Water = 20
 },
 PathSettings = {
   SupportPartialPath = true
 }
})
-- Compute the path
local success, errorMessage = pcall(function()
 path:ComputeAsync(startPosition, finishPosition)
end)
-- Confirm the computation was successful or it returned partial path
if success and ( path.Status == Enum.PathStatus.Success or path.Status == Enum.PathStatus.ClosestNoPath) then
--- custom code for movement
end

Acknowledgements

Please try out this update and let us know your feedback! We want to continue investing in improvements to Pathfinding and other aspects of NPCs. A huge thank you to the entire community for filing reports, sharing test scenes, and following up with us. In particular, we would like to acknowledge @xChris_vC and @Halferee for providing initial feedback on these updates, and a special thanks to @xChris_vC for the awesome maze test that truly pushed the boundaries of our algorithm during testing.

@WatisInTheName, @oldmannt, @Bloxsometa and the Movement and Pathfinding team

454 Likes

This topic was automatically opened after 11 minutes.

Well, this will help a LOT! Will really help my enemy NPC pathfinding.

45 Likes

image

Super excited to try this new tech out! As someone who has previously fought tooth and nail with the pathfinding system prior offered. Especially the returning partial paths and fixes to agents getting stuck on walls.

I’ve been trying to get NPCs to nicely pathfind when said NPCs are using the relatively new PhysicsController feature, but they have an increased tendency to get stuck on things, particularly when it involves jumping due to lowered friction.

143 Likes

Couldn’t have come at a better time. I’m starting to think about NPCs. Bless

23 Likes

A while back i reported an issue with paths not generating if they’re outside of the live-baked navmesh radius going from point Start to finish despite a clear path being available visually anyway. does partial paths now somewhat allows for a way around this or not?

Report in question

23 Likes

Would be great to know if there is better perfomance or not from it!
Some people are already satisfied with the current pathfinding so knowing if upgrading it makes a difference would be great.

14 Likes

Would be cool if you could do simple obbies with this new pathfinding tho…

14 Likes

This change should be performance-neutral or, in some cases, even better. The update focuses on generating improved paths. We highly recommend trying it out and letting us know if you encounter any performance-related issues.

Our goal is to make this default sometime in 2025 based on the community feedback.

30 Likes

I was just thinking about the pathfinding system having these glitches 1-2 days ago! I wonder what else my mind comes up with that gets fixed / releases.
Overall, I approve this system!

13 Likes

This is great! I wonder how fast is it for the server

15 Likes

Thank you very much. this is one of the best announcements for years

16 Likes

Does pathfinding take advantage of parallel luau? I’m not very familiar with how path finding systems work under the hood so im curious to know how performant this all is along with the fact of whenever or not pathfinding uses any sort of parallelism.

12 Likes

THANK YOU
LETS GOOOOOOOOO, FINALLY MAN, (Suffered for years because of this)

13 Likes

you did not have to COOK this hard, this is probably the best improvement I’ve ever seen.

will this be permanent?

13 Likes

I appreciate all of the work the entire team does on every feature! These updates are amazing and definitely improve pathfinding!

But, I have to be honest, we have too many of these behavioral properties with the value of Default under Workspace. This introduces many inconsistencies and unexpected behavior across games. There’s also some of these in other places in the explorer. These only keep increasing with each new feature added.

I request cleanup. Otherwise, keep up the good work! :+1:

18 Likes

Hi @watIsInTheName I have tested the new pathfinding and i found a bug.

Inside CreatePath() if CanJump Variable is set to false. the agent sometimes collides with stair walls, and its jittering backwards and forwards also when it goes down it keeps jitter near the stairs.
Capture
Capture2

it has like 30% change to not get the right angle to climb the stairs with that

here is the file:
PathTest.rbxl (225.8 KB)

12 Likes

Yes, this will become the default behavior in 2025. This feature will be permanent unless we encounter a critical performance issue that needs to be addressed. The idea is to let developers test this in their games. If they are satisfied, they can enable it for their production games. We intend to keep it permanent unless any critical issues arise.

11 Likes

Might be one of the most exciting improvements in some time! Pathfinding has been annoying to do and i’m glad this is finally happening! W roblox :pray:

9 Likes

Will closest no path be un-deprecated then?

15 Likes