Custom Pathfinding System

So I’m in progress of making my own custom pathfinding system, using A*. I already have custom nodes for each map.

How practical is it to make your own custom pathfinding system? We all know Roblox’s current one is trash.

Can it turn out more optimized than Roblox’s current one?

12 Likes

@ScriptOn did this for multiple games in the past. If i’ve learned anything from him, its to create your own custom pathfinding.

It should work pretty smoothly, and if ScriptOn sees this post maybe he could give some more insight.

5 Likes

Nah I saw it

It cant even go up stairs.

He uses it for a car game on a map. That’s probably one of his better works

I see. I’m working with tight spaces though. That might affect something.

1 Like

The Roblox pathfinding system is good for reaching static targets, but it is hard to use when following dynamically moving targets.

One of the issues that I had is that if you want an npc to follow a moving target, it can never truly outrun or reach the target, since the space between the path waypoints is relative to the target’s speed if you are constantly redrawing the path. So if you have a monster that is walking at 30 SPS and a human that is walking 16 SPS the monster wont be able to outrun him since he will just have to stop once he gets close to the human and wait for the next waypoint. This frustrated me so much and I could not find a legitimate workaround without sacrificing the obstacle avoidance property of the pathfinding (which is kinda the whole point).

But on the other hand making a pathfinding system requires a lot of math knowledge (which I do not have) , so I was never able to fully make a pathfinder as I wanted to.

Depends on how much better you are than the Roblox engineers :man_shrugging:

7 Likes

It probably depends on the type of game, but I’m using A* for a tile-based game I’m working on and it’s going much smoother than when I’ve used Roblox pathfinding for similar things in the past. You can explicitly say which areas are pathable and what isn’t more easily which can be very helpful. I don’t have any numbers to compare but it seems to be similar if not less cpu-intensive.

2 Likes

Not necessarily, roblox services I’d imagine will be much faster than what you can do yourself in lua

1 Like

Thats kinda useless when it’s already bad

I don’t agree with this, for a fast dynamic nav mesh based pathfinder I find it does a pretty amazing job. If your map doesnt change at all and you don’t mind sacrificing some more realistic routes you can get away with doing a simple node based system .

Biggest downside I see to the pathfinding service is you can’t give paths a whitelist or ignore list

7 Likes

“Trash” is a very rough description.

The Roblox path finding system is very good at what it was designed to do. The problem a lot of developers run into is that it is not very customizable.

6 Likes

I can. I have my own node generation system and I can fine tune it.

The problem that a lot of developers run into is that is not very customization PLUS it can’t find simple routes sometimes.

EDIT: A lot of times, my bad.

I wrote my own awhile back
https://twitter.com/Roblox_Vineyard/status/1066470482529185792

To answer your original question. It is very practical. That 100x100 node array took like .03 seconds to find the path and I did another with 500x500 that was .12 seconds to solve. And there were still plently of optimization techniques I did not implement.

1 Like

Yeah it’s a different story when your map isn’t a 2d flat grid.

By the way for all of you who don’t know, you CAN now specify the agent height and radius with pathfinding service now. It was the only reason I couldn’t use it before

2 Likes

I’ve created my own A* pathfinding system, I’ve recorded it on youtube as a serie, sadly I stopped working on it and worked on other things.
Now my A* was suprisingly fast actually, but it used actual parts and the code was kinda messy. If I had optimized it and didn’t use bricks, it could end up being even faster.

I believe, if you do it correctly you can come up with a really fast pathfinding algorithm.

This is my custom pathfinding system so far. This is just a visual. I have all the points/web information in module scripts already.

Finding the closet node to a player once already puts the script activity to 5%. That’s without algorithm implementation. I’m planning to use A*.

I’m starting to doubt it will work well. It will probably we very very performance intensive when it’s all done.

What do you guys think?

16 Likes

I see you already have nodes everywhere, I believe there are better methods for pathfinding than A* when you already have nodes.

Dijkstra’s algorithm, read about it here:
https://en.wikipedia.org/wiki/Pathfinding#Dijkstra’s_algorithm

Let me find some real quick, I’ll edit the post once I found it.
(Short question, why not use Region3 to detect a dot near the player? That shouldn’t take up 5%)

2 Likes

You mean find parts in region 3?