Pathfinding Help Needed (NPCs getting Stuck)

Hi everyone,

I come to the DevForum with a cry for help. (I hardly create topics like this, so you know it’s serious)

In my game, the player has a house template. They can add furniture, and walls to create seperate rooms in the house.

The player (landlord) can then rent the house out to tenants. The tenants are NPCs and currently I use Pathfinding to move them from the entrance of the house into the different areas of the house.

Unfortunately though, the Pathfinding Service is truly terrible. Players are getting stuck at the most random areas in my game.

You can see here that the NPC is stuck facing the wall, where all they had to do was walk out of the grey door behind my character:

Not only that, but when you introduce other things such as objects which the player can collide with, there is further chance of them getting stuck. I have had to make all objects uncollidable, at the expense of taking away from the realism of the game (e.g NPC walks into a shower through it’s back wall)

However, I can’t just make the walls uncollidable. That’d look so bad. I just have no idea what to do now. The problem is that because the user adds their own walls and objects, there’s always a complete different path that the NPC will need to take - and I simply cannot trust the PathfindingService to compute competently.

Example life of an NPC:
Spawn outside > Walk in to designated room of apartment/flat > Walk to shower inside room > Walk to couch > Walk out of the building > Destroy NPC

I have seen from other posts people recommending custom pathfinding solutions - however, I really don’t know where to start with a system like this nor know whether it will work, especially with user-generated furniture and walls, where each house / map is different. The NPC aspect is crucial to my game alongside the “freedom to build” ability to place walls or objects anywhere.

Any help appreciated.

Cheers,
AlvinBlox

30 Likes

Can you make a visualizer? Place red parts at the waypoints. That’ll help you determine whether the pathfinding is broken, or your code to navigate them is broken.

Without that info, all I can do is guess. Here are my guesses:

If its the pathfinding, the walls might be too thin for the voxel to count as blocked
If it’s your code, you might be trying to move to the next waypoint before the previous is complete, leading to attempts at “cutting corners” that can be blocked.

Hope this helps!

10 Likes

Have heard the thing about the walls from a few people now. I’ll do a bit of investigating. I’d say most of the time if your house interior structure isn’t complex or crowded, it would work quite well, but again as it’s user generated you want it to be quite accurate so you don’t have bugs like this.

I will update thread with outcomes. Any other help still appreciated!

Thanks boatbomber.

4 Likes

I think I have an idea. I read this post a while ago and while it is not really targeted to pathfinding, it could be applied in that way.

The idea is that if you have some floor that is tiled, meaning you can only place furniture on a finite number of tiles, then you can calculate a path using an algorithm similar to a flood fill. Taking the NPC’s current location, and only being able to walk across tiles that aren’t occupied, you can find a path that goes from A to B (assuming the player didn’t block every single possible route). To calculate the shortest route you can find a direction vector pointing to the destination and choose the empty tile that is most in line with that vector. The key is that you can define which tiles are available to walk across. This will also avoid running into walls and it might even add an element where the player shouldn’t be obstructing doorways or important throughways.

Just to clarify, I have not implemented this before. Let me know if it makes any sense, hopefully it is of some use :slight_smile:

2 Likes

Quick thing of code;

local Visuals = {}
    function Agent:ViewWayPoints(WP) -- pass the waypoints
    	for n, x in pairs(Visuals) do
    		x:Destroy()
    	end
    		local Att = Instance.new("Attachment")
    		local Bem = Instance.new("Beam")
    		Bem.FaceCamera = true
    		Att.Visible = true
    		for n, x in pairs(WP) do
    			local Point = Att:Clone()
    			Point.Parent = workspace.Terrain
    			Point.Position = x.Position
    			if n ~= 1 then
    				local Con = Bem:Clone()
    				Con.Attachment1 = Point
    				Con.Attachment0 = Visuals[n-1]
    				Con.Parent = Point
    			end
    			Visuals[n] = Point
    		end
    end

