Creating Splines From Navigation Paths

RainbowFlashbang · January 1, 2020, 3:52pm

Hey, everyone.

I’ve been trying to create a method to draw/render a Navigation Path using Splines for… Let’s say “a while” and leave it at that.
On a flat surface, this is actually really easy—just set the Spline points to be the same as the Navigation Path points and you’re all set. The problem I’ve been struggling with only really applies to uneven terrain (slopes/ramps/landscapes); when a path runs straight up or down a slope, the Navigation System places no points on that slope.
This is fine for keeping paths simple, sure, but it means that a spline constructed from those points clips through the terrain:
[SPOILER]

[/SPOILER]
This is making things kinda… Tricky, because I’m using the generated Spline to display the limited distance the player character can move, so naturally it needs to accurately show the distance covered *on the ground. *
The (hopefully temporary) solution I’ve come up with is to flatten the Spline to the player’s Z position, and crawl along it at 5UU intervals, running vertical Line Traces to check for changes in slope and elevation underneath it and update the Spline with new points as it goes. Essentially brute-forcing it.
The result is a line that looks like this:
[SPOILER]
[/SPOILER]
…Which… *Technically *works. It freaks out a bit on lumpier terrain such as Landscapes, and of course running so many Line Traces *every single frame *the Spline is displayed isn’t exactly fantastic, especially as it gets longer.

So is there a better way to do this, short of overhauling the NavMesh pathfinding for a grid? I’ve been hoping to adapt it (Eventually) into a gridless turn-based movement system, but this has seriously been slowing me down.

Thanks in advance!

Fieol · January 3, 2020, 6:10am

Can you share how the navigation path data sends you information and how you are using it with splines ?

RainbowFlashbang · January 4, 2020, 8:07am

Sure! I’ve actually overhauled this since my post, but I’ll try to break down what I’ve got working now. It’ll be a bit long!
Essentially, my player character actor contains a spline component (Not a spline mesh component). When I want to update the spine with a path to a new location, I call a function:

This first part sets the spline’s points to be the same as the path, and adds those points and the distances along the spline to those points to a couple of arrays for later.
It also remembers the Z position of the player character, so it has something to compare the later points to. I made it straighten out the spline every time its points are updated to make sure it gets the correct locations when I use GetWorldLocationAtDistanceAlongSpline.

This is the section I’ve overhauled. Essentially, it does 4 checks between each of the spline’s points. If the next point is higher or lower than the current one, it does much smaller steps and more along that section.
Each check projects the point to navigation, then sees if that position is higher or lower than the last one it checked. If it is, it adds that point to an array of new points. Otherwise, it ignores it.
Once it finishes the span between two path points, it adds the next point to the array of new points. This is to make sure the spline still works on *flat *ground as well.

This is way better than what I was doing before, because it reduces the number of points on the Spline whenever it isn’t running over slopes or ramps.

This last little bit just makes sure the spline is straight after setting it to use the new points, and double-checks that the end of the spline isn’t too far away.
It also draws the spline using Niagara, sets the end position (Which is sent to a MoveToLocation to actually move the character), and returns the length of that generated spline.
So now, moving up and down a slope, my spline looks like this:

…Which is much, much better. It also runs much smoother than it did before—I can increase the maximum length of the spline 10 times over and run it through complicated terrain without noticeable performance loss.

The last thing I need to work out is how exactly to draw those orange DebugPoints during actual gameplay. I have the locations, but I haven’t figured out whether I should try to get Niagara to place particles there (Somehow) or just use Sprites.
Anyway, I hope I covered enough of the code for you! Hopefully this’ll help someone trying to do something similar in their own project.

Fieol · January 6, 2020, 4:58am

@RainbowFlashbang beautiful description!

I got the idea that you are creating the spline on run-time for uneven surfaces in a way that it gives you optimum spline points to move to a certain position in 3D space.

How does it work on curved roads or if you have a turn or something like that in the terrain? just wondering, may be that’s not your use case.

You have to pick out the spline points on every new position player set for the character, this can also be done in


Runnable Threads

which UE4 provides if you fear that your calculation can get stuck in main thread.

Here is the link and one more on how to make a thread in UE4, may be that helps to optimize it performance critical scenarios.

Keep me posted with your updates, great work !

RainbowFlashbang · January 7, 2020, 6:30pm

The function keeps the original path points generated when I call FindPathToLocationSynchronously on the Navigation System. The final spline points are a mix of the updated ones which conform the path between those points to the terrain, and those points themselves.
This means that a spline the function generates still follows the path generated on the Navigation System, but it now accounts for the extra distance the player would have to move up/down slopes. It’s actually really important that is does this, since I’m expecting most of the levels to be mainly flat regions separated by slopes or stairs.
Here’s an example of the spline moving up a slope *and *around a few corners:

Of course this means it works fine on totally flat terrain with corners as well, since the original path points still exist. Because it only keeps important changes in height while it crawls along the spline, the path it makes on flat ground is identical to the original Navigation Path:

…And finally, I worked out a kind-of edge case where the destination of the path is at the same elevation as the starting point, but there’s a change in terrain between them.
This was admittedly harder than I expected it would be to wrap my head around, but the gist is that it now checks one step ahead of itself when looking for sloped terrain as it crawls along the spline, in addition to comparing the current point to the last one. I also increased the fine step distance since 25UU was a bit too small, and clamped the minimum distance it will step along the spline. The clamp is to make sure that paths with more than 10 meters between each point don’t lose any more precision (even though it’s unlikely spaces in the path will be much longer than that).
The updated crawl function looks a little like this:

And it does its job pretty well, I think!

I also did a bit of tweaking to the code I was using to find the actual endpoint, so that it defers to either the mouse position or the last Navigation Path point (whichever is closest to the maximum distance along the spline), and then moves that point to where it should be.
Here’s it in action moving to points at the same height as the starting position, with changes in height between them:

Oh, I’ll have to look into these links! It usually runs fine for the cases I’m expecting, but it can get a bit heavy since I expanded the function to check for dips/rises—especially when the spline gets longer—but generally only when it’s trying to get the spline over convoluted Landscape terrain.

It’s nice to know someone’s interested in this, at least!
I think the function is almost done, the way it is. I’ll probably come back to see about working multi-threading into it at some point to try speeding it up, though!

Fieol · January 10, 2020, 6:51am

What you have created is a dynamic point gathering system which can get each of them where the player should walk on, irrespective of different terrains or heights. That’s mind blowing man ! Good work !

chaosgaming · October 6, 2023, 4:32pm

Nice work, I’m nicking that to help we with some dynamic roads