Custom Pathfinding System

Help and Feedback Scripting Support
#21

You need to find the closest node to the player right?

Set up a region3 of 10,10,10 (for example) and the position it on the player, that should find the nearest nodes, then just sort the list by nodeposition-playerposition, take the first one, and you have the closest node.

1 Like
#22

I already have a system for this. Before it was taking 25% to find the closest node. And that utterly crapped on the server performance every time it cycles.

I spitted the nodes into chunks and only search in the closet chunk.

#23

Returning to the main question,
The images show that there are only paths to the nearest nodes. What if you changed it so it also finds the furtest nodes and create a path to that, then the algorithm can use that path instaid of a thousand smaller paths.

#24

Actually, A* is usually faster than Djikstra’s, since it relies on a heuristic. Both of them are Graph searches, which means that they only operate on a graph (ie given nodes and edges)

2 Likes
#25

How did you generate this grid?

Also, generally, it is beneficial to store nearby nodes as a linked list, so it takes atmost 8 comparisons to find the next node to expand to. This seems like an issue with the datastructures you are using, rather than the algorithm.

1 Like
#26

I am using a linked list.

I’m generate these nodes using raycast.

1 Like
#27

Perhaps a solution would be to use a raycast to detect if the player is unobstructed and then switch to MoveTo? It would mitigate the jitter and as soon as the player is re-obstructed the AI could switch pack to pathfinding. Not sure how efficient this is

#28

It isn’t practical. What happens if the player can be seen but there’s a drop in between?

1 Like
#29

Good catch. You could possibly raycast along the initial ray to detect drops, but at that point it’d be way too inefficient. I’m not very experienced with custom pathfinding sadly

#30

That is the solution that I tried, however the npc would often get stuck in a strange jittery panic where it would switch from pathfinding to moving straight to the target, making the npc even slower and less effective. I tried workarounds but there wasn’t much else I could come up with apart from just making the npc lunge clumsily in the direction of the player when it was close enough, but it just looked stupid and was more often than not inacurate.

1 Like
#31

For drops you can just check if the player’s position is higher than your position, and then jump until you reach their elevation.

1 Like
#32

How do you think a custom pathfinding system would do compared to Roblox’s current one?

1 Like
#33

Honestly, I think it all depends on how well you make the system. I think its totally possible to make a custom path-finding system that works better than Roblox’s right now, but that all depends on how skilled you are at making it.

That being said, there might be some simple workarounds that we are just not seeing to common pathfinding issues that require no change of the system on Roblox’s part.

#34

The biggest issue is the nav mesh isn’t accurate.

The nav mesh says it can get over a certain object, but in reality it cannot.

1 Like
#35

Maybe it’s something I’m doing when computing the path? Maybe I need to set an agent size?

#36

What is A*?

#37

Well it more than possible that the pathfindingService isnt accounting for the size of the character and how its head/legs/torso could collide with things.

#38

image
image1063×824 536 KB

image
image1067×650 448 KB

Roblox’s pathfinding is not good, it doesn’t do its job.

#39

Here’s another pic.

image
image1049×820 565 KB

#40

Did someone mention pathfinding?!? I love pathfinding, go to my profile and search “pathfinding” for all sorts of interesting comments about it.

As you’ve found out, quite practical. Making a pathfinder is not at all difficult. It does take some debugging knowledge, research, and the ability to implement a well documented algorithm.

Theoretically, yes. The reason is that Roblox’s pathfinder is meant to work on every game. You, however, are developing a pathfinder for your own game and can make many assumptions where Roblox had to be more general. In addition, Roblox internally uses the open source Recast and Detour pathfinding libraries, but has only tacked on very abtract support for them and doesn’t near the level of detail and sophistication to make use of such a powerful library. Roblox does have the advantage though that their pathfinder is compiled in C and C++, making it much, much quicker out of the box than one implemented in Lua.

We’ll see if Roblox actually puts effort into a better pathfinding API in the future. In the mean time, here are some thing you can do to make your pathfinder more efficient than the Roblox one.

  1. Implement hierarchical pathfinding. At its basic level, this means divide your node graph into regions. One region could be a room or a whole building. Searching a region is much quicker than searching the entire map. Making a new graph where each node is a region of the previous, you can make higher level decisions than “does this node lower my heuristic” and more like “do I have to walk through this room to get to this one?” As humans, we naturally think like this. When planning a cross country road trip, we know what state we need to get to. We decide on a highway to get us there. Next, look at the city we need to get to and find the nearest exit. Finally, we look at the address and decide what streets to take. We definitely don’t pull out a map a start asking “if I take a left here, does that get my closer to my goal?” That would take FOREVER! The more levels of abstraction, the better.
  2. Implement deferred pathfinding. Often times in a dynamic map, your target moves before you reach it, or the path becomes blocked! Finding a complete path hundreds of times a minute to achieve realistic results can be expensive. Using hierarchical pathfinding allows us decide what highway we need to get on to reach the destination, and think about the exit we’ll need to take once we get a bit closer. As long as the target stays in the same state (in the same building, room) then we know we are heading in the right direction.
  3. While the two above are relatively easy to implement, this one is a bit more difficult. Instead of using a graph of nodes, use at the base level a navigation mesh. Each convex polygon in your navigation mesh could be a node in your classic A* pathfinder, but when actually walking from one node to another, the agent can stay anywhere inside the polygon it is coming from and going to. This allows for much better low level path replanning if a part falls in the way of the agent but doesn’t block the whole path from one polygon to another. In essence, a polygon contains much more information about where is walkable than a point. Infinitely more in two dimensions! It also allows for each flock and group pathfinding because each can walk the same path and just adjust their positions inside the polygon.

Hopefully that helps! Pathfinding is fun :slight_smile:

48 Likes