how thick are the walls? As good as the new pathfinding system is, I’ve still found a few cases where it’ll path through thin obstacles.

5 Likes

Thank you :100: :smiley:
They are 0.5 studs thick. (or thin should I say haha)

3 Likes

With the code I’ve added there, just use one NPC and see if its creating a path through the wall.
I’ve found problems with parts smaller than 1.5 being clipped through.

It may also be worth asking, what are you calling to generate the path?
There is the Path:ComputeAsync() which is the newer version;
Then theres the older version, which I can no longer find documentation for! It uses a 4x4x4 voxel system, and is more prone to problems with parts not correctly aligned to that grid.

ComputeAsync indeed. Just trying your code out now, I am going to have to dig into a player’s save slot to find a case where the NPC does get stuck

1 Like

Interesting development!

It seems that increasing the size of the walls to 2 studs instead of 0.5 considerably increases the accuracy of the pathfinding. I would send a GIF comparison, but it is taking so long to upload over the Internet that I aborted.

Of course, I can’t yet tell whether this will make PathfindingService sustainable, as I’ve only tested it in 1 player’s save. But it’s still not ideal for some things, such as objects having to now be un-collidable.

Will update tomorrow after more testing. Thanks everybody!

PS: @edenojack that waypoint visualiser is awesome

5 Likes

I thought I would just add in a small tip about network ownership because many people who had asked me about failing npc usually ended up fixing by assigning it for appropriate owner(e.g. most npc’s network owner is server because client does not need control over it )

I had a play about with pathfinding a while back while working on an RPG game. We had some really nice houses but we had to add invisible walls that were several studs thick around the house to make sure it recognised the doors.

Make sure all of your doors and openings are plenty wide enough too. As long as both arms and the torso comfortably fit through it should be okay.

If you want your walls to stay 0.5 for aesthetic reasons, add invisible 2 stud thick walls so they extend 0.75 studs beyond each surface. Most people won’t notice.

2 Likes

Ok, i not am sure if this really can help you, but long time ago i read a topic and the solution was to add Raycasting: For example, if you make a zombie game, i know games in them the zombie stuck in the wall. Now, you can raycast to see if it was a wall before your NPC, and if it was so, then you can recompute thr Path. Else you can yeld a bit, then create the path. Or you can use A* Pathfinding system, hope it helped you. Last chance: Terrain Path With A* Pathfinding - #3 by Jaycbee05, else really can‘t more help.

Solution idea for your collision issue, why don’t you create a collision group for the NPCs and furniture? It’ll be easier to move them around and players can still interact with the furniture. Or is this not ideal ?

3 Likes

A NPC that go through a wall, else this was a ghost :roll_eyes:, not think this was a good idea, but if this can help then why not try.

Pathfinding Service can automatically generate a path around obstacles, but if a NEW obstacle is presented in front of the NPC after the path was already created then it will get stuck.

(you need to update the path AS the NPC is moving or you can update the path when he touches certain objects)
1 Like

Good idea! Why not add Raycasting to this instead using a touched event.

raycasting would be more efficient IMO, i would definitely recommend it, just depends on the design/developer i suppose.

Hey everyone, thought I’d reply and give you an update.

So this is my main struggle right now with the pathfinding. As you can see in the attached image, there are three desks which all have been set to collidable (CanCollide = True). However, you can see that instead of just simply walking around the reception desk, it gets stuck. You can also see the visualised path trying to direct the NPC through the desk.

I’m really confused as to why the NPCs are not walking around the obstacle here. It will re-compute the path if it gets blocked up to a maximum of three times, but even still, it’s still computing the same path each time?!

Thanks for the help so far, much appreciated.

4 Likes

When you create the tween, there is an agent-radius property. Maybe if you decreased that and agent-height, It would work better.

1 Like

Hey, @Alvin_Blox, can you make a place with only your issue as model (scripts included). I not really undderstand why it don‘t work, you can only send us the important objects, we don‘t need the rest. But your choice. Then, have you tried to change the Hipheight of your NPC‘s?

1 Like