"Bézier" pathfinding

I find Roblox In-Built pathfinding algorithm to be very problematic when dealing with realism. I think everyone that has tried or successfully made a realistic movement system with pathfinding can agree to that one way or another. The thing I want to eliminate is sudden changes in direction, this is mostly common when the Roblox In-Built pathfinding algorithm has deal to deal with the most important and basic aspect of a realistic pathfinding algorithm: Obstacles.

Of course Roblox In-Built pathfinding does its job of finding the shortest path between two points, but maybe that’s not what the desired output we want is, yes we can edit some values like:

AgentRadius = 2,
AgentHeight = 5,
AgentCanJump = false,
AgentMaxSlope = 45,

But there will still be strange sudden turns, If only there would have been a SmoothnessFactor

So with a little bit of sanity and a solid minute to brainstorm any solution, I came up with an idea of using Bézier curves! But I am not the first to think of this, In another post someone references that GTA is a game that utilises Bézier curves for pathfinding.

Where I’ve gotten stuck is converting an array of x size (the point that a dummy has to walk in order to arrive at the destination according to Roblox In-Built pathfinding) into one Bézier curve.

For now I’ll hack in a crude method of just ignoring the issue and trying to cope with making the characters movements look more smooth rather than the path it will take, but if anyone has any ideas please let me know! I would gladly like to discuss them

3 Likes

What if when the waypoints get generated, you then generate new points between those points which are bezier curves?

1 Like

Ah, Of course! Amazing idea! I’ll later try coding it to see if this would be the correct intuition to implement! But before I do something I usually try to think of if anything might go wrong in some systems, just so I am sure that a any Idea will always work

  1. if we image a simple case of a box, two points and a line representing the shortest path between these two points without intersection of the cube it would look something like this:

  2. These lines can be divided into the array of waypoints the pathfinding algorithm makes

  3. Then after using your idea we can make a smoother turn!

Hm, there’s an intersection. But that’s a simple fix! If I increase AgentRadius I can have more room for larger Bézier curves in turn giving me just what I want!

This is just what I need! Thanks @NotSpideeyDev for the idea :wink: If the system works nicely when I’ve coded it I’ll happily mark your idea as the solution!

3 Likes

What I’m about to say can be either a good or a bad idea depending on how good I understood what you want.

NotSpideeyDev 's idea is very good. However, a potential problem is that the generated curve may overlap with corners, such as in that image you have posted.

Why not adding a pre-step to smoothing the waypoints out with Bézier, that, wherever a waypoint causes a change in direction (or forms a non-180° angle), adds a little extrapolated ‘bump’ (or ‘smoothing tolerance’) in the coplanar direction where the angle that’s formed is pointing to? Just so the curve generated doesn’t overlap with the point that’s causing the angle in the waypoint, such as in the image I quoted above…

1 Like

I know that overlapping curves may happen but I don’t think that it will be a massive issue considering when you increase the AgentRadius the path will be further and further from the walls meaning that the Bézier curves will have less and less of a chance of clipping. In my drawing I deliberately made it so that the AgentRadius was 0 to address the issue to just reflect on the fix. I’m not sure if I’m wrong or not on that idea so if you know otherwise I’d like to hear.

This drawing shows the waypoints this time distanced by some radius R to see if the Idea still works.

Also I beg you pardon but when you mean “smoothing the waypoints out with Bézier” what are you implying?

1 Like

Does your map contain narrow spaces? If that’s the case you should maybe first check if a point has found an obstacle within a distance of the agentradius to be sure it won’t hit an object because of your curve. Btw, your sketches are quite soothing to the human eye.

1 Like

Why thank you :joy: ! Your idea is plausible and won’t require many expensive calculations, only using GetTouchingParts() once by only testing it at t=.5 in the Bézier curve! For now my map doesn’t contain narrow spaces but this could be an important thing to take note of when I work on making narrow corridors, thanks!

1 Like

Yeah, exactly, that looks way better!

Ah, nothing, just applying your Bézier algorithm, haha.

2 Likes

How is the system going so far?

1 Like

So far I’ve made a script that just contains the normal pathfinding system, although I hope today I can get to implement the bezier idea without bugs!

So far the idea is looking very promising! For once I can see the end of the tunnel!

Screenshot 2025-01-03 at 07.55.50

However, there’s a challenging bug that I’ve been grappling with: determining the precise moment to apply the Bezier curves. The image below demonstrates what happens when the dummy is positioned just in the right place to cause the Beziers to fail.

Tackling the Challenge

To address this, I drew inspiration from a previous project where I worked on viewport frame shadows. The key insight from that experience? Detecting corners.

The Shadows Analogy

Imagine projecting the corners of a box onto an infinitely large, flat surface (a quad). This is straightforward: cast rays from the box’s corners, find their intersection points on the quad, and connect them to outline the projection.

