PathfindingService Woes

[EchoReaper]

At RDC US, ROBLOX announced some upcoming improvements to PathfindingService (1:32:35). If you aren’t able to watch the linked video, the primary improvements are improved pathing and the ability for NPCs to jump over small gaps. Here’s a screenshot showing how the new PathfindingService maps out the world:

User Story:

As a developer, even with the upcoming PathfindingService improvements, it’s impossible to integrate PathfindingService with my game.

Elaboration:

Let’s imagine that I have a troll that can break down a wall. The troll’s goal is to break into the player’s castle and steal their nexus crystal, but if the castle is fully walled-off and the gates are closed, there’s no way for PathfindingService to find a path to the crystal, despite the troll being able to break down walls. I would either have to program the troll to naively attack random walls, or develop my own pathfinding.

Potential Solutions:

One thing that’d help in general is the ability to specify “portals” to PathfindingService. I’d provide it a start point, an end point, and the time it takes to move between them. I could use this to knit in literal portals with PathfindingService, or in the case of the troll, create a portals with the start/end points being on each wall segment and the “time to move” being the time it took to break through the wall. Once the NPC reached the start point of a portal, I could suspend PathfindingService, the NPC would do what it needed to do (use the literal portal to teleport to another ship, break down the wall, etc) and then resume PathfindingService when I’m done.

Another thing that’d be useful is the ability to weight certain regions with PathfindingService. For instance, once discovered I could mark tripwires as dangerous, or maybe an area a group of enemy soldiers is patrolling, and provide a distance of effect – pathing would try to find a solution around this. I could do the inverse as well, and encourage pathing to go through areas with lots of cover, or healing AoEs.

Use Cases:

“Portals”:

• NPCs can path through destructible objects, taking into account how long it’d take to destroy them
• NPCs can path through literal portals
• NPCs can use elevators, drawbridges, etc in their paths
• Climbable objects e.g. ladders, a rope which isn’t climbable by ROBLOX NPCs, etc
• NPCs can use Donkey Kong -like human-projectile cannons

“Weighting”:

• Encourage NPCs to walk through areas with cover, even if it’s slightly longer than a path with no cover
• Stealth NPCs can avoid patrols
• Soldiers can avoid walking into archer/artillery-covered zones
• Fire Skeletons can avoid snow terrain
• Human NPCs can avoid CrackedLava terrain
• NPCs can avoid traps
• Hostile NPCs can avoid neutral territory/safe zones for players

Further Problems Not Resolved

• Pathing for non-land, but “grounded” units e.g. boats, etc
• Pathing for units that can move on all three axes e.g. planes, spaceships, submarines, swimming NPCs, etc
• Size of NPC taken into account by PathfindingService (e.g. a footsoldier could fit through a human door, but a troll could not)
• Mass of NPC taken into account by PathfindingService when determining jumps (a flea can make huge jumps, but a troll can’t really jump)

[sparker22]

A lot of this seems beyond what pathfinding was even intended for.

Pathing for non-land, but “grounded” units e.g. boats, etc
Pathing for units that can move on all three axes e.g. planes, spaceships, submarines, swimming NPCs, etc
Size of NPC taken into account by PathfindingService (e.g. a footsoldier could fit through a human door, but a troll could not)
Mass of NPC taken into account by PathfindingService when determining jumps (a flea can make huge jumps, but a troll can’t really jump)

These sure.

The rest you should be using PathfindingService in combination with your own code to determine the end point of the Path. (Pathfind to the wall, initiate an anim to break it down, a path is created, pathfind to the crystal) To claim its impossible is 100% false.

[EchoReaper]

Pathfind to the wall

How do I know which wall segment to pathfind to? I’d have to implement my own pathing, which would defeat the purpose of PathfindingService. The problem is that it’s not possible to use PathfindingService in combination with our games’ code without having to render PathfindingService redundant.

[sparker22]

http://wiki.roblox.com/index.php?title=API:Class/Path/CheckOcclusionAsync
By this. You could actually setup a pathfind to the crystal and this will show the wall obstruction in the path.

[EchoReaper]

That gives me a single blocking segment – it doesn’t continue. It would return the wooden fence in front of me despite having 10 layers of stone walls behind it, rather than the slightly more inconvenient-to-access segment which has open space behind it. I thoroughly looked through PathfindingService and brainstormed all possible ways it could be integrated into my games – it does not satisfy any of the use cases mentioned in the OP.

[sparker22]

That gives me a single blocking segment – it doesn’t continue.

Recompute the path and try again until success. ???

[EchoReaper]

Hi Sparker,

There is no way to ignore certain areas/obstructions, so recomputing the path would provide the same result. I encourage you to check out the Pathfinding tutorial on the ROBLOX Wiki to gain a better understanding of how PathfindingService functions, and to review the use cases in the feature request.

Also, please note that ROBLOX is constantly evolving, and its features will grow along with it regardless of their original intentions. Our talented engineers ultimately decide how these features should evolve based on demand from the community – if you are negatively impacted by these changes, please share how they would affect you, but otherwise Feature Requests is for proposing changes, rather than deciding the way they will evolve ourselves.

Thanks,
Echo