Now, consider adding a second box twice as large as the shadow caster. Suddenly, the complexity increases: each vertex of the original box can result in two possible projections, creating up to 16 cases.

At this point, I asked myself: how can I accurately calculate the projected box with both corners and edges now fighting against the idea of projecting shapes onto surfaces on Roblox? The short answer is you can’t, not without expensive computations. But I became determined to find a more efficient approach.

Using Raycasts to Detect Corners

Raycasting in Roblox returns three critical values:

  • Instance
  • Position
  • Normal

Before I say the solution, I’d like for you to ponder of what happens to these values as the ray transitions from hitting one surface (e.g., a floor) to another (e.g., a wall),

Here’s the key observation: as a ray transitions from hitting one surface to another, the Normalvector changes as soon as it hits the next surface. This shift is consistent and reliable, no matter the corner.

Applying This Insight

The central question here is: how do we detect a change in direction?

The solution lies in:

  1. Calculating the unit direction vector from the current point to the next.
  2. Tracking these direction vectors.
  3. Identifying changes in direction (maybe only in the y axis): when a shift occurs, it signals where to apply a Bezier curve. If there’s no change, the path can remain a straight line.

Final Thoughts

While this is a detailed explanation, I believe it’s a great way to outline my thoughts behind the approach. If you have any worries about the approach I’d love to hear on how to refine this idea further.

1 Like

but wait, why don’t you just go through every waypoint, get the prev, next and current waypoint position. Then check the angle (if it’s a pyramide or straight line or square or whatever) and then if it’s more of a pyramid you make a bézier curve out of it? In this case you don’t have to rely on objects and you can just handle it with what you have. If you want I can explain it in more depth if you’re not sure what I mean.

Also, could I perhaps get your Discord?

1 Like

Ah, the images that showcases the path the dummy takes as dots is just a visualisation. Nothing is inserted as a necessary part of calculating the path of which the dummy takes!

I see what you mean, basically getting the angle from the center point relative to both the top and bottom. But this requires a bit more math, and for simplicity’s sake by keeping track of the current angle (in units) and calculating the next angle we can deduce if the path is not straight in a much more cost effective way : )

I hope I understood correctly!

Maybe, for what reason may I ask?

1 Like

Screenshot 2025-01-03 at 14.16.48
And wow! That is never something I would expect to see!

I’ll start to move the dummy along the path but this is actually way better than I was expecting!

Thanks a lot for the amazing idea @NotSpideeyDev

2 Likes

It just felt like a hassle to message via posts everytime and that it’d be easier to just DM you. I also think that you’re quite an interesting scripter that I’d love to be able to DM sometime for for instance scripting jobs.

Oh damn, it actually starts to look quite good. Hopefully the NPC won’t stutter because of the big amount of waypoints.

This is definitely how I would have solved it, great progress. It would be interesting to see an implementation where you don’t need to worry about agent radius, but instead develop a system to go by each waypoint and generate a bezier curve to the next so that each point wouldn’t intersect. I imagine it a bit like inverse kinematics where each part of the curve is generated until it no longer collides (and the collision box would be at each point with customizable width/etc).

The only reason I bring it up is that the agent radius sometimes causes general pathfinding failures because something is just a micro-stud off or too small when the rig can fit through it. But anyway, no pressure to implement anything of that complexity. I’ll check back soon and see what you can cook up.

1 Like

I did actually notice that the dummy would do that, a lot! I fixed it by simple decreasing the detail of the bezier curves whilst setting the network owner of that dummy to nil!

Thank you so much for your kind words, it means a lot that you find my scripting work interesting! I totally get how DMs might feel more convenient sometimes, but I’ve found that sticking to posts works best for me. I hope you can understand.

Again, massive thanks for the help! I really appreciate it

1 Like

It’s an interesting idea you’ve got, and I’m tempted to try doing it. But I do wonder if the computational power would outweigh the benefits.

Adding a distance to the wall is almost crucial for generating the realistic movement I was thinking of, although as you outlined if the agent radius variable can cause pathfinding failures.

Lets think for a second, Instead of using Inverse kinematics which would be expensive to run for +20 points maybe we can draw inspiration from particle based fluid simulations (sounds random I know but let me explain).

Each particle in a fluid wants to be at a region there they meet the target-density but to do that they have to move according to the derivative or slope of the density map, Sebastian league covers the creation of a fluid simulation very well and I would recommend you go watch him. And to convert this idea to what you recommended we can sample the surroundings of the points and calculate the slope of where the little space is most dissipating and move it a slight step towards that direction.

To also make sure no point goes to far from one another we can imagine springs between all points that make sure that the distance is no more than some value

Using this idea we would be able to decrease agent radius and instead increase the custom made “agent radius” around those points to compensate for the close corners the dummy takes

I might not do this since I have got to start working on the other problems I’m currently facing in the game I’m working on, well see : )

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.