[Den_S]

Sort of hoping there will be a way to disable jumping and maybe falling of large ledges completely. No clue how flexible the pathfinding on the generated navmesh is though…

[GooblesTheAlien (Goobles)]

Maybe this idea could be used with the new instance tagging feature, allowing us to mark which objects are “safe” or “dangerous”.

[sparker22]

There is no way to ignore certain areas/obstructions, so recomputing the path would provide the same result. I encourage you to check out the Pathfinding tutorial on the ROBLOX Wiki to gain a better understanding of how PathfindingService functions, and to review the use cases in the feature request.

Invisible parts + collision filters can do this.

Please note that half of your reply was redundant and completely unproductive to the conversation and seems to only exist as a subtle way to take a stab at me. Being subtle does not excuse this and is highly unnecessary.

[Xan_TheDragon (Xan)]

(To sparker) To be honest what you told him was rather vague. You effectively just said “try to pathfind over and over until it suddenly works for no specific reason”. Absolutely no workable solution. Now that you have mentioned “Invisible parts + collision filters can do this.”, that’s a bit more descriptive and makes sense.

@EchoReaper I did have an idea for this, and what you could do is add nodes to an area outside of each wall (so outside of the castle, have a part outside of the breakable sections that’s a certain distance from the wall) and then have the troll pathfind towards that node until they get within some larger distance of it, like 15-20 studs. After they are within that radius from the node, I THINK you can set EmptyCutoff to 1 and pathfind to the crystal, which will cause a path to be made no matter what (Because nothing can be considered a full voxel in the pathfinding grid and is thus ignored as an obstruction).

Try that out and see how it works, I can elaborate further if you want.

[sparker22]

(To sparker) To be honest what you told him was rather vague. You effectively just said “try to pathfind over and over until it suddenly works for no specific reason”. Absolutely no workable solution. Now that you have mentioned “Invisible parts + collision filters can do this.”, that’s a bit more descriptive and makes sense.

You have to take the previous part of the conversation into context. I said to make a pathfind to the wall, tear it down etc and pathfind to the crystal. He said how will be know which wall segment, in that case he can pathfind to the crystal, get the first obstruction to tear it down. He then questioned about the pathfinding continuing. Which you would just recompute the path and keep trying tearing down the walls until success. I figured when I said recompute and pathfind until success also implied the tear down wall part, maybe that wasn’t clear enough.

Invisible parts + collision filters is for the weighting issue.

[1waffle1 (Waffle)]

The fact that a solution exists does not mean it is a good solution. That would be slower than just writing your own pathfinding system in Lua, which ignores the point of putting the load on C-sided APIs. The worst case for the pathfinding API is when no path exists.

[EchoReaper]

Hi Sparker,

A number of features can be accomplished by hacking around existing limitations (AnchorPoint, Instance Tagging, Region/Ray whitelists/blacklists, etc) – including pathfinding. The original features these branched off of were designed to be suit users’ needs, feedback showed they never or no longer did, and they were improved. Needing to hack around existing limitations of a feature demonstrates a flaw in that feature fulfilling users’ needs.

As waffle mentioned as well, there are other implications such as performance concerning current workarounds. The following is taken from the context of ROBLOX animations, but it applies to pathfinding as well:

Allow animation instances to be played -- not just by ID

I’ve said it before and I’ll say it again - custom animation systems are bad. The amount of overhead in Lua compared to C++ is insane. We’re planning to work on this next year, but it will never be good - Lua just sucks from a performance standpoint, frankly - it will just be less bad.

Thanks,
Echo

[sparker22]

1. Do you have any backing to those claims
2. First performance has to be an issue.

[portenio]

Weighting is something we will most likely add to NavigationService in the near future.
Also parameter sets, to allow for custom agent sizes and capabilities (i.e. agent width, height, jump distance, max fall).

Portals are an interesting idea and we will consider it.
Although for your castle use case, setting a high weight to the walls could do the trick and even be easier to set up.

The new service should gracefully handle “grounded” objects.

Adding support for CollectionService and CollisionGroups is also something we are looking into.

[Locard]

Sorry for the bump, but this is very important / relevant to my current projects.

I have to reprogram my AI for a third time to somehow get by the current limitations of the service. Aside from the lack of functionality when you get NoPath, I can’t add an ignorelist when checking for occupancy. Because of this, I have to calculate paths around the outer edges of whatever model or part I do. This can be done with a ray or some Vector3 math, but I shouldn’t have to be doing that by now (4 months after the release of the upgraded service).

Edit: 4 months not 6 months.

[bigcrazycarboy]

I’d really love to see something be done to accommodate vehicles. Perhaps the PathfindingService could include an ignore list and an include list? This way we can make vehicles follow roads the way they always should have

[filiptibell]

@portenio

Adding support for CollectionService and CollisionGroups is also something we are looking into.

Hi,

It’s been quite some time, is this something Roblox is still looking into?

[Judgy_Oreo (phoenixwhitefire2000)]

PathfindingModifiers can be used to allow agents to ignore certain obstacles like doors, and PathfindingLinks can be used to specify a “link” between two areas with custom functionality, which facilitates the “portals” feature